Lines Matching refs:node
58 * it states that the overflow field of node headers is used by internal nodes
59 * to point to another node that "effectively continues this one". Here is what
60 * I believe that means. Each key in internal nodes points to another node that
62 * in the internal node is not the last key in the index. Keys that are
63 * greater than the last key in the internal node go into the overflow node.
66 * Second, it states that the header of a btree node is sufficient to
79 * In memory structure of each btree node
82 befs_host_btree_nodehead head; /* head of node converted to cpu byteorder */
84 befs_btree_nodehead *od_node; /* on disk node */
100 struct befs_btree_node *node,
103 static int befs_leafnode(struct befs_btree_node *node);
105 static fs16 *befs_bt_keylen_index(struct befs_btree_node *node);
107 static fs64 *befs_bt_valarray(struct befs_btree_node *node);
109 static char *befs_bt_keydata(struct befs_btree_node *node);
112 struct befs_btree_node *node,
116 struct befs_btree_node *node,
172 * befs_bt_read_node - read in btree node and convert to cpu byteorder
175 * @node: Buffer in which to place the btree node
176 * @node_off: Starting offset (in bytes) of the node in @ds
178 * Calls befs_read_datastream to read in the indicated btree node and
181 * Note: node->bh must be NULL when this function is called the first time.
182 * Don't forget brelse(node->bh) after last call.
184 * On success, returns BEFS_OK and *@node contains the btree node that
185 * starts at @node_off, with the node->head fields in cpu byte order.
192 struct befs_btree_node *node, befs_off_t node_off)
198 if (node->bh)
199 brelse(node->bh);
201 node->bh = befs_read_datastream(sb, ds, node_off, &off);
202 if (!node->bh) {
204 "node at %llu", __func__, node_off);
209 node->od_node =
210 (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
212 befs_dump_index_node(sb, node->od_node);
214 node->head.left = fs64_to_cpu(sb, node->od_node->left);
215 node->head.right = fs64_to_cpu(sb, node->od_node->right);
216 node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);
217 node->head.all_key_count =
218 fs16_to_cpu(sb, node->od_node->all_key_count);
219 node->head.all_key_length =
220 fs16_to_cpu(sb, node->od_node->all_key_length);
241 * Once at the correct leaf node, use befs_find_key() again to get the
271 /* read in root node */
275 "node at %llu", node_off);
281 /* if no key set, try the overflow node */
286 "node at %llu", node_off);
291 /* at a leaf node now, check if it is correct */
316 * befs_find_key - Search for a key within a node
318 * @node: Node to find the key within
323 * If there is no match and node's value array is too small for key, return
325 * If no match and node should countain this key, return BEFS_BT_NOT_FOUND.
330 befs_find_key(struct super_block *sb, struct befs_btree_node *node,
344 /* if node can not contain key, just skip this node */
345 last = node->head.all_key_count - 1;
346 thiskey = befs_bt_get_key(sb, node, last, &keylen);
350 befs_debug(sb, "<--- node can't contain %s", findkey);
354 valarray = befs_bt_valarray(node);
363 thiskey = befs_bt_get_key(sb, node, mid, &keylen);
380 /* return an existing value so caller can arrive to a leaf node */
407 * node. If not, follow the node->right link to the next leafnode. Repeat
457 /* find the leaf node containing the key_no key */
478 befs_error(sb, "%s failed to read node at %llu",
487 /* get pointers to datastructures within the node body */
533 * @node_off: Pointer to offset of current node within datastream. Modified
537 * start of the first leaf node.
552 "node at %llu", __func__, *node_off);
555 befs_debug(sb, "Seekleaf to root node %llu", *node_off);
566 "an empty interior node: %llu. Using Overflow "
567 "node: %llu", __func__, *node_off,
576 "node at %llu", __func__, *node_off);
580 befs_debug(sb, "Seekleaf to child node %llu", *node_off);
582 befs_debug(sb, "Node %llu is a leaf node", *node_off);
592 * befs_leafnode - Determine if the btree node is a leaf node or an
593 * interior node
594 * @node: Pointer to node structure to test
599 befs_leafnode(struct befs_btree_node *node)
601 /* all interior nodes (and only interior nodes) have an overflow node */
602 if (node->head.overflow == BEFS_BT_INVAL)
609 * befs_bt_keylen_index - Finds start of keylen index in a node
610 * @node: Pointer to the node structure to find the keylen index within
613 * of the B+tree node *@node
615 * "The length of all the keys in the node is added to the size of the
622 befs_bt_keylen_index(struct befs_btree_node *node)
626 (sizeof (befs_btree_nodehead) + node->head.all_key_length);
632 return (fs16 *) ((void *) node->od_node + off);
636 * befs_bt_valarray - Finds the start of value array in a node
637 * @node: Pointer to the node structure to find the value array within
640 * of the node pointed to by the node header
643 befs_bt_valarray(struct befs_btree_node *node)
645 void *keylen_index_start = (void *) befs_bt_keylen_index(node);
646 size_t keylen_index_size = node->head.all_key_count * sizeof (fs16);
652 * befs_bt_keydata - Finds start of keydata array in a node
653 * @node: Pointer to the node structure to find the keydata array within
656 * of the node pointed to by the node header
659 befs_bt_keydata(struct befs_btree_node *node)
661 return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
667 * @node: node in which to look for the key
671 * Returns a valid pointer into @node on success.
675 befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
682 if (index < 0 || index > node->head.all_key_count) {
687 keystart = befs_bt_keydata(node);
688 keylen_index = befs_bt_keylen_index(node);