Changeset: ba08ddec8ae9 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=ba08ddec8ae9
Modified Files:
monetdb5/modules/mal/Tests/pqueue2.mal
monetdb5/modules/mal/pqueue.c
monetdb5/modules/mal/pqueue.h
monetdb5/modules/mal/pqueue.mal
Branch: default
Log Message:
Another round of the new pqueue code.
Ready for detailed assessment of correctness in all corner cases.
diffs (truncated from 632 to 300 lines):
diff --git a/monetdb5/modules/mal/Tests/pqueue2.mal
b/monetdb5/modules/mal/Tests/pqueue2.mal
--- a/monetdb5/modules/mal/Tests/pqueue2.mal
+++ b/monetdb5/modules/mal/Tests/pqueue2.mal
@@ -36,23 +36,23 @@ bat.append(c,"stefan");
io.print(c);
# topn of b, new interface should return void,oid(position)
-bp:= pqueue.topn_min(b,0:wrd,false);
+bp:= pqueue.topn_min(b,0:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,1:wrd,false);
+bp:= pqueue.topn_min(b,1:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,2:wrd,false);
+bp:= pqueue.topn_min(b,2:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,3:wrd,false);
+bp:= pqueue.topn_min(b,3:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,4:wrd,false);
+bp:= pqueue.topn_min(b,4:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,5:wrd,false);
+bp:= pqueue.topn_min(b,5:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,6:wrd,false);
+bp:= pqueue.topn_min(b,6:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,7:wrd,false);
+bp:= pqueue.topn_min(b,7:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,8:wrd,false);
+bp:= pqueue.topn_min(b,8:wrd);
io.print(bp);
# utopn only count the unique values - topn of b,
@@ -60,7 +60,8 @@ io.print(bp);
# get the same group id.
#
# returns both void,pos, void,gid
-(bp,bg):= pqueue.utopn_min(b,0:wrd,false);
+io.print("Start of compound");
+(bp,bg):= pqueue.topn_min(b,0:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
@@ -68,70 +69,70 @@ io.print(ap);
# (sub) topn input: aligned bg group id, ap values bat
# output: void,pos
# returns the topn of the combination gid,value
-bp:= pqueue.topn_min(bg,ap,0:wrd,false);
+bp:= pqueue.topn_min(bg,ap,0:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,1:wrd,false);
+(bp,bg):= pqueue.topn_min(b,1:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,1:wrd,false);
+bp:= pqueue.topn_min(bg,ap,1:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,2:wrd,false);
+(bp,bg):= pqueue.topn_min(b,2:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,2:wrd,false);
+bp:= pqueue.topn_min(bg,ap,2:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,3:wrd,false);
+(bp,bg):= pqueue.topn_min(b,3:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,3:wrd,false);
+bp:= pqueue.topn_min(bg,ap,3:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,4:wrd,false);
+(bp,bg):= pqueue.topn_min(b,4:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,4:wrd,false);
+bp:= pqueue.topn_min(bg,ap,4:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,5:wrd,false);
+(bp,bg):= pqueue.topn_min(b,5:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,5:wrd,false);
+bp:= pqueue.topn_min(bg,ap,5:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,6:wrd,false);
+(bp,bg):= pqueue.topn_min(b,6:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,6:wrd,false);
+bp:= pqueue.topn_min(bg,ap,6:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,7:wrd,false);
+(bp,bg):= pqueue.topn_min(b,7:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,7:wrd,false);
+bp:= pqueue.topn_min(bg,ap,7:wrd);
io.print(bp);
-(bp,bg):= pqueue.utopn_min(b,8:wrd,false);
+(bp,bg):= pqueue.topn_min(b,8:wrd);
io.print(bp);
io.print(bg);
ap := algebra.leftfetchjoin(bp, a);
io.print(ap);
-bp:= pqueue.topn_min(bg,ap,8:wrd,false);
+bp:= pqueue.topn_min(bg,ap,8:wrd);
io.print(bp);
diff --git a/monetdb5/modules/mal/pqueue.c b/monetdb5/modules/mal/pqueue.c
--- a/monetdb5/modules/mal/pqueue.c
+++ b/monetdb5/modules/mal/pqueue.c
@@ -1414,25 +1414,23 @@ PQtopreplace_anymax(Client cntxt, MalBlk
for(o = 0; o < lim; o++){\
v = val[o];\
oo = o;\
+ if( top == size && !((TYPE) v OPER (TYPE) val[idx[top-1]]) )\
+ continue;\
for (i= 0; i<top; i++)\
if ( (TYPE) v OPER (TYPE) val[idx[i]]) {\
v= val[idx[i]];\
tmp = idx[i];\
idx[i]= oo;\
oo = tmp;\
- } else \
- if (elimdup && (TYPE) val[o] == (TYPE) val[idx[i]])\
- goto skipit##TYPE##LAB;\
+ } \
if( top < size)\
idx[top++] = oo;\
- skipit##TYPE##LAB:;\
}\
}
str PQtopn_minmax(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
int tpe, *ret;
- int elimdup;
BAT *b,*bn;
BUN i, size,top = 0;
oid *idx, lim, o, oo, tmp;
@@ -1442,7 +1440,6 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
ret = (int*) getArgReference(stk, pci, 0);
tpe = ATOMstorage(getColumnType(getArgType(mb, pci, 1)));
size = (BUN) *(wrd*) getArgReference(stk,pci,2);
- elimdup = *(bit*) getArgReference(stk,pci,3);
max = strstr(getFunctionId(pci),"max") != 0;
b = BATdescriptor(*(bat *) getArgReference(stk, pci, 1));
@@ -1488,12 +1485,9 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
tmp = idx[i];
idx[i]= oo;
oo = tmp;
- } else
- if (elimdup && k == 0)
- goto skipitdefaultGTR;
+ }
if( top < size)
idx[top++] = oo;
- skipitdefaultGTR:;
}
}
}
@@ -1518,12 +1512,9 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
tmp = idx[i];
idx[i]= oo;
oo = tmp;
- } else
- if (elimdup && k == 0)
- goto skipitdefault;
+ }
if( top < size)
idx[top++] = oo;
- skipitdefault:;
}
}
}
@@ -1537,99 +1528,291 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
return MAL_SUCCEED;
}
+/* some new code for headless */
+#define QTOPN_shuffle2(TYPE,OPER)\
+{ TYPE *val = (TYPE *) Tloc(b,BUNfirst(b));\
+ uniq = 0;\
+ for(o = 0; o < lim; o++){\
+ if(uniq >= size && !((TYPE) val[o] OPER##= (TYPE)
val[idx[top-1]]) )\
+ continue;\
+ idx[top] = gdx[top] = o;\
+ uniq++;\
+ for (i= top; i>0; i--){\
+ if( (TYPE) val[idx[i]] OPER (TYPE) val[idx[i-1]]){\
+ tmp= idx[i]; idx[i] = idx[i-1]; idx[i-1] = tmp;\
+ tmp= gdx[i]; gdx[i] = gdx[i-1]; gdx[i-1] = tmp;\
+ } else\
+ if( (TYPE) val[idx[i]] == (TYPE) val[idx[i-1]]){\
+ uniq--; gdx[i] = gdx[i-1];\
+ break;\
+ } else break;\
+ }\
+ if( uniq <= size) top++;\
+ }\
+}
+
str PQtopn2_minmax(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
+ int tpe, *ret, *ret1;
+ BAT *b,*bpiv, *bgid;
+ BUN i, size, top = 0, uniq;
+ oid *idx, *gdx, lim, o, tmp;
+ int max = 0;
+
+ (void) cntxt;
+ ret = (int*) getArgReference(stk, pci, 0);
+ ret1 = (int*) getArgReference(stk, pci, 1);
+ tpe = ATOMstorage(getColumnType(getArgType(mb, pci, 2)));
+ size = (BUN) *(wrd*) getArgReference(stk,pci,3);
+ max = strstr(getFunctionId(pci),"max") != 0;
+
+ b = BATdescriptor(*(bat *) getArgReference(stk, pci, 2));
+ if (!b)
+ throw(MAL, "topn_min", RUNTIME_OBJECT_MISSING);
+
+ bpiv = BATnew(TYPE_void, TYPE_oid, BATcount(b));
+ if (!bpiv){
+ BBPreleaseref(b->batCacheid);
+ throw(MAL, "topn_min", RUNTIME_OBJECT_MISSING);
+ }
+ bgid = BATnew(TYPE_void, TYPE_oid, BATcount(b));
+ if (!bgid){
+ BBPreleaseref(b->batCacheid);
+ BBPreleaseref(bpiv->batCacheid);
+ throw(MAL, "topn_min", RUNTIME_OBJECT_MISSING);
+ }
+ lim = BATcount(b);
+
+ BATseqbase(bpiv,0);
+ BATseqbase(bgid,0);
+ idx = (oid*) Tloc(bpiv,BUNfirst(bpiv));
+ gdx = (oid*) Tloc(bgid,BUNfirst(bgid));
+
+ // shuffle insert new values, keep it simple!
+ if( size){
+ if ( max ==0)
+ switch(tpe){
+ case TYPE_bte: QTOPN_shuffle2(bte,<) break;
+ case TYPE_sht: QTOPN_shuffle2(sht,<) break;
+ case TYPE_int: QTOPN_shuffle2(int,<) break;
+ case TYPE_wrd: QTOPN_shuffle2(wrd,<) break;
+ case TYPE_lng: QTOPN_shuffle2(lng,<) break;
+ case TYPE_flt: QTOPN_shuffle2(flt,<) break;
+ case TYPE_dbl: QTOPN_shuffle2(dbl,<) break;
+ default:
+ { int k;
+ uniq = 0;
+ for(o = 0; o < lim; o++){
+ k = atom_CMP( Tloc(b,o), Tloc(b,idx[top-1]),
tpe) >= 0;
+ if( uniq >= size && k)
+ continue;
+ uniq++;
+ idx[top] = gdx[top] = o;
+ for (i= top; i>0; i--){
+ if ( (k = atom_CMP( Tloc(b,idx[i]),
Tloc(b,idx[i-1]), tpe)) < 0) {
+ tmp= idx[i]; idx[i] = idx[i-1];
idx[i-1] = tmp;
+ tmp= gdx[i]; gdx[i] = gdx[i-1];
gdx[i-1] = tmp;
+ } else
+ if ( atom_CMP( Tloc(b,idx[i]),
Tloc(b,idx[i-1]), tpe) == 0) {
+ gdx[i] = gdx[i-1];
+ uniq--;
+ break;
+ } else break;
+ }
+ if( uniq < size) top++;
+ }
+ }
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
