2 * index.c: Implementation of index.h.
10 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
12 #define min(x,y) ((x)<(y) ? (x):(y))
13 #define max(x,y) ((x)>(y) ? (x):(y))
15 #define PADDING(x, mod) ( ((mod) - ((x) % (mod))) % (mod) )
18 off_t children
[2], element
;
19 int maxdepth
; /* maximum depth of this subtree */
20 unsigned long long totalsize
;
24 * Determine the maximum depth of an AVL tree containing a certain
27 static int index_maxdepth(int nodecount
)
32 * Model the tree growing at maximum imbalance. We do this by
33 * determining the number of nodes in the most unbalanced
34 * (i.e. smallest) tree of any given depth, and stopping when
35 * that's larger than nodecount.
40 while (b
<= nodecount
) {
52 off_t
index_initial_size(off_t currentsize
, int nodecount
)
54 currentsize
+= PADDING(currentsize
, alignof(off_t
));
55 currentsize
+= nodecount
* sizeof(off_t
);
56 currentsize
+= PADDING(currentsize
, alignof(struct avlnode
));
61 /* ----------------------------------------------------------------------
62 * Functions to build the index.
68 struct avlnode
*nodes
;
70 struct avlnode
*currroot
;
71 struct avlnode
*firstmutable
;
74 #define ELEMENT(t,offset) \
75 ((offset) ? (struct trie_file *)((char *)(t) + (offset)) : NULL)
76 #define NODE(t,offset) \
77 ((offset) ? (struct avlnode *)((char *)(t) + (offset)) : NULL)
78 #define OFFSET(t,node) \
79 ((node) ? (off_t)((const char *)node - (const char *)t) : 0)
80 #define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)
82 indexbuild
*indexbuild_new(void *t
, off_t startoff
, int nodecount
,
85 indexbuild
*ib
= snew(indexbuild
);
88 startoff
+= PADDING(startoff
, alignof(off_t
));
89 ib
->roots
= (off_t
*)((char *)t
+ startoff
);
90 trie_set_index_offset(t
, startoff
);
91 startoff
+= nodecount
* sizeof(off_t
);
92 startoff
+= PADDING(startoff
, alignof(struct avlnode
));
93 ib
->nodes
= (struct avlnode
*)((char *)t
+ startoff
);
94 ib
->nnodes
= ib
->n
= 0;
96 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
99 *delta
= sizeof(struct avlnode
) * (1 + index_maxdepth(nodecount
));
105 * Return a mutable node, which is n or a copy of n if n is
108 static struct avlnode
*avl_makemutable(indexbuild
*ib
, struct avlnode
*n
)
110 struct avlnode
*newnode
;
112 if (n
&& n
>= ib
->firstmutable
)
113 return n
; /* already mutable */
115 newnode
= ib
->nodes
+ ib
->nnodes
++;
117 *newnode
= *n
; /* structure copy */
122 * Fix the annotations in a tree node.
124 static void avl_fix(indexbuild
*ib
, struct avlnode
*n
)
127 * Make sure the max depth field is right.
129 n
->maxdepth
= 1 + max(MAXDEPTH(NODE(ib
->t
, n
->children
[0])),
130 MAXDEPTH(NODE(ib
->t
, n
->children
[1])));
133 (ELEMENT(ib
->t
, n
->element
)->size
+
134 (n
->children
[0] ?
NODE(ib
->t
, n
->children
[0])->totalsize
: 0) +
135 (n
->children
[1] ?
NODE(ib
->t
, n
->children
[1])->totalsize
: 0));
138 static struct avlnode
*avl_insert(indexbuild
*ib
, struct avlnode
*n
,
141 struct trie_file
*newfile
;
142 struct trie_file
*oldfile
;
147 * Recursion bottoming out: if the subtree we're inserting
148 * into is null, just construct and return a fresh node.
151 n
= avl_makemutable(ib
, NULL
);
152 n
->children
[0] = n
->children
[1] = 0;
159 * Otherwise, we have to insert into an existing tree.
163 * Determine which subtree to insert this node into. Ties
164 * aren't important, so we just break them any old way.
166 newfile
= (struct trie_file
*)((char *)ib
->t
+ node
);
167 oldfile
= (struct trie_file
*)((char *)ib
->t
+ n
->element
);
168 if (newfile
->atime
> oldfile
->atime
)
174 * Construct a copy of the node we're looking at.
176 n
= avl_makemutable(ib
, n
);
179 * Recursively insert into the next subtree down.
181 nn
= avl_insert(ib
, NODE(ib
->t
, n
->children
[subtree
]), node
);
182 n
->children
[subtree
] = OFFSET(ib
->t
, nn
);
185 * Rebalance if necessary, to ensure that our node's children
186 * differ in maximum depth by at most one. Of course, the
187 * subtree we've just modified will be the deeper one if so.
189 if (MAXDEPTH(NODE(ib
->t
, n
->children
[subtree
])) >
190 MAXDEPTH(NODE(ib
->t
, n
->children
[1-subtree
])) + 1) {
191 struct avlnode
*p
, *q
;
194 * There are two possible cases, one of which requires a
195 * single tree rotation and the other requires two. It all
196 * depends on which subtree of the next node down (here p)
197 * is the taller. (It turns out that they can't both be
198 * the same height: any tree which has just increased in
199 * depth must have one subtree strictly taller than the
202 p
= NODE(ib
->t
, n
->children
[subtree
]);
203 assert(p
>= ib
->firstmutable
);
204 if (MAXDEPTH(NODE(ib
->t
, p
->children
[subtree
])) >=
205 MAXDEPTH(NODE(ib
->t
, p
->children
[1-subtree
]))) {
213 n
->children
[subtree
] = p
->children
[1-subtree
];
214 p
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
218 q
= NODE(ib
->t
, p
->children
[1-subtree
]);
219 assert(q
>= ib
->firstmutable
);
220 p
->children
[1-subtree
] = OFFSET(ib
->t
, q
);
224 * [k] p == [k] p -> n p
226 * [k+1] [k] q [k] [k] \ / [k]
227 * / \ [k-1,k] [k-1,k]
230 n
->children
[subtree
] = q
->children
[1-subtree
];
231 p
->children
[1-subtree
] = q
->children
[subtree
];
232 q
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
233 q
->children
[subtree
] = OFFSET(ib
->t
, p
);
241 * Fix up our maximum depth field.
251 void indexbuild_add(indexbuild
*ib
, const struct trie_file
*tf
)
253 off_t node
= OFFSET(ib
->t
, tf
);
254 ib
->currroot
= avl_insert(ib
, ib
->currroot
, node
);
255 ib
->roots
[ib
->n
++] = 0;
258 void indexbuild_tag(indexbuild
*ib
)
261 ib
->roots
[ib
->n
- 1] = OFFSET(ib
->t
, ib
->currroot
);
262 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
265 void indexbuild_rebase(indexbuild
*ib
, void *t
)
267 ptrdiff_t diff
= (unsigned char *)t
- (unsigned char *)(ib
->t
);
270 ib
->nodes
= (struct avlnode
*)((unsigned char *)ib
->nodes
+ diff
);
271 ib
->roots
= (off_t
*)((unsigned char *)ib
->roots
+ diff
);
273 ib
->currroot
= (struct avlnode
*)
274 ((unsigned char *)ib
->currroot
+ diff
);
275 ib
->firstmutable
= (struct avlnode
*)((unsigned char *)ib
->firstmutable
+ diff
);
278 off_t
indexbuild_realsize(indexbuild
*ib
)
280 return OFFSET(ib
->t
, (ib
->nodes
+ ib
->nnodes
));
283 void indexbuild_free(indexbuild
*ib
)
285 assert(ib
->n
== trie_count(ib
->t
));
289 unsigned long long index_query(const void *t
, int n
, unsigned long long at
)
292 const struct avlnode
*node
;
294 unsigned long long ret
;
296 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
300 count
= trie_count(t
);
305 node
= NODE(t
, roots
[n
-1]);
310 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
311 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
312 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
314 if (at
<= tf
->atime
) {
318 ret
+= left
->totalsize
;
327 unsigned long long index_order_stat(const void *t
, double f
)
330 const struct avlnode
*node
;
332 unsigned long long size
;
334 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
335 count
= trie_count(t
);
336 assert(roots
[count
-1]);
337 node
= NODE(t
, roots
[count
-1]);
339 size
= node
->totalsize
* f
;
340 assert(size
<= node
->totalsize
);
343 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
344 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
345 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
347 if (left
&& size
< left
->totalsize
) {
350 size
< (left ? left
->totalsize
: 0) + tf
->size
) {
354 size
-= left
->totalsize
;