2 * index.c: Implementation of index.h.
10 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
12 #define PADDING(x, mod) ( ((mod) - ((x) % (mod))) % (mod) )
15 off_t children
[2], element
;
16 int maxdepth
; /* maximum depth of this subtree */
17 unsigned long long totalsize
;
21 * Determine the maximum depth of an AVL tree containing a certain
24 static int index_maxdepth(int nodecount
)
29 * Model the tree growing at maximum imbalance. We do this by
30 * determining the number of nodes in the most unbalanced
31 * (i.e. smallest) tree of any given depth, and stopping when
32 * that's larger than nodecount.
37 while (b
<= nodecount
) {
49 off_t
index_initial_size(off_t currentsize
, int nodecount
)
51 currentsize
+= PADDING(currentsize
, alignof(off_t
));
52 currentsize
+= nodecount
* sizeof(off_t
);
53 currentsize
+= PADDING(currentsize
, alignof(struct avlnode
));
58 /* ----------------------------------------------------------------------
59 * Functions to build the index.
65 struct avlnode
*nodes
;
67 struct avlnode
*currroot
;
68 struct avlnode
*firstmutable
;
71 #define ELEMENT(t,offset) \
72 ((struct trie_file *) ((offset) ? ((char *)(t) + (offset)) : NULL))
73 #define NODE(t,offset) \
74 ((struct avlnode *) ((offset) ? ((char *)(t) + (offset)) : NULL))
75 #define OFFSET(t,node) \
76 ((node) ? (off_t)((const char *)node - (const char *)t) : (off_t)0)
77 #define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)
79 indexbuild
*indexbuild_new(void *t
, off_t startoff
, int nodecount
,
82 indexbuild
*ib
= snew(indexbuild
);
85 startoff
+= PADDING(startoff
, alignof(off_t
));
86 ib
->roots
= (off_t
*)((char *)t
+ startoff
);
87 trie_set_index_offset(t
, startoff
);
88 startoff
+= nodecount
* sizeof(off_t
);
89 startoff
+= PADDING(startoff
, alignof(struct avlnode
));
90 ib
->nodes
= (struct avlnode
*)((char *)t
+ startoff
);
91 ib
->nnodes
= ib
->n
= 0;
93 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
96 *delta
= sizeof(struct avlnode
) * (1 + index_maxdepth(nodecount
));
102 * Return a mutable node, which is n or a copy of n if n is
105 static struct avlnode
*avl_makemutable(indexbuild
*ib
, struct avlnode
*n
)
107 struct avlnode
*newnode
;
109 if (n
&& n
>= ib
->firstmutable
)
110 return n
; /* already mutable */
112 newnode
= ib
->nodes
+ ib
->nnodes
++;
114 *newnode
= *n
; /* structure copy */
119 * Fix the annotations in a tree node.
121 static void avl_fix(indexbuild
*ib
, struct avlnode
*n
)
124 * Make sure the max depth field is right.
126 n
->maxdepth
= 1 + max(MAXDEPTH(NODE(ib
->t
, n
->children
[0])),
127 MAXDEPTH(NODE(ib
->t
, n
->children
[1])));
130 (ELEMENT(ib
->t
, n
->element
)->size
+
131 (n
->children
[0] ?
NODE(ib
->t
, n
->children
[0])->totalsize
: 0) +
132 (n
->children
[1] ?
NODE(ib
->t
, n
->children
[1])->totalsize
: 0));
135 static struct avlnode
*avl_insert(indexbuild
*ib
, struct avlnode
*n
,
138 struct trie_file
*newfile
;
139 struct trie_file
*oldfile
;
144 * Recursion bottoming out: if the subtree we're inserting
145 * into is null, just construct and return a fresh node.
148 n
= avl_makemutable(ib
, NULL
);
149 n
->children
[0] = n
->children
[1] = 0;
156 * Otherwise, we have to insert into an existing tree.
160 * Determine which subtree to insert this node into. Ties
161 * aren't important, so we just break them any old way.
163 newfile
= (struct trie_file
*)((char *)ib
->t
+ node
);
164 oldfile
= (struct trie_file
*)((char *)ib
->t
+ n
->element
);
165 if (newfile
->atime
> oldfile
->atime
)
171 * Construct a copy of the node we're looking at.
173 n
= avl_makemutable(ib
, n
);
176 * Recursively insert into the next subtree down.
178 nn
= avl_insert(ib
, NODE(ib
->t
, n
->children
[subtree
]), node
);
179 n
->children
[subtree
] = OFFSET(ib
->t
, nn
);
182 * Rebalance if necessary, to ensure that our node's children
183 * differ in maximum depth by at most one. Of course, the
184 * subtree we've just modified will be the deeper one if so.
186 if (MAXDEPTH(NODE(ib
->t
, n
->children
[subtree
])) >
187 MAXDEPTH(NODE(ib
->t
, n
->children
[1-subtree
])) + 1) {
188 struct avlnode
*p
, *q
;
191 * There are two possible cases, one of which requires a
192 * single tree rotation and the other requires two. It all
193 * depends on which subtree of the next node down (here p)
194 * is the taller. (It turns out that they can't both be
195 * the same height: any tree which has just increased in
196 * depth must have one subtree strictly taller than the
199 p
= NODE(ib
->t
, n
->children
[subtree
]);
200 assert(p
>= ib
->firstmutable
);
201 if (MAXDEPTH(NODE(ib
->t
, p
->children
[subtree
])) >=
202 MAXDEPTH(NODE(ib
->t
, p
->children
[1-subtree
]))) {
210 n
->children
[subtree
] = p
->children
[1-subtree
];
211 p
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
215 q
= NODE(ib
->t
, p
->children
[1-subtree
]);
216 assert(q
>= ib
->firstmutable
);
217 p
->children
[1-subtree
] = OFFSET(ib
->t
, q
);
221 * [k] p == [k] p -> n p
223 * [k+1] [k] q [k] [k] \ / [k]
224 * / \ [k-1,k] [k-1,k]
227 n
->children
[subtree
] = q
->children
[1-subtree
];
228 p
->children
[1-subtree
] = q
->children
[subtree
];
229 q
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
230 q
->children
[subtree
] = OFFSET(ib
->t
, p
);
238 * Fix up our maximum depth field.
248 void indexbuild_add(indexbuild
*ib
, const struct trie_file
*tf
)
250 off_t node
= OFFSET(ib
->t
, tf
);
251 ib
->currroot
= avl_insert(ib
, ib
->currroot
, node
);
252 ib
->roots
[ib
->n
++] = 0;
255 void indexbuild_tag(indexbuild
*ib
)
258 ib
->roots
[ib
->n
- 1] = OFFSET(ib
->t
, ib
->currroot
);
259 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
262 void indexbuild_rebase(indexbuild
*ib
, void *t
)
264 ptrdiff_t diff
= (unsigned char *)t
- (unsigned char *)(ib
->t
);
267 ib
->nodes
= (struct avlnode
*)((unsigned char *)ib
->nodes
+ diff
);
268 ib
->roots
= (off_t
*)((unsigned char *)ib
->roots
+ diff
);
270 ib
->currroot
= (struct avlnode
*)
271 ((unsigned char *)ib
->currroot
+ diff
);
272 ib
->firstmutable
= (struct avlnode
*)((unsigned char *)ib
->firstmutable
+ diff
);
275 off_t
indexbuild_realsize(indexbuild
*ib
)
277 return OFFSET(ib
->t
, (ib
->nodes
+ ib
->nnodes
));
280 void indexbuild_free(indexbuild
*ib
)
282 assert(ib
->n
== trie_count(ib
->t
));
286 int index_has_root(const void *t
, int n
)
290 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
294 if (n
< 0 || n
>= trie_count(t
) || !roots
[n
-1])
299 unsigned long long index_query(const void *t
, int n
, unsigned long long at
)
302 const struct avlnode
*node
;
304 unsigned long long ret
;
306 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
310 count
= trie_count(t
);
315 node
= NODE(t
, roots
[n
-1]);
320 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
321 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
322 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
324 if (at
<= tf
->atime
) {
328 ret
+= left
->totalsize
;
337 unsigned long long index_order_stat(const void *t
, double f
)
340 const struct avlnode
*node
;
342 unsigned long long size
;
344 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
345 count
= trie_count(t
);
346 assert(roots
[count
-1]);
347 node
= NODE(t
, roots
[count
-1]);
349 size
= node
->totalsize
* f
;
350 assert(size
<= node
->totalsize
);
353 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
354 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
355 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
357 if (left
&& size
< left
->totalsize
) {
360 size
< (left ? left
->totalsize
: 0) + tf
->size
) {
364 size
-= left
->totalsize
;