Changeset: ba7fe8cd0d72 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=ba7fe8cd0d72
Modified Files:
gdk/gdk.h
gdk/gdk_cand.c
Branch: candidate-exceptions
Log Message:
Use linear scan.
The weird binary search didn't work so great.
diffs (60 lines):
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -1254,26 +1254,10 @@ BUNtoid(BAT *b, BUN p)
return o;
}
const oid *exc = (oid *) b->tvheap->base;
- if (o < exc[0]) {
- /* before first exception */
- return o;
- }
- BUN hi = nexc - 1;
- if (o + hi >= exc[hi]) {
- /* after last exception */
- return o + nexc;
- }
- BUN lo = 0;
- /* perform binary search on exception list
- * loop invariant: o + lo <= exc[lo] && o + hi > exc[hi] */
- while (lo + 1 < hi) {
- BUN mid = (lo + hi) / 2;
- if (o + mid <= exc[mid])
- lo = mid;
- else
- hi = mid;
- }
- return o + hi;
+ for (BUN i = 0; i < nexc; i++)
+ if (o + i < exc[i])
+ return o + i;
+ return o + nexc;
}
static inline BATiter
diff --git a/gdk/gdk_cand.c b/gdk/gdk_cand.c
--- a/gdk/gdk_cand.c
+++ b/gdk/gdk_cand.c
@@ -667,18 +667,10 @@ canditer_idx(struct canditer *ci, BUN p)
return o;
if (o + ci->noids > ci->oids[ci->noids - 1])
return o + ci->noids;
- /* perform binary search on exception list
- * loop invariant:
- * o + lo <= ci->oids[lo] && o + hi > ci->oids[hi] */
- BUN lo = 0, hi = ci->noids - 1;
- while (lo + 1 < hi) {
- BUN mid = (lo + hi) / 2;
- if (o + mid <= ci->oids[mid])
- lo = mid;
- else
- hi = mid;
- }
- return o + hi;
+ for (BUN i = 0; i < ci->noids; i++)
+ if (o + i < ci->oids[i])
+ return o + i;
+ return o + ci->noids;
}
void
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
