Changeset: d9f558b45d71 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d9f558b45d71
Added Files:
gdk/gdk_search.c
gdk/gdk_search.h
Removed Files:
gdk/gdk_search.mx
Modified Files:
gdk/Makefile.ag
gdk/gdk.h
gdk/gdk_bat.c
gdk/gdk_private.h
gdk/gdk_relop.mx
monetdb5/mal/Tests/tst270.stable.out
monetdb5/mal/Tests/tst870.stable.out
monetdb5/modules/kernel/bat5.c
monetdb5/optimizer/opt_recycler.c
monetdb5/tests/gdkTests/Tests/void.stable.out
Branch: xid
Log Message:
Merge with default branch.
diffs (truncated from 1811 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -35,8 +35,10 @@ lib_gdk = {
gdk_scanselect_defs_fix.mx \
gdk_scanselect_defs_var.mx \
gdk_scanselect.mx gdk.h gdk_batop.c \
- gdk_search.mx gdk_tm.c gdk_align.c gdk_bbp.c gdk_bbp.h \
- gdk_heap.c gdk_setop.mx gdk_utils.c gdk_utils.h gdk_atoms.c
gdk_atoms.h \
+ gdk_search.c gdk_search.h gdk_tm.c \
+ gdk_align.c gdk_bbp.c gdk_bbp.h \
+ gdk_heap.c gdk_setop.mx gdk_utils.c gdk_utils.h \
+ gdk_atoms.c gdk_atoms.h \
gdk_qsort.c gdk_qsort_impl.h gdk_ssort.c gdk_ssort_impl.h \
gdk_storage.c gdk_bat.c gdk_bat.h \
gdk_delta.c gdk_relop.mx gdk_system.c gdk_value.c \
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -1313,10 +1313,10 @@ gdk_export BUN BUNfnd(BAT *b, const void
} while (0)
#define BUNfndSTD(p,bi,v) ((p) = BUNfnd(bi.b,v))
-#define BAThtype(b) ((b)->htype == TYPE_void && (b)->hseqbase == oid_nil ?\
- TYPE_void : ATOMtype((b)->htype))
-#define BATttype(b) ((b)->ttype == TYPE_void && (b)->tseqbase == oid_nil ?\
- TYPE_void : ATOMtype((b)->ttype))
+#define BAThtype(b) ((b)->htype == TYPE_void && (b)->hseqbase != oid_nil ? \
+ TYPE_oid : (b)->htype)
+#define BATttype(b) ((b)->ttype == TYPE_void && (b)->tseqbase != oid_nil ? \
+ TYPE_oid : (b)->ttype)
#define BAThstore(b) (BAThdense(b) ? TYPE_void : (b)->htype)
#define BATtstore(b) (BATtdense(b) ? TYPE_void : (b)->ttype)
#define Hbase(b) ((b)->H->vheap->base)
diff --git a/gdk/gdk_bat.c b/gdk/gdk_bat.c
--- a/gdk/gdk_bat.c
+++ b/gdk/gdk_bat.c
@@ -1763,8 +1763,8 @@ BUNfnd(BAT *b, const void *v)
return r;
}
if (!b->H->hash) {
- if (BAThordered(b))
- return (BUN) SORTfnd(b, v);
+ if (BAThordered(b) || BAThrevordered(b))
+ return SORTfnd(b, v);
}
switch (ATOMstorage(b->htype)) {
case TYPE_bte:
@@ -1861,11 +1861,11 @@ BUNlocate(BAT *b, const void *x, const v
}
/* next, try to restrict the range using sorted columns */
- if (BATtordered(b)) {
+ if (BATtordered(b) || BATtrevordered(b)) {
p = SORTfndfirst(b, y);
q = SORTfndlast(b, y);
}
- if (BAThordered(b)) {
+ if (BAThordered(b) || BAThrevordered(b)) {
BUN mp = SORTfndfirst(BATmirror(b), x);
BUN mq = SORTfndlast(BATmirror(b), x);
diff --git a/gdk/gdk_private.h b/gdk/gdk_private.h
--- a/gdk/gdk_private.h
+++ b/gdk/gdk_private.h
@@ -101,31 +101,6 @@ oid OIDread(str buf);
oid OIDseed(oid seed);
int oidWrite(oid *a, stream *s, size_t cnt);
int OIDwrite(stream *fp);
-/* type specific binary search implementations */
-BUN SORTfnd_bte(BAT *b, const void *v);
-BUN SORTfnd_dbl(BAT *b, const void *v);
-BUN SORTfnd_flt(BAT *b, const void *v);
-BUN SORTfnd_int(BAT *b, const void *v);
-BUN SORTfnd_lng(BAT *b, const void *v);
-BUN SORTfnd_loc(BAT *b, const void *v);
-BUN SORTfnd_sht(BAT *b, const void *v);
-BUN SORTfnd_var(BAT *b, const void *v);
-BUN SORTfndfirst_bte(BAT *b, const void *v);
-BUN SORTfndfirst_dbl(BAT *b, const void *v);
-BUN SORTfndfirst_flt(BAT *b, const void *v);
-BUN SORTfndfirst_int(BAT *b, const void *v);
-BUN SORTfndfirst_lng(BAT *b, const void *v);
-BUN SORTfndfirst_loc(BAT *b, const void *v);
-BUN SORTfndfirst_sht(BAT *b, const void *v);
-BUN SORTfndfirst_var(BAT *b, const void *v);
-BUN SORTfndlast_bte(BAT *b, const void *v);
-BUN SORTfndlast_dbl(BAT *b, const void *v);
-BUN SORTfndlast_flt(BAT *b, const void *v);
-BUN SORTfndlast_int(BAT *b, const void *v);
-BUN SORTfndlast_lng(BAT *b, const void *v);
-BUN SORTfndlast_loc(BAT *b, const void *v);
-BUN SORTfndlast_sht(BAT *b, const void *v);
-BUN SORTfndlast_var(BAT *b, const void *v);
void strCleanHash(Heap *hp, int rebuild);
int strCmpNoNil(const unsigned char *l, const unsigned char *r);
int strElimDoubles(Heap *h);
@@ -175,8 +150,8 @@ extern MT_Lock MT_system_lock;
#define SORTloop_TYPE(b, p, q, tl, th, TYPE) \
if (!BATtordered(b)) \
GDKerror("SORTloop_" #TYPE ": BAT not sorted.\n"); \
- else for (p = simple_EQ(tl, &TYPE##_nil, TYPE) ? BUNfirst(b) :
SORTfndfirst_##TYPE(b, tl), \
- q = simple_EQ(th, &TYPE##_nil, TYPE) ? BUNfirst(b) :
SORTfndlast_##TYPE(b, th); \
+ else for (p = simple_EQ(tl, &TYPE##_nil, TYPE) ? BUNfirst(b) :
SORTfndfirst(b, tl), \
+ q = simple_EQ(th, &TYPE##_nil, TYPE) ? BUNfirst(b) :
SORTfndlast(b, th); \
p < q; \
p++)
@@ -192,36 +167,11 @@ extern MT_Lock MT_system_lock;
#define SORTloop_loc(b,p,q,tl,th) \
if (!BATtordered(b)) \
GDKerror("SORTloop_loc: BAT not sorted.\n"); \
- else for (p = atom_EQ(tl, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndfirst_loc(b, tl), \
- q = atom_EQ(th, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndlast_loc(b, th); \
+ else for (p = atom_EQ(tl, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndfirst(b, tl), \
+ q = atom_EQ(th, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndlast(b, th); \
p < q; \
p++)
-#define SORTloop_var(b,p,q,tl,th) \
- if (!BATtordered(b)) \
- GDKerror("SORTloop_var: BAT not sorted.\n"); \
- else for (p = atom_EQ(tl, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndfirst_var(b, tl), \
- q = atom_EQ(th, ATOMnilptr((b)->ttype), (b)->ttype) ?
BUNfirst(b) : SORTfndlast_var(b, th); \
- p < q; \
- p++)
+#define SORTloop_var(b,p,q,tl,th) SORTloop_loc(b,p,q,tl,th)
-/* OIDDEPEND */
-#if SIZEOF_OID == SIZEOF_INT
-#define SORTfnd_oid(b,v) SORTfnd_int(b,v)
-#define SORTfndfirst_oid(b,v) SORTfndfirst_int(b,v)
-#define SORTfndlast_oid(b,v) SORTfndlast_int(b,v)
-#else
-#define SORTfnd_oid(b,v) SORTfnd_lng(b,v)
-#define SORTfndfirst_oid(b,v) SORTfndfirst_lng(b,v)
-#define SORTfndlast_oid(b,v) SORTfndlast_lng(b,v)
-#endif
-#if SIZEOF_WRD == SIZEOF_INT
-#define SORTfnd_wrd(b,v) SORTfnd_int(b,v)
-#define SORTfndfirst_wrd(b,v) SORTfndfirst_int(b,v)
-#define SORTfndlast_wrd(b,v) SORTfndlast_int(b,v)
-#else
-#define SORTfnd_wrd(b,v) SORTfnd_lng(b,v)
-#define SORTfndfirst_wrd(b,v) SORTfndfirst_lng(b,v)
-#define SORTfndlast_wrd(b,v) SORTfndlast_lng(b,v)
-#endif
#define SORTloop_bit(b,p,q,tl,th) SORTloop_bte(b,p,q,tl,th)
diff --git a/gdk/gdk_relop.mx b/gdk/gdk_relop.mx
--- a/gdk/gdk_relop.mx
+++ b/gdk/gdk_relop.mx
@@ -237,7 +237,7 @@ All Rights Reserved.
/* use binary search after failed scan
or if scanning is impossible (l not sorted) */
if (r_scan < 0 || r_start < r_last) {
/* if merge not ended (or if no
merge at all) */
- r_start = (BUN)
SORTfndfirst_@4(rr, v1);
+ r_start = SORTfndfirst(rr, v1);
}
if (r_start < r_last) {
v2 = BUNh@3(ri, r_start);
@@ -2032,7 +2032,7 @@ BATnlthetajoin(BAT *l, BAT *r, int op, B
BATloop(l, lp, lq) {
ptr v = BUNh@1(li, lp);
- if (!@3_EQ(v, nil, @2) && SORTfnd_@2(r, v) != BUN_NONE)
{
+ if (!@3_EQ(v, nil, @2) && SORTfnd(r, v) != BUN_NONE) {
bunfastins(bn, v, BUNtail(li, lp));
}
}
@@ -3131,7 +3131,7 @@ BATmultijoin(int argc, BAT *argv[], RowF
#define STDcmp(v1,v2) (*cmp)(v1,v2)
if (ATOMstorage(lead_col->b->htype) == ATOMstorage(TYPE_oid)) {
- @:multijoin(hloc,OID,_oid,_oid)@
+ @:multijoin(hloc,OID,_oid)@
} else {
int (*cmp) (const void *, const void *) =
BATatoms[lead_col->b->htype].atomCmp;
@@ -3258,7 +3258,7 @@ BATmultijoin(int argc, BAT *argv[], RowF
BUN last = BUNlast(b);
if (n->binsearch) {
- n->cur = (BUN)
SORTfndfirst@4(BATmirror(b), h);
+ n->cur = SORTfndfirst(BATmirror(b), h);
if (n->cur >= last)
break; /* NOT FOUND */
} else {
diff --git a/gdk/gdk_search.mx b/gdk/gdk_search.c
rename from gdk/gdk_search.mx
rename to gdk/gdk_search.c
--- a/gdk/gdk_search.mx
+++ b/gdk/gdk_search.c
@@ -1,25 +1,26 @@
-@/
-The contents of this file are subject to the MonetDB Public License
-Version 1.1 (the "License"); you may not use this file except in
-compliance with the License. You may obtain a copy of the License at
-http://www.monetdb.org/Legal/MonetDBLicense
+/*
+ * The contents of this file are subject to the MonetDB Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.monetdb.org/Legal/MonetDBLicense
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
+ * License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * The Original Code is the MonetDB Database System.
+ *
+ * The Initial Developer of the Original Code is CWI.
+ * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
+ * Copyright August 2008-2012 MonetDB B.V.
+ * All Rights Reserved.
+ */
-Software distributed under the License is distributed on an "AS IS"
-basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
-License for the specific language governing rights and limitations
-under the License.
-
-The Original Code is the MonetDB Database System.
-
-The Initial Developer of the Original Code is CWI.
-Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
-Copyright August 2008-2012 MonetDB B.V.
-All Rights Reserved.
-@
-
-@f gdk_search
-
-@c
+/*
+ * @f gdk_search
+ *
+ */
/*
* @a M. L. Kersten, P. Boncz, N. Nes
*
@@ -62,219 +63,6 @@ All Rights Reserved.
*
* @+ Interface Declarations
*/
-@h
-#ifndef _GDK_SEARCH_H_
-#define _GDK_SEARCH_H_
-/*
- * @+ Hash indexing
- *
- * This is a highly efficient implementation of simple bucket-chained
- * hashing.
- *
- * In the past, we used integer modulo for hashing, with bucket chains
- * of mean size 4. This was shown to be inferior to direct hashing
- * with integer anding. The new implementation reflects this.
- */
-gdk_export void HASHremove(BAT *b);
-gdk_export void HASHdestroy(BAT *b);
-gdk_export BUN HASHprobe(Hash *h, const void *v);
-gdk_export BUN HASHlist(Hash *h, BUN i);
-
-#define mix_sht(X) (((X)>>7)^(X))
-#define mix_int(X) (((X)>>7)^((X)>>13)^((X)>>21)^(X))
-#define hash_loc(H,V) hash_any(H,V)
-#define hash_var(H,V) hash_any(H,V)
-#define hash_any(H,V) (ATOMhash((H)->type, (V)) & (H)->mask)
-#define heap_hash_any(hp,H,V) ((hp) && (hp)->hashash ? ((BUN *) (V))[-1] &
(H)->mask : hash_any(H,V))
-#define hash_bte(H,V) ((BUN) (*(const unsigned char*) (V)) & (H)->mask)
-#define hash_sht(H,V) ((BUN) mix_sht(*((const unsigned short*) (V))) &
(H)->mask)
-#define hash_int(H,V) ((BUN) mix_int(*((const unsigned int*) (V))) &
(H)->mask)
-/* XXX return size_t-sized value for 8-byte oid? */
-#define hash_lng(H,V) ((BUN) mix_int((unsigned int) (*(const lng *)(V)
^ (*(lng *)(V) >> 32))) & (H)->mask)
-#if SIZEOF_OID == SIZEOF_INT
-#define hash_oid(H,V) ((BUN) mix_int((unsigned int) *((const oid*)
(V))) & (H)->mask)
-#else
-#define hash_oid(H,V) ((BUN) mix_int((unsigned int) (*(const oid *)(V)
^ (*(const oid *)(V) >> 32))) & (H)->mask)
-#endif
-#if SIZEOF_WRD == SIZEOF_INT
-#define hash_wrd(H,V) ((BUN) mix_int((unsigned int) *((const wrd*)
(V))) & (H)->mask)
-#else
-#define hash_wrd(H,V) ((BUN) mix_int((unsigned int) (*(const wrd *)(V)
^ (*(const wrd *)(V) >> 32))) & (H)->mask)
-#endif
-
-#define hash_flt(H,V) hash_int(H,V)
-#define hash_dbl(H,V) hash_lng(H,V)
-
-#define HASHfnd_str(x,y,z) \
- do { \
- BUN _i; \
- (x) = BUN_NONE; \
- if ((y).b->H->hash || BAThash((y).b, 0) || \
- GDKfatal("HASHfnd_str: hash build failed on %s.\n", \
- BATgetId((y).b))) \
- HASHloop_str((y), (y).b->H->hash, _i, (z)) { \
- (x) = _i; \
- break; \
- } \
- } while (0)
-#define HASHfnd_str_hv(x,y,z) \
_______________________________________________
Checkin-list mailing list
Checkin-list@monetdb.org
http://mail.monetdb.org/mailman/listinfo/checkin-list
