MonetDB: default - More efficient searching.

[Sjoerd Mullender]

Changeset: 88be472e74f5 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=88be472e74f5
Modified Files:
        gdk/gdk.h
        gdk/gdk_cand.c
Branch: default
Log Message:

More efficient searching.


diffs (66 lines):

diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -1259,25 +1259,18 @@ BUNtoid(BAT *b, BUN p)
                return o;
        }
        const oid *exc = (oid *) b->tvheap->base;
-       BUN hi = 0;
-       if (nexc > 1024) {
-               BUN lo = 0;
-               hi = nexc - 1;
-               while (hi > lo + 1) {
-                       BUN mid = (lo + hi) / 2;
-                       if (exc[mid] == o) {
-                               hi = mid;
-                               break;
-                       }
-                       if (exc[mid] < o)
-                               lo = mid;
-                       else
-                               hi = mid;
-               }
+       if (o < exc[0])
+               return o;
+       if (o + nexc > exc[nexc - 1])
+               return o + nexc;
+       BUN lo = 0, hi = nexc - 1;
+       while (hi - lo > 1) {
+               BUN mid = (hi + lo) / 2;
+               if (exc[mid] - mid > o)
+                       hi = mid;
+               else
+                       lo = mid;
        }
-       for (; hi < nexc; hi++)
-               if (o + hi < exc[hi])
-                       break;
        return o + hi;
 }
 
diff --git a/gdk/gdk_cand.c b/gdk/gdk_cand.c
--- a/gdk/gdk_cand.c
+++ b/gdk/gdk_cand.c
@@ -647,13 +647,15 @@ canditer_idx(struct canditer *ci, BUN p)
                return o;
        if (o + ci->noids > ci->oids[ci->noids - 1])
                return o + ci->noids;
-       BUN i = 0;
-       if (ci->noids > 1024)
-               i = binsearchcand(ci->oids, ci->noids, o);
-       for (; i < ci->noids; i++)
-               if (o + i < ci->oids[i])
-                       return o + i;
-       return o + ci->noids;
+       BUN lo = 0, hi = ci->noids - 1;
+       while (hi - lo > 1) {
+               BUN mid = (hi + lo) / 2;
+               if (ci->oids[mid] - mid > o)
+                       hi = mid;
+               else
+                       lo = mid;
+       }
+       return o + hi;
 }
 
 void
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list