[svn] commit: r3983 - in /trunk: ./ src/bin/bind10/bind10.py.in src/bin/stats/tests/isc/util/ src/lib/datasrc/tests/zonetable_unittest.cc src/lib/datasrc/zonetable.cc src/lib/datasrc/zonetable.h
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Dec 23 11:10:29 UTC 2010
Author: vorner
Date: Thu Dec 23 11:10:29 2010
New Revision: 3983
Log:
Merge #440 (ZoneTable uses RBTree)
Modified:
trunk/ (props changed)
trunk/src/bin/bind10/bind10.py.in (props changed)
trunk/src/bin/stats/tests/isc/util/ (props changed)
trunk/src/lib/datasrc/tests/zonetable_unittest.cc
trunk/src/lib/datasrc/zonetable.cc
trunk/src/lib/datasrc/zonetable.h
Modified: trunk/src/lib/datasrc/tests/zonetable_unittest.cc
==============================================================================
--- trunk/src/lib/datasrc/tests/zonetable_unittest.cc (original)
+++ trunk/src/lib/datasrc/tests/zonetable_unittest.cc Thu Dec 23 11:10:29 2010
@@ -75,7 +75,7 @@
EXPECT_THROW(zone_table.addZone(ZonePtr()), isc::InvalidParameter);
}
-TEST_F(ZoneTableTest, removeZone) {
+TEST_F(ZoneTableTest, DISABLED_removeZone) {
EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone1));
EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone2));
EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone3));
Modified: trunk/src/lib/datasrc/zonetable.cc
==============================================================================
--- trunk/src/lib/datasrc/zonetable.cc (original)
+++ trunk/src/lib/datasrc/zonetable.cc Thu Dec 23 11:10:29 2010
@@ -12,14 +12,12 @@
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.
-// Note: map and utility (for 'pair') are for temporary workaround.
-// we'll soon replace them with built-in intelligent backend structure.
-#include <map>
-#include <utility>
+#include <cassert>
#include <dns/name.h>
#include <datasrc/zonetable.h>
+#include <datasrc/rbtree.h>
using namespace std;
using namespace isc::dns;
@@ -27,13 +25,77 @@
namespace isc {
namespace datasrc {
-// This is a temporary, inefficient implementation using std::map and handmade
-// iteration to realize longest match.
+/// \short Private data and implementation of ZoneTable
+struct ZoneTable::ZoneTableImpl {
+ // Type aliases to make it shorter
+ typedef RBTree<Zone> ZoneTree;
+ typedef RBNode<Zone> ZoneNode;
+ // The actual storage
+ ZoneTree zones_;
-struct ZoneTable::ZoneTableImpl {
- typedef map<Name, ZonePtr> ZoneMap;
- typedef pair<Name, ZonePtr> NameAndZone;
- ZoneMap zones;
+ /*
+ * The implementation methods are here and just wrap-called in the
+ * ZoneTable. We have variables locally (without impl_->), have
+ * type aliases, etc. And they will get inlined anyway.
+ */
+
+ // Implementation of ZoneTable::addZone
+ result::Result addZone(ZonePtr zone) {
+ // Sanity check
+ if (!zone) {
+ isc_throw(InvalidParameter,
+ "Null pointer is passed to ZoneTable::addZone()");
+ }
+
+ // Get the node where we put the zone
+ ZoneNode* node(NULL);
+ switch (zones_.insert(zone->getOrigin(), &node)) {
+ // This is OK
+ case ZoneTree::SUCCEED:
+ case ZoneTree::ALREADYEXIST:
+ break;
+ // Can Not Happen
+ default:
+ assert(0);
+ }
+ // Can Not Happen
+ assert(node);
+
+ // Is it empty? We either just created it or it might be nonterminal
+ if (node->isEmpty()) {
+ node->setData(zone);
+ return (result::SUCCESS);
+ } else { // There's something there already
+ return (result::EXIST);
+ }
+ }
+
+ // Implementation of ZoneTable::findZone
+ ZoneTable::FindResult findZone(const Name& name) const {
+ ZoneNode *node(NULL);
+ result::Result my_result;
+
+ // Translate the return codes
+ switch (zones_.find(name, &node)) {
+ case ZoneTree::EXACTMATCH:
+ my_result = result::SUCCESS;
+ break;
+ case ZoneTree::PARTIALMATCH:
+ my_result = result::PARTIALMATCH;
+ break;
+ // We have no data there, so translate the pointer to NULL as well
+ case ZoneTree::NOTFOUND:
+ return (FindResult(result::NOTFOUND, ConstZonePtr()));
+ // Can Not Happen
+ default:
+ assert(0);
+ }
+
+ // Can Not Happen (remember, NOTFOUND is handled)
+ assert(node);
+
+ return (FindResult(my_result, node->getData()));
+ }
};
ZoneTable::ZoneTable() : impl_(new ZoneTableImpl)
@@ -45,40 +107,19 @@
result::Result
ZoneTable::addZone(ZonePtr zone) {
- if (!zone) {
- isc_throw(InvalidParameter,
- "Null pointer is passed to ZoneTable::addZone()");
- }
-
- if (impl_->zones.insert(
- ZoneTableImpl::NameAndZone(zone->getOrigin(), zone)).second
- == true) {
- return (result::SUCCESS);
- } else {
- return (result::EXIST);
- }
+ return (impl_->addZone(zone));
}
result::Result
-ZoneTable::removeZone(const Name& origin) {
- return (impl_->zones.erase(origin) == 1 ? result::SUCCESS :
- result::NOTFOUND);
+ZoneTable::removeZone(const Name&) {
+ // TODO Implement
+ assert(0);
}
ZoneTable::FindResult
ZoneTable::findZone(const Name& name) const {
- // Inefficient internal loop to find a longest match.
- // This will be replaced with a single call to more intelligent backend.
- for (int i = 0; i < name.getLabelCount(); ++i) {
- Name matchname(name.split(i));
- ZoneTableImpl::ZoneMap::const_iterator found =
- impl_->zones.find(matchname);
- if (found != impl_->zones.end()) {
- return (FindResult(i == 0 ? result::SUCCESS :
- result::PARTIALMATCH, (*found).second));
- }
- }
- return (FindResult(result::NOTFOUND, ConstZonePtr()));
+ return (impl_->findZone(name));
}
+
} // end of namespace datasrc
} // end of namespace isc
Modified: trunk/src/lib/datasrc/zonetable.h
==============================================================================
--- trunk/src/lib/datasrc/zonetable.h (original)
+++ trunk/src/lib/datasrc/zonetable.h Thu Dec 23 11:10:29 2010
@@ -71,8 +71,18 @@
//@}
/// Add a \c Zone to the \c ZoneTable.
- /// See the description of <code>MemoryDataSrc::addZone()</code> for more
- /// details.
+ ///
+ /// \c Zone must not be associated with a NULL pointer; otherwise
+ /// an exception of class \c InvalidParameter will be thrown.
+ /// If internal resource allocation fails, a corresponding standard
+ /// exception will be thrown.
+ /// This method never throws an exception otherwise.
+ ///
+ /// \param zone A \c Zone object to be added.
+ /// \return \c result::SUCCESS If the zone is successfully
+ /// added to the zone table.
+ /// \return \c result::EXIST The zone table already contains
+ /// zone of the same origin.
result::Result addZone(ZonePtr zone);
/// Remove a \c Zone of the given origin name from the \c ZoneTable.
@@ -87,8 +97,23 @@
result::Result removeZone(const isc::dns::Name& origin);
/// Find a \c Zone that best matches the given name in the \c ZoneTable.
- /// See the description of <code>MemoryDataSrc::findZone()</code> for more
- /// details.
+ ///
+ /// It searches the internal storage for a \c Zone that gives the
+ /// longest match against \c name, and returns the result in the
+ /// form of a \c FindResult object as follows:
+ /// - \c code: The result code of the operation.
+ /// - \c result::SUCCESS: A zone that gives an exact match
+ /// is found
+ /// - \c result::PARTIALMATCH: A zone whose origin is a
+ /// super domain of \c name is found (but there is no exact match)
+ /// - \c result::NOTFOUND: For all other cases.
+ /// - \c zone: A <Boost> shared pointer to the found \c Zone object if one
+ /// is found; otherwise \c NULL.
+ ///
+ /// This method never throws an exception.
+ ///
+ /// \param name A domain name for which the search is performed.
+ /// \return A \c FindResult object enclosing the search result (see above).
FindResult findZone(const isc::dns::Name& name) const;
private:
More information about the bind10-changes
mailing list