Lines Matching defs:node
86 static int insert_at(size_t value_size, struct btree_node *node, unsigned int index,
90 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);
91 uint32_t max_entries = le32_to_cpu(node->header.max_entries);
97 DMERR("too many entries in btree node for insert");
104 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le);
105 array_insert(value_base(node), value_size, nr_entries, index, value);
106 node->header.nr_entries = cpu_to_le32(nr_entries + 1);
227 * This is a shared node, so we can just decrement it's
424 struct dm_block *node;
427 r = bn_read_lock(info, root, &node);
431 n = dm_block_data(node);
466 dm_tm_unlock(info->tm, node);
504 * Copies entries from one region of a btree node to another. The regions
518 * Moves entries from one region fo a btree node to another. The regions
532 * Erases the first 'count' entries of a btree node, shifting following
541 * Moves entries in a btree node up 'count' places, making space for
542 * new entries at the start of the node.
580 * node is empty.
625 * Splits a node by creating a sibling node and shifting half the nodes
626 * contents across. Assumes there is a parent node, and it has room for
703 * We often need to modify a sibling node. This function shadows a particular
704 * child of the given parent node. Making sure to update the parent to point
713 struct btree_node *node;
722 node = dm_block_data(*result);
725 inc_children(info->tm, node, vt);
818 * Splits a node by creating two new children beneath the given node.
913 * Redistributes a node's entries with its left sibling.
971 * Returns the number of spare entries in a node.
978 struct btree_node *node;
984 node = dm_block_data(block);
985 nr_entries = le32_to_cpu(node->header.nr_entries);
986 *space = le32_to_cpu(node->header.max_entries) - nr_entries;
993 * Make space in a node, either by moving some entries to a sibling,
994 * or creating a new sibling node. SPACE_THRESHOLD defines the minimum
1047 * We need to split the node, normally we split two nodes
1050 * a single node into two.
1061 * Does the node contain a particular key?
1063 static bool contains_key(struct btree_node *node, uint64_t key)
1065 int i = lower_bound(node, key);
1067 if (i >= 0 && le64_to_cpu(node->keys[i]) == key)
1075 * node on the spine when doing an insert. But we can avoid that with
1078 static bool has_space_for_insert(struct btree_node *node, uint64_t key)
1080 if (node->header.nr_entries == node->header.max_entries) {
1081 if (le32_to_cpu(node->header.flags) & LEAF_NODE) {
1083 return contains_key(node, key);
1097 struct btree_node *node;
1104 node = dm_block_data(shadow_current(s));
1107 * We have to patch up the parent node, ugly, but I don't
1119 node = dm_block_data(shadow_current(s));
1121 if (!has_space_for_insert(node, key)) {
1130 /* making space can cause the current node to change */
1131 node = dm_block_data(shadow_current(s));
1134 i = lower_bound(node, key);
1136 if (le32_to_cpu(node->header.flags) & LEAF_NODE)
1141 node->keys[0] = cpu_to_le64(key);
1145 root = value64(node, i);
1149 if (i < 0 || le64_to_cpu(node->keys[i]) != key)
1160 struct btree_node *node;
1168 node = dm_block_data(shadow_current(s));
1171 * We have to patch up the parent node, ugly, but I don't
1183 node = dm_block_data(shadow_current(s));
1184 i = lower_bound(node, key);
1187 BUG_ON(i >= le32_to_cpu(node->header.nr_entries));
1189 if (le32_to_cpu(node->header.flags) & LEAF_NODE) {
1190 if (key != le64_to_cpu(node->keys[i]))
1195 root = value64(node, i);
1227 static bool need_insert(struct btree_node *node, uint64_t *keys,
1230 return ((index >= le32_to_cpu(node->header.nr_entries)) ||
1231 (le64_to_cpu(node->keys[index]) != keys[level]));
1427 struct dm_block *node;
1431 r = bn_read_lock(info, block, &node);
1435 n = dm_block_data(node);
1452 dm_tm_unlock(info->tm, node);
1498 DMERR("couldn't push cursor node, stack depth too high");