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 radixtree.h.
#define RADIX_TREE_EXCEPTIONAL_ENTRY 2 
Definition at line 51 of file radixtree.h.
#define RADIX_TREE_EXCEPTIONAL_SHIFT 2 
Definition at line 52 of file radixtree.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 radixtree.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 radixtree.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 radixtree.h.
radix_tree_for_each_slot  iterate over nonempty 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 radixtree.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 radixtree.h.
#define RADIX_TREE_INDIRECT_PTR 1 
Definition at line 44 of file radixtree.h.
#define RADIX_TREE_INIT  (  mask  ) 
Definition at line 70 of file radixtree.h.
#define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */ 
Definition at line 283 of file radixtree.h.
#define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */ 
Definition at line 281 of file radixtree.h.
#define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */ 
Definition at line 282 of file radixtree.h.
#define RADIX_TREE_MAX_TAGS 3 
Definition at line 61 of file radixtree.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 indexascending 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 radixtree.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 indexascending 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 radixtree.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 indexascending 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 radixtree.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 indexascending 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 radixtree.c.
Definition at line 1447 of file radixtree.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 radixtree.c.
unsigned long radix_tree_locate_item  (  struct radix_tree_root *  root, 
void *  item  
) 
Definition at line 1230 of file radixtree.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 radixtree.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 updateifexists 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 radixtree.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 radixtree.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 (notpresent entry) : tree root : index key : maximum range to search
Search the set [index, min(index+max_scan1, 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 wraparound, 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 radixtree.c.
int radix_tree_preload  (  gfp_t  gfp_mask  ) 
Definition at line 267 of file radixtree.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 (notpresent entry) : tree root : index key : maximum range to search
Search backwards in the range [max(indexmax_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 wraparound, 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 radixtree.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 radixtree.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 nexttoleaf 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 radixtree.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 radixtree.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 notpresent item is a bug.
Definition at line 514 of file radixtree.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 radixtree.c.