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)
261 if (!node)
265 if (keycmp(geo, node, i, key) == 0)
266 return bval(geo, node, i);
275 unsigned long *node = head->node;
282 if (keycmp(geo, node, i, key) <= 0)
286 node = bval(geo, node, i);
287 if (!node)
291 if (!node)
295 if (keycmp(geo, node, i, key) == 0) {
296 setval(geo, node, i, val);
305 * a parent node may be smaller than the smallest key of all its siblings.
315 unsigned long *node, *oldnode;
327 node = head->node;
330 if (keycmp(geo, node, i, key) <= 0)
334 oldnode = node;
335 node = bval(geo, node, i);
336 if (!node)
341 if (!node)
345 if (keycmp(geo, node, i, key) <= 0) {
346 if (bval(geo, node, i)) {
347 longcpy(__key, bkey(geo, node, i), geo->keylen);
348 return bval(geo, node, i);
363 static int getpos(struct btree_geo *geo, unsigned long *node,
369 if (keycmp(geo, node, i, key) <= 0)
375 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
380 if (!bval(geo, node, i))
386 * locate the correct leaf node in the btree
391 unsigned long *node = head->node;
396 if (keycmp(geo, node, i, key) <= 0)
399 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
404 setkey(geo, node, i, key);
407 node = bval(geo, node, i);
409 BUG_ON(!node);
410 return node;
416 unsigned long *node;
419 node = btree_node_alloc(head, gfp);
420 if (!node)
422 if (head->node) {
423 fill = getfill(geo, head->node, 0);
424 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
425 setval(geo, node, 0, head->node);
427 head->node = node;
434 unsigned long *node;
440 node = head->node;
441 fill = getfill(geo, node, 0);
443 head->node = bval(geo, node, 0);
445 mempool_free(node, head->mempool);
452 unsigned long *node;
463 node = find_level(head, geo, key, level);
464 pos = getpos(geo, node, key);
465 fill = getfill(geo, node, pos);
467 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
470 /* need to split node */
477 bkey(geo, node, fill / 2 - 1),
484 setkey(geo, new, i, bkey(geo, node, i));
485 setval(geo, new, i, bval(geo, node, i));
486 setkey(geo, node, i, bkey(geo, node, i + fill / 2));
487 setval(geo, node, i, bval(geo, node, i + fill / 2));
488 clearpair(geo, node, i + fill / 2);
491 setkey(geo, node, i, bkey(geo, node, fill - 1));
492 setval(geo, node, i, bval(geo, node, fill - 1));
493 clearpair(geo, node, fill - 1);
501 setkey(geo, node, i, bkey(geo, node, i - 1));
502 setval(geo, node, i, bval(geo, node, i - 1));
504 setkey(geo, node, pos, key);
505 setval(geo, node, pos, val);
548 * can happen. Parent node contains a single child, this
549 * node, so merging with a sibling never happens.
594 unsigned long *node;
601 head->node = NULL;
605 node = find_level(head, geo, key, level);
606 pos = getpos(geo, node, key);
607 fill = getfill(geo, node, pos);
608 if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
610 ret = bval(geo, node, pos);
614 setkey(geo, node, i, bkey(geo, node, i + 1));
615 setval(geo, node, i, bval(geo, node, i + 1));
617 clearpair(geo, node, fill - 1);
621 rebalance(head, geo, key, level, node, fill - 1);
649 if (!(target->node)) {
651 target->node = victim->node;
677 unsigned long *node, unsigned long opaque,
687 child = bval(geo, node, i);
694 func(child, opaque, bkey(geo, node, i), count++,
698 mempool_free(node, head->mempool);
757 if (head->node)
758 count = __btree_for_each(head, geo, head->node, opaque, func,
775 if (head->node)
776 count = __btree_for_each(head, geo, head->node, opaque, func,