Changeset: c3724f77cb63 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=c3724f77cb63
Modified Files:
gdk/gdk_bat.c
gdk/gdk_search.c
Branch: default
Log Message:
Implemented binary search on reverse-ordered BATs.
diffs (149 lines):
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_search.c b/gdk/gdk_search.c
--- a/gdk/gdk_search.c
+++ b/gdk/gdk_search.c
@@ -456,23 +456,23 @@ SORTfndwhich(BAT *b, const void *v, int
BATiter bi = bat_iterator(b);
BUN diff, end;
- if (b == NULL || !b->tsorted)
+ if (b == NULL || (!b->tsorted && !b->trevsorted))
return BUN_NONE;
if (which < 0) {
end = lo;
- if (lo >= hi || atom_GE(BUNtail(bi, lo), v, b->ttype)) {
+ if (lo >= hi || (b->tsorted ? atom_GE(BUNtail(bi, lo), v,
b->ttype) : atom_LE(BUNtail(bi, lo), v, b->ttype))) {
/* shortcut: if BAT is empty or first (and
- * hence all) tail value is >= v, we're
- * done */
+ * hence all) tail value is >= v (if sorted)
+ * or <= v (if revsorted), we're done */
return lo;
}
} else if (which > 0) {
end = hi;
- if (lo >= hi || atom_LE(BUNtail(bi, hi - 1), v, b->ttype)) {
- /* shortcut: if BAT is empty or last (and
- * hence all) tail value is <= v, we're
- * done */
+ if (lo >= hi || (b->tsorted ? atom_LE(BUNtail(bi, hi - 1), v,
b->ttype) : atom_GE(BUNtail(bi, hi - 1), v, b->ttype))) {
+ /* shortcut: if BAT is empty or first (and
+ * hence all) tail value is <= v (if sorted)
+ * or >= v (if revsorted), we're done */
return hi;
}
} else {
@@ -483,31 +483,60 @@ SORTfndwhich(BAT *b, const void *v, int
}
}
- switch (ATOMstorage(b->ttype)) {
- case TYPE_bte:
- SORTfndloop(bte, simple_CMP, BUNtloc);
- break;
- case TYPE_sht:
- SORTfndloop(sht, simple_CMP, BUNtloc);
- break;
- case TYPE_int:
- SORTfndloop(int, simple_CMP, BUNtloc);
- break;
- case TYPE_lng:
- SORTfndloop(lng, simple_CMP, BUNtloc);
- break;
- case TYPE_flt:
- SORTfndloop(flt, simple_CMP, BUNtloc);
- break;
- case TYPE_dbl:
- SORTfndloop(dbl, simple_CMP, BUNtloc);
- break;
- default:
- if (b->tvarsized)
- SORTfndloop(b->ttype, atom_CMP, BUNtvar);
- else
- SORTfndloop(b->ttype, atom_CMP, BUNtloc);
- break;
+ if (b->tsorted) {
+ switch (ATOMstorage(b->ttype)) {
+ case TYPE_bte:
+ SORTfndloop(bte, simple_CMP, BUNtloc);
+ break;
+ case TYPE_sht:
+ SORTfndloop(sht, simple_CMP, BUNtloc);
+ break;
+ case TYPE_int:
+ SORTfndloop(int, simple_CMP, BUNtloc);
+ break;
+ case TYPE_lng:
+ SORTfndloop(lng, simple_CMP, BUNtloc);
+ break;
+ case TYPE_flt:
+ SORTfndloop(flt, simple_CMP, BUNtloc);
+ break;
+ case TYPE_dbl:
+ SORTfndloop(dbl, simple_CMP, BUNtloc);
+ break;
+ default:
+ if (b->tvarsized)
+ SORTfndloop(b->ttype, atom_CMP, BUNtvar);
+ else
+ SORTfndloop(b->ttype, atom_CMP, BUNtloc);
+ break;
+ }
+ } else {
+ switch (ATOMstorage(b->ttype)) {
+ case TYPE_bte:
+ SORTfndloop(bte, -simple_CMP, BUNtloc);
+ break;
+ case TYPE_sht:
+ SORTfndloop(sht, -simple_CMP, BUNtloc);
+ break;
+ case TYPE_int:
+ SORTfndloop(int, -simple_CMP, BUNtloc);
+ break;
+ case TYPE_lng:
+ SORTfndloop(lng, -simple_CMP, BUNtloc);
+ break;
+ case TYPE_flt:
+ SORTfndloop(flt, -simple_CMP, BUNtloc);
+ break;
+ case TYPE_dbl:
+ SORTfndloop(dbl, -simple_CMP, BUNtloc);
+ break;
+ default:
+ if (b->tvarsized)
+ SORTfndloop(b->ttype, -atom_CMP, BUNtvar);
+ else
+ SORTfndloop(b->ttype, -atom_CMP, BUNtloc);
+ break;
+ }
}
if (which < 0) {
_______________________________________________
Checkin-list mailing list
Checkin-list@monetdb.org
http://mail.monetdb.org/mailman/listinfo/checkin-list
