97 	unsigned long *node;  in btree_node_alloc()  local
99 	node = mempool_alloc(head->mempool, gfp);  in btree_node_alloc()
100 	if (likely(node))  in btree_node_alloc()
101 		memset(node, 0, NODESIZE);  in btree_node_alloc()
102 	return node;  in btree_node_alloc()
150 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)  in bkey()  argument
152 	return &node[n * geo->keylen];  in bkey()
155 static void *bval(struct btree_geo *geo, unsigned long *node, int n)  in bval()  argument
157 	return (void *)node[geo->no_longs + n];  in bval()
160 static void setkey(struct btree_geo *geo, unsigned long *node, int n,  in setkey()  argument
163 	longcpy(bkey(geo, node, n), key, geo->keylen);  in setkey()
166 static void setval(struct btree_geo *geo, unsigned long *node, int n,  in setval()  argument
169 	node[geo->no_longs + n] = (unsigned long) val;  in setval()
172 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)  in clearpair()  argument
174 	longset(bkey(geo, node, n), 0, geo->keylen);  in clearpair()
175 	node[geo->no_longs + n] = 0;  in clearpair()
180 	head->node = NULL;  in __btree_init()
203 	mempool_free(head->node, head->mempool);  in btree_destroy()
213 	unsigned long *node = head->node;  in btree_last()  local
219 		node = bval(geo, node, 0);  in btree_last()
221 	longcpy(key, bkey(geo, node, 0), geo->keylen);  in btree_last()
222 	return bval(geo, node, 0);  in btree_last()
226 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,  in keycmp()  argument
229 	return longcmp(bkey(geo, node, pos), key, geo->keylen);  in keycmp()
247 	unsigned long *node = head->node;  in btree_lookup()  local
254 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup()
258 		node = bval(geo, node, i);  in btree_lookup()
259 		if (!node)  in btree_lookup()
263 	if (!node)  in btree_lookup()
267 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
268 			return bval(geo, node, i);  in btree_lookup()
277 	unsigned long *node = head->node;  in btree_update()  local
284 			if (keycmp(geo, node, i, key) <= 0)  in btree_update()
288 		node = bval(geo, node, i);  in btree_update()
289 		if (!node)  in btree_update()
293 	if (!node)  in btree_update()
297 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
298 			setval(geo, node, i, val);  in btree_update()
317 	unsigned long *node, *oldnode;  in btree_get_prev()  local
329 	node = head->node;  in btree_get_prev()
332 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
336 		oldnode = node;  in btree_get_prev()
337 		node = bval(geo, node, i);  in btree_get_prev()
338 		if (!node)  in btree_get_prev()
343 	if (!node)  in btree_get_prev()
347 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
348 			if (bval(geo, node, i)) {  in btree_get_prev()
349 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
350 				return bval(geo, node, i);  in btree_get_prev()
365 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
371 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
377 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
382 		if (!bval(geo, node, i))  in getfill()
393 	unsigned long *node = head->node;  in find_level()  local
398 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
401 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
406 			setkey(geo, node, i, key);  in find_level()
409 		node = bval(geo, node, i);  in find_level()
411 	BUG_ON(!node);  in find_level()
412 	return node;  in find_level()
418 	unsigned long *node;  in btree_grow()  local
421 	node = btree_node_alloc(head, gfp);  in btree_grow()
422 	if (!node)  in btree_grow()
424 	if (head->node) {  in btree_grow()
425 		fill = getfill(geo, head->node, 0);  in btree_grow()
426 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
427 		setval(geo, node, 0, head->node);  in btree_grow()
429 	head->node = node;  in btree_grow()
436 	unsigned long *node;  in btree_shrink()  local
442 	node = head->node;  in btree_shrink()
443 	fill = getfill(geo, node, 0);  in btree_shrink()
445 	head->node = bval(geo, node, 0);  in btree_shrink()
447 	mempool_free(node, head->mempool);  in btree_shrink()
454 	unsigned long *node;  in btree_insert_level()  local
465 	node = find_level(head, geo, key, level);  in btree_insert_level()
466 	pos = getpos(geo, node, key);  in btree_insert_level()
467 	fill = getfill(geo, node, pos);  in btree_insert_level()
469 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
479 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
486 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
487 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
488 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
489 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
490 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
493 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
494 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
495 			clearpair(geo, node, fill - 1);  in btree_insert_level()
503 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
504 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
506 	setkey(geo, node, pos, key);  in btree_insert_level()
507 	setval(geo, node, pos, val);  in btree_insert_level()
596 	unsigned long *node;  in btree_remove_level()  local
603 		head->node = NULL;  in btree_remove_level()
607 	node = find_level(head, geo, key, level);  in btree_remove_level()
608 	pos = getpos(geo, node, key);  in btree_remove_level()
609 	fill = getfill(geo, node, pos);  in btree_remove_level()
610 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
612 	ret = bval(geo, node, pos);  in btree_remove_level()
616 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
617 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
619 	clearpair(geo, node, fill - 1);  in btree_remove_level()
623 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
651 	if (!(target->node)) {  in btree_merge()
653 		target->node = victim->node;  in btree_merge()
679 			       unsigned long *node, unsigned long opaque,  in __btree_for_each()  argument
689 		child = bval(geo, node, i);  in __btree_for_each()
696 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
700 		mempool_free(node, head->mempool);  in __btree_for_each()
759 	if (head->node)  in btree_visitor()
760 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
777 	if (head->node)  in btree_grim_visitor()
778 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()