3431d985cccaa3952810d9b87d913695b6c59c89
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
;
23 static int index_navlnodes(int nodecount
)
25 int b
, c
, maxdepth
, ret
;
28 * Model the tree growing at maximum imbalance. We do this by
29 * determining the number of nodes in the most unbalanced
30 * (i.e. smallest) tree of any given depth, and stopping when
31 * that's larger than nodecount.
37 while (b
<= nodecount
) {
41 * A tree with at most b nodes can be at most depth
42 * maxdepth-1. A tree with more than b but at most c can
43 * be at most maxdepth. Therefore, for each tree size
44 * between b and c, we might need to adjust maxdepth+1
47 tmp
= min(c
, nodecount
);
48 ret
+= (tmp
- b
) * maxdepth
;
59 off_t
index_compute_size(off_t currentsize
, int nodecount
)
61 currentsize
+= PADDING(currentsize
, alignof(off_t
));
62 currentsize
+= nodecount
+ sizeof(off_t
);
63 currentsize
+= PADDING(currentsize
, alignof(struct avlnode
));
64 currentsize
+= index_navlnodes(nodecount
) * sizeof(struct avlnode
);
69 /* ----------------------------------------------------------------------
70 * Functions to build the index.
75 int n
, nnodes
, maxnodes
;
76 struct avlnode
*nodes
;
78 struct avlnode
*currroot
;
79 struct avlnode
*firstmutable
;
82 #define ELEMENT(t,offset) \
83 ((offset) ? (struct trie_file *)((char *)(t) + (offset)) : NULL)
84 #define NODE(t,offset) \
85 ((offset) ? (struct avlnode *)((char *)(t) + (offset)) : NULL)
86 #define OFFSET(t,node) \
87 ((node) ? (off_t)((const char *)node - (const char *)t) : 0)
88 #define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)
90 indexbuild
*indexbuild_new(void *t
, off_t startoff
, int nodecount
)
92 indexbuild
*ib
= snew(indexbuild
);
95 startoff
+= PADDING(startoff
, alignof(off_t
));
96 ib
->roots
= (off_t
*)((char *)t
+ startoff
);
97 trie_set_index_offset(t
, startoff
);
98 startoff
+= nodecount
* sizeof(off_t
);
99 startoff
+= PADDING(startoff
, alignof(struct avlnode
));
100 ib
->nodes
= (struct avlnode
*)((char *)t
+ startoff
);
101 ib
->maxnodes
= index_navlnodes(nodecount
);
102 ib
->nnodes
= ib
->n
= 0;
104 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
110 * Return a mutable node, which is n or a copy of n if n is
113 static struct avlnode
*avl_makemutable(indexbuild
*ib
, struct avlnode
*n
)
115 struct avlnode
*newnode
;
117 if (n
&& n
>= ib
->firstmutable
)
118 return n
; /* already mutable */
120 assert(ib
->nnodes
< ib
->maxnodes
);
121 newnode
= ib
->nodes
+ ib
->nnodes
++;
123 *newnode
= *n
; /* structure copy */
128 * Fix the annotations in a tree node.
130 static void avl_fix(indexbuild
*ib
, struct avlnode
*n
)
133 * Make sure the max depth field is right.
135 n
->maxdepth
= 1 + max(MAXDEPTH(NODE(ib
->t
, n
->children
[0])),
136 MAXDEPTH(NODE(ib
->t
, n
->children
[1])));
139 (ELEMENT(ib
->t
, n
->element
)->size
+
140 (n
->children
[0] ?
NODE(ib
->t
, n
->children
[0])->totalsize
: 0) +
141 (n
->children
[1] ?
NODE(ib
->t
, n
->children
[1])->totalsize
: 0));
144 static struct avlnode
*avl_insert(indexbuild
*ib
, struct avlnode
*n
,
147 struct trie_file
*newfile
;
148 struct trie_file
*oldfile
;
153 * Recursion bottoming out: if the subtree we're inserting
154 * into is null, just construct and return a fresh node.
157 n
= avl_makemutable(ib
, NULL
);
158 n
->children
[0] = n
->children
[1] = 0;
165 * Otherwise, we have to insert into an existing tree.
169 * Determine which subtree to insert this node into. Ties
170 * aren't important, so we just break them any old way.
172 newfile
= (struct trie_file
*)((char *)ib
->t
+ node
);
173 oldfile
= (struct trie_file
*)((char *)ib
->t
+ n
->element
);
174 if (newfile
->atime
> oldfile
->atime
)
180 * Construct a copy of the node we're looking at.
182 n
= avl_makemutable(ib
, n
);
185 * Recursively insert into the next subtree down.
187 nn
= avl_insert(ib
, NODE(ib
->t
, n
->children
[subtree
]), node
);
188 n
->children
[subtree
] = OFFSET(ib
->t
, nn
);
191 * Rebalance if necessary, to ensure that our node's children
192 * differ in maximum depth by at most one. Of course, the
193 * subtree we've just modified will be the deeper one if so.
195 if (MAXDEPTH(NODE(ib
->t
, n
->children
[subtree
])) >
196 MAXDEPTH(NODE(ib
->t
, n
->children
[1-subtree
])) + 1) {
197 struct avlnode
*p
, *q
;
200 * There are two possible cases, one of which requires a
201 * single tree rotation and the other requires two. It all
202 * depends on which subtree of the next node down (here p)
203 * is the taller. (It turns out that they can't both be
204 * the same height: any tree which has just increased in
205 * depth must have one subtree strictly taller than the
208 p
= NODE(ib
->t
, n
->children
[subtree
]);
209 assert(p
>= ib
->firstmutable
);
210 if (MAXDEPTH(NODE(ib
->t
, p
->children
[subtree
])) >=
211 MAXDEPTH(NODE(ib
->t
, p
->children
[1-subtree
]))) {
219 n
->children
[subtree
] = p
->children
[1-subtree
];
220 p
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
224 q
= NODE(ib
->t
, p
->children
[1-subtree
]);
225 assert(q
>= ib
->firstmutable
);
226 p
->children
[1-subtree
] = OFFSET(ib
->t
, q
);
230 * [k] p == [k] p -> n p
232 * [k+1] [k] q [k] [k] \ / [k]
233 * / \ [k-1,k] [k-1,k]
236 n
->children
[subtree
] = q
->children
[1-subtree
];
237 p
->children
[1-subtree
] = q
->children
[subtree
];
238 q
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
239 q
->children
[subtree
] = OFFSET(ib
->t
, p
);
247 * Fix up our maximum depth field.
257 void indexbuild_add(indexbuild
*ib
, const struct trie_file
*tf
)
259 off_t node
= OFFSET(ib
->t
, tf
);
260 ib
->currroot
= avl_insert(ib
, ib
->currroot
, node
);
261 ib
->roots
[ib
->n
++] = 0;
264 void indexbuild_tag(indexbuild
*ib
)
267 ib
->roots
[ib
->n
- 1] = OFFSET(ib
->t
, ib
->currroot
);
268 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
271 off_t
indexbuild_realsize(indexbuild
*ib
)
273 return OFFSET(ib
->t
, (ib
->nodes
+ ib
->nnodes
));
276 void indexbuild_free(indexbuild
*ib
)
278 assert(ib
->n
== trie_count(ib
->t
));
282 unsigned long long index_query(const void *t
, int n
, unsigned long long at
)
285 const struct avlnode
*node
;
287 unsigned long long ret
;
289 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
293 count
= trie_count(t
);
298 node
= NODE(t
, roots
[n
-1]);
303 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
304 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
305 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
307 if (at
<= tf
->atime
) {
311 ret
+= left
->totalsize
;
320 unsigned long long index_order_stat(const void *t
, double f
)
323 const struct avlnode
*node
;
325 unsigned long long size
;
327 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
328 count
= trie_count(t
);
329 assert(roots
[count
-1]);
330 node
= NODE(t
, roots
[count
-1]);
332 size
= node
->totalsize
* f
;
333 assert(size
<= node
->totalsize
);
336 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
337 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
338 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
340 if (left
&& size
< left
->totalsize
) {
343 size
< (left ? left
->totalsize
: 0) + tf
->size
) {
347 size
-= left
->totalsize
;