[sgt/agedu] / index.c

/*
 * index.c: Implementation of index.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 {
    off_t children[2], element;
    int maxdepth;		       /* maximum depth of this subtree */
    unsigned long long totalsize;
};

static int index_navlnodes(int nodecount)
{
    int b, c, maxdepth, ret;

    /*
     * Model the tree growing at maximum imbalance. We do this by
     * determining the number of nodes in the most unbalanced
     * (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;
}

off_t index_compute_size(off_t currentsize, int nodecount)
{
    currentsize += PADDING(currentsize, alignof(off_t));
    currentsize += nodecount + sizeof(off_t);
    currentsize += PADDING(currentsize, alignof(struct avlnode));
    currentsize += index_navlnodes(nodecount) * sizeof(struct avlnode);

    return currentsize;
}

/* ----------------------------------------------------------------------
 * Functions to build the index.
 */

struct indexbuild {
    void *t;
    int n, nnodes, maxnodes;
    struct avlnode *nodes;
    off_t *roots;
    struct avlnode *currroot;
    struct avlnode *firstmutable;
};

#define ELEMENT(t,offset) \
    ((offset) ? (struct trie_file *)((char *)(t) + (offset)) : NULL)
#define NODE(t,offset) \
    ((offset) ? (struct avlnode *)((char *)(t) + (offset)) : NULL)
#define OFFSET(t,node) \
    ((node) ? (off_t)((const char *)node - (const char *)t) : 0)
#define MAXDEPTH(node) ((node) ? (node)->maxdepth : 0)

indexbuild *indexbuild_new(void *t, off_t startoff, int nodecount)
{
    indexbuild *ib = snew(indexbuild);

    ib->t = t;
    startoff += PADDING(startoff, alignof(off_t));
    ib->roots = (off_t *)((char *)t + startoff);
    trie_set_index_offset(t, startoff);
    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;

    return ib;
}

/*
 * Return a mutable node, which is n or a copy of n if n is
 * non-NULL.
 */
static struct avlnode *avl_makemutable(indexbuild *ib, struct avlnode *n)
{
    struct avlnode *newnode;

    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 */
    return newnode;
}

/*
 * Fix the annotations in a tree node.
 */
static void avl_fix(indexbuild *ib, struct avlnode *n)
{
    /*
     * Make sure the max depth field is right.
     */
    n->maxdepth = 1 + max(MAXDEPTH(NODE(ib->t, n->children[0])),
			  MAXDEPTH(NODE(ib->t, n->children[1])));

    n->totalsize =
	(ELEMENT(ib->t, n->element)->size +
	 (n->children[0] ? NODE(ib->t, n->children[0])->totalsize : 0) +
	 (n->children[1] ? NODE(ib->t, n->children[1])->totalsize : 0));
}

static struct avlnode *avl_insert(indexbuild *ib, struct avlnode *n,
				  off_t node)
{
    struct trie_file *newfile;
    struct trie_file *oldfile;
    int subtree;
    struct avlnode *nn;
 
    /*
     * Recursion bottoming out: if the subtree we're inserting
     * into is null, just construct and return a fresh node.
     */
    if (!n) {
	n = avl_makemutable(ib, NULL);
	n->children[0] = n->children[1] = 0;
	n->element = node;
	avl_fix(ib, n);
	return n;
    }

    /*
     * Otherwise, we have to insert into an existing tree.
     */

    /*
     * Determine which subtree to insert this node into. Ties
     * aren't important, so we just break them any old way.
     */
    newfile = (struct trie_file *)((char *)ib->t + node);
    oldfile = (struct trie_file *)((char *)ib->t + n->element);
    if (newfile->atime > oldfile->atime)
	subtree = 1;
    else
	subtree = 0;

    /*
     * Construct a copy of the node we're looking at.
     */
    n = avl_makemutable(ib, n);

    /*
     * Recursively insert into the next subtree down.
     */
    nn = avl_insert(ib, NODE(ib->t, n->children[subtree]), node);
    n->children[subtree] = OFFSET(ib->t, nn);

    /*
     * Rebalance if necessary, to ensure that our node's children
     * differ in maximum depth by at most one. Of course, the
     * subtree we've just modified will be the deeper one if so.
     */
    if (MAXDEPTH(NODE(ib->t, n->children[subtree])) >
	MAXDEPTH(NODE(ib->t, n->children[1-subtree])) + 1) {
	struct avlnode *p, *q;

	/*
	 * There are two possible cases, one of which requires a
	 * single tree rotation and the other requires two. It all
	 * depends on which subtree of the next node down (here p)
	 * is the taller. (It turns out that they can't both be
	 * the same height: any tree which has just increased in
	 * depth must have one subtree strictly taller than the
	 * other.)
	 */
	p = NODE(ib->t, n->children[subtree]);
	assert(p >= ib->firstmutable);
	if (MAXDEPTH(NODE(ib->t, p->children[subtree])) >=
	    MAXDEPTH(NODE(ib->t, p->children[1-subtree]))) {
	    /*
	     *     n                       p
	     *    / \                     / \
	     *  [k]  p         ->        n  [k+1]
	     *      / \                 / \
	     *    [k] [k+1]           [k] [k]
	     */
	    n->children[subtree] = p->children[1-subtree];
	    p->children[1-subtree] = OFFSET(ib->t, n);
	    avl_fix(ib, n);
	    n = p;
	} else {
	    q = NODE(ib->t, p->children[1-subtree]);
	    assert(q >= ib->firstmutable);
	    p->children[1-subtree] = OFFSET(ib->t, q);
	    /*
	     *     n               n                 q
	     *    / \             / \              /   \
	     *  [k]  p    ==    [k]  p      ->    n     p
	     *      / \             / \          / \   / \
	     *  [k+1] [k]          q  [k]      [k]  \ /  [k]
	     *                    / \         [k-1,k] [k-1,k]
	     *              [k-1,k] [k-1,k]
	     */
	    n->children[subtree] = q->children[1-subtree];
	    p->children[1-subtree] = q->children[subtree];
	    q->children[1-subtree] = OFFSET(ib->t, n);
	    q->children[subtree] = OFFSET(ib->t, p);
	    avl_fix(ib, n);
	    avl_fix(ib, p);
	    n = q;
	}
    }

    /*
     * Fix up our maximum depth field.
     */
    avl_fix(ib, n);

    /*
     * Done.
     */
    return n;
}

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->firstmutable = ib->nodes + ib->nnodes;
}

off_t indexbuild_realsize(indexbuild *ib)
{
    return OFFSET(ib->t, (ib->nodes + ib->nnodes));
}

void indexbuild_free(indexbuild *ib)
{
    sfree(ib);
}

unsigned long long index_query(const void *t, int n, unsigned long long at)
{
    const off_t *roots;
    const struct avlnode *node;
    unsigned long count;
    unsigned long long ret;

    roots = (const off_t *)((const char *)t + trie_get_index_offset(t));

    if (n < 1)
	return 0;
    count = trie_count(t);
    if (n > count)
	n = count;

    node = NODE(t, roots[n-1]);

    ret = 0;

    while (node) {
	const struct trie_file *tf = ELEMENT(t, node->element);
	const struct avlnode *left = NODE(t, node->children[0]);
	const struct avlnode *right = NODE(t, node->children[1]);

	if (at <= tf->atime) {
	    node = left;
	} else {
	    if (left)
		ret += left->totalsize;
	    ret += tf->size;
	    node = right;
	}
    }

    return ret;
}

unsigned long long index_order_stat(const void *t, double f)
{
    const off_t *roots;
    const struct avlnode *node;
    unsigned long count;
    unsigned long long size;

    roots = (const off_t *)((const char *)t + trie_get_index_offset(t));
    count = trie_count(t);
    node = NODE(t, roots[count-1]);

    size = node->totalsize * f;
    assert(size <= node->totalsize);

    while (1) {
	const struct trie_file *tf = ELEMENT(t, node->element);
	const struct avlnode *left = NODE(t, node->children[0]);
	const struct avlnode *right = NODE(t, node->children[1]);

	if (left && size < left->totalsize) {
	    node = left;
	} else if (!right ||
                   size < (left ? left->totalsize : 0) + tf->size) {
	    return tf->atime;
	} else {
	    if (left)
		size -= left->totalsize;
	    size -= tf->size;
	    node = right;
	}
    }
}
Commit	Line	Data
70322ae3	1	/*
	2	* index.c: Implementation of index.h.
	3	*/
	4
50e82fdc	5	#include "agedu.h"
70322ae3	6	#include "trie.h"
70322ae3	7	#include "index.h"
995db599	8	#include "alloc.h"
70322ae3	9
	10	#define alignof(typ) ( offsetof(struct { char c; typ t; }, t) )
	11
	12	#define min(x,y) ((x)<(y) ? (x):(y))
	13	#define max(x,y) ((x)>(y) ? (x):(y))
	14
	15	#define PADDING(x, mod) ( ((mod) - ((x) % (mod))) % (mod) )
	16
	17	struct avlnode {
	18	off_t children[2], element;
	19	int maxdepth; /* maximum depth of this subtree */
	20	unsigned long long totalsize;
	21	};
	22
	23	static int index_navlnodes(int nodecount)
	24	{
	25	int b, c, maxdepth, ret;
	26
	27	/*
	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.
	32	*/
	33	ret = 0;
	34	maxdepth = 1;
	35	b = 0;
	36	c = 1;
	37	while (b <= nodecount) {
	38	int tmp;
	39
	40	/*
	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
	45	* nodes.
	46	*/
	47	tmp = min(c, nodecount);
	48	ret += (tmp - b) * maxdepth;
	49
	50	tmp = 1 + b + c;
	51	b = c;
	52	c = tmp;
	53	maxdepth++;
	54	}
	55
	56	return ret;
	57	}
	58
	59	off_t index_compute_size(off_t currentsize, int nodecount)
	60	{
	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);
	65
	66	return currentsize;
	67	}
	68
	69	/* ----------------------------------------------------------------------
	70	* Functions to build the index.
	71	*/
	72
73	struct indexbuild {
74	void *t;
75	int n, nnodes, maxnodes;
76	struct avlnode *nodes;
77	off_t *roots;
78	struct avlnode *currroot;
79	struct avlnode *firstmutable;
80	};
81
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)
89
90	indexbuild indexbuild_new(void t, off_t startoff, int nodecount)
91	{
92	indexbuild *ib = snew(indexbuild);
93
94	ib->t = t;
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;
103	ib->currroot = NULL;
104	ib->firstmutable = ib->nodes + ib->nnodes;
105
106	return ib;
107	}
108
109	/*
110	* Return a mutable node, which is n or a copy of n if n is
111	* non-NULL.
112	*/
113	static struct avlnode avl_makemutable(indexbuild ib, struct avlnode *n)
114	{
115	struct avlnode *newnode;
116
117	if (n && n >= ib->firstmutable)
118	return n; /* already mutable */
119
120	assert(ib->nnodes < ib->maxnodes);
121	newnode = ib->nodes + ib->nnodes++;
122	if (n)
123	newnode = n; /* structure copy */
124	return newnode;
125	}
126
127	/*
128	* Fix the annotations in a tree node.
129	*/
130	static void avl_fix(indexbuild ib, struct avlnode n)
131	{
132	/*
133	* Make sure the max depth field is right.
134	*/
135	n->maxdepth = 1 + max(MAXDEPTH(NODE(ib->t, n->children[0])),
136	MAXDEPTH(NODE(ib->t, n->children[1])));
137
138	n->totalsize =
84849cbd	139	(ELEMENT(ib->t, n->element)->size +
70322ae3	140	(n->children[0] ? NODE(ib->t, n->children[0])->totalsize : 0) +
	141	(n->children[1] ? NODE(ib->t, n->children[1])->totalsize : 0));
	142	}
	143
	144	static struct avlnode avl_insert(indexbuild ib, struct avlnode *n,
	145	off_t node)
	146	{
	147	struct trie_file *newfile;
	148	struct trie_file *oldfile;
	149	int subtree;
	150	struct avlnode *nn;
	151
	152	/*
	153	* Recursion bottoming out: if the subtree we're inserting
	154	* into is null, just construct and return a fresh node.
	155	*/
	156	if (!n) {
	157	n = avl_makemutable(ib, NULL);
	158	n->children[0] = n->children[1] = 0;
	159	n->element = node;
	160	avl_fix(ib, n);
	161	return n;
	162	}
	163
	164	/*
	165	* Otherwise, we have to insert into an existing tree.
	166	*/
	167
	168	/*
	169	* Determine which subtree to insert this node into. Ties
	170	* aren't important, so we just break them any old way.
	171	*/
	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)
	175	subtree = 1;
	176	else
	177	subtree = 0;
	178
	179	/*
	180	* Construct a copy of the node we're looking at.
	181	*/
	182	n = avl_makemutable(ib, n);
	183
	184	/*
	185	* Recursively insert into the next subtree down.
	186	*/
	187	nn = avl_insert(ib, NODE(ib->t, n->children[subtree]), node);
	188	n->children[subtree] = OFFSET(ib->t, nn);
	189
	190	/*
	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.
	194	*/
	195	if (MAXDEPTH(NODE(ib->t, n->children[subtree])) >
	196	MAXDEPTH(NODE(ib->t, n->children[1-subtree])) + 1) {
	197	struct avlnode p, q;
	198
	199	/*
	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
206	* other.)
207	*/
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]))) {
212	/*
213	* n p
214	* / \ / \
215	* [k] p -> n [k+1]
216	* / \ / \
217	* [k] [k+1] [k] [k]
218	*/
219	n->children[subtree] = p->children[1-subtree];
220	p->children[1-subtree] = OFFSET(ib->t, n);
221	avl_fix(ib, n);
222	n = p;
223	} else {
224	q = NODE(ib->t, p->children[1-subtree]);
225	assert(q >= ib->firstmutable);
226	p->children[1-subtree] = OFFSET(ib->t, q);
227	/*
228	* n n q
229	* / \ / \ / \
230	* [k] p == [k] p -> n p
231	* / \ / \ / \ / \
232	* [k+1] [k] q [k] [k] \ / [k]
233	* / \ [k-1,k] [k-1,k]
234	* [k-1,k] [k-1,k]
235	*/
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);
240	avl_fix(ib, n);
241	avl_fix(ib, p);
242	n = q;
243	}
244	}
245
246	/*
247	* Fix up our maximum depth field.
248	*/
249	avl_fix(ib, n);
250
251	/*
252	* Done.
253	*/
254	return n;
255	}
256
257	void indexbuild_add(indexbuild ib, const struct trie_file tf)
258	{
259	off_t node = OFFSET(ib->t, tf);
260	ib->currroot = avl_insert(ib, ib->currroot, node);
261	ib->roots[ib->n++] = OFFSET(ib->t, ib->currroot);
262	ib->firstmutable = ib->nodes + ib->nnodes;
263	}
264
265	off_t indexbuild_realsize(indexbuild *ib)
266	{
267	return OFFSET(ib->t, (ib->nodes + ib->nnodes));
268	}
269
270	void indexbuild_free(indexbuild *ib)
271	{
272	sfree(ib);
273	}
274
275	unsigned long long index_query(const void *t, int n, unsigned long long at)
276	{
277	const off_t *roots;
278	const struct avlnode *node;
279	unsigned long count;
280	unsigned long long ret;
281
282	roots = (const off_t )((const char )t + trie_get_index_offset(t));
283
284	if (n < 1)
285	return 0;
286	count = trie_count(t);
287	if (n > count)
288	n = count;
289
290	node = NODE(t, roots[n-1]);
291
292	ret = 0;
293
294	while (node) {
295	const struct trie_file *tf = ELEMENT(t, node->element);
296	const struct avlnode *left = NODE(t, node->children[0]);
297	const struct avlnode *right = NODE(t, node->children[1]);
298
299	if (at <= tf->atime) {
300	node = left;
301	} else {
302	if (left)
303	ret += left->totalsize;
84849cbd	304	ret += tf->size;
70322ae3	305	node = right;
	306	}
	307	}
	308
	309	return ret;
	310	}
	311
	312	unsigned long long index_order_stat(const void *t, double f)
	313	{
	314	const off_t *roots;
	315	const struct avlnode *node;
	316	unsigned long count;
	317	unsigned long long size;
	318
	319	roots = (const off_t )((const char )t + trie_get_index_offset(t));
	320	count = trie_count(t);
	321	node = NODE(t, roots[count-1]);
	322
	323	size = node->totalsize * f;
	324	assert(size <= node->totalsize);
	325
	326	while (1) {
	327	const struct trie_file *tf = ELEMENT(t, node->element);
	328	const struct avlnode *left = NODE(t, node->children[0]);
	329	const struct avlnode *right = NODE(t, node->children[1]);
	330
	331	if (left && size < left->totalsize) {
	332	node = left;
	333	} else if (!right \|\|
84849cbd	334	size < (left ? left->totalsize : 0) + tf->size) {
70322ae3	335	return tf->atime;
	336	} else {
	337	if (left)
	338	size -= left->totalsize;
84849cbd	339	size -= tf->size;
70322ae3	340	node = right;
	341	}
	342	}
	343	}