Use binary search to check for string enumerations

5 files changed, 74 insertions, 19 deletions

diff --git a/libxsde/xsde/cxx/parser/validating/string-common.cxx b/libxsde/xsde/cxx/parser/validating/string-common.cxx
index e226766..328f2ce 100644
--- a/libxsde/xsde/cxx/parser/validating/string-common.cxx
+++ b/libxsde/xsde/cxx/parser/validating/string-common.cxx
@@ -3,7 +3,7 @@
 // copyright : Copyright (c) 2005-2010 Code Synthesis Tools CC
 // license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
 
-#include <string.h> // strcmp
+#include <xsde/cxx/string-search.hxx>
 #include <xsde/cxx/parser/validating/string-common.hxx>
 
 namespace xsde
@@ -40,13 +40,7 @@ namespace xsde
 
           if (f.enum_count_ != 0)
           {
-            size_t i = 0;
-
-            for (; i < f.enum_count_; ++i)
-            {
-              if (strcmp (s, f.enum_[i]) == 0)
-                break;
-            }
+            size_t i = search (f.enum_, f.enum_count_, s);
 
             if (i == f.enum_count_)
             {
diff --git a/libxsde/xsde/cxx/serializer/validating/string-common.cxx b/libxsde/xsde/cxx/serializer/validating/string-common.cxx
index f7d49b6..5dab6c9 100644
--- a/libxsde/xsde/cxx/serializer/validating/string-common.cxx
+++ b/libxsde/xsde/cxx/serializer/validating/string-common.cxx
@@ -3,7 +3,8 @@
 // copyright : Copyright (c) 2005-2010 Code Synthesis Tools CC
 // license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
 
-#include <string.h> // strlen, strcmp
+#include <string.h> // strlen
+#include <xsde/cxx/string-search.hxx>
 #include <xsde/cxx/serializer/validating/string-common.hxx>
 
 namespace xsde
@@ -56,15 +57,7 @@ namespace xsde
 
           if (f.enum_count_ != 0)
           {
-            size_t i = 0;
-
-            for (; i < f.enum_count_; ++i)
-            {
-              if (strcmp (s, f.enum_[i]) == 0)
-                break;
-            }
-
-            if (i == f.enum_count_)
+            if (search (f.enum_, f.enum_count_, s) == f.enum_count_)
             {
               ctx.schema_error (schema_error::value_not_in_enumeration);
               return false;
diff --git a/libxsde/xsde/cxx/string-search.cxx b/libxsde/xsde/cxx/string-search.cxx
new file mode 100644
index 0000000..10da5f0
--- /dev/null
+++ b/libxsde/xsde/cxx/string-search.cxx
@@ -0,0 +1,41 @@
+// file      : xsde/cxx/string-search.cxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2005-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#include <string.h> // strcmp
+#include <xsde/cxx/string-search.hxx>
+
+namespace xsde
+{
+  namespace cxx
+  {
+    size_t
+    search (const char* const* array, size_t size, const char* s)
+    {
+      if (size == 0)
+        return 0;
+
+      int r (1);
+      size_t m;
+      size_t l = 0;
+      size_t h = size - 1;
+
+      while (l <= h)
+      {
+        m = l + (h - l) / 2;
+        r = strcmp (array[m], s);
+
+        if (r == 0)
+          break;
+
+        if (r < 0)
+          l = m + 1;
+        else
+          h = m - 1;
+      }
+
+      return r == 0 ? m : size;
+    }
+  }
+}
diff --git a/libxsde/xsde/cxx/string-search.hxx b/libxsde/xsde/cxx/string-search.hxx
new file mode 100644
index 0000000..3319c4c
--- /dev/null
+++ b/libxsde/xsde/cxx/string-search.hxx
@@ -0,0 +1,23 @@
+// file      : xsde/cxx/string-search.hxx
+// author    : Boris Kolpackov <boris@codesynthesis.com>
+// copyright : Copyright (c) 2005-2010 Code Synthesis Tools CC
+// license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
+
+#ifndef XSDE_CXX_STRING_SEARCH_HXX
+#define XSDE_CXX_STRING_SEARCH_HXX
+
+#include <stddef.h> // size_t
+
+namespace xsde
+{
+  namespace cxx
+  {
+    // Binary search in a sorted string array. Return size if no
+    // element found.
+    //
+    size_t
+    search (const char* const* array, size_t size, const char* s);
+  }
+}
+
+#endif // XSDE_CXX_STRING_SEARCH_HXX
diff --git a/libxsde/xsde/makefile b/libxsde/xsde/makefile
index fc1355d..f313347 100644
--- a/libxsde/xsde/makefile
+++ b/libxsde/xsde/makefile
@@ -8,7 +8,11 @@ include $(dir $(lastword $(MAKEFILE_LIST)))../../build/bootstrap.make
 c_tun := c/expat/xmlparse.c c/expat/xmlrole.c c/expat/xmltok.c
 c_tun += c/genx/genx.c c/genx/char-props.c
 
-cxx_tun := cxx/string.cxx cxx/ro-string.cxx cxx/stack.cxx
+cxx_tun :=            \
+cxx/string.cxx        \
+cxx/string-search.cxx \
+cxx/ro-string.cxx     \
+cxx/stack.cxx
 
 ifeq ($(xsde_encoding),iso8859-1)
 cxx_tun += cxx/iso8859-1.cxx