Major optimization, rewrite to avoid deep recursion if possible.

[SXSI/xpathcomp.git] / results.c

diff --git a/results.c b/results.c
index 161f295..4e7b4ec 100644 (file)
--- a/results.c
+++ b/results.c
@@ -26,8 +26,11 @@ results createResults (int n)
        { fprintf(stderr,"Error, redefine logW as %i and recompile\n",lg(W)-1);\r
         exit(1);\r
        }\r
+\r
     R.n = 2*n-1;\r
     R.lgn = lg(n);\r
+    //fprintf(stderr,"Size of the result set : %i elements, %li kB\n", n,\r
+    //(((R.n+W-1)/W)*sizeof(int)/1024));\r
     R.tree = (int*) malloc (((R.n+W-1)/W)*sizeof(int));\r
     clearBit(R.tree,0); // clear all\r
     return R;\r
@@ -42,15 +45,13 @@ void freeResults (results R)
 static int conv (int p, int n, int lgn)\r
 \r
   { int t = n+1-(1<<lgn);\r
-    if (p < t) return p;\r
-    return (p<<1)-t;\r
+    return (p < t) ? p : (p<<1)-t;\r
   }\r
 \r
 static int unconv (int p, int n, int lgn)\r
 \r
   { int t = n+1-(1<<lgn);\r
-    if (p < t) return p;\r
-    return (p+t)>>1;\r
+    return (p < t) ? p : (p+t)>>1;\r
   }\r
 \r
 int readResult (results R, int p) // returns 0 or 1\r
@@ -181,9 +182,9 @@ static int nextLarger (int *tree, int n, int p, int pos, int pot)
 \r
   { int answ;\r
     if (!getBit(tree,pos)) return -1; // no answer\r
-    pot--;\r
     pos = (pos<<1)+1;\r
     if (pos >= n) return 0; // when n is not a power of 2, missing leaves\r
+    pot--;\r
     if ((p>>pot) == 0) // p goes left\r
        { answ = nextLarger(tree,n,p&~(1<<pot),pos,pot);\r
         if (answ != -1) return answ;\r
@@ -202,10 +203,23 @@ int nextResult (results R, int p) // returns pos of next(p) or -1 if none
   { int answ;\r
     if (((p+1)<<1) > R.n) return -1; // next(last), p+1 out of bounds\r
     answ = nextLarger(R.tree,R.n,conv(p+1,R.n,R.lgn),0,R.lgn);\r
-    if (answ == -1) return -1;\r
-    return unconv(answ,R.n,R.lgn);\r
+    return (answ == -1) ? -1 : unconv(answ,R.n,R.lgn);\r
   }\r
 \r
+// Naively implemented by kim\r
+\r
+unsigned int countResult(results R) {\r
+  unsigned int result = -1;\r
+  int i = 0;\r
+  while ( i != -1 && i < R.n) {\r
+    result ++; \r
+    i = unconv(nextLarger(R.tree,R.n,conv(i+1,R.n,R.lgn),0,R.lgn),R.n,R.lgn);\r
+  };\r
+  return result;\r
+   \r
+}\r
+\r
+\r
 static void prnspace (int k)\r
 \r
   { while (k--) putchar(' ');\r