Lines Matching defs:index
43 * The worst case is a zero height tree with just a single item at index 0,
44 * and then inserting an item at index ULONG_MAX. This requires 2 new branches
86 struct radix_tree_node **nodep, unsigned long index)
88 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
172 * @tag: the tag index
205 return iter->index & RADIX_TREE_MAP_MASK;
209 * The maximum index which can be stored in a radix tree
221 static unsigned long next_index(unsigned long index,
225 return (index & ~node_maxindex(node)) + (offset << node->shift);
406 * Extend a radix tree so it can store key @index.
409 unsigned long index, unsigned int shift)
417 while (index > shift_maxindex(maxshift))
585 * @index: index key
590 * at position @index in the radix tree @root.
599 unsigned long index, struct radix_tree_node **nodep,
606 unsigned long max = index;
636 offset = radix_tree_descend(node, &child, index);
698 * @index: index key
701 * Insert an item into the radix tree at position @index.
703 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
712 error = __radix_tree_create(root, index, &node, &slot);
736 * @index: index key
740 * Lookup and return the item at position @index in the radix
748 unsigned long index, struct radix_tree_node **nodep,
759 if (index > maxindex)
766 offset = radix_tree_descend(parent, &node, index);
784 * @index: index key
786 * Returns: the slot corresponding to the position @index in the
795 unsigned long index)
799 if (!__radix_tree_lookup(root, index, NULL, &slot))
808 * @index: index key
810 * Lookup the item at the position @index in the radix tree @root.
817 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
819 return __radix_tree_lookup(root, index, NULL, NULL);
957 * @index: index key
958 * @tag: tag index
961 * corresponding to @index in the radix tree. From
968 unsigned long index, unsigned int tag)
974 BUG_ON(index > maxindex);
980 offset = radix_tree_descend(parent, &node, index);
1018 * @index: index key
1019 * @tag: tag index
1022 * corresponding to @index in the radix tree. If this causes
1030 unsigned long index, unsigned int tag)
1037 if (index > maxindex)
1044 offset = radix_tree_descend(parent, &node, index);
1069 * @index: index key
1070 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
1082 unsigned long index, unsigned int tag)
1091 if (index > maxindex)
1098 offset = radix_tree_descend(parent, &node, index);
1139 iter->index = __radix_tree_iter_add(iter, 1);
1140 iter->next_index = iter->index;
1151 * @flags: RADIX_TREE_ITER_* flags and tag index
1159 unsigned long index, offset, maxindex;
1165 * Catch next_index overflow after ~0UL. iter->index never overflows
1173 index = iter->next_index;
1174 if (!index && iter->index)
1179 if (index > maxindex)
1186 iter->index = index;
1195 offset = radix_tree_descend(node, &child, index);
1213 index &= ~node_maxindex(node);
1214 index += offset << node->shift;
1216 if (!index)
1230 iter->index = (index &~ node_maxindex(node)) | offset;
1231 iter->next_index = (index | node_maxindex(node)) + 1;
1248 * Performs an index-ascending scan of the tree for present items. Places
1295 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1297 * Performs an index-ascending scan of the tree for present items which
1336 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1338 * Performs an index-ascending scan of the tree for present items which
1398 iter->index = iter->next_index;
1405 * @index: index key
1408 * Remove @item at @index from the radix tree rooted at @root.
1411 * or the entry at the given @index was not @item.
1414 unsigned long index, void *item)
1420 entry = __radix_tree_lookup(root, index, &node, &slot);
1439 * @index: index key
1441 * Remove the entry at @index from the radix tree rooted at @root.
1445 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1447 return radix_tree_delete_item(root, index, NULL);
1537 iter->index = start;