Changeset: 221d1a179287 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/221d1a179287
Modified Files:
gdk/gdk_join.c
gdk/gdk_private.h
gdk/gdk_select.c
Branch: default
Log Message:
Reuse code to find highest set bit.
diffs (167 lines):
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -1806,8 +1806,7 @@ mergejoin(BAT **r1p, BAT **r2p, BAT *l,
}
}
/* determine opportunistic scan window for l */
- for (nl = lci->ncand, lscan = 4; nl > 0; lscan++)
- nl >>= 1;
+ lscan = 4 + ilog2(lci->ncand);
} else {
/* if l not sorted, we will always use binary search
* on r */
@@ -1819,8 +1818,7 @@ mergejoin(BAT **r1p, BAT **r2p, BAT *l,
}
/* determine opportunistic scan window for r; if l is not
* sorted this is only used to find range of equal values */
- for (nl = rci->ncand, rscan = 4; nl > 0; rscan++)
- nl >>= 1;
+ rscan = 4 + ilog2(rci->ncand);
if (!equal_order) {
/* we go through r backwards */
diff --git a/gdk/gdk_private.h b/gdk/gdk_private.h
--- a/gdk/gdk_private.h
+++ b/gdk/gdk_private.h
@@ -253,6 +253,67 @@ gdk_return VIEWreset(BAT *b)
BAT *virtualize(BAT *bn)
__attribute__((__visibility__("hidden")));
+/* calculate the integer 2 logarithm (i.e. position of highest set
+ * bit) of the argument (with a slight twist: 0 gives 0, 1 gives 1,
+ * 0x8 to 0xF give 4, etc.) */
+static inline unsigned
+ilog2(BUN x)
+{
+ if (x == 0)
+ return 0;
+#if defined(__GNUC__)
+#if SIZEOF_BUN == 8
+ return (unsigned) (64 - __builtin_clzll((unsigned long long) x));
+#else
+ return (unsigned) (32 - __builtin_clz((unsigned) x));
+#endif
+#elif defined(_MSC_VER)
+ unsigned long n;
+ if (
+#if SIZEOF_BUN == 8
+ _BitScanReverse64(&n, (unsigned __int64) x)
+#else
+ _BitScanReverse(&n, (unsigned long) x)
+#endif
+ )
+ return (unsigned) n + 1;
+ else
+ return 0;
+#else
+ unsigned n = 0;
+ BUN y;
+
+ /* use a "binary search" method */
+#if SIZEOF_BUN == 8
+ if ((y = x >> 32) != 0) {
+ x = y;
+ n += 32;
+ }
+#endif
+ if ((y = x >> 16) != 0) {
+ x = y;
+ n += 16;
+ }
+ if ((y = x >> 8) != 0) {
+ x = y;
+ n += 8;
+ }
+ if ((y = x >> 4) != 0) {
+ x = y;
+ n += 4;
+ }
+ if ((y = x >> 2) != 0) {
+ x = y;
+ n += 2;
+ }
+ if ((y = x >> 1) != 0) {
+ x = y;
+ n += 1;
+ }
+ return n + (x != 0);
+#endif
+}
+
/* some macros to help print info about BATs when using ALGODEBUG */
#define ALGOBATFMT "%s#" BUNFMT "@" OIDFMT "[%s]%s%s%s%s%s%s%s%s%s"
#define ALGOBATPAR(b) \
diff --git a/gdk/gdk_select.c b/gdk/gdk_select.c
--- a/gdk/gdk_select.c
+++ b/gdk/gdk_select.c
@@ -814,69 +814,6 @@ scanselect(BAT *b, struct canditer *rest
return bn;
}
-/* calculate the integer 2 logarithm (i.e. position of highest set
- * bit) of the argument (with a slight twist: 0 gives 0, 1 gives 1,
- * 0x8 to 0xF give 4, etc.) */
-static inline unsigned
-ilog2(BUN x)
-{
-#if defined(__GNUC__)
- if (x == 0)
- return 0;
-#if SIZEOF_BUN == 8
- return (unsigned) (64 - __builtin_clzll((unsigned long long) x));
-#else
- return (unsigned) (32 - __builtin_clz((unsigned) x));
-#endif
-#elif defined(_MSC_VER)
- if (x == 0)
- return 0;
- unsigned long n;
- if (
-#if SIZEOF_BUN == 8
- _BitScanReverse64(&n, (unsigned __int64) x)
-#else
- _BitScanReverse(&n, (unsigned long) x)
-#endif
- )
- return (unsigned) n + 1;
- else
- return 0;
-#else
- unsigned n = 0;
- BUN y;
-
- /* use a "binary search" method */
-#if SIZEOF_BUN == 8
- if ((y = x >> 32) != 0) {
- x = y;
- n += 32;
- }
-#endif
- if ((y = x >> 16) != 0) {
- x = y;
- n += 16;
- }
- if ((y = x >> 8) != 0) {
- x = y;
- n += 8;
- }
- if ((y = x >> 4) != 0) {
- x = y;
- n += 4;
- }
- if ((y = x >> 2) != 0) {
- x = y;
- n += 2;
- }
- if ((y = x >> 1) != 0) {
- x = y;
- n += 1;
- }
- return n + (x != 0);
-#endif
-}
-
/* Normalize the variables li, hi, lval, hval, possibly changing anti
* in the process. This works for all (and only) numeric types.
*
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
