|
Linux Kernel
3.7.1
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
|
Linux Kernel
3.7.1
|
#include <linux/preempt.h>#include <linux/types.h>#include <linux/bug.h>#include <linux/kernel.h>#include <linux/rcupdate.h>Go to the source code of this file.
Data Structures | |
| struct | radix_tree_root |
| struct | radix_tree_iter |
Macros | |
| #define | RADIX_TREE_INDIRECT_PTR 1 |
| #define | RADIX_TREE_EXCEPTIONAL_ENTRY 2 |
| #define | RADIX_TREE_EXCEPTIONAL_SHIFT 2 |
| #define | RADIX_TREE_MAX_TAGS 3 |
| #define | RADIX_TREE_INIT(mask) |
| #define | RADIX_TREE(name, mask) struct radix_tree_root name = RADIX_TREE_INIT(mask) |
| #define | INIT_RADIX_TREE(root, mask) |
| #define | RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */ |
| #define | RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */ |
| #define | RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */ |
| #define | radix_tree_for_each_chunk(slot, root, iter, start, flags) |
| #define | radix_tree_for_each_chunk_slot(slot, iter, flags) for (; slot ; slot = radix_tree_next_slot(slot, iter, flags)) |
| #define | radix_tree_for_each_slot(slot, root, iter, start) |
| #define | radix_tree_for_each_contig(slot, root, iter, start) |
| #define | radix_tree_for_each_tagged(slot, root, iter, start, tag) |
| #define RADIX_TREE | ( | name, | |
| mask | |||
| ) | struct radix_tree_root name = RADIX_TREE_INIT(mask) |
Definition at line 76 of file radix-tree.h.
| #define RADIX_TREE_EXCEPTIONAL_ENTRY 2 |
Definition at line 51 of file radix-tree.h.
| #define RADIX_TREE_EXCEPTIONAL_SHIFT 2 |
Definition at line 52 of file radix-tree.h.
radix_tree_for_each_chunk - iterate over chunks
: the void** variable for pointer to chunk first slot : the struct radix_tree_root pointer : the struct radix_tree_iter pointer : iteration starting index : RADIX_TREE_ITER_* and tag index
Locks can be released and reacquired between iterations.
Definition at line 392 of file radix-tree.h.
| #define radix_tree_for_each_chunk_slot | ( | slot, | |
| iter, | |||
| flags | |||
| ) | for (; slot ; slot = radix_tree_next_slot(slot, iter, flags)) |
radix_tree_for_each_chunk_slot - iterate over slots in one chunk
: the void** variable, at the beginning points to chunk first slot : the struct radix_tree_iter pointer : RADIX_TREE_ITER_*, should be constant
This macro is designed to be nested inside radix_tree_for_each_chunk(). points to the radix tree slot, ->index contains its index.
Definition at line 406 of file radix-tree.h.
radix_tree_for_each_contig - iterate over contiguous slots
: the void** variable for pointer to slot : the struct radix_tree_root pointer : the struct radix_tree_iter pointer : iteration starting index
points to radix tree slot, ->index contains its index.
Definition at line 434 of file radix-tree.h.
radix_tree_for_each_slot - iterate over non-empty slots
: the void** variable for pointer to slot : the struct radix_tree_root pointer : the struct radix_tree_iter pointer : iteration starting index
points to radix tree slot, ->index contains its index.
Definition at line 419 of file radix-tree.h.
radix_tree_for_each_tagged - iterate over tagged slots
: the void** variable for pointer to slot : the struct radix_tree_root pointer : the struct radix_tree_iter pointer : iteration starting index : tag index
points to radix tree slot, ->index contains its index.
Definition at line 452 of file radix-tree.h.
| #define RADIX_TREE_INDIRECT_PTR 1 |
Definition at line 44 of file radix-tree.h.
| #define RADIX_TREE_INIT | ( | mask | ) |
Definition at line 70 of file radix-tree.h.
| #define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */ |
Definition at line 283 of file radix-tree.h.
| #define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */ |
Definition at line 281 of file radix-tree.h.
| #define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */ |
Definition at line 282 of file radix-tree.h.
| #define RADIX_TREE_MAX_TAGS 3 |
Definition at line 61 of file radix-tree.h.
| void* radix_tree_delete | ( | struct radix_tree_root * | root, |
| unsigned long | index | ||
| ) |
| unsigned int radix_tree_gang_lookup | ( | struct radix_tree_root * | root, |
| void ** | results, | ||
| unsigned long | first_index, | ||
| unsigned int | max_items | ||
| ) |
radix_tree_gang_lookup - perform multiple lookup on a radix tree : radix tree root : where the results of the lookup are placed : start the lookup from this key : place up to this many items at *results
Performs an index-ascending scan of the tree for present items. Places them at * and returns the number of items which were placed at *.
The implementation is naive.
Like radix_tree_lookup, radix_tree_gang_lookup may be called under rcu_read_lock. In this case, rather than the returned results being an atomic snapshot of the tree at a single point in time, the semantics of an RCU protected gang lookup are as though multiple radix_tree_lookups have been issued in individual locks, and results stored in 'results'.
Definition at line 1007 of file radix-tree.c.
| unsigned int radix_tree_gang_lookup_slot | ( | struct radix_tree_root * | root, |
| void *** | results, | ||
| unsigned long * | indices, | ||
| unsigned long | first_index, | ||
| unsigned int | max_items | ||
| ) |
radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree : radix tree root : where the results of the lookup are placed : where their indices should be placed (but usually NULL) : start the lookup from this key : place up to this many items at *results
Performs an index-ascending scan of the tree for present items. Places their slots at * and returns the number of items which were placed at *.
The implementation is naive.
Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must be dereferenced with radix_tree_deref_slot, and if using only RCU protection, radix_tree_deref_slot may fail requiring a retry.
Definition at line 1048 of file radix-tree.c.
| unsigned int radix_tree_gang_lookup_tag | ( | struct radix_tree_root * | root, |
| void ** | results, | ||
| unsigned long | first_index, | ||
| unsigned int | max_items, | ||
| unsigned int | tag | ||
| ) |
radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree based on a tag : radix tree root : where the results of the lookup are placed : start the lookup from this key : place up to this many items at *results : the tag index (< RADIX_TREE_MAX_TAGS)
Performs an index-ascending scan of the tree for present items which have the tag indexed by set. Places the items at * and returns the number of items which were placed at *.
Definition at line 1085 of file radix-tree.c.
| unsigned int radix_tree_gang_lookup_tag_slot | ( | struct radix_tree_root * | root, |
| void *** | results, | ||
| unsigned long | first_index, | ||
| unsigned int | max_items, | ||
| unsigned int | tag | ||
| ) |
radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a radix tree based on a tag : radix tree root : where the results of the lookup are placed : start the lookup from this key : place up to this many items at *results : the tag index (< RADIX_TREE_MAX_TAGS)
Performs an index-ascending scan of the tree for present items which have the tag indexed by set. Places the slots at * and returns the number of slots which were placed at *.
Definition at line 1122 of file radix-tree.c.
Definition at line 1447 of file radix-tree.c.
| int radix_tree_insert | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| void * | item | ||
| ) |
radix_tree_insert - insert into a radix tree : radix tree root : index key : item to insert
Insert an item into the radix tree at position .
Definition at line 360 of file radix-tree.c.
| unsigned long radix_tree_locate_item | ( | struct radix_tree_root * | root, |
| void * | item | ||
| ) |
Definition at line 1230 of file radix-tree.c.
| void* radix_tree_lookup | ( | struct radix_tree_root * | root, |
| unsigned long | index | ||
| ) |
radix_tree_lookup - perform lookup operation on a radix tree : radix tree root : index key
Lookup the item at the position in the radix tree .
This function can be called under rcu_read_lock, however the caller must manage lifetimes of leaf nodes (eg. RCU may also be used to free them safely). No RCU barriers are required to access or modify the returned item, however.
Definition at line 495 of file radix-tree.c.
| void** radix_tree_lookup_slot | ( | struct radix_tree_root * | root, |
| unsigned long | index | ||
| ) |
radix_tree_lookup_slot - lookup a slot in a radix tree : radix tree root : index key
Returns: the slot corresponding to the position in the radix tree . This is useful for update-if-exists operations.
This function can be called under rcu_read_lock iff the slot is not modified by radix_tree_replace_slot, otherwise it must be called exclusive from other writers. Any dereference of the slot must be done using radix_tree_deref_slot.
Definition at line 477 of file radix-tree.c.
| void** radix_tree_next_chunk | ( | struct radix_tree_root * | root, |
| struct radix_tree_iter * | iter, | ||
| unsigned | flags | ||
| ) |
radix_tree_next_chunk - find next chunk of slots for iteration
: radix tree root : iterator state : RADIX_TREE_ITER_* flags and tag index Returns: pointer to chunk first slot, or NULL if there no more left
This function looks up the next chunk in the radix tree starting from ->next_index. It returns a pointer to the chunk's first slot. Also it fills with data about chunk: position in the tree (index), its end (next_index), and constructs a bit mask for tagged iterating (tags).
radix_tree_next_chunk - find next chunk of slots for iteration
: radix tree root : iterator state : RADIX_TREE_ITER_* flags and tag index Returns: pointer to chunk first slot, or NULL if iteration is over
Definition at line 674 of file radix-tree.c.
| unsigned long radix_tree_next_hole | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| unsigned long | max_scan | ||
| ) |
radix_tree_next_hole - find the next hole (not-present entry) : tree root : index key : maximum range to search
Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest indexed hole.
Returns: the index of the hole if found, otherwise returns an index outside of the set specified (in which case 'return - index >= max_scan' will be true). In rare cases of index wrap-around, 0 will be returned.
radix_tree_next_hole may be called under rcu_read_lock. However, like radix_tree_gang_lookup, this will not atomically search a snapshot of the tree at a single point in time. For example, if a hole is created at index 5, then subsequently a hole is created at index 10, radix_tree_next_hole covering both indexes may return 10 if called under rcu_read_lock.
Definition at line 933 of file radix-tree.c.
| int radix_tree_preload | ( | gfp_t | gfp_mask | ) |
Definition at line 267 of file radix-tree.c.
| unsigned long radix_tree_prev_hole | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| unsigned long | max_scan | ||
| ) |
radix_tree_prev_hole - find the prev hole (not-present entry) : tree root : index key : maximum range to search
Search backwards in the range [max(index-max_scan+1, 0), index] for the first hole.
Returns: the index of the hole if found, otherwise returns an index outside of the set specified (in which case 'index - return >= max_scan' will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
radix_tree_next_hole may be called under rcu_read_lock. However, like radix_tree_gang_lookup, this will not atomically search a snapshot of the tree at a single point in time. For example, if a hole is created at index 10, then subsequently a hole is created at index 5, radix_tree_prev_hole covering both indexes may return 5 if called under rcu_read_lock.
Definition at line 970 of file radix-tree.c.
| unsigned long radix_tree_range_tag_if_tagged | ( | struct radix_tree_root * | root, |
| unsigned long * | first_indexp, | ||
| unsigned long | last_index, | ||
| unsigned long | nr_to_tag, | ||
| unsigned int | iftag, | ||
| unsigned int | settag | ||
| ) |
radix_tree_range_tag_if_tagged - for each item in given range set given tag if item has another tag set : radix tree root : pointer to a starting index of a range to scan : last index of a range to scan : maximum number items to tag : tag index to test : tag index to set if tested tag is set
This function scans range of radix tree from first_index to last_index (inclusive). For each item in the range if iftag is set, the function sets also settag. The function stops either after tagging nr_to_tag items or after reaching last_index.
The tags must be set from the leaf level only and propagated back up the path to the root. We must do this so that we resolve the full path before setting any tags on intermediate nodes. If we set tags as we descend, then we can get to the leaf node and find that the index that has the iftag set is outside the range we are scanning. This reults in dangling tags and can lead to problems with later tag operations (e.g. livelocks on lookups).
The function returns number of leaves where the tag was set and sets *first_indexp to the first unscanned index. WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must be prepared to handle that.
Definition at line 809 of file radix-tree.c.
| void* radix_tree_tag_clear | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| unsigned int | tag | ||
| ) |
radix_tree_tag_clear - clear a tag on a radix tree node : radix tree root : index key : tag index
Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) corresponding to in the radix tree. If this causes the leaf node to have no tags set then clear the tag in the next-to-leaf node, etc.
Returns the address of the tagged item on success, else NULL. ie: has the same return value and semantics as radix_tree_lookup().
Definition at line 560 of file radix-tree.c.
| int radix_tree_tag_get | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| unsigned int | tag | ||
| ) |
radix_tree_tag_get - get a tag on a radix tree node : radix tree root : index key : tag index (< RADIX_TREE_MAX_TAGS)
Return values:
0: tag not present or not set 1: tag set
Note that the return value of this function may not be relied on, even if the RCU lock is held, unless tag modification and node deletion are excluded from concurrency.
Definition at line 624 of file radix-tree.c.
| void* radix_tree_tag_set | ( | struct radix_tree_root * | root, |
| unsigned long | index, | ||
| unsigned int | tag | ||
| ) |
radix_tree_tag_set - set a tag on a radix tree node : radix tree root : index key : tag index
Set the search tag (which must be < RADIX_TREE_MAX_TAGS) corresponding to in the radix tree. From the root all the way down to the leaf node.
Returns the address of the tagged item. Setting a tag on a not-present item is a bug.
Definition at line 514 of file radix-tree.c.
| int radix_tree_tagged | ( | struct radix_tree_root * | root, |
| unsigned int | tag | ||
| ) |
radix_tree_tagged - test whether any items in the tree are tagged : radix tree root : tag to test
Definition at line 1395 of file radix-tree.c.
1.8.2