Lines Matching refs:index
254 * Extend a radix tree so it can store key @index.
256 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
264 while (index > radix_tree_maxindex(height))
300 * @index: index key
303 * Insert an item into the radix tree at position @index.
306 unsigned long index, void *item)
316 if (index > radix_tree_maxindex(root->height)) {
317 error = radix_tree_extend(root, index);
342 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
372 unsigned long index, int is_slot)
382 if (index > 0)
389 if (index > radix_tree_maxindex(height))
396 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
411 * @index: index key
413 * Returns: the slot corresponding to the position @index in the
421 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
423 return (void **)radix_tree_lookup_element(root, index, 1);
430 * @index: index key
432 * Lookup the item at the position @index in the radix tree @root.
439 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
441 return radix_tree_lookup_element(root, index, 0);
448 * @index: index key
449 * @tag: tag index
452 * corresponding to @index in the radix tree. From
459 unsigned long index, unsigned int tag)
465 BUG_ON(index > radix_tree_maxindex(height));
473 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
493 * @index: index key
494 * @tag: tag index
497 * corresponding to @index in the radix tree. If
505 unsigned long index, unsigned int tag)
516 if (index > radix_tree_maxindex(height))
529 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
562 * @index: index key
563 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
575 unsigned long index, unsigned int tag)
590 return (index == 0);
594 if (index > radix_tree_maxindex(height))
605 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
626 * @first_indexp: pointer to a starting index of a range to scan
627 * @last_index: last index of a range to scan
629 * @iftag: tag index to test
630 * @settag: tag index to set if tested tag is set
640 * we can get to the leaf node and find that the index that has the iftag
645 * *first_indexp to the first unscanned index.
660 unsigned long index = *first_indexp;
663 if (index > last_index)
681 * we fill the path from (root->height - 2) to 0, leaving the index at
690 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
721 index = ((index >> shift) + 1) << shift;
723 if (index > last_index || !index)
727 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
743 *first_indexp = index;
753 * @index: index key
756 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
759 * Returns: the index of the hole if found, otherwise returns an index
760 * outside of the set specified (in which case 'return - index >= max_scan'
761 * will be true). In rare cases of index wrap-around, 0 will be returned.
766 * at index 5, then subsequently a hole is created at index 10,
771 unsigned long index, unsigned long max_scan)
776 if (!radix_tree_lookup(root, index))
778 index++;
779 if (index == 0)
783 return index;
790 * @index: index key
793 * Search backwards in the range [max(index-max_scan+1, 0), index]
796 * Returns: the index of the hole if found, otherwise returns an index
797 * outside of the set specified (in which case 'index - return >= max_scan'
803 * at index 10, then subsequently a hole is created at index 5,
808 unsigned long index, unsigned long max_scan)
813 if (!radix_tree_lookup(root, index))
815 index--;
816 if (index == ULONG_MAX)
820 return index;
825 __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
838 i = (index >> shift) & RADIX_TREE_MAP_MASK;
842 index &= ~((1UL << shift) - 1);
843 index += 1UL << shift;
844 if (index == 0)
858 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
859 index++;
867 *next_index = index;
878 * Performs an index-ascending scan of the tree for present items. Places
949 * Performs an index-ascending scan of the tree for present items. Places
1002 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
1014 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
1019 index &= ~((1UL << shift) - 1);
1020 index += 1UL << shift;
1021 if (index == 0)
1029 unsigned long j = index & RADIX_TREE_MAP_MASK;
1032 index++;
1058 *next_index = index;
1069 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1071 * Performs an index-ascending scan of the tree for present items which
1139 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1141 * Performs an index-ascending scan of the tree for present items which
1258 * @index: index key
1260 * Remove the item at @index from the radix tree rooted at @root.
1264 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1278 if (index > radix_tree_maxindex(height))
1297 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1313 radix_tree_tag_clear(root, index, tag);