Changeset: 8f4d2e3652d9 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=8f4d2e3652d9
Modified Files:
monetdb5/modules/mal/Tests/pqueue.stable.out
monetdb5/modules/mal/Tests/pqueue2.mal
monetdb5/modules/mal/Tests/pqueue3.mal
monetdb5/modules/mal/pqueue.c
Branch: default
Log Message:
Refinement of the pqueue code base
next step SQL testing
diffs (truncated from 357 to 300 lines):
diff --git a/monetdb5/modules/mal/Tests/pqueue.stable.out
b/monetdb5/modules/mal/Tests/pqueue.stable.out
--- a/monetdb5/modules/mal/Tests/pqueue.stable.out
+++ b/monetdb5/modules/mal/Tests/pqueue.stable.out
@@ -125,7 +125,7 @@ end main;
[ 2@0, 2@0 ]
[ 3@0, 3@0 ]
[ 4@0, 6@0 ]
-[ 5@0, 5@0 ]
+[ 5@0, 4@0 ]
#--------------------------#
# h t # name
# void oid # type
@@ -135,8 +135,8 @@ end main;
[ 2@0, 2@0 ]
[ 3@0, 3@0 ]
[ 4@0, 6@0 ]
-[ 5@0, 5@0 ]
-[ 6@0, 4@0 ]
+[ 5@0, 4@0 ]
+[ 6@0, 5@0 ]
#--------------------------#
# h t # name
# void oid # type
@@ -146,8 +146,8 @@ end main;
[ 2@0, 2@0 ]
[ 3@0, 3@0 ]
[ 4@0, 6@0 ]
-[ 5@0, 5@0 ]
-[ 6@0, 4@0 ]
+[ 5@0, 4@0 ]
+[ 6@0, 5@0 ]
#--------------------------#
# h t # name
# void oid # type
@@ -177,7 +177,7 @@ end main;
[ 0@0, 4@0 ]
[ 1@0, 5@0 ]
[ 2@0, 6@0 ]
-[ 3@0, 3@0 ]
+[ 3@0, 2@0 ]
#--------------------------#
# h t # name
# void oid # type
@@ -185,8 +185,8 @@ end main;
[ 0@0, 4@0 ]
[ 1@0, 5@0 ]
[ 2@0, 6@0 ]
-[ 3@0, 3@0 ]
-[ 4@0, 2@0 ]
+[ 3@0, 2@0 ]
+[ 4@0, 3@0 ]
#--------------------------#
# h t # name
# void oid # type
@@ -194,8 +194,8 @@ end main;
[ 0@0, 4@0 ]
[ 1@0, 5@0 ]
[ 2@0, 6@0 ]
-[ 3@0, 3@0 ]
-[ 4@0, 2@0 ]
+[ 3@0, 2@0 ]
+[ 4@0, 3@0 ]
[ 5@0, 0@0 ]
#--------------------------#
# h t # name
@@ -204,8 +204,8 @@ end main;
[ 0@0, 4@0 ]
[ 1@0, 5@0 ]
[ 2@0, 6@0 ]
-[ 3@0, 3@0 ]
-[ 4@0, 2@0 ]
+[ 3@0, 2@0 ]
+[ 4@0, 3@0 ]
[ 5@0, 0@0 ]
[ 6@0, 1@0 ]
#--------------------------#
@@ -215,8 +215,8 @@ end main;
[ 0@0, 4@0 ]
[ 1@0, 5@0 ]
[ 2@0, 6@0 ]
-[ 3@0, 3@0 ]
-[ 4@0, 2@0 ]
+[ 3@0, 2@0 ]
+[ 4@0, 3@0 ]
[ 5@0, 0@0 ]
[ 6@0, 1@0 ]
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
@@ -23,18 +23,6 @@ bat.append(b,3);
io.print(b);
-c:= bat.new(:oid,:str);
-
-bat.append(c,"sjoerd");
-bat.append(c,"peter");
-bat.append(c,"stefan");
-bat.append(c,"stefan");
-bat.append(c,"niels");
-bat.append(c,"martin");
-bat.append(c,"stefan");
-
-io.print(c);
-
# topn of b, new interface should return void,oid(position)
bp:= pqueue.topn_min(b,0:wrd);
io.print(bp);
diff --git a/monetdb5/modules/mal/Tests/pqueue3.mal
b/monetdb5/modules/mal/Tests/pqueue3.mal
--- a/monetdb5/modules/mal/Tests/pqueue3.mal
+++ b/monetdb5/modules/mal/Tests/pqueue3.mal
@@ -24,23 +24,23 @@ bat.append(a,"stefan");
io.print(a);
# topn of b, new interface should return void,oid(position)
-bp:= pqueue.topn_min(b,0:wrd);
+bp:= pqueue.topn_min(a,0:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,1:wrd);
+bp:= pqueue.topn_min(a,1:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,2:wrd);
+bp:= pqueue.topn_min(a,2:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,3:wrd);
+bp:= pqueue.topn_min(a,3:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,4:wrd);
+bp:= pqueue.topn_min(a,4:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,5:wrd);
+bp:= pqueue.topn_min(a,5:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,6:wrd);
+bp:= pqueue.topn_min(a,6:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,7:wrd);
+bp:= pqueue.topn_min(a,7:wrd);
io.print(bp);
-bp:= pqueue.topn_min(b,8:wrd);
+bp:= pqueue.topn_min(a,8:wrd);
io.print(bp);
# utopn only count the unique values - topn of b,
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
@@ -20,22 +20,17 @@
#include "monetdb_config.h"
#include "pqueue.h"
-#define QTOPN_shuffle(TYPE,OPER,LAB)\
-{ TYPE *val = (TYPE *) Tloc(b,BUNfirst(b)), v;\
+#define QTOPN_shuffle(TYPE,OPER)\
+{ TYPE *val = (TYPE *) Tloc(b,BUNfirst(b));\
for(o = 0; o < lim; o++){\
- v = val[o];\
- oo = o;\
- if( top == size && !((TYPE) v OPER (TYPE) val[idx[top-1]]) )\
+ if( top == size && !((TYPE) val[o] 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;\
- } \
- if( top < size)\
- idx[top++] = oo;\
+ idx[top] = o;\
+ 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;\
+ } else break; \
+ if( top < size) top++;\
}\
}
@@ -44,8 +39,8 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
int tpe, *ret;
BAT *b,*bn;
BUN i, size,top = 0;
- oid *idx, lim, o, oo, tmp, off;
- int max = 0;
+ oid *idx, lim, o, tmp, off;
+ int max = 0,min=0;
(void) cntxt;
ret = (int*) getArgReference(stk, pci, 0);
@@ -53,8 +48,9 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
size = (BUN) *(wrd*) getArgReference(stk,pci,2);
max = strstr(getFunctionId(pci),"max") != 0;
+ min = strstr(getFunctionId(pci),"min") != 0;
- max = (max)?0:1;
+ assert(max+min == 1);
b = BATdescriptor(*(bat *) getArgReference(stk, pci, 1));
if (!b)
throw(MAL, "topn_min", RUNTIME_OBJECT_MISSING);
@@ -86,59 +82,50 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
}
// shuffle insert new values, keep it simple!
if( size){
+ if ( min )
+ switch(tpe){
+ case TYPE_bte: QTOPN_shuffle(bte,<) break;
+ case TYPE_sht: QTOPN_shuffle(sht,<) break;
+ case TYPE_int: QTOPN_shuffle(int,<) break;
+ case TYPE_wrd: QTOPN_shuffle(wrd,<) break;
+ case TYPE_lng: QTOPN_shuffle(lng,<) break;
+ case TYPE_flt: QTOPN_shuffle(flt,<) break;
+ case TYPE_dbl: QTOPN_shuffle(dbl,<) break;
+ default:
+ for(o = 0; o < lim; o++){
+ if( top == size && atom_CMP((void*) Tloc(b,o),
(void*) Tloc(b,idx[top-1]), tpe) > 0 )
+ continue;
+ idx[top] = o;
+ for (i= top; i> 0; i--)
+ if ( 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;
+ } else break;
+ if( top < size)
+ top++;
+ }
+ }
if ( max )
switch(tpe){
- case TYPE_bte: QTOPN_shuffle(bte,>,GTR) break;
- case TYPE_sht: QTOPN_shuffle(sht,>,GTR) break;
- case TYPE_int: QTOPN_shuffle(int,>,GTR) break;
- case TYPE_wrd: QTOPN_shuffle(wrd,>,GTR) break;
- case TYPE_lng: QTOPN_shuffle(lng,>,GTR) break;
- case TYPE_flt: QTOPN_shuffle(flt,>,GTR) break;
- case TYPE_dbl: QTOPN_shuffle(dbl,>,GTR) break;
+ case TYPE_bte: QTOPN_shuffle(bte,>) break;
+ case TYPE_sht: QTOPN_shuffle(sht,>) break;
+ case TYPE_int: QTOPN_shuffle(int,>) break;
+ case TYPE_wrd: QTOPN_shuffle(wrd,>) break;
+ case TYPE_lng: QTOPN_shuffle(lng,>) break;
+ case TYPE_flt: QTOPN_shuffle(flt,>) break;
+ case TYPE_dbl: QTOPN_shuffle(dbl,>) break;
default:
- { void *v;
-
for(o = 0; o < lim; o++){
- v = (void*) Tloc(b,o);
- oo = o;
- for (i= 0; i<top; i++)
- if ( atom_CMP( v, Tloc(b,idx[i]), tpe) > 0) {
- v = Tloc(b,idx[i]);
- tmp = idx[i];
- idx[i]= oo;
- oo = tmp;
- }
+ if( top == size && atom_CMP((void*) Tloc(b,o),
(void*) Tloc(b,idx[top-1]), tpe) < 0 )
+ continue;
+ idx[top] = o;
+ for (i= top; i> 0; i--)
+ if ( 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;
+ } else break;
if( top < size)
- idx[top++] = oo;
+ top++;
}
}
- }
- if ( max == 0 )
- switch(tpe){
- case TYPE_bte: QTOPN_shuffle(bte,<,LESS) break;
- case TYPE_sht: QTOPN_shuffle(sht,<,LESS) break;
- case TYPE_int: QTOPN_shuffle(int,<,LESS) break;
- case TYPE_wrd: QTOPN_shuffle(wrd,<,LESS) break;
- case TYPE_lng: QTOPN_shuffle(lng,<,LESS) break;
- case TYPE_flt: QTOPN_shuffle(flt,<,LESS) break;
- case TYPE_dbl: QTOPN_shuffle(dbl,<,LESS) break;
- default:
- { void *v;
- for(o = 0; o < lim; o++){
- v = (void*) Tloc(b,o);
- oo = o;
- for (i= 0; i<top; i++)
- if ( atom_CMP( v, Tloc(b,idx[i]), tpe) < 0) {
- v = Tloc(b,idx[i]);
- tmp = idx[i];
- idx[i]= oo;
- oo = tmp;
- }
- if( top < size)
- idx[top++] = oo;
- }
- }
- }
}
BATsetcount(bn, (BUN) top);
@@ -159,7 +146,7 @@ str PQtopn_minmax(Client cntxt, MalBlkPt
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
