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
94 	unsigned long *node;  in btree_node_alloc()  local
96 	node = mempool_alloc(head->mempool, gfp);  in btree_node_alloc()
97 	if (likely(node))  in btree_node_alloc()
98 		memset(node, 0, NODESIZE);  in btree_node_alloc()
99 	return node;  in btree_node_alloc()
147 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)  in bkey()  argument
149 	return &node[n * geo->keylen];  in bkey()
152 static void *bval(struct btree_geo *geo, unsigned long *node, int n)  in bval()  argument
154 	return (void *)node[geo->no_longs + n];  in bval()
157 static void setkey(struct btree_geo *geo, unsigned long *node, int n,  in setkey()  argument
160 	longcpy(bkey(geo, node, n), key, geo->keylen);  in setkey()
163 static void setval(struct btree_geo *geo, unsigned long *node, int n,  in setval()  argument
166 	node[geo->no_longs + n] = (unsigned long) val;  in setval()
169 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)  in clearpair()  argument
171 	longset(bkey(geo, node, n), 0, geo->keylen);  in clearpair()
172 	node[geo->no_longs + n] = 0;  in clearpair()
177 	head->node = NULL;  in __btree_init()
200 	mempool_free(head->node, head->mempool);  in btree_destroy()
210 	unsigned long *node = head->node;  in btree_last()  local
216 		node = bval(geo, node, 0);  in btree_last()
218 	longcpy(key, bkey(geo, node, 0), geo->keylen);  in btree_last()
219 	return bval(geo, node, 0);  in btree_last()
223 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,  in keycmp()  argument
226 	return longcmp(bkey(geo, node, pos), key, geo->keylen);  in keycmp()
244 	unsigned long *node = head->node;  in btree_lookup_node()  local
251 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup_node()
255 		node = bval(geo, node, i);  in btree_lookup_node()
256 		if (!node)  in btree_lookup_node()
259 	return node;  in btree_lookup_node()
266 	unsigned long *node;  in btree_lookup()  local
268 	node = btree_lookup_node(head, geo, key);  in btree_lookup()
269 	if (!node)  in btree_lookup()
273 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
274 			return bval(geo, node, i);  in btree_lookup()
283 	unsigned long *node;  in btree_update()  local
285 	node = btree_lookup_node(head, geo, key);  in btree_update()
286 	if (!node)  in btree_update()
290 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
291 			setval(geo, node, i, val);  in btree_update()
300  * a parent node may be smaller than the smallest key of all its siblings.
310 	unsigned long *node, *oldnode;  in btree_get_prev()  local
322 	node = head->node;  in btree_get_prev()
325 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
329 		oldnode = node;  in btree_get_prev()
330 		node = bval(geo, node, i);  in btree_get_prev()
331 		if (!node)  in btree_get_prev()
336 	if (!node)  in btree_get_prev()
340 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
341 			if (bval(geo, node, i)) {  in btree_get_prev()
342 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
343 				return bval(geo, node, i);  in btree_get_prev()
358 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
364 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
370 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
375 		if (!bval(geo, node, i))  in getfill()
381  * locate the correct leaf node in the btree
386 	unsigned long *node = head->node;  in find_level()  local
391 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
394 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
399 			setkey(geo, node, i, key);  in find_level()
402 		node = bval(geo, node, i);  in find_level()
404 	BUG_ON(!node);  in find_level()
405 	return node;  in find_level()
411 	unsigned long *node;  in btree_grow()  local
414 	node = btree_node_alloc(head, gfp);  in btree_grow()
415 	if (!node)  in btree_grow()
417 	if (head->node) {  in btree_grow()
418 		fill = getfill(geo, head->node, 0);  in btree_grow()
419 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
420 		setval(geo, node, 0, head->node);  in btree_grow()
422 	head->node = node;  in btree_grow()
429 	unsigned long *node;  in btree_shrink()  local
435 	node = head->node;  in btree_shrink()
436 	fill = getfill(geo, node, 0);  in btree_shrink()
438 	head->node = bval(geo, node, 0);  in btree_shrink()
440 	mempool_free(node, head->mempool);  in btree_shrink()
447 	unsigned long *node;  in btree_insert_level()  local
458 	node = find_level(head, geo, key, level);  in btree_insert_level()
459 	pos = getpos(geo, node, key);  in btree_insert_level()
460 	fill = getfill(geo, node, pos);  in btree_insert_level()
462 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
465 		/* need to split node */  in btree_insert_level()
472 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
479 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
480 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
481 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
482 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
483 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
486 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
487 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
488 			clearpair(geo, node, fill - 1);  in btree_insert_level()
496 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
497 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
499 	setkey(geo, node, pos, key);  in btree_insert_level()
500 	setval(geo, node, pos, val);  in btree_insert_level()
543 		 * can happen.  Parent node contains a single child, this  in rebalance()
544 		 * node, so merging with a sibling never happens.  in rebalance()
589 	unsigned long *node;  in btree_remove_level()  local
596 		head->node = NULL;  in btree_remove_level()
600 	node = find_level(head, geo, key, level);  in btree_remove_level()
601 	pos = getpos(geo, node, key);  in btree_remove_level()
602 	fill = getfill(geo, node, pos);  in btree_remove_level()
603 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
605 	ret = bval(geo, node, pos);  in btree_remove_level()
609 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
610 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
612 	clearpair(geo, node, fill - 1);  in btree_remove_level()
616 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
644 	if (!(target->node)) {  in btree_merge()
646 		target->node = victim->node;  in btree_merge()
672 			       unsigned long *node, unsigned long opaque,  in __btree_for_each()  argument
682 		child = bval(geo, node, i);  in __btree_for_each()
689 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
693 		mempool_free(node, head->mempool);  in __btree_for_each()
752 	if (head->node)  in btree_visitor()
753 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
770 	if (head->node)  in btree_grim_visitor()
771 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()