BIND 10 trac2281, updated. 8e33f9e96aa79b1f99828c063cab84328ce3f248 [2281] Use map::lower_bound() to speed up partial match searches
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Feb 12 05:35:52 UTC 2013
The branch, trac2281 has been updated
via 8e33f9e96aa79b1f99828c063cab84328ce3f248 (commit)
via d404649f95abf23268f91c31b30d52b06e5a3df3 (commit)
via cfd00e940391d98c71f3cb026558d66f291a59e0 (commit)
via d7f14ea88e8cc0f3e7f08b4ee6c4647ff2908279 (commit)
from 6a06b311fb9efe408fa6bf6dc2fe37a5ffcf2154 (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 8e33f9e96aa79b1f99828c063cab84328ce3f248
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Feb 12 10:53:15 2013 +0530
[2281] Use map::lower_bound() to speed up partial match searches
... by using the reverse of the name as the key.
commit d404649f95abf23268f91c31b30d52b06e5a3df3
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Feb 12 10:03:48 2013 +0530
[2281] Pass a null config to ZoneTableSegment::create() for now
commit cfd00e940391d98c71f3cb026558d66f291a59e0
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Feb 12 10:00:21 2013 +0530
[2281] Add documentation for the static datasource shared object's public symbols
commit d7f14ea88e8cc0f3e7f08b4ee6c4647ff2908279
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Feb 12 09:49:15 2013 +0530
[2281] Rename factory_link.h to static_datasrc.h
This is because the config argument will have to be documented.
-----------------------------------------------------------------------
Summary of changes:
src/bin/auth/tests/query_unittest.cc | 46 ++++++++++++--------
src/lib/datasrc/Makefile.am | 1 +
.../datasrc/{factory_link.h => static_datasrc.h} | 17 ++++++--
src/lib/datasrc/static_datasrc_link.cc | 8 +++-
4 files changed, 50 insertions(+), 22 deletions(-)
rename src/lib/datasrc/{factory_link.h => static_datasrc.h} (64%)
-----------------------------------------------------------------------
diff --git a/src/bin/auth/tests/query_unittest.cc b/src/bin/auth/tests/query_unittest.cc
index 0c15ebd..3309d6c 100644
--- a/src/bin/auth/tests/query_unittest.cc
+++ b/src/bin/auth/tests/query_unittest.cc
@@ -829,20 +829,33 @@ createDataSrcClientList(DataSrcType type, DataSourceClient& client) {
class MockClient : public DataSourceClient {
public:
virtual FindResult findZone(const isc::dns::Name& origin) const {
- // First, check if an exact match is available. If it is, return
- // it.
+ const Name r_origin(origin.reverse());
std::map<Name, ZoneFinderPtr>::const_iterator it =
- zone_finders_.find(origin);
+ zone_finders_.lower_bound(r_origin);
+
if (it != zone_finders_.end()) {
- return (FindResult(result::SUCCESS, it->second));
+ const NameComparisonResult result =
+ origin.compare((it->first).reverse());
+ if (result.getRelation() == NameComparisonResult::EQUAL) {
+ return (FindResult(result::SUCCESS, it->second));
+ } else if (result.getRelation() == NameComparisonResult::SUBDOMAIN) {
+ return (FindResult(result::PARTIALMATCH, it->second));
+ }
}
- // Do a slow linear search for a partial match now.
- for (it = zone_finders_.begin(); it != zone_finders_.end(); ++it) {
- const NameComparisonResult result = origin.compare(it->first);
- if (result.getRelation() == NameComparisonResult::SUBDOMAIN) {
- return (FindResult(result::PARTIALMATCH, it->second));
- }
+ // If it is at the beginning of the map, then the name was not
+ // found (we have already handled the element the iterator
+ // points to).
+ if (it == zone_finders_.begin()) {
+ return (FindResult(result::NOTFOUND, ZoneFinderPtr()));
+ }
+
+ // Check if the previous element is a partial match.
+ --it;
+ const NameComparisonResult result =
+ origin.compare((it->first).reverse());
+ if (result.getRelation() == NameComparisonResult::SUBDOMAIN) {
+ return (FindResult(result::PARTIALMATCH, it->second));
}
return (FindResult(result::NOTFOUND, ZoneFinderPtr()));
@@ -860,19 +873,18 @@ public:
}
result::Result addZone(ZoneFinderPtr finder) {
- zone_finders_[finder->getOrigin()] = finder;
+ // Use the reverse of the name as the key, so we can quickly
+ // find partial matches in the map.
+ zone_finders_[finder->getOrigin().reverse()] = finder;
return (result::SUCCESS);
}
private:
-
// Note that because we no longer have the old RBTree, and the new
// in-memory DomainTree is not useful as it returns const nodes, we
- // use a std::map instead. This is slightly slower when no exact
- // match occurs as far as these unittests are concerned, but they
- // are tests anyway and there aren't many zones in the map (2-3 at
- // most), so we can ignore this slight inefficiency. It may even be
- // faster due to the lack of overhead.
+ // use a std::map instead. In this map, the key is a name stored in
+ // reverse order of labels to aid in finding partial matches
+ // quickly.
std::map<Name, ZoneFinderPtr> zone_finders_;
};
diff --git a/src/lib/datasrc/Makefile.am b/src/lib/datasrc/Makefile.am
index 8a7c009..be79557 100644
--- a/src/lib/datasrc/Makefile.am
+++ b/src/lib/datasrc/Makefile.am
@@ -52,6 +52,7 @@ sqlite3_ds_la_LIBADD += libb10-datasrc.la
sqlite3_ds_la_LIBADD += $(SQLITE_LIBS)
static_ds_la_SOURCES = static_datasrc_link.cc
+static_ds_la_SOURCES += static_datasrc.h
static_ds_la_LDFLAGS = -module -avoid-version
static_ds_la_LIBADD = $(top_builddir)/src/lib/exceptions/libb10-exceptions.la
static_ds_la_LIBADD += libb10-datasrc.la
diff --git a/src/lib/datasrc/factory_link.h b/src/lib/datasrc/factory_link.h
deleted file mode 100644
index de670fc..0000000
--- a/src/lib/datasrc/factory_link.h
+++ /dev/null
@@ -1,39 +0,0 @@
-// Copyright (C) 2013 Internet Systems Consortium, Inc. ("ISC")
-//
-// Permission to use, copy, modify, and/or distribute this software for any
-// purpose with or without fee is hereby granted, provided that the above
-// copyright notice and this permission notice appear in all copies.
-//
-// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
-// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
-// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
-// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
-// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
-// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
-// PERFORMANCE OF THIS SOFTWARE.
-
-
-#ifndef DATASRC_FACTORY_LINK_H
-#define DATASRC_FACTORY_LINK_H
-
-#include <datasrc/database.h>
-#include <cc/data.h>
-
-#include <string>
-
-namespace isc {
-namespace datasrc {
-
-extern "C" DataSourceClient* createInstance(isc::data::ConstElementPtr config,
- std::string& error);
-
-extern "C" void destroyInstance(DataSourceClient* instance);
-
-}
-}
-
-#endif // DATASRC_FACTORY_LINK_H
-
-// Local Variables:
-// mode: c++
-// End:
diff --git a/src/lib/datasrc/static_datasrc.h b/src/lib/datasrc/static_datasrc.h
new file mode 100644
index 0000000..d5d8875
--- /dev/null
+++ b/src/lib/datasrc/static_datasrc.h
@@ -0,0 +1,50 @@
+// Copyright (C) 2013 Internet Systems Consortium, Inc. ("ISC")
+//
+// Permission to use, copy, modify, and/or distribute this software for any
+// purpose with or without fee is hereby granted, provided that the above
+// copyright notice and this permission notice appear in all copies.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
+// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
+// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
+// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+// PERFORMANCE OF THIS SOFTWARE.
+
+
+#ifndef DATASRC_STATIC_H
+#define DATASRC_STATIC_H
+
+#include <datasrc/database.h>
+#include <cc/data.h>
+
+#include <string>
+
+namespace isc {
+namespace datasrc {
+
+/// \brief Creates an instance of the static datasource client
+///
+/// Currently the configuration passed here must be a StringElement,
+/// containing the path to a zone file for the BIND./CH zone.
+///
+/// \param config The configuration for the datasource instance (see above)
+/// \param error This string will be set to an error message if an error occurs
+/// during initialization
+/// \return An instance of the static datasource client, or NULL if there was
+/// an error
+extern "C" DataSourceClient* createInstance(isc::data::ConstElementPtr config,
+ std::string& error);
+
+/// \brief Destroy the instance created by createInstance()
+extern "C" void destroyInstance(DataSourceClient* instance);
+
+}
+}
+
+#endif // DATASRC_STATIC_H
+
+// Local Variables:
+// mode: c++
+// End:
diff --git a/src/lib/datasrc/static_datasrc_link.cc b/src/lib/datasrc/static_datasrc_link.cc
index 82eacaa..1b767a4 100644
--- a/src/lib/datasrc/static_datasrc_link.cc
+++ b/src/lib/datasrc/static_datasrc_link.cc
@@ -13,7 +13,7 @@
// PERFORMANCE OF THIS SOFTWARE.
#include "client.h"
-#include "factory_link.h"
+#include "static_datasrc.h"
#include <datasrc/memory/memory_client.h>
#include <datasrc/memory/zone_table_segment.h>
@@ -34,8 +34,12 @@ namespace datasrc {
DataSourceClient*
createInstance(ConstElementPtr config, string& error) {
try {
+ // FIXME: Fix the config that should be passed to
+ // ZoneTableSegment::create() when it actually uses the config
+ // to do something.
shared_ptr<memory::ZoneTableSegment> ztable_segment(
- memory::ZoneTableSegment::create(*config, RRClass::CH()));
+ memory::ZoneTableSegment::create(isc::data::NullElement(),
+ RRClass::CH()));
// Create the data source
auto_ptr<memory::InMemoryClient> client
(new memory::InMemoryClient(ztable_segment, RRClass::CH()));
More information about the bind10-changes
mailing list