Lines Matching refs:node
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;
97 node = mempool_alloc(head->mempool, gfp);
98 if (likely(node))
99 memset(node, 0, NODESIZE);
100 return node;
148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
150 return &node[n * geo->keylen];
153 static void *bval(struct btree_geo *geo, unsigned long *node, int n)
155 return (void *)node[geo->no_longs + n];
158 static void setkey(struct btree_geo *geo, unsigned long *node, int n,
161 longcpy(bkey(geo, node, n), key, geo->keylen);
164 static void setval(struct btree_geo *geo, unsigned long *node, int n,
167 node[geo->no_longs + n] = (unsigned long) val;
170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
172 longset(bkey(geo, node, n), 0, geo->keylen);
173 node[geo->no_longs + n] = 0;
178 head->node = NULL;
201 mempool_free(head->node, head->mempool);
211 unsigned long *node = head->node;
217 node = bval(geo, node, 0);
219 longcpy(key, bkey(geo, node, 0), geo->keylen);
220 return bval(geo, node, 0);
224 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
227 return longcmp(bkey(geo, node, pos), key, geo->keylen);
245 unsigned long *node = head->node;
252 if (keycmp(geo, node, i, key) <= 0)
256 node = bval(geo, node, i);
257 if (!node)
260 return node;
267 unsigned long *node;
269 node = btree_lookup_node(head, geo, key);
270 if (!node)
274 if (keycmp(geo, node, i, key) == 0)
275 return bval(geo, node, i);
284 unsigned long *node;
286 node = btree_lookup_node(head, geo, key);
287 if (!node)
291 if (keycmp(geo, node, i, key) == 0) {
292 setval(geo, node, i, val);
301 * a parent node may be smaller than the smallest key of all its siblings.
311 unsigned long *node, *oldnode;
323 node = head->node;
326 if (keycmp(geo, node, i, key) <= 0)
330 oldnode = node;
331 node = bval(geo, node, i);
332 if (!node)
337 if (!node)
341 if (keycmp(geo, node, i, key) <= 0) {
342 if (bval(geo, node, i)) {
343 longcpy(__key, bkey(geo, node, i), geo->keylen);
344 return bval(geo, node, i);
359 static int getpos(struct btree_geo *geo, unsigned long *node,
365 if (keycmp(geo, node, i, key) <= 0)
371 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
376 if (!bval(geo, node, i))
382 * locate the correct leaf node in the btree
387 unsigned long *node = head->node;
392 if (keycmp(geo, node, i, key) <= 0)
395 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
400 setkey(geo, node, i, key);
403 node = bval(geo, node, i);
405 BUG_ON(!node);
406 return node;
412 unsigned long *node;
415 node = btree_node_alloc(head, gfp);
416 if (!node)
418 if (head->node) {
419 fill = getfill(geo, head->node, 0);
420 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
421 setval(geo, node, 0, head->node);
423 head->node = node;
430 unsigned long *node;
436 node = head->node;
437 fill = getfill(geo, node, 0);
439 head->node = bval(geo, node, 0);
441 mempool_free(node, head->mempool);
448 unsigned long *node;
459 node = find_level(head, geo, key, level);
460 pos = getpos(geo, node, key);
461 fill = getfill(geo, node, pos);
463 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
466 /* need to split node */
473 bkey(geo, node, fill / 2 - 1),
480 setkey(geo, new, i, bkey(geo, node, i));
481 setval(geo, new, i, bval(geo, node, i));
482 setkey(geo, node, i, bkey(geo, node, i + fill / 2));
483 setval(geo, node, i, bval(geo, node, i + fill / 2));
484 clearpair(geo, node, i + fill / 2);
487 setkey(geo, node, i, bkey(geo, node, fill - 1));
488 setval(geo, node, i, bval(geo, node, fill - 1));
489 clearpair(geo, node, fill - 1);
497 setkey(geo, node, i, bkey(geo, node, i - 1));
498 setval(geo, node, i, bval(geo, node, i - 1));
500 setkey(geo, node, pos, key);
501 setval(geo, node, pos, val);
544 * can happen. Parent node contains a single child, this
545 * node, so merging with a sibling never happens.
590 unsigned long *node;
597 head->node = NULL;
601 node = find_level(head, geo, key, level);
602 pos = getpos(geo, node, key);
603 fill = getfill(geo, node, pos);
604 if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
606 ret = bval(geo, node, pos);
610 setkey(geo, node, i, bkey(geo, node, i + 1));
611 setval(geo, node, i, bval(geo, node, i + 1));
613 clearpair(geo, node, fill - 1);
617 rebalance(head, geo, key, level, node, fill - 1);
645 if (!(target->node)) {
647 target->node = victim->node;
673 unsigned long *node, unsigned long opaque,
683 child = bval(geo, node, i);
690 func(child, opaque, bkey(geo, node, i), count++,
694 mempool_free(node, head->mempool);
753 if (head->node)
754 count = __btree_for_each(head, geo, head->node, opaque, func,
771 if (head->node)
772 count = __btree_for_each(head, geo, head->node, opaque, func,