Lines Matching refs:index
41 * The worst case is a zero height tree with just a single item at index 0,
42 * and then inserting an item at index ULONG_MAX. This requires 2 new branches
84 struct radix_tree_node **nodep, unsigned long index)
86 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
203 return iter->index & RADIX_TREE_MAP_MASK;
207 * The maximum index which can be stored in a radix tree
219 static unsigned long next_index(unsigned long index,
223 return (index & ~node_maxindex(node)) + (offset << node->shift);
404 * Extend a radix tree so it can store key @index.
407 unsigned long index, unsigned int shift)
415 while (index > shift_maxindex(maxshift))
583 * @index: index key
588 * at position @index in the radix tree @root.
597 unsigned long index, struct radix_tree_node **nodep,
604 unsigned long max = index;
634 offset = radix_tree_descend(node, &child, index);
696 * @index: index key
699 * Insert an item into the radix tree at position @index.
701 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
710 error = __radix_tree_create(root, index, &node, &slot);
734 * @index: index key
738 * Lookup and return the item at position @index in the radix
746 unsigned long index, struct radix_tree_node **nodep,
757 if (index > maxindex)
764 offset = radix_tree_descend(parent, &node, index);
782 * @index: index key
784 * Returns: the slot corresponding to the position @index in the
793 unsigned long index)
797 if (!__radix_tree_lookup(root, index, NULL, &slot))
806 * @index: index key
808 * Lookup the item at the position @index in the radix tree @root.
815 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
817 return __radix_tree_lookup(root, index, NULL, NULL);
954 * @index: index key
955 * @tag: tag index
958 * corresponding to @index in the radix tree. From
965 unsigned long index, unsigned int tag)
971 BUG_ON(index > maxindex);
977 offset = radix_tree_descend(parent, &node, index);
1015 * @index: index key
1016 * @tag: tag index
1019 * corresponding to @index in the radix tree. If this causes
1027 unsigned long index, unsigned int tag)
1034 if (index > maxindex)
1041 offset = radix_tree_descend(parent, &node, index);
1066 * @index: index key
1067 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
1079 unsigned long index, unsigned int tag)
1088 if (index > maxindex)
1095 offset = radix_tree_descend(parent, &node, index);
1136 iter->index = __radix_tree_iter_add(iter, 1);
1137 iter->next_index = iter->index;
1148 * @flags: RADIX_TREE_ITER_* flags and tag index
1156 unsigned long index, offset, maxindex;
1162 * Catch next_index overflow after ~0UL. iter->index never overflows
1170 index = iter->next_index;
1171 if (!index && iter->index)
1176 if (index > maxindex)
1183 iter->index = index;
1192 offset = radix_tree_descend(node, &child, index);
1210 index &= ~node_maxindex(node);
1211 index += offset << node->shift;
1213 if (!index)
1227 iter->index = (index &~ node_maxindex(node)) | offset;
1228 iter->next_index = (index | node_maxindex(node)) + 1;
1245 * Performs an index-ascending scan of the tree for present items. Places
1292 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1294 * Performs an index-ascending scan of the tree for present items which
1333 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1335 * Performs an index-ascending scan of the tree for present items which
1395 iter->index = iter->next_index;
1402 * @index: index key
1405 * Remove @item at @index from the radix tree rooted at @root.
1408 * or the entry at the given @index was not @item.
1411 unsigned long index, void *item)
1417 entry = __radix_tree_lookup(root, index, &node, &slot);
1436 * @index: index key
1438 * Remove the entry at @index from the radix tree rooted at @root.
1442 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1444 return radix_tree_delete_item(root, index, NULL);
1534 iter->index = start;