算法 - LINUX内核 - IDR实现分析

struct idr {
        struct radix_tree_root  idr_rt;
        unsigned int            idr_next;
};

// from radix-tree.h
struct radix_tree_root {
        gfp_t                   gfp_mask;
        struct radix_tree_node  __rcu *rnode;
};

/**
 * struct radix_tree_iter - radix tree iterator state
 *
 * @index:      index of current slot
 * @next_index: one beyond the last index for this chunk
 * @tags:       bit-mask for tag-iterating
 * @node:       node that contains current slot
 * @shift:      shift for the node that holds our slots
 *
 * This radix tree iterator works in terms of "chunks" of slots.  A chunk is a
 * subinterval of slots contained within one radix tree leaf node.  It is
 * described by a pointer to its first slot and a struct radix_tree_iter
 * which holds the chunk's position in the tree and its size.  For tagged
 * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
 * radix tree tag.
 */
struct radix_tree_iter {
        unsigned long   index;
        unsigned long   next_index;
        unsigned long   tags;
        struct radix_tree_node *node;
#ifdef CONFIG_RADIX_TREE_MULTIORDER
        unsigned int    shift;
#endif
};

/**
 * idr_alloc - allocate an id
 * @idr: idr handle
 * @ptr: pointer to be associated with the new id
 * @start: the minimum id (inclusive)
 * @end: the maximum id (exclusive)
 * @gfp: memory allocation flags
 *
 * Allocates an unused ID in the range [start, end).  Returns -ENOSPC
 * if there are no unused IDs in that range.
 *
 * Note that @end is treated as max when <= 0.  This is to always allow
 * using @start + N as @end as long as N is inside integer range.
 *
 * Simultaneous modifications to the @idr are not allowed and should be
 * prevented by the user, usually with a lock.  idr_alloc() may be called
 * concurrently with read-only accesses to the @idr, such as idr_find() and
 * idr_for_each_entry().
 */
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp);