2 * index.c: Implementation of index.h.
13 #define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
15 #define min(x,y) ((x)<(y) ? (x):(y))
16 #define max(x,y) ((x)>(y) ? (x):(y))
18 #define PADDING(x, mod) ( ((mod) - ((x) % (mod))) % (mod) )
21 off_t children
[2], element
;
22 int maxdepth
; /* maximum depth of this subtree */
23 unsigned long long totalsize
;
26 static int index_navlnodes(int nodecount
)
28 int b
, c
, maxdepth
, ret
;
31 * Model the tree growing at maximum imbalance. We do this by
32 * determining the number of nodes in the most unbalanced
33 * (i.e. smallest) tree of any given depth, and stopping when
34 * that's larger than nodecount.
40 while (b
<= nodecount
) {
44 * A tree with at most b nodes can be at most depth
45 * maxdepth-1. A tree with more than b but at most c can
46 * be at most maxdepth. Therefore, for each tree size
47 * between b and c, we might need to adjust maxdepth+1
50 tmp
= min(c
, nodecount
);
51 ret
+= (tmp
- b
) * maxdepth
;
62 off_t
index_compute_size(off_t currentsize
, int nodecount
)
64 currentsize
+= PADDING(currentsize
, alignof(off_t
));
65 currentsize
+= nodecount
+ sizeof(off_t
);
66 currentsize
+= PADDING(currentsize
, alignof(struct avlnode
));
67 currentsize
+= index_navlnodes(nodecount
) * sizeof(struct avlnode
);
72 /* ----------------------------------------------------------------------
73 * Functions to build the index.
78 int n
, nnodes
, maxnodes
;
79 struct avlnode
*nodes
;
81 struct avlnode
*currroot
;
82 struct avlnode
*firstmutable
;
85 #define ELEMENT(t,offset) \
86 ((offset) ? (struct trie_file *)((char *)(t) + (offset)) : NULL)
87 #define NODE(t,offset) \
88 ((offset) ? (struct avlnode *)((char *)(t) + (offset)) : NULL)
89 #define OFFSET(t,node) \
90 ((node) ? (off_t)((const char *)node - (const char *)t) : 0)
91 #define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)
93 indexbuild
*indexbuild_new(void *t
, off_t startoff
, int nodecount
)
95 indexbuild
*ib
= snew(indexbuild
);
98 startoff
+= PADDING(startoff
, alignof(off_t
));
99 ib
->roots
= (off_t
*)((char *)t
+ startoff
);
100 trie_set_index_offset(t
, startoff
);
101 startoff
+= nodecount
* sizeof(off_t
);
102 startoff
+= PADDING(startoff
, alignof(struct avlnode
));
103 ib
->nodes
= (struct avlnode
*)((char *)t
+ startoff
);
104 ib
->maxnodes
= index_navlnodes(nodecount
);
105 ib
->nnodes
= ib
->n
= 0;
107 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
113 * Return a mutable node, which is n or a copy of n if n is
116 static struct avlnode
*avl_makemutable(indexbuild
*ib
, struct avlnode
*n
)
118 struct avlnode
*newnode
;
120 if (n
&& n
>= ib
->firstmutable
)
121 return n
; /* already mutable */
123 assert(ib
->nnodes
< ib
->maxnodes
);
124 newnode
= ib
->nodes
+ ib
->nnodes
++;
126 *newnode
= *n
; /* structure copy */
131 * Fix the annotations in a tree node.
133 static void avl_fix(indexbuild
*ib
, struct avlnode
*n
)
136 * Make sure the max depth field is right.
138 n
->maxdepth
= 1 + max(MAXDEPTH(NODE(ib
->t
, n
->children
[0])),
139 MAXDEPTH(NODE(ib
->t
, n
->children
[1])));
142 (ELEMENT(ib
->t
, n
->element
)->size
+
143 (n
->children
[0] ?
NODE(ib
->t
, n
->children
[0])->totalsize
: 0) +
144 (n
->children
[1] ?
NODE(ib
->t
, n
->children
[1])->totalsize
: 0));
147 static struct avlnode
*avl_insert(indexbuild
*ib
, struct avlnode
*n
,
150 struct trie_file
*newfile
;
151 struct trie_file
*oldfile
;
156 * Recursion bottoming out: if the subtree we're inserting
157 * into is null, just construct and return a fresh node.
160 n
= avl_makemutable(ib
, NULL
);
161 n
->children
[0] = n
->children
[1] = 0;
168 * Otherwise, we have to insert into an existing tree.
172 * Determine which subtree to insert this node into. Ties
173 * aren't important, so we just break them any old way.
175 newfile
= (struct trie_file
*)((char *)ib
->t
+ node
);
176 oldfile
= (struct trie_file
*)((char *)ib
->t
+ n
->element
);
177 if (newfile
->atime
> oldfile
->atime
)
183 * Construct a copy of the node we're looking at.
185 n
= avl_makemutable(ib
, n
);
188 * Recursively insert into the next subtree down.
190 nn
= avl_insert(ib
, NODE(ib
->t
, n
->children
[subtree
]), node
);
191 n
->children
[subtree
] = OFFSET(ib
->t
, nn
);
194 * Rebalance if necessary, to ensure that our node's children
195 * differ in maximum depth by at most one. Of course, the
196 * subtree we've just modified will be the deeper one if so.
198 if (MAXDEPTH(NODE(ib
->t
, n
->children
[subtree
])) >
199 MAXDEPTH(NODE(ib
->t
, n
->children
[1-subtree
])) + 1) {
200 struct avlnode
*p
, *q
;
203 * There are two possible cases, one of which requires a
204 * single tree rotation and the other requires two. It all
205 * depends on which subtree of the next node down (here p)
206 * is the taller. (It turns out that they can't both be
207 * the same height: any tree which has just increased in
208 * depth must have one subtree strictly taller than the
211 p
= NODE(ib
->t
, n
->children
[subtree
]);
212 assert(p
>= ib
->firstmutable
);
213 if (MAXDEPTH(NODE(ib
->t
, p
->children
[subtree
])) >=
214 MAXDEPTH(NODE(ib
->t
, p
->children
[1-subtree
]))) {
222 n
->children
[subtree
] = p
->children
[1-subtree
];
223 p
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
227 q
= NODE(ib
->t
, p
->children
[1-subtree
]);
228 assert(q
>= ib
->firstmutable
);
229 p
->children
[1-subtree
] = OFFSET(ib
->t
, q
);
233 * [k] p == [k] p -> n p
235 * [k+1] [k] q [k] [k] \ / [k]
236 * / \ [k-1,k] [k-1,k]
239 n
->children
[subtree
] = q
->children
[1-subtree
];
240 p
->children
[1-subtree
] = q
->children
[subtree
];
241 q
->children
[1-subtree
] = OFFSET(ib
->t
, n
);
242 q
->children
[subtree
] = OFFSET(ib
->t
, p
);
250 * Fix up our maximum depth field.
260 void indexbuild_add(indexbuild
*ib
, const struct trie_file
*tf
)
262 off_t node
= OFFSET(ib
->t
, tf
);
263 ib
->currroot
= avl_insert(ib
, ib
->currroot
, node
);
264 ib
->roots
[ib
->n
++] = OFFSET(ib
->t
, ib
->currroot
);
265 ib
->firstmutable
= ib
->nodes
+ ib
->nnodes
;
268 off_t
indexbuild_realsize(indexbuild
*ib
)
270 return OFFSET(ib
->t
, (ib
->nodes
+ ib
->nnodes
));
273 void indexbuild_free(indexbuild
*ib
)
278 unsigned long long index_query(const void *t
, int n
, unsigned long long at
)
281 const struct avlnode
*node
;
283 unsigned long long ret
;
285 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
289 count
= trie_count(t
);
293 node
= NODE(t
, roots
[n
-1]);
298 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
299 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
300 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
302 if (at
<= tf
->atime
) {
306 ret
+= left
->totalsize
;
315 unsigned long long index_order_stat(const void *t
, double f
)
318 const struct avlnode
*node
;
320 unsigned long long size
;
322 roots
= (const off_t
*)((const char *)t
+ trie_get_index_offset(t
));
323 count
= trie_count(t
);
324 node
= NODE(t
, roots
[count
-1]);
326 size
= node
->totalsize
* f
;
327 assert(size
<= node
->totalsize
);
330 const struct trie_file
*tf
= ELEMENT(t
, node
->element
);
331 const struct avlnode
*left
= NODE(t
, node
->children
[0]);
332 const struct avlnode
*right
= NODE(t
, node
->children
[1]);
334 if (left
&& size
< left
->totalsize
) {
337 size
< (left ? left
->totalsize
: 0) + tf
->size
) {
341 size
-= left
->totalsize
;