16  * well is that access to a random tree node is much faster than a large number
17  * of operations within each node.
35  * values are to the right, not to the left.  All used slots within a node
95 	unsigned long *node;  in btree_node_alloc()  local
97 	node = mempool_alloc(head->mempool, gfp);  in btree_node_alloc()
98 	if (likely(node))  in btree_node_alloc()
99 		memset(node, 0, NODESIZE);  in btree_node_alloc()
100 	return node;  in btree_node_alloc()
148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)  in bkey()  argument
150 	return &node[n * geo->keylen];  in bkey()
153 static void *bval(struct btree_geo *geo, unsigned long *node, int n)  in bval()  argument
155 	return (void *)node[geo->no_longs + n];  in bval()
158 static void setkey(struct btree_geo *geo, unsigned long *node, int n,  in setkey()  argument
161 	longcpy(bkey(geo, node, n), key, geo->keylen);  in setkey()
164 static void setval(struct btree_geo *geo, unsigned long *node, int n,  in setval()  argument
167 	node[geo->no_longs + n] = (unsigned long) val;  in setval()
170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)  in clearpair()  argument
172 	longset(bkey(geo, node, n), 0, geo->keylen);  in clearpair()
173 	node[geo->no_longs + n] = 0;  in clearpair()
178 	head->node = NULL;  in __btree_init()
201 	mempool_free(head->node, head->mempool);  in btree_destroy()
211 	unsigned long *node = head->node;  in btree_last()  local
217 		node = bval(geo, node, 0);  in btree_last()
219 	longcpy(key, bkey(geo, node, 0), geo->keylen);  in btree_last()
220 	return bval(geo, node, 0);  in btree_last()
224 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,  in keycmp()  argument
227 	return longcmp(bkey(geo, node, pos), key, geo->keylen);  in keycmp()
245 	unsigned long *node = head->node;  in btree_lookup()  local
252 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup()
256 		node = bval(geo, node, i);  in btree_lookup()
257 		if (!node)  in btree_lookup()
261 	if (!node)  in btree_lookup()
265 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
266 			return bval(geo, node, i);  in btree_lookup()
275 	unsigned long *node = head->node;  in btree_update()  local
282 			if (keycmp(geo, node, i, key) <= 0)  in btree_update()
286 		node = bval(geo, node, i);  in btree_update()
287 		if (!node)  in btree_update()
291 	if (!node)  in btree_update()
295 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
296 			setval(geo, node, i, val);  in btree_update()
305  * a parent node may be smaller than the smallest key of all its siblings.
315 	unsigned long *node, *oldnode;  in btree_get_prev()  local
327 	node = head->node;  in btree_get_prev()
330 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
334 		oldnode = node;  in btree_get_prev()
335 		node = bval(geo, node, i);  in btree_get_prev()
336 		if (!node)  in btree_get_prev()
341 	if (!node)  in btree_get_prev()
345 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
346 			if (bval(geo, node, i)) {  in btree_get_prev()
347 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
348 				return bval(geo, node, i);  in btree_get_prev()
363 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
369 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
375 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
380 		if (!bval(geo, node, i))  in getfill()
386  * locate the correct leaf node in the btree
391 	unsigned long *node = head->node;  in find_level()  local
396 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
399 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
404 			setkey(geo, node, i, key);  in find_level()
407 		node = bval(geo, node, i);  in find_level()
409 	BUG_ON(!node);  in find_level()
410 	return node;  in find_level()
416 	unsigned long *node;  in btree_grow()  local
419 	node = btree_node_alloc(head, gfp);  in btree_grow()
420 	if (!node)  in btree_grow()
422 	if (head->node) {  in btree_grow()
423 		fill = getfill(geo, head->node, 0);  in btree_grow()
424 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
425 		setval(geo, node, 0, head->node);  in btree_grow()
427 	head->node = node;  in btree_grow()
434 	unsigned long *node;  in btree_shrink()  local
440 	node = head->node;  in btree_shrink()
441 	fill = getfill(geo, node, 0);  in btree_shrink()
443 	head->node = bval(geo, node, 0);  in btree_shrink()
445 	mempool_free(node, head->mempool);  in btree_shrink()
452 	unsigned long *node;  in btree_insert_level()  local
463 	node = find_level(head, geo, key, level);  in btree_insert_level()
464 	pos = getpos(geo, node, key);  in btree_insert_level()
465 	fill = getfill(geo, node, pos);  in btree_insert_level()
467 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
470 		/* need to split node */  in btree_insert_level()
477 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
484 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
485 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
486 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
487 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
488 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
491 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
492 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
493 			clearpair(geo, node, fill - 1);  in btree_insert_level()
501 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
502 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
504 	setkey(geo, node, pos, key);  in btree_insert_level()
505 	setval(geo, node, pos, val);  in btree_insert_level()
548 		 * can happen.  Parent node contains a single child, this  in rebalance()
549 		 * node, so merging with a sibling never happens.  in rebalance()
594 	unsigned long *node;  in btree_remove_level()  local
601 		head->node = NULL;  in btree_remove_level()
605 	node = find_level(head, geo, key, level);  in btree_remove_level()
606 	pos = getpos(geo, node, key);  in btree_remove_level()
607 	fill = getfill(geo, node, pos);  in btree_remove_level()
608 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
610 	ret = bval(geo, node, pos);  in btree_remove_level()
614 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
615 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
617 	clearpair(geo, node, fill - 1);  in btree_remove_level()
621 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
649 	if (!(target->node)) {  in btree_merge()
651 		target->node = victim->node;  in btree_merge()
677 			       unsigned long *node, unsigned long opaque,  in __btree_for_each()  argument
687 		child = bval(geo, node, i);  in __btree_for_each()
694 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
698 		mempool_free(node, head->mempool);  in __btree_for_each()
757 	if (head->node)  in btree_visitor()
758 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
775 	if (head->node)  in btree_grim_visitor()
776 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()