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_node()  local
252 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup_node()
256 		node = bval(geo, node, i);  in btree_lookup_node()
257 		if (!node)  in btree_lookup_node()
260 	return node;  in btree_lookup_node()
267 	unsigned long *node;  in btree_lookup()  local
269 	node = btree_lookup_node(head, geo, key);  in btree_lookup()
270 	if (!node)  in btree_lookup()
274 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
275 			return bval(geo, node, i);  in btree_lookup()
284 	unsigned long *node;  in btree_update()  local
286 	node = btree_lookup_node(head, geo, key);  in btree_update()
287 	if (!node)  in btree_update()
291 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
292 			setval(geo, node, i, val);  in btree_update()
311 	unsigned long *node, *oldnode;  in btree_get_prev()  local
323 	node = head->node;  in btree_get_prev()
326 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
330 		oldnode = node;  in btree_get_prev()
331 		node = bval(geo, node, i);  in btree_get_prev()
332 		if (!node)  in btree_get_prev()
337 	if (!node)  in btree_get_prev()
341 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
342 			if (bval(geo, node, i)) {  in btree_get_prev()
343 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
344 				return bval(geo, node, i);  in btree_get_prev()
359 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
365 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
371 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
376 		if (!bval(geo, node, i))  in getfill()
387 	unsigned long *node = head->node;  in find_level()  local
392 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
395 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
400 			setkey(geo, node, i, key);  in find_level()
403 		node = bval(geo, node, i);  in find_level()
405 	BUG_ON(!node);  in find_level()
406 	return node;  in find_level()
412 	unsigned long *node;  in btree_grow()  local
415 	node = btree_node_alloc(head, gfp);  in btree_grow()
416 	if (!node)  in btree_grow()
418 	if (head->node) {  in btree_grow()
419 		fill = getfill(geo, head->node, 0);  in btree_grow()
420 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
421 		setval(geo, node, 0, head->node);  in btree_grow()
423 	head->node = node;  in btree_grow()
430 	unsigned long *node;  in btree_shrink()  local
436 	node = head->node;  in btree_shrink()
437 	fill = getfill(geo, node, 0);  in btree_shrink()
439 	head->node = bval(geo, node, 0);  in btree_shrink()
441 	mempool_free(node, head->mempool);  in btree_shrink()
448 	unsigned long *node;  in btree_insert_level()  local
459 	node = find_level(head, geo, key, level);  in btree_insert_level()
460 	pos = getpos(geo, node, key);  in btree_insert_level()
461 	fill = getfill(geo, node, pos);  in btree_insert_level()
463 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
473 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
480 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
481 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
482 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
483 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
484 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
487 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
488 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
489 			clearpair(geo, node, fill - 1);  in btree_insert_level()
497 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
498 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
500 	setkey(geo, node, pos, key);  in btree_insert_level()
501 	setval(geo, node, pos, val);  in btree_insert_level()
590 	unsigned long *node;  in btree_remove_level()  local
597 		head->node = NULL;  in btree_remove_level()
601 	node = find_level(head, geo, key, level);  in btree_remove_level()
602 	pos = getpos(geo, node, key);  in btree_remove_level()
603 	fill = getfill(geo, node, pos);  in btree_remove_level()
604 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
606 	ret = bval(geo, node, pos);  in btree_remove_level()
610 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
611 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
613 	clearpair(geo, node, fill - 1);  in btree_remove_level()
617 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
645 	if (!(target->node)) {  in btree_merge()
647 		target->node = victim->node;  in btree_merge()
673 			       unsigned long *node, unsigned long opaque,  in __btree_for_each()  argument
683 		child = bval(geo, node, i);  in __btree_for_each()
690 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
694 		mempool_free(node, head->mempool);  in __btree_for_each()
753 	if (head->node)  in btree_visitor()
754 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
771 	if (head->node)  in btree_grim_visitor()
772 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()