Change the magic number used to introduce a trie file, so that instead

[sgt/agedu] / index.c

diff --git a/index.c b/index.c
index 56d657d..f4b9801 100644 (file)
--- a/index.c
+++ b/index.c
@@ -2,19 +2,13 @@
  * index.c: Implementation of index.h.
  */
 
-#include <assert.h>
-#include <stdio.h>
-#include <stddef.h>
-
+#include "agedu.h"
 #include "trie.h"
 #include "index.h"
 #include "alloc.h"
 
 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
 
-#define min(x,y) ((x)<(y) ? (x):(y))
-#define max(x,y) ((x)>(y) ? (x):(y))
-
 #define PADDING(x, mod) ( ((mod) - ((x) % (mod))) % (mod) )
 
 struct avlnode {
@@ -23,9 +17,13 @@ struct avlnode {
     unsigned long long totalsize;
 };
 
-static int index_navlnodes(int nodecount)
+/*
+ * Determine the maximum depth of an AVL tree containing a certain
+ * number of nodes.
+ */
+static int index_maxdepth(int nodecount)
 {
-    int b, c, maxdepth, ret;
+    int b, c, maxdepth;
 
     /*
      * Model the tree growing at maximum imbalance. We do this by
@@ -33,38 +31,26 @@ static int index_navlnodes(int nodecount)
      * (i.e. smallest) tree of any given depth, and stopping when
      * that's larger than nodecount.
      */
-    ret = 0;
     maxdepth = 1;
     b = 0;
     c = 1;
     while (b <= nodecount) {
        int tmp;
 
-       /*
-        * A tree with at most b nodes can be at most depth
-        * maxdepth-1. A tree with more than b but at most c can
-        * be at most maxdepth. Therefore, for each tree size
-        * between b and c, we might need to adjust maxdepth+1
-        * nodes.
-        */
-       tmp = min(c, nodecount);
-       ret += (tmp - b) * maxdepth;
-
        tmp = 1 + b + c;
        b = c;
        c = tmp;
        maxdepth++;
     }
 
-    return ret;
+    return maxdepth;
 }
 
-off_t index_compute_size(off_t currentsize, int nodecount)
+off_t index_initial_size(off_t currentsize, int nodecount)
 {
     currentsize += PADDING(currentsize, alignof(off_t));
-    currentsize += nodecount + sizeof(off_t);
+    currentsize += nodecount * sizeof(off_t);
     currentsize += PADDING(currentsize, alignof(struct avlnode));
-    currentsize += index_navlnodes(nodecount) * sizeof(struct avlnode);
 
     return currentsize;
 }
@@ -75,7 +61,7 @@ off_t index_compute_size(off_t currentsize, int nodecount)
 
 struct indexbuild {
     void *t;
-    int n, nnodes, maxnodes;
+    int n, nnodes;
     struct avlnode *nodes;
     off_t *roots;
     struct avlnode *currroot;
@@ -83,14 +69,15 @@ struct indexbuild {
 };
 
 #define ELEMENT(t,offset) \
-    ((offset) ? (struct trie_file *)((char *)(t) + (offset)) : NULL)
+    ((struct trie_file *) ((offset) ? ((char *)(t) + (offset)) : NULL))
 #define NODE(t,offset) \
-    ((offset) ? (struct avlnode *)((char *)(t) + (offset)) : NULL)
+    ((struct avlnode *) ((offset) ? ((char *)(t) + (offset)) : NULL))
 #define OFFSET(t,node) \
-    ((node) ? (off_t)((const char *)node - (const char *)t) : 0)
+    ((node) ? (off_t)((const char *)node - (const char *)t) : (off_t)0)
 #define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)
 
-indexbuild *indexbuild_new(void *t, off_t startoff, int nodecount)
+indexbuild *indexbuild_new(void *t, off_t startoff, int nodecount,
+                          size_t *delta)
 {
     indexbuild *ib = snew(indexbuild);
 
@@ -101,11 +88,13 @@ indexbuild *indexbuild_new(void *t, off_t startoff, int nodecount)
     startoff += nodecount * sizeof(off_t);
     startoff += PADDING(startoff, alignof(struct avlnode));
     ib->nodes = (struct avlnode *)((char *)t + startoff);
-    ib->maxnodes = index_navlnodes(nodecount);
     ib->nnodes = ib->n = 0;
     ib->currroot = NULL;
     ib->firstmutable = ib->nodes + ib->nnodes;
 
+    if (delta)
+       *delta = sizeof(struct avlnode) * (1 + index_maxdepth(nodecount));
+
     return ib;
 }
 
@@ -120,7 +109,6 @@ static struct avlnode *avl_makemutable(indexbuild *ib, struct avlnode *n)
     if (n && n >= ib->firstmutable)
        return n;                      /* already mutable */
 
-    assert(ib->nnodes < ib->maxnodes);
     newnode = ib->nodes + ib->nnodes++;
     if (n)
        *newnode = *n;                 /* structure copy */
@@ -261,10 +249,29 @@ void indexbuild_add(indexbuild *ib, const struct trie_file *tf)
 {
     off_t node = OFFSET(ib->t, tf);
     ib->currroot = avl_insert(ib, ib->currroot, node);
-    ib->roots[ib->n++] = OFFSET(ib->t, ib->currroot);
+    ib->roots[ib->n++] = 0;
+}
+
+void indexbuild_tag(indexbuild *ib)
+{
+    if (ib->n > 0)
+       ib->roots[ib->n - 1] = OFFSET(ib->t, ib->currroot);
     ib->firstmutable = ib->nodes + ib->nnodes;
 }
 
+void indexbuild_rebase(indexbuild *ib, void *t)
+{
+    ptrdiff_t diff = (unsigned char *)t - (unsigned char *)(ib->t);
+
+    ib->t = t;
+    ib->nodes = (struct avlnode *)((unsigned char *)ib->nodes + diff);
+    ib->roots = (off_t *)((unsigned char *)ib->roots + diff);
+    if (ib->currroot)
+       ib->currroot = (struct avlnode *)
+           ((unsigned char *)ib->currroot + diff);
+    ib->firstmutable = (struct avlnode *)((unsigned char *)ib->firstmutable + diff);
+}
+
 off_t indexbuild_realsize(indexbuild *ib)
 {
     return OFFSET(ib->t, (ib->nodes + ib->nnodes));
@@ -272,9 +279,23 @@ off_t indexbuild_realsize(indexbuild *ib)
 
 void indexbuild_free(indexbuild *ib)
 {
+    assert(ib->n == trie_count(ib->t));
     sfree(ib);
 }
 
+int index_has_root(const void *t, int n)
+{
+    const off_t *roots;
+
+    roots = (const off_t *)((const char *)t + trie_get_index_offset(t));
+
+    if (n == 0)
+       return 1;
+    if (n < 0 || n >= trie_count(t) || !roots[n-1])
+       return 0;
+    return 1;
+}
+
 unsigned long long index_query(const void *t, int n, unsigned long long at)
 {
     const off_t *roots;
@@ -290,6 +311,7 @@ unsigned long long index_query(const void *t, int n, unsigned long long at)
     if (n > count)
        n = count;
 
+    assert(roots[n-1]);
     node = NODE(t, roots[n-1]);
 
     ret = 0;
@@ -321,6 +343,7 @@ unsigned long long index_order_stat(const void *t, double f)
 
     roots = (const off_t *)((const char *)t + trie_get_index_offset(t));
     count = trie_count(t);
+    assert(roots[count-1]);
     node = NODE(t, roots[count-1]);
 
     size = node->totalsize * f;