BIND 10 jreed-doxygen, updated. 66174ced68123b63ec6d23a5f4ecd17302fd2e8b [jreed-doxygen] remove wrong documentation
BIND 10 source code commits
bind10-changes at lists.isc.org
Wed Feb 9 13:23:35 UTC 2011
The branch, jreed-doxygen has been updated
via 66174ced68123b63ec6d23a5f4ecd17302fd2e8b (commit)
via ef6da9e4e8d00024a6c7565eecc6216331ddfee1 (commit)
via 57fdfeac98e3519e64105849495c1557388bc402 (commit)
via c9f6acc81e24c4b8f0eb351123dc7b43f64e0914 (commit)
via 29c6946c6a6a13a833b6037057debfa82ee19c22 (commit)
via 6e31e88f3be72f3e774892b46e58dc00da565dac (commit)
via d2cb311448c6f9010ff2f614ca6ffbc0c0d668a8 (commit)
via 24bb934f0ad2732c50730187376d96ddadefecbc (commit)
via f0b6f321beecb5145776a730461b61426a52a4f1 (commit)
via c73a307cb41eb3e8bb6681dd963f6953973330ca (commit)
via 3048f118d4b4c9995d7ee258c9405f9d7abbc576 (commit)
via 2931606d7c3d6709284788890b016ff434d0f5e2 (commit)
via 1a52db4373a1c4169b0bbd9bc6a550e5a3e68b39 (commit)
via bbd103fff6a6a6e775a075c5132bc1cdd38a5acf (commit)
via ad83fe6b6c31a54e39116f12eb5c70d9fce8d9ea (commit)
via 12aa5f7fd9f8ce0aa10b66cbd3608c363eb3390f (commit)
via 873ab3f9db15055ec293533202bc73d908ab73c1 (commit)
via a929e898df74d43fc590e8df793edeb5f355e29d (commit)
via c11ea16f0ce2d7eac933dfc9e7b57e0e82972205 (commit)
via 2565b9fe9daf6ba63234b06b9f0eb5b8168257b4 (commit)
via c2b374e5e2d608ce0236b7f49b63bf70b57c761f (commit)
via 2e93f9a6c23985a4e9968c13c3068c61f202ca4f (commit)
via 6031b9096d5a9c73468afa386a3e311984125522 (commit)
via ed3436f599952a3e070dbf19668e5bcb2e9dacac (commit)
via dd2f336165e9f974aaed88569b5e718493cd5757 (commit)
via 324b135b99582c63aa49f50d8c80e00d6e43e2f9 (commit)
via 6fb3a7ca7f9f1b7018493a263b3063b0b0962b5e (commit)
via b211d93037f31731426dbf073098ebfa8ae16bc4 (commit)
via 89cbb6aafeaf5cbc51b50a0caa4542c7b0f43eb4 (commit)
via 3aa87f6826846585666e907b446a3809ccfce560 (commit)
via ee7acfccb0cd0d68dc4d7e64ae7fa0655314b444 (commit)
via 80dd41d265d1e2c366c8ea2dc1e79ee353f1e8f1 (commit)
via 89f3a8b45f18f1bf4e1a2e6082a93513582b6d55 (commit)
via 64ebfb19dd4c42b8ba81b258a1a408345c3b1caf (commit)
via 9d0ec38ee3ef9e08778abd66c6946bdec5f2d25b (commit)
via fb981291afb0a4dc0fcbd16b9bb552e5fbb5c20b (commit)
via 2f151e47e2579aed8c124385dacb3c971978ed45 (commit)
via 94270478763c9c4000ca94afb94fb4762f56c3f9 (commit)
via bebfa15d5007c3ba8ce740403c8333ea6480b83e (commit)
via 597bb698382ffdd04cdd2869ce5d2570dd5ac875 (commit)
via e01dadd724cfe1274f45c6be4b5ba6f532df8c0e (commit)
from dd1809bf5b3c9b6ac372523f5fc96a1baaf7d0a5 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 66174ced68123b63ec6d23a5f4ecd17302fd2e8b
Author: Jeremy C. Reed <jreed at ISC.org>
Date: Tue Feb 8 11:12:54 2011 -0600
[jreed-doxygen] remove wrong documentation
Briefly mentioned on jabber.
commit ef6da9e4e8d00024a6c7565eecc6216331ddfee1
Merge: dd1809bf5b3c9b6ac372523f5fc96a1baaf7d0a5 57fdfeac98e3519e64105849495c1557388bc402
Author: Jeremy C. Reed <jreed at ISC.org>
Date: Tue Feb 8 07:29:33 2011 -0600
[jreed-doxygen]Merge branch 'master' into jreed-doxygen
I manually removed conflicts.
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 5 +
src/bin/auth/auth_srv.cc | 12 +-
src/bin/auth/auth_srv.h | 3 +-
src/bin/auth/config.cc | 7 +-
src/bin/auth/tests/command_unittest.cc | 2 +-
src/bin/auth/tests/config_unittest.cc | 4 +
src/lib/asiolink/asiolink.cc | 36 +-
src/lib/asiolink/asiolink.h | 47 +--
src/lib/asiolink/tests/asiolink_unittest.cc | 116 +++---
src/lib/datasrc/memory_datasrc.cc | 3 +-
src/lib/datasrc/rbtree.h | 544 ++++++++++++++++++++-------
src/lib/datasrc/tests/rbtree_unittest.cc | 231 +++++++-----
src/lib/dns/rrset.h | 3 -
src/lib/log/tests/run_time_init_test.sh.in | 3 +-
14 files changed, 661 insertions(+), 355 deletions(-)
-----------------------------------------------------------------------
diff --git a/ChangeLog b/ChangeLog
index 29e62c9..ae4e72a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+ 164. [bug] y-aharen
+ IntervalTimer: Modified the interface to accept interval in
+ milliseconds. It shortens the time of the tests of IntervalTimer.
+ (Trac #452, git c9f6acc81e24c4b8f0eb351123dc7b43f64e0914)
+
163. [func] vorner
The pimpl design pattern is used in UDPServer, with a shared pointer. This
makes it smaller to copy (which is done a lot as a sideeffect of being
diff --git a/src/bin/auth/auth_srv.cc b/src/bin/auth/auth_srv.cc
index b8d5730..045fe7f 100644
--- a/src/bin/auth/auth_srv.cc
+++ b/src/bin/auth/auth_srv.cc
@@ -354,7 +354,7 @@ AuthSrv::setMemoryDataSrc(const isc::dns::RRClass& rrclass,
uint32_t
AuthSrv::getStatisticsTimerInterval() const {
- return (impl_->statistics_timer_.getInterval());
+ return (impl_->statistics_timer_.getInterval() / 1000);
}
void
@@ -362,11 +362,17 @@ AuthSrv::setStatisticsTimerInterval(uint32_t interval) {
if (interval == impl_->statistics_timer_.getInterval()) {
return;
}
+ if (interval > 86400) {
+ // It can't occur since the value is checked in
+ // statisticsIntervalConfig::build().
+ isc_throw(InvalidParameter, "Too long interval: " << interval);
+ }
if (interval == 0) {
impl_->statistics_timer_.cancel();
} else {
- impl_->statistics_timer_.setupTimer(
- boost::bind(&AuthSrv::submitStatistics, this), interval);
+ impl_->statistics_timer_.setup(boost::bind(&AuthSrv::submitStatistics,
+ this),
+ interval * 1000);
}
if (impl_->verbose_mode_) {
if (interval == 0) {
diff --git a/src/bin/auth/auth_srv.h b/src/bin/auth/auth_srv.h
index 7806be9..4772a02 100644
--- a/src/bin/auth/auth_srv.h
+++ b/src/bin/auth/auth_srv.h
@@ -318,7 +318,8 @@ public:
/// If the specified value is non 0, the \c AuthSrv object will submit
/// its statistics to the statistics module every \c interval seconds.
/// If it's 0, and \c AuthSrv currently submits statistics, the submission
- /// will be disabled.
+ /// will be disabled. \c interval must be equal to or shorter than 86400
+ /// seconds (1 day).
///
/// This method should normally not throw an exception; however, its
/// underlying library routines may involve resource allocation, and
diff --git a/src/bin/auth/config.cc b/src/bin/auth/config.cc
index 1f258e3..5befc6e 100644
--- a/src/bin/auth/config.cc
+++ b/src/bin/auth/config.cc
@@ -179,9 +179,14 @@ public:
virtual void build(ConstElementPtr config_value) {
const int32_t config_interval = config_value->intValue();
if (config_interval < 0) {
- isc_throw(AuthConfigError, "negative statistics-interval value: "
+ isc_throw(AuthConfigError, "Negative statistics interval value: "
<< config_interval);
}
+ if (config_interval > 86400) {
+ isc_throw(AuthConfigError, "Statistics interval value "
+ << config_interval
+ << " must be equal to or shorter than 86400");
+ }
interval_ = config_interval;
}
virtual void commit() {
diff --git a/src/bin/auth/tests/command_unittest.cc b/src/bin/auth/tests/command_unittest.cc
index 0ba5e86..f788d9e 100644
--- a/src/bin/auth/tests/command_unittest.cc
+++ b/src/bin/auth/tests/command_unittest.cc
@@ -98,7 +98,7 @@ AuthConmmandTest::stopServer() {
TEST_F(AuthConmmandTest, shutdown) {
asiolink::IntervalTimer itimer(server.getIOService());
- itimer.setupTimer(boost::bind(&AuthConmmandTest::stopServer, this), 1);
+ itimer.setup(boost::bind(&AuthConmmandTest::stopServer, this), 1);
server.getIOService().run();
EXPECT_EQ(0, rcode);
}
diff --git a/src/bin/auth/tests/config_unittest.cc b/src/bin/auth/tests/config_unittest.cc
index 0e0aee9..b8b379e 100644
--- a/src/bin/auth/tests/config_unittest.cc
+++ b/src/bin/auth/tests/config_unittest.cc
@@ -365,5 +365,9 @@ TEST_F(StatisticsIntervalConfigTest, badInterval) {
EXPECT_THROW(parser->build(Element::fromJSON("2.5")),
isc::data::TypeError);
EXPECT_THROW(parser->build(Element::fromJSON("-1")), AuthConfigError);
+ // bounds check: interval value must be equal to or shorter than
+ // 86400 seconds (1 day)
+ EXPECT_NO_THROW(parser->build(Element::fromJSON("86400")));
+ EXPECT_THROW(parser->build(Element::fromJSON("86401")), AuthConfigError);
}
}
diff --git a/src/lib/asiolink/asiolink.cc b/src/lib/asiolink/asiolink.cc
index 9adb52b..6fe7666 100644
--- a/src/lib/asiolink/asiolink.cc
+++ b/src/lib/asiolink/asiolink.cc
@@ -656,21 +656,20 @@ private:
public:
IntervalTimerImpl(IOService& io_service);
~IntervalTimerImpl();
- void setupTimer(const IntervalTimer::Callback& cbfunc,
- const uint32_t interval);
+ void setup(const IntervalTimer::Callback& cbfunc, const long interval);
void callback(const asio::error_code& error);
void cancel() {
timer_.cancel();
interval_ = 0;
}
- uint32_t getInterval() const { return (interval_); }
+ long getInterval() const { return (interval_); }
private:
// a function to update timer_ when it expires
- void updateTimer();
+ void update();
// a function to call back when timer_ expires
IntervalTimer::Callback cbfunc_;
- // interval in seconds
- uint32_t interval_;
+ // interval in milliseconds
+ long interval_;
// asio timer
asio::deadline_timer timer_;
};
@@ -683,12 +682,13 @@ IntervalTimerImpl::~IntervalTimerImpl()
{}
void
-IntervalTimerImpl::setupTimer(const IntervalTimer::Callback& cbfunc,
- const uint32_t interval)
+IntervalTimerImpl::setup(const IntervalTimer::Callback& cbfunc,
+ const long interval)
{
- // Interval should not be 0.
- if (interval == 0) {
- isc_throw(isc::BadValue, "Interval should not be 0");
+ // Interval should not be less than or equal to 0.
+ if (interval <= 0) {
+ isc_throw(isc::BadValue, "Interval should not be less than or "
+ "equal to 0");
}
// Call back function should not be empty.
if (cbfunc.empty()) {
@@ -699,19 +699,19 @@ IntervalTimerImpl::setupTimer(const IntervalTimer::Callback& cbfunc,
// Set initial expire time.
// At this point the timer is not running yet and will not expire.
// After calling IOService::run(), the timer will expire.
- updateTimer();
+ update();
return;
}
void
-IntervalTimerImpl::updateTimer() {
+IntervalTimerImpl::update() {
if (interval_ == 0) {
// timer has been canceled. Do nothing.
return;
}
try {
// Update expire time to (current time + interval_).
- timer_.expires_from_now(boost::posix_time::seconds(interval_));
+ timer_.expires_from_now(boost::posix_time::millisec(interval_));
} catch (const asio::system_error& e) {
isc_throw(isc::Unexpected, "Failed to update timer");
}
@@ -726,7 +726,7 @@ IntervalTimerImpl::callback(const asio::error_code& cancelled) {
if (!cancelled) {
cbfunc_();
// Set next expire time.
- updateTimer();
+ update();
}
}
@@ -739,8 +739,8 @@ IntervalTimer::~IntervalTimer() {
}
void
-IntervalTimer::setupTimer(const Callback& cbfunc, const uint32_t interval) {
- return (impl_->setupTimer(cbfunc, interval));
+IntervalTimer::setup(const Callback& cbfunc, const long interval) {
+ return (impl_->setup(cbfunc, interval));
}
void
@@ -748,7 +748,7 @@ IntervalTimer::cancel() {
impl_->cancel();
}
-uint32_t
+long
IntervalTimer::getInterval() const {
return (impl_->getInterval());
}
diff --git a/src/lib/asiolink/asiolink.h b/src/lib/asiolink/asiolink.h
index 8b3e0bc..521aebf 100644
--- a/src/lib/asiolink/asiolink.h
+++ b/src/lib/asiolink/asiolink.h
@@ -617,38 +617,36 @@ private:
/// \brief The \c IntervalTimer class is a wrapper for the ASIO
/// \c asio::deadline_timer class.
///
-/// This class is implemented to use \c asio::deadline_timer as
-/// interval timer.
+/// This class is implemented to use \c asio::deadline_timer as interval
+/// timer.
///
-/// \c setupTimer() sets a timer to expire on (now + interval) and
-/// a call back function.
+/// \c setup() sets a timer to expire on (now + interval) and a call back
+/// function.
///
-/// \c IntervalTimerImpl::callback() is called by the timer when
-/// it expires.
+/// \c IntervalTimerImpl::callback() is called by the timer when it expires.
///
-/// The function calls the call back function set by \c setupTimer()
-/// and updates the timer to expire in (now + interval) seconds.
+/// The function calls the call back function set by \c setup() and updates
+/// the timer to expire in (now + interval) milliseconds.
/// The type of call back function is \c void(void).
///
-/// The call back function will not be called if the instance of this
-/// class is destructed before the timer is expired.
+/// The call back function will not be called if the instance of this class is
+/// destroyed before the timer is expired.
///
-/// Note: Destruction of an instance of this class while call back
-/// is pending causes throwing an exception from \c IOService.
+/// Note: Destruction of an instance of this class while call back is pending
+/// causes throwing an exception from \c IOService.
///
/// Sample code:
/// \code
/// void function_to_call_back() {
/// // this function will be called periodically
/// }
-/// int interval_in_seconds = 1;
+/// int interval_in_milliseconds = 1000;
/// IOService io_service;
///
/// IntervalTimer intervalTimer(io_service);
-/// intervalTimer.setupTimer(function_to_call_back, interval_in_seconds);
+/// intervalTimer.setup(function_to_call_back, interval_in_milliseconds);
/// io_service.run();
/// \endcode
-///
class IntervalTimer {
public:
/// \name The type of timer callback function
@@ -671,7 +669,6 @@ public:
/// This constructor may also throw \c asio::system_error.
///
/// \param io_service A reference to an instance of IOService
- ///
IntervalTimer(IOService& io_service);
/// \brief The destructor.
@@ -680,28 +677,26 @@ public:
///
/// On the destruction of this class the timer will be canceled
/// inside \c asio::deadline_timer.
- ///
~IntervalTimer();
//@}
/// \brief Register timer callback function and interval.
///
- /// This function sets callback function and interval in seconds.
+ /// This function sets callback function and interval in milliseconds.
/// Timer will actually start after calling \c IOService::run().
///
/// \param cbfunc A reference to a function \c void(void) to call back
/// when the timer is expired (should not be an empty functor)
- /// \param interval Interval in seconds (greater than 0)
+ /// \param interval Interval in milliseconds (greater than 0)
///
/// Note: IntervalTimer will not pass \c asio::error_code to
/// call back function. In case the timer is cancelled, the function
/// will not be called.
///
/// \throw isc::InvalidParameter cbfunc is empty
- /// \throw isc::BadValue interval is 0
+ /// \throw isc::BadValue interval is less than or equal to 0
/// \throw isc::Unexpected ASIO library error
- ///
- void setupTimer(const Callback& cbfunc, const uint32_t interval);
+ void setup(const Callback& cbfunc, const long interval);
/// Cancel the timer.
///
@@ -715,15 +710,11 @@ public:
/// Return the timer interval.
///
- /// This method returns the timer interval in seconds if it's running;
+ /// This method returns the timer interval in milliseconds if it's running;
/// if the timer has been canceled it returns 0.
///
/// This method never throws an exception.
- ///
- /// Note: We may want to change the granularity of the timer to
- /// milliseconds or even finer. If and when this happens the semantics
- /// of the return value of this method will be changed accordingly.
- uint32_t getInterval() const;
+ long getInterval() const;
private:
IntervalTimerImpl* impl_;
diff --git a/src/lib/asiolink/tests/asiolink_unittest.cc b/src/lib/asiolink/tests/asiolink_unittest.cc
index be08136..2044d50 100644
--- a/src/lib/asiolink/tests/asiolink_unittest.cc
+++ b/src/lib/asiolink/tests/asiolink_unittest.cc
@@ -1028,13 +1028,12 @@ protected:
++count_;
if (count_ == 1) {
// First time of call back.
- // Call setupTimer() to update callback function
- // to TimerCallBack.
+ // Call setup() to update callback function to TimerCallBack.
test_obj_->timer_called_ = false;
- timer_.setupTimer(TimerCallBack(test_obj_), 1);
+ timer_.setup(TimerCallBack(test_obj_), 100);
} else if (count_ == 2) {
// Second time of call back.
- // If it reaches here, re-setupTimer() is failed (unexpected).
+ // If it reaches here, re-setup() is failed (unexpected).
// We should stop here.
test_obj_->io_service_.stop();
}
@@ -1055,10 +1054,11 @@ TEST_F(IntervalTimerTest, invalidArgumentToIntervalTimer) {
// Create asio_link::IntervalTimer and setup.
IntervalTimer itimer(io_service_);
// expect throw if call back function is empty
- EXPECT_THROW(itimer.setupTimer(IntervalTimer::Callback(), 1),
- isc::InvalidParameter);
- // expect throw if interval is 0
- EXPECT_THROW(itimer.setupTimer(TimerCallBack(this), 0), isc::BadValue);
+ EXPECT_THROW(itimer.setup(IntervalTimer::Callback(), 1),
+ isc::InvalidParameter);
+ // expect throw if interval is not greater than 0
+ EXPECT_THROW(itimer.setup(TimerCallBack(this), 0), isc::BadValue);
+ EXPECT_THROW(itimer.setup(TimerCallBack(this), -1), isc::BadValue);
}
TEST_F(IntervalTimerTest, startIntervalTimer) {
@@ -1070,33 +1070,30 @@ TEST_F(IntervalTimerTest, startIntervalTimer) {
boost::posix_time::ptime start;
start = boost::posix_time::microsec_clock::universal_time();
// setup timer
- itimer.setupTimer(TimerCallBack(this), 1);
- EXPECT_EQ(1, itimer.getInterval());
+ itimer.setup(TimerCallBack(this), 100);
+ EXPECT_EQ(100, itimer.getInterval());
io_service_.run();
// reaches here after timer expired
- // delta: difference between elapsed time and 1 second
+ // delta: difference between elapsed time and 100 milliseconds.
boost::posix_time::time_duration delta =
(boost::posix_time::microsec_clock::universal_time() - start)
- - boost::posix_time::seconds(1);
+ - boost::posix_time::millisec(100);
if (delta.is_negative()) {
delta.invert_sign();
}
// expect TimerCallBack is called; timer_called_ is true
EXPECT_TRUE(timer_called_);
- // expect interval is 1 second +/- TIMER_MARGIN_MSEC.
+ // expect interval is 100 milliseconds +/- TIMER_MARGIN_MSEC.
EXPECT_TRUE(delta < TIMER_MARGIN_MSEC);
}
TEST_F(IntervalTimerTest, destructIntervalTimer) {
- // Note: This test currently takes 6 seconds. The timer should have
- // finer granularity and timer periods in this test should be shorter
- // in the future.
// This code isn't exception safe, but we'd rather keep the code
// simpler and more readable as this is only for tests and if it throws
// the program would immediately terminate anyway.
// The call back function will not be called after the timer is
- // destructed.
+ // destroyed.
//
// There are two timers:
// itimer_counter (A)
@@ -1105,31 +1102,30 @@ TEST_F(IntervalTimerTest, destructIntervalTimer) {
// itimer_canceller (B)
// (Calls TimerCallBackCancelDeleter)
// - first time of callback, it stores the counter value of
- // callback_canceller and destructs itimer_counter
+ // callback_canceller and destroys itimer_counter
// - second time of callback, it compares the counter value of
// callback_canceller with stored value
// if they are same the timer was not called; expected result
- // if they are different the timer was called after destructed
- //
- // 0 1 2 3 4 5 6 (s)
- // (A) i-----+--x
- // ^
- // |destruct itimer_counter
- // (B) i--------+--------s
- // ^stop io_service
- // and test itimer_counter have been stopped
+ // if they are different the timer was called after destroyed
//
+ // 0 100 200 300 400 500 600 (ms)
+ // (A) i--------+----x
+ // ^
+ // |destroy itimer_counter
+ // (B) i-------------+--------------s
+ // ^stop io_service
+ // and check if itimer_counter have been
+ // stopped
// itimer_counter will be deleted in TimerCallBackCancelDeleter
IntervalTimer* itimer_counter = new IntervalTimer(io_service_);
IntervalTimer itimer_canceller(io_service_);
timer_cancel_success_ = false;
TimerCallBackCounter callback_canceller(this);
- itimer_counter->setupTimer(callback_canceller, 2);
- itimer_canceller.setupTimer(
- TimerCallBackCancelDeleter(this, itimer_counter,
- callback_canceller),
- 3);
+ itimer_counter->setup(callback_canceller, 200);
+ itimer_canceller.setup(
+ TimerCallBackCancelDeleter(this, itimer_counter, callback_canceller),
+ 300);
io_service_.run();
EXPECT_TRUE(timer_cancel_success_);
}
@@ -1140,9 +1136,8 @@ TEST_F(IntervalTimerTest, cancel) {
IntervalTimer itimer_counter(io_service_);
IntervalTimer itimer_watcher(io_service_);
unsigned int counter = 0;
- itimer_counter.setupTimer(TimerCallBackCanceller(counter, itimer_counter),
- 1);
- itimer_watcher.setupTimer(TimerCallBack(this), 3);
+ itimer_counter.setup(TimerCallBackCanceller(counter, itimer_counter), 100);
+ itimer_watcher.setup(TimerCallBack(this), 200);
io_service_.run();
EXPECT_EQ(1, counter);
EXPECT_EQ(0, itimer_counter.getInterval());
@@ -1152,36 +1147,31 @@ TEST_F(IntervalTimerTest, cancel) {
}
TEST_F(IntervalTimerTest, overwriteIntervalTimer) {
- // Note: This test currently takes 4 seconds. The timer should have
- // finer granularity and timer periods in this test should be shorter
- // in the future.
-
- // Calling setupTimer() multiple times updates call back function
- // and interval.
+ // Calling setup() multiple times updates call back function and interval.
//
// There are two timers:
// itimer (A)
// (Calls TimerCallBackCounter / TimerCallBack)
// - increments internal counter in callback function
// (TimerCallBackCounter)
- // interval: 2 seconds
+ // interval: 300 milliseconds
// - io_service_.stop() (TimerCallBack)
- // interval: 1 second
+ // interval: 100 milliseconds
// itimer_overwriter (B)
// (Calls TimerCallBackOverwriter)
- // - first time of callback, it calls setupTimer() to change
- // call back function and interval of itimer to
- // TimerCallBack / 1 second
- // after 3 + 1 seconds from the beginning of this test,
+ // - first time of callback, it calls setup() to change call back
+ // function to TimerCallBack and interval of itimer to 100
+ // milliseconds
+ // after 300 + 100 milliseconds from the beginning of this test,
// TimerCallBack() will be called and io_service_ stops.
// - second time of callback, it means the test fails.
//
- // 0 1 2 3 4 5 6 (s)
- // (A) i-----+--C--s
- // ^ ^stop io_service
- // |change call back function
- // (B) i--------+--------S
- // ^(stop io_service on fail)
+ // 0 100 200 300 400 500 600 700 800 (ms)
+ // (A) i-------------+----C----s
+ // ^ ^stop io_service
+ // |change call back function
+ // (B) i------------------+-------------------S
+ // ^(stop io_service on fail)
//
IntervalTimer itimer(io_service_);
@@ -1189,22 +1179,22 @@ TEST_F(IntervalTimerTest, overwriteIntervalTimer) {
// store start time
boost::posix_time::ptime start;
start = boost::posix_time::microsec_clock::universal_time();
- itimer.setupTimer(TimerCallBackCounter(this), 2);
- itimer_overwriter.setupTimer(TimerCallBackOverwriter(this, itimer), 3);
+ itimer.setup(TimerCallBackCounter(this), 300);
+ itimer_overwriter.setup(TimerCallBackOverwriter(this, itimer), 400);
io_service_.run();
// reaches here after timer expired
// if interval is updated, it takes
- // 3 seconds for TimerCallBackOverwriter
- // + 1 second for TimerCallBack (stop)
- // = 4 seconds.
+ // 400 milliseconds for TimerCallBackOverwriter
+ // + 100 milliseconds for TimerCallBack (stop)
+ // = 500 milliseconds.
// otherwise (test fails), it takes
- // 3 seconds for TimerCallBackOverwriter
- // + 3 seconds for TimerCallBackOverwriter (stop)
- // = 6 seconds.
- // delta: difference between elapsed time and 3 + 1 seconds
+ // 400 milliseconds for TimerCallBackOverwriter
+ // + 400 milliseconds for TimerCallBackOverwriter (stop)
+ // = 800 milliseconds.
+ // delta: difference between elapsed time and 400 + 100 milliseconds
boost::posix_time::time_duration delta =
(boost::posix_time::microsec_clock::universal_time() - start)
- - boost::posix_time::seconds(3 + 1);
+ - boost::posix_time::millisec(400 + 100);
if (delta.is_negative()) {
delta.invert_sign();
}
diff --git a/src/lib/datasrc/memory_datasrc.cc b/src/lib/datasrc/memory_datasrc.cc
index 8f46aa4..31c5a95 100644
--- a/src/lib/datasrc/memory_datasrc.cc
+++ b/src/lib/datasrc/memory_datasrc.cc
@@ -290,7 +290,8 @@ struct MemoryZone::MemoryZoneImpl {
// Get the node
DomainNode* node(NULL);
FindState state(options);
- switch (domains_.find(name, &node, cutCallback, &state)) {
+ RBTreeNodeChain<Domain> node_path;
+ switch (domains_.find(name, &node, node_path, cutCallback, &state)) {
case DomainTree::PARTIALMATCH:
/*
* In fact, we could use a single variable instead of
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 2afd4f3..cf413e8 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -26,9 +26,10 @@
#include <dns/name.h>
#include <boost/utility.hpp>
#include <boost/shared_ptr.hpp>
-#include <exception>
+#include <exceptions/exceptions.h>
#include <ostream>
#include <algorithm>
+#include <cassert>
namespace isc {
namespace datasrc {
@@ -54,7 +55,9 @@ operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
}
}
-template <typename T, bool returnEmptyNode>
+/// Forward declare RBTree class here is convinent for following friend
+/// class declare inside RBNode and RBTreeNodeChain
+template <typename T>
class RBTree;
/// \brief \c RBNode is used by RBTree to store any data related to one domain
@@ -82,8 +85,7 @@ class RBNode : public boost::noncopyable {
private:
/// The RBNode is meant for use from within RBTree, so it has access to
/// it.
- template <typename U, bool returnEmptyNode>
- friend class RBTree;
+ friend class RBTree<T>;
/// \name Constructors
///
@@ -142,6 +144,7 @@ public:
/// non-terminal domains, but it is possible (yet probably meaningless)
/// empty nodes anywhere.
bool isEmpty() const { return (data_.get() == NULL); }
+
//@}
/// \name Setter functions.
@@ -176,6 +179,23 @@ private:
return (&null_node);
}
+ /// \brief return the next node which is bigger than current node
+ /// in the same subtree
+ ///
+ /// The next successor for this node is the next bigger node in terms of
+ /// the DNSSEC order relation within the same single subtree.
+ /// Note that it may NOT be the next bigger node in the entire RBTree;
+ /// RBTree is a tree in tree, and the real next node may reside in
+ /// an upper or lower subtree of the subtree where this node belongs.
+ /// For example, if this node has a sub domain, the real next node is
+ /// the smallest node in the sub domain tree.
+ ///
+ /// If this node is the biggest node within the subtree, this method
+ /// returns \c NULL_NODE().
+ ///
+ /// This method never throws an exception.
+ const RBNode<T>* successor() const;
+
/// \name Data to maintain the rbtree structure.
//@{
RBNode<T>* parent_;
@@ -239,6 +259,169 @@ template <typename T>
RBNode<T>::~RBNode() {
}
+template <typename T>
+const RBNode<T>*
+RBNode<T>::successor() const {
+ const RBNode<T>* current = this;
+ // If it has right node, the successor is the left-most node of the right
+ // subtree.
+ if (right_ != NULL_NODE()) {
+ current = right_;
+ while (current->left_ != NULL_NODE()) {
+ current = current->left_;
+ }
+ return (current);
+ }
+
+
+ // Otherwise go up until we find the first left branch on our path to
+ // root. If found, the parent of the branch is the successor.
+ // Otherwise, we return the null node
+ const RBNode<T>* parent = current->parent_;
+ while (parent != NULL_NODE() && current == parent->right_) {
+ current = parent;
+ parent = parent->parent_;
+ }
+ return (parent);
+}
+
+
+/// \brief RBTreeNodeChain is used to keep track of the sequence of
+/// nodes to reach any given node from the root of RBTree.
+///
+/// Currently, RBNode does not have "up" pointers in them (i.e., back pointers
+/// from the root of one level of tree of trees to the node in the parent
+/// tree whose down pointer points to that root node) for memory usage
+/// reasons, so there is no other way to find the path back to the root from
+/// any given RBNode.
+///
+/// \note This design may change in future versions. In particular, it's
+/// quite likely we want to have that pointer if we want to optimize name
+/// compression by exploiting the structure of the zone. If and when that
+/// happens we should also revisit the need for the chaining.
+///
+/// RBTreeNodeChain is constructed and manipulated only inside the \c RBTree
+/// class.
+/// \c RBTree uses it as an inner data structure to iterate over the whole
+/// RBTree.
+/// This is the reason why manipulation methods such as \c push() and \c pop()
+/// are private (and not shown in the doxygen document).
+template <typename T>
+class RBTreeNodeChain {
+ /// RBTreeNodeChain is initialized by RBTree, only RBTree has
+ /// knowledge to manipuate it.
+ friend class RBTree<T>;
+public:
+ /// \name Constructors and Assignment Operator.
+ ///
+ /// \note The copy constructor and the assignment operator are
+ /// intentionally defined as private, making this class non copyable.
+ /// This may have to be changed in a future version with newer need.
+ /// For now we explicitly disable copy to avoid accidental copy happens
+ /// unintentionally.
+ //{@
+ /// The default constructor.
+ ///
+ /// \exception None
+ RBTreeNodeChain() : node_count_(0) {}
+
+private:
+ RBTreeNodeChain(const RBTreeNodeChain<T>&);
+ RBTreeNodeChain<T>& operator=(const RBTreeNodeChain<T>&);
+ //@}
+
+public:
+ /// \brief Return the number of levels stored in the chain.
+ ///
+ /// It's equal to the number of nodes in the chain; for an empty
+ /// chain, 0 will be returned.
+ ///
+ /// \exception None
+ unsigned int getLevelCount() const { return (node_count_); }
+
+ /// \brief return the absolute name for the node which this
+ /// \c RBTreeNodeChain currently refers to.
+ ///
+ /// The chain must not be empty.
+ ///
+ /// \exception isc::BadValue the chain is empty.
+ /// \exception std::bad_alloc memory allocation for the new name fails.
+ isc::dns::Name getAbsoluteName() const {
+ if (isEmpty()) {
+ isc_throw(isc::BadValue,
+ "RBTreeNodeChain::getAbsoluteName is called on an empty "
+ "chain");
+ }
+
+ const RBNode<T>* top_node = top();
+ isc::dns::Name absolute_name = top_node->getName();
+ int node_count = node_count_ - 1;
+ while (node_count > 0) {
+ top_node = nodes_[node_count - 1];
+ absolute_name = absolute_name.concatenate(top_node->getName());
+ --node_count;
+ }
+ return (absolute_name);
+ }
+
+private:
+ // the following private functions check invariants about the internal
+ // state using assert() instead of exception. The state of a chain
+ // can only be modified operations within this file, so if any of the
+ // assumptions fails it means an internal bug.
+
+ /// \brief return whther node chain has node in it.
+ ///
+ /// \exception None
+ bool isEmpty() const { return (node_count_ == 0); }
+
+ /// \brief return the top node for the node chain
+ ///
+ /// RBTreeNodeChain store all the nodes along top node to
+ /// root node of RBTree
+ ///
+ /// \exception None
+ const RBNode<T>* top() const {
+ assert(!isEmpty());
+ return (nodes_[node_count_ - 1]);
+ }
+
+ /// \brief pop the top node from the node chain
+ ///
+ /// After pop, up/super node of original top node will be
+ /// the top node
+ ///
+ /// \exception None
+ void pop() {
+ assert(!isEmpty());
+ --node_count_;
+ }
+
+ /// \brief add the node into the node chain
+ ///
+ /// If the node chain isn't empty, the node should be
+ /// the sub domain of the original top node in node chain
+ /// otherwise the node should be the root node of RBTree.
+ ///
+ /// \exception None
+ void push(const RBNode<T>* node) {
+ assert(node_count_ < RBT_MAX_LEVEL);
+ nodes_[node_count_++] = node;
+ }
+
+private:
+ // The max label count for one domain name is Name::MAX_LABELS (128).
+ // Since each node in rbtree stores at least one label, and the root
+ // name always shares the same level with some others (which means
+ // all top level nodes except the one for the root name contain at least
+ // two labels), the possible maximum level is MAX_LABELS - 1.
+ // It's also the possible maximum nodes stored in a chain.
+ const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS - 1;
+
+ const RBNode<T>* nodes_[RBT_MAX_LEVEL];
+ int node_count_;
+};
+
// note: the following class description is documented using multiline comments
// because the verbatim diagram contain a backslash, which could be interpreted
@@ -258,11 +441,16 @@ RBNode<T>::~RBNode() {
* - Decreases the memory footprint, as it doesn't store the suffix labels
* multiple times.
*
- * Depending on different usage, rbtree will support different search policy.
- * Whether return empty node to end user is one policy among them. Search
- * policy is as the last template parameter, the default policy will NOT
- * return empty node to end user, pass ture will get empty node during find
- * is needed
+ * Depending on different usage, rbtree will support different search policies.
+ * Whether to return an empty node to end user is one policy among them.
+ * The default policy is to NOT return an empty node to end user;
+ * to change the behavior, specify \c true for the constructor parameter
+ * \c returnEmptyNode.
+ * \note The search policy only affects the \c find() behavior of RBTree.
+ * When inserting one name into RBTree, if the node with the name already
+ * exists in the RBTree and it's an empty node which doesn't have any data,
+ * the \c insert() method will still return \c ALREADYEXISTS regardless of
+ * the search policy.
*
* \anchor diagram
*
@@ -277,7 +465,7 @@ RBNode<T>::~RBNode() {
* - p.w.y.d.e.f
* - q.w.y.d.e.f
*
- * the tree will looks like:
+ * the tree will look like:
* \verbatim
b
/ \
@@ -297,10 +485,8 @@ RBNode<T>::~RBNode() {
* - add remove interface
* - add iterator to iterate over the whole \c RBTree. This may be necessary,
* for example, to support AXFR.
- * - since \c RBNode only has down pointer without up pointer, the node path
- * during finding should be recorded for later use
*/
-template <typename T, bool returnEmptyNode = false>
+template <typename T>
class RBTree : public boost::noncopyable {
friend class RBNode<T>;
public:
@@ -320,7 +506,7 @@ public:
/// The constructor.
///
/// It never throws an exception.
- explicit RBTree();
+ explicit RBTree(bool returnEmptyNode = false);
/// \b Note: RBTree is not intended to be inherited so the destructor
/// is not virtual
@@ -333,22 +519,25 @@ public:
///
/// \anchor find
///
- /// These methods search the RBTree for a node whose name is a longest
+ /// These methods search the RBTree for a node whose name is longest
/// against name. The found node, if any, is returned via the node pointer.
///
/// By default, nodes that don't have data (see RBNode::isEmpty) are
/// ignored and the result can be NOTFOUND even if there's a node whose
- /// name mathes. The plan is to introduce a "no data OK" mode for this
- /// method, that would match any node of the tree regardless of wheather
- /// the node has any data or not.
+ /// name matches. If the \c RBTree is constructed with its
+ /// \c returnEmptyNode parameter being \c true, an empty node will also
+ /// be match candidates.
///
- /// The case with "no data OK" mode is not as easy as it seems. For example
- /// in the diagram shown in the class description, the name y.d.e.f is
- /// logically contained in the tree as part of the node w.y. It cannot be
- /// identified simply by checking whether existing nodes (such as
- /// d.e.f or w.y) has data.
+ /// \note Even when \c returnEmptyNode is \c true, not all empty nodes
+ /// in terms of the DNS protocol may necessarily be found by this method.
+ /// For example, in the \ref diagram shown in the class description,
+ /// the name y.d.e.f is logically contained in the tree as part of the
+ /// node w.y, but the \c find() variants cannot find the former for
+ /// the search key of y.d.e.f, no matter how the \c RBTree is constructed.
+ /// The caller of this method must use a different way to identify the
+ /// hidden match when necessary.
///
- /// These methods involves operations on names that can throw an exception.
+ /// These methods involve operations on names that can throw an exception.
/// If that happens the exception will be propagated to the caller.
/// The callback function should generally not throw an exception, but
/// if it throws, the exception will be propagated to the caller.
@@ -369,13 +558,39 @@ public:
/// of it. In that case, node parameter is left intact.
//@{
- /// \brief Find with callback.
+ /// \brief Simple find.
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, RBNode<T>** node) const {
+ RBTreeNodeChain<T> node_path;
+ return (find<void*>(name, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find returning immutable node.
+ ///
+ /// Acts as described in the \ref find section, but returns immutable node
+ /// pointer.
+ Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
+ RBTreeNodeChain<T> node_path;
+ RBNode<T> *target_node = NULL;
+ Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+
+ /// \brief Find with callback and node chain.
///
- /// \anchor callback
+ /// This version of \c find() is specifically designed for the backend
+ /// of the \c MemoryZone class, and implements all necessary features
+ /// for that purpose. Other applications shouldn't need these additional
+ /// features, and should normally use the simpler versions.
///
- /// This version of find calls the callback whenever traversing (on the
- /// way from root down the tree) a marked node on the way down through the
- /// domain namespace (see RBNode::enableCallback and related functions).
+ /// This version of \c find() calls the callback whenever traversing (on
+ /// the way from root down the tree) a marked node on the way down through
+ /// the domain namespace (see RBNode::enableCallback and related
+ /// functions).
///
/// If you return true from the callback, the search is stopped and a
/// PARTIALMATCH is returned with the given node. Note that this node
@@ -388,9 +603,32 @@ public:
/// The callbacks are not general functors for the same reason - we don't
/// expect it to be needed.
///
+ /// Another special feature of this version is the ability to provide
+ /// a node chain containing a path to the found node. The chain will be
+ /// returned via the \c node_path parameter.
+ /// The passed parameter must be empty.
+ /// On success, it will contain all the ancestor nodes from the found
+ /// node towards the root.
+ /// For example, if we look for o.w.y.d.e.f in the example \ref diagram,
+ /// \c node_path will contain w.y and d.e.f; the \c top() node of the
+ /// chain will be o, w.f and d.e.f will be stored below it.
+ ///
+ /// This feature can be used to get the absolute name for a node;
+ /// to do so, we need to travel upside from the node toward the root,
+ /// concatenating all ancestor names. With the current implementation
+ /// it's not possible without a node chain, because there is a no pointer
+ /// from the root of a subtree to the parent subtree (this may change
+ /// in a future version). A node chain can also be used to find the next
+ /// node of a given node in the entire RBTree; the \c nextNode() method
+ /// takes a node chain as a parameter.
+ ///
+ /// \exception isc::BadValue node_path is not empty.
+ ///
/// \param name Target to be found
/// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
/// it will store a pointer to the matching node
+ /// \param node_path It will store all the ancestor nodes in the RBTree
+ /// from the found node to the root. The found node is stored.
/// \param callback If non \c NULL, a call back function to be called
/// at marked nodes (see above).
/// \param callback_arg A caller supplied argument to be passed to
@@ -399,33 +637,57 @@ public:
/// \return As described above, but in case of callback returning true,
/// it returns immediately with the current node.
template <typename CBARG>
- Result find(const isc::dns::Name& name, RBNode<T>** node,
+ Result find(const isc::dns::Name& name,
+ RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
CBARG callback_arg) const;
- /// \brief Find with callback returning immutable node.
+ /// \brief Simple find returning immutable node.
///
- /// It has the same behaviour as the find with \ref callback version.
+ /// Acts as described in the \ref find section, but returns immutable
+ /// node pointer.
template <typename CBARG>
- Result find(const isc::dns::Name& name, const RBNode<T>** node,
+ Result find(const isc::dns::Name& name,
+ const RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const;
-
- /// \brief Simple find.
- ///
- /// Acts as described in the \ref find section.
- Result find(const isc::dns::Name& name, RBNode<T>** node) const {
- return (find<void*>(name, node, NULL, NULL));
+ CBARG callback_arg) const
+ {
+ RBNode<T>* target_node = NULL;
+ Result ret = find(name, &target_node, node_path, callback,
+ callback_arg);
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
}
+ //@}
- /// \brief Simple find returning immutable node.
+ /// \brief return the next bigger node in DNSSEC order from a given node
+ /// chain.
///
- /// Acts as described in the \ref find section, but returns immutable node
- /// pointer.
- Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
- return (find<void*>(name, node, NULL, NULL));
- }
- //@}
+ /// This method identifies the next bigger node of the node currently
+ /// referenced in \c node_path and returns it.
+ /// This method also updates the passed \c node_path so that it will store
+ /// the path for the returned next node.
+ /// It will be convenient when we want to iterate over the all nodes
+ /// of \c RBTree; we can do this by calling this method repeatedly
+ /// starting from the root node.
+ ///
+ /// \note \c nextNode() will iterate over all the nodes in RBTree including
+ /// empty nodes. If empty node isn't desired, it's easy to add logic to
+ /// check return node and keep invoking \c nextNode() until the non-empty
+ /// node is retrieved.
+ ///
+ /// \exception isc::BadValue node_path is empty.
+ ///
+ /// \param node_path A node chain that stores all the nodes along the path
+ /// from root to node.
+ ///
+ /// \return An \c RBNode that is next bigger than \c node; if \c node is
+ /// the largest, \c NULL will be returned.
+ const RBNode<T>* nextNode(RBTreeNodeChain<T>& node_path) const;
/// \brief Get the total number of nodes in the tree
///
@@ -502,23 +764,11 @@ private:
//@{
/// \brief delete tree whose root is equal to node
void deleteHelper(RBNode<T> *node);
- /// \brief find the node with name
- ///
- /// Internal searching function.
- ///
- /// \param name What should be found.
- /// \param up It will point to the node whose down pointer points
- /// to the tree containing node. If we looked for o.w.y.d.e.f in the
- /// \ref diagram, the up would point to the w.y node.
- /// This parameter is not used currently, but it will be soon.
- /// \param node The found node.
- template <typename CBARG>
- Result findHelper(const isc::dns::Name& name, const RBNode<T>** up,
- RBNode<T>** node,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const;
+
+ /// \brief Print the information of given RBNode.
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const;
+
/// \brief Indentation helper function for dumpTree
static void indent(std::ostream& os, unsigned int depth);
@@ -529,39 +779,43 @@ private:
void nodeFission(RBNode<T>& node, const isc::dns::Name& sub_name);
//@}
- RBNode<T>* root_;
RBNode<T>* NULLNODE;
+ RBNode<T>* root_;
/// the node count of current tree
unsigned int node_count_;
+ /// search policy for rbtree
+ const bool needsReturnEmptyNode_;
};
-template <typename T, bool S>
-RBTree<T,S>::RBTree() {
- NULLNODE = RBNode<T>::NULL_NODE();
- root_ = NULLNODE;
- node_count_ = 0;
+template <typename T>
+RBTree<T>::RBTree(bool returnEmptyNode) :
+ NULLNODE(RBNode<T>::NULL_NODE()),
+ root_(NULLNODE),
+ node_count_(0),
+ needsReturnEmptyNode_(returnEmptyNode)
+{
}
-template <typename T, bool S>
-RBTree<T,S>::~RBTree() {
+template <typename T>
+RBTree<T>::~RBTree() {
deleteHelper(root_);
assert(node_count_ == 0);
}
-template <typename T, bool S>
-void
-RBTree<T,S>::deleteHelper(RBNode<T> *root) {
+template <typename T>
+void
+RBTree<T>::deleteHelper(RBNode<T>* root) {
if (root == NULLNODE) {
return;
}
- RBNode<T> *node = root;
+ RBNode<T>* node = root;
while (root->left_ != NULLNODE || root->right_ != NULLNODE) {
while (node->left_ != NULLNODE || node->right_ != NULLNODE) {
node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
}
- RBNode<T> *parent = node->parent_;
+ RBNode<T>* parent = node->parent_;
if (parent->left_ == node) {
parent->left_ = NULLNODE;
} else {
@@ -579,48 +833,23 @@ RBTree<T,S>::deleteHelper(RBNode<T> *root) {
--node_count_;
}
-template <typename T, bool S>
+template <typename T>
template <typename CBARG>
-typename RBTree<T,S>::Result
-RBTree<T,S>::find(const isc::dns::Name& name, RBNode<T>** node,
+typename RBTree<T>::Result
+RBTree<T>::find(const isc::dns::Name& target_name,
+ RBNode<T>** target,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
CBARG callback_arg) const
{
- const RBNode<T>* up_node = NULLNODE;
- return (findHelper(name, &up_node, node, callback, callback_arg));
-}
+ using namespace helper;
-template <typename T, bool S>
-template <typename CBARG>
-typename RBTree<T,S>::Result
-RBTree<T,S>::find(const isc::dns::Name& name, const RBNode<T>** node,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const
-{
- const RBNode<T>* up_node;
- RBNode<T>* target_node;
- const typename RBTree<T,S>::Result ret =
- findHelper(name, &up_node, &target_node, callback, callback_arg);
- if (ret != NOTFOUND) {
- *node = target_node;
+ if (!node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
}
- return (ret);
-}
-
-template <typename T, bool returnEmptyNode>
-template <typename CBARG>
-typename RBTree<T,returnEmptyNode>::Result
-RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
- const RBNode<T>** up_node,
- RBNode<T>** target,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const
-{
- using namespace helper;
RBNode<T>* node = root_;
- typename RBTree<T,returnEmptyNode>::Result ret = NOTFOUND;
- *up_node = NULLNODE;
+ Result ret = NOTFOUND;
isc::dns::Name name = target_name;
while (node != NULLNODE) {
@@ -629,7 +858,8 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
const isc::dns::NameComparisonResult::NameRelation relation =
compare_result.getRelation();
if (relation == isc::dns::NameComparisonResult::EQUAL) {
- if (returnEmptyNode || !node->isEmpty()) {
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ node_path.push(node);
*target = node;
ret = EXACTMATCH;
}
@@ -642,8 +872,8 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
node = (compare_result.getOrder() < 0) ?
node->left_ : node->right_;
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
- if (returnEmptyNode || !node->isEmpty()) {
- ret = RBTree<T,returnEmptyNode>::PARTIALMATCH;
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ ret = PARTIALMATCH;
*target = node;
if (callback != NULL && node->callback_required_) {
if ((callback)(*node, callback_arg)) {
@@ -651,7 +881,7 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
}
}
}
- *up_node = node;
+ node_path.push(node);
name = name - node->name_;
node = node->down_;
} else {
@@ -663,11 +893,54 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
return (ret);
}
+template <typename T>
+const RBNode<T>*
+RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
+ if (node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::nextNode is given an empty chain");
+ }
+
+ const RBNode<T>* node = node_path.top();
+ // if node has sub domain, the next domain is the smallest
+ // domain in sub domain tree
+ if (node->down_ != NULLNODE) {
+ const RBNode<T>* left_most = node->down_;
+ while (left_most->left_ != NULLNODE) {
+ left_most = left_most->left_;
+ }
+ node_path.push(left_most);
+ return (left_most);
+ }
+
+ // node_path go to up level
+ node_path.pop();
+ // otherwise found the successor node in current level
+ const RBNode<T>* successor = node->successor();
+ if (successor != NULLNODE) {
+ node_path.push(successor);
+ return (successor);
+ }
+
+ // if no successor found move to up level, the next successor
+ // is the successor of up node in the up level tree, if
+ // up node doesn't have successor we gonna keep moving to up
+ // level
+ while (!node_path.isEmpty()) {
+ const RBNode<T>* up_node_successor = node_path.top()->successor();
+ node_path.pop();
+ if (up_node_successor != NULLNODE) {
+ node_path.push(up_node_successor);
+ return (up_node_successor);
+ }
+ }
+
+ return (NULL);
+}
+
-template <typename T, bool returnEmptyNode>
-typename RBTree<T,returnEmptyNode>::Result
-RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
- RBNode<T>** new_node) {
+template <typename T>
+typename RBTree<T>::Result
+RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
RBNode<T>* parent = NULLNODE;
RBNode<T>* current = root_;
@@ -684,12 +957,7 @@ RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
if (new_node != NULL) {
*new_node = current;
}
-
- if (current->isEmpty() && !returnEmptyNode) {
- return (SUCCESS);
- } else {
- return (ALREADYEXISTS);
- }
+ return (ALREADYEXISTS);
} else {
const int common_label_count = compare_result.getCommonLabels();
if (common_label_count == 1) {
@@ -746,9 +1014,9 @@ RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
+RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
using namespace helper;
const isc::dns::Name sub_name = node.name_ - base_name;
// using auto_ptr here is to avoid memory leak in case of exception raised
@@ -769,9 +1037,9 @@ RBTree<T,S>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* uncle;
while (node != *root && node->parent_->color_ == RBNode<T>::RED) {
@@ -815,9 +1083,9 @@ RBTree<T,S>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
}
-template <typename T, bool S>
+template <typename T>
RBNode<T>*
-RBTree<T,S>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* right = node->right_;
node->right_ = right->left_;
if (right->left_ != NULLNODE)
@@ -840,9 +1108,9 @@ RBTree<T,S>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
return (node);
}
-template <typename T, bool S>
+template <typename T>
RBNode<T>*
-RBTree<T,S>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* left = node->left_;
node->left_ = left->right_;
if (left->right_ != NULLNODE)
@@ -865,17 +1133,17 @@ RBTree<T,S>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::dumpTree(std::ostream& os, unsigned int depth) const {
+RBTree<T>::dumpTree(std::ostream& os, unsigned int depth) const {
indent(os, depth);
os << "tree has " << node_count_ << " node(s)\n";
dumpTreeHelper(os, root_, depth);
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
+RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const
{
if (node == NULLNODE) {
@@ -900,15 +1168,13 @@ RBTree<T,S>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
dumpTreeHelper(os, node->right_, depth + 1);
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::indent(std::ostream& os, unsigned int depth) {
+RBTree<T>::indent(std::ostream& os, unsigned int depth) {
static const unsigned int INDENT_FOR_EACH_DEPTH = 5;
os << std::string(depth * INDENT_FOR_EACH_DEPTH, ' ');
}
-
-
}
}
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 0105cad..24d94a3 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -15,6 +15,8 @@
#include <gtest/gtest.h>
+#include <exceptions/exceptions.h>
+
#include <dns/name.h>
#include <dns/rrclass.h>
#include <dns/rrset.h>
@@ -26,10 +28,15 @@
#include <dns/tests/unittest_util.h>
using namespace std;
+using namespace isc;
using namespace isc::dns;
using isc::UnitTestUtil;
using namespace isc::datasrc;
+// XXX: some compilers cannot find class static constants used in
+// EXPECT_xxx macros, for which we need an explicit empty definition.
+const size_t Name::MAX_LABELS;
+
/* The initial structure of rbtree
*
* b
@@ -50,9 +57,10 @@ using namespace isc::datasrc;
namespace {
class RBTreeTest : public::testing::Test {
protected:
- RBTreeTest() : rbtree() {
- const char * domain_names[] = {"c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h",
- "o.w.y.d.e.f", "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f"};
+ RBTreeTest() : rbtree_expose_empty_node(true) {
+ const char* const domain_names[] = {
+ "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
+ "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f"};
int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
for (int i = 0; i < name_count; ++i) {
rbtree.insert(Name(domain_names[i]), &rbtnode);
@@ -65,8 +73,7 @@ protected:
}
RBTree<int> rbtree;
- typedef RBTree<int, true> ExposeRBTree;
- ExposeRBTree rbtree_expose_empty_node;
+ RBTree<int> rbtree_expose_empty_node;
RBNode<int>* rbtnode;
const RBNode<int>* crbtnode;
};
@@ -82,69 +89,34 @@ TEST_F(RBTreeTest, setGetData) {
}
TEST_F(RBTreeTest, insertNames) {
- //if don't expose empty node, even the node already exsit which is caused by node fission
- //we will return succeed
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("d.e.f"),
+ &rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
EXPECT_EQ(13, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("d.e.f"), &rbtnode));
- EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
- EXPECT_EQ(13, rbtree_expose_empty_node.getNodeCount());
-
-
//insert not exist node
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("."), &rbtnode));
EXPECT_EQ(Name("."), rbtnode->getName());
EXPECT_EQ(14, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS, rbtree_expose_empty_node.insert(
- Name("."), &rbtnode));
- EXPECT_EQ(Name("."), rbtnode->getName());
- EXPECT_EQ(14, rbtree_expose_empty_node.getNodeCount());
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
- EXPECT_EQ(ExposeRBTree::SUCCESS, rbtree_expose_empty_node.insert(
- Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree_expose_empty_node.getNodeCount());
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
-
-
// return ALREADYEXISTS, since node "example.com" already has been explicitly inserted
EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree_expose_empty_node.getNodeCount());
-
// split the node "d.e.f"
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("k.e.f"), &rbtnode));
EXPECT_EQ(Name("k"), rbtnode->getName());
EXPECT_EQ(17, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("k.e.f"), &rbtnode));
- EXPECT_EQ(Name("k"), rbtnode->getName());
- EXPECT_EQ(17, rbtree_expose_empty_node.getNodeCount());
-
-
// split the node "g.h"
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("h"), &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
EXPECT_EQ(18, rbtree.getNodeCount());
- //node fission will create node "h"
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("h"), &rbtnode));
- EXPECT_EQ(Name("h"), rbtnode->getName());
- EXPECT_EQ(18, rbtree_expose_empty_node.getNodeCount());
-
-
// add child domain
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(Name("m"), rbtnode->getName());
@@ -153,41 +125,18 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(Name("n"), rbtnode->getName());
EXPECT_EQ(20, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(Name("m"), rbtnode->getName());
- EXPECT_EQ(19, rbtree_expose_empty_node.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(Name("n"), rbtnode->getName());
- EXPECT_EQ(20, rbtree_expose_empty_node.getNodeCount());
-
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("l.a"), &rbtnode));
EXPECT_EQ(Name("l"), rbtnode->getName());
EXPECT_EQ(21, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("l.a"), &rbtnode));
- EXPECT_EQ(Name("l"), rbtnode->getName());
- EXPECT_EQ(21, rbtree_expose_empty_node.getNodeCount());
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("r.d.e.f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("s.d.e.f"), &rbtnode));
EXPECT_EQ(23, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("r.d.e.f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("s.d.e.f"), &rbtnode));
- EXPECT_EQ(23, rbtree_expose_empty_node.getNodeCount());
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("h.w.y.d.e.f"), &rbtnode));
// add more nodes one by one to cover leftRotate and rightRotate
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("nm"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("om"), &rbtnode));
@@ -198,32 +147,8 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("i"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("ae"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n"), &rbtnode));
-
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("m"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("nm"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("om"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("k"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("l"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("fe"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("ge"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("i"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("ae"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("n"), &rbtnode));
}
-
TEST_F(RBTreeTest, findName) {
// find const rbtnode
// exact match
@@ -236,15 +161,33 @@ TEST_F(RBTreeTest, findName) {
EXPECT_EQ(RBTree<int>::NOTFOUND, rbtree.find(Name("x"), &crbtnode));
EXPECT_EQ(RBTree<int>::NOTFOUND, rbtree.find(Name("m.n"), &crbtnode));
+ // if we expose empty node, we can get the empty node created during insert
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("d.e.f"), &crbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("w.y.d.e.f"), &crbtnode));
+
// partial match
EXPECT_EQ(RBTree<int>::PARTIALMATCH, rbtree.find(Name("m.b"), &crbtnode));
EXPECT_EQ(Name("b"), crbtnode->getName());
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ rbtree_expose_empty_node.find(Name("m.d.e.f"), &crbtnode));
// find rbtnode
EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find(Name("q.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(Name("q"), rbtnode->getName());
}
+TEST_F(RBTreeTest, findError) {
+ // For the version that takes a node chain, the chain must be empty.
+ RBTreeNodeChain<int> chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find<void*>(Name("a"), &crbtnode,
+ chain, NULL, NULL));
+ // trying to reuse the same chain. it should result in an exception.
+ EXPECT_THROW(rbtree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL),
+ BadValue);
+}
+
bool
testCallback(const RBNode<int>&, bool* callack_checker) {
*callack_checker = true;
@@ -272,7 +215,7 @@ TEST_F(RBTreeTest, callback) {
&subrbtnode));
subrbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
RBNode<int>* parentrbtnode;
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example"),
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example"),
&parentrbtnode));
// the chilld/parent nodes shouldn't "inherit" the callback flag.
// "rbtnode" may be invalid due to the insertion, so we need to re-find
@@ -284,22 +227,121 @@ TEST_F(RBTreeTest, callback) {
EXPECT_FALSE(parentrbtnode->isCallbackEnabled());
// check if the callback is called from find()
+ RBTreeNodeChain<int> node_path1;
bool callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("sub.callback.example"), &crbtnode,
+ rbtree.find(Name("sub.callback.example"), &crbtnode, node_path1,
testCallback, &callback_called));
EXPECT_TRUE(callback_called);
// enable callback at the parent node, but it doesn't have data so
// the callback shouldn't be called.
+ RBTreeNodeChain<int> node_path2;
parentrbtnode->enableCallback();
callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("callback.example"), &crbtnode,
+ rbtree.find(Name("callback.example"), &crbtnode, node_path2,
testCallback, &callback_called));
EXPECT_FALSE(callback_called);
}
+TEST_F(RBTreeTest, chainLevel) {
+ RBTreeNodeChain<int> chain;
+
+ // by default there should be no level in the chain.
+ EXPECT_EQ(0, chain.getLevelCount());
+
+ // insert one node to the tree and find it. there should be exactly
+ // one level in the chain.
+ RBTree<int> tree(true);
+ Name node_name(Name::ROOT_NAME());
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(1, chain.getLevelCount());
+
+ /*
+ * Now creating a possibly deepest tree with MAX_LABELS - 1 levels.
+ * it should look like:
+ * a
+ * /|
+ * (.)a
+ * |
+ * a
+ * : (MAX_LABELS - 1) "a"'s
+ *
+ * then confirm that find() for the deepest name succeeds without any
+ * disruption, and the resulting chain has the expected level.
+ * Note that "a." and the root name (".") belong to the same level.
+ * So the possible maximum level is MAX_LABELS - 1, not MAX_LABELS.
+ */
+ for (unsigned int i = 1; i < Name::MAX_LABELS; ++i) {
+ node_name = Name("a.").concatenate(node_name);
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ RBTreeNodeChain<int> found_chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, found_chain,
+ NULL, NULL));
+ EXPECT_EQ(i, found_chain.getLevelCount());
+ }
+
+ // Confirm the last inserted name has the possible maximum length with
+ // maximum label count. This confirms the rbtree and chain level cannot
+ // be larger.
+ EXPECT_EQ(Name::MAX_LABELS, node_name.getLabelCount());
+ EXPECT_THROW(node_name.concatenate(Name("a.")), TooLongName);
+}
+
+TEST_F(RBTreeTest, getAbsoluteNameError) {
+ // an empty chain isn't allowed.
+ RBTreeNodeChain<int> chain;
+ EXPECT_THROW(chain.getAbsoluteName(), BadValue);
+}
+
+/*
+ *the domain order should be:
+ * a, b, c, d.e.f, x.d.e.f, w.y.d.e.f, o.w.y.d.e.f, p.w.y.d.e.f, q.w.y.d.e.f,
+ * z.d.e.f, j.z.d.e.f, g.h, i.g.h
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \
+ * x | z
+ * | |
+ * p j
+ * / \
+ * o q
+ */
+TEST_F(RBTreeTest, nextNode) {
+ const char* const names[] = {
+ "a", "b", "c", "d.e.f", "x.d.e.f", "w.y.d.e.f", "o.w.y.d.e.f",
+ "p.w.y.d.e.f", "q.w.y.d.e.f", "z.d.e.f", "j.z.d.e.f", "g.h", "i.g.h"};
+ const int name_count = sizeof(names) / sizeof(names[0]);
+ RBTreeNodeChain<int> node_path;
+ const RBNode<int>* node = NULL;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree.find<void*>(Name(names[0]), &node, node_path, NULL,
+ NULL));
+ for (int i = 0; i < name_count; ++i) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
+ node = rbtree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+TEST_F(RBTreeTest, nextNodeError) {
+ // Empty chain for nextNode() is invalid.
+ RBTreeNodeChain<int> chain;
+ EXPECT_THROW(rbtree.nextNode(chain), BadValue);
+}
+
TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
@@ -336,5 +378,4 @@ TEST_F(RBTreeTest, swap) {
tree2.dumpTree(out);
ASSERT_EQ(str1.str(), out.str());
}
-
}
diff --git a/src/lib/dns/rrset.h b/src/lib/dns/rrset.h
index 552d09e..c17bd88 100644
--- a/src/lib/dns/rrset.h
+++ b/src/lib/dns/rrset.h
@@ -278,9 +278,6 @@ public:
/// name when possible in the context of zone dump. This is a future
/// TODO item.
///
-/* TODO: why does this have a param when not in argument list? */
- /// \param rrset A reference to a (derived class of) \c AbstractRRset object
- /// whose content is to be converted.
/// \return A string representation of the RRset.
virtual std::string toText() const = 0;
diff --git a/src/lib/log/tests/run_time_init_test.sh.in b/src/lib/log/tests/run_time_init_test.sh.in
index 1ef8a0f..be52ded 100755
--- a/src/lib/log/tests/run_time_init_test.sh.in
+++ b/src/lib/log/tests/run_time_init_test.sh.in
@@ -13,9 +13,8 @@
# OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
# PERFORMANCE OF THIS SOFTWARE.
-tempfile=`echo /tmp/run_init_test_$$`
failcount=0
-localmes=@abs_builddir@/localdef.mes
+localmes=@abs_srcdir@/localdef.mes
tempfile=@abs_builddir@/run_time_init_test_tempfile_$$
passfail() {
More information about the bind10-changes
mailing list