Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Data Structures | Macros | Functions
idr.h File Reference
#include <linux/types.h>
#include <linux/bitops.h>
#include <linux/init.h>
#include <linux/rcupdate.h>

Go to the source code of this file.

Data Structures

struct  idr_layer
 
struct  idr
 
struct  ida_bitmap
 
struct  ida
 

Macros

#define IDR_SIZE   (1 << IDR_BITS)
 
#define IDR_MASK   ((1 << IDR_BITS)-1)
 
#define MAX_IDR_SHIFT   (sizeof(int)*8 - 1)
 
#define MAX_IDR_BIT   (1U << MAX_IDR_SHIFT)
 
#define MAX_IDR_MASK   (MAX_IDR_BIT - 1)
 
#define MAX_IDR_LEVEL   ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS)
 
#define MAX_IDR_FREE   (MAX_IDR_LEVEL * 2)
 
#define IDR_INIT(name)
 
#define DEFINE_IDR(name)   struct idr name = IDR_INIT(name)
 
#define IDR_NEED_TO_GROW   -2
 
#define IDR_NOMORE_SPACE   -3
 
#define _idr_rc_to_errno(rc)   ((rc) == -1 ? -EAGAIN : -ENOSPC)
 
#define IDA_CHUNK_SIZE   128 /* 128 bytes per chunk */
 
#define IDA_BITMAP_LONGS   (IDA_CHUNK_SIZE / sizeof(long) - 1)
 
#define IDA_BITMAP_BITS   (IDA_BITMAP_LONGS * sizeof(long) * 8)
 
#define IDA_INIT(name)   { .idr = IDR_INIT(name), .free_bitmap = NULL, }
 
#define DEFINE_IDA(name)   struct ida name = IDA_INIT(name)
 

Functions

voididr_find (struct idr *idp, int id)
 
int idr_pre_get (struct idr *idp, gfp_t gfp_mask)
 
int idr_get_new (struct idr *idp, void *ptr, int *id)
 
int idr_get_new_above (struct idr *idp, void *ptr, int starting_id, int *id)
 
int idr_for_each (struct idr *idp, int(*fn)(int id, void *p, void *data), void *data)
 
voididr_get_next (struct idr *idp, int *nextid)
 
voididr_replace (struct idr *idp, void *ptr, int id)
 
void idr_remove (struct idr *idp, int id)
 
void idr_remove_all (struct idr *idp)
 
void idr_destroy (struct idr *idp)
 
void idr_init (struct idr *idp)
 
int ida_pre_get (struct ida *ida, gfp_t gfp_mask)
 
int ida_get_new_above (struct ida *ida, int starting_id, int *p_id)
 
int ida_get_new (struct ida *ida, int *p_id)
 
void ida_remove (struct ida *ida, int id)
 
void ida_destroy (struct ida *ida)
 
void ida_init (struct ida *ida)
 
int ida_simple_get (struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask)
 
void ida_simple_remove (struct ida *ida, unsigned int id)
 
void __init idr_init_cache (void)
 

Macro Definition Documentation

#define _idr_rc_to_errno (   rc)    ((rc) == -1 ? -EAGAIN : -ENOSPC)

Definition at line 81 of file idr.h.

#define DEFINE_IDA (   name)    struct ida name = IDA_INIT(name)

Definition at line 140 of file idr.h.

#define DEFINE_IDR (   name)    struct idr name = IDR_INIT(name)

Definition at line 75 of file idr.h.

#define IDA_BITMAP_BITS   (IDA_BITMAP_LONGS * sizeof(long) * 8)

Definition at line 127 of file idr.h.

#define IDA_BITMAP_LONGS   (IDA_CHUNK_SIZE / sizeof(long) - 1)

Definition at line 126 of file idr.h.

#define IDA_CHUNK_SIZE   128 /* 128 bytes per chunk */

Definition at line 125 of file idr.h.

#define IDA_INIT (   name)    { .idr = IDR_INIT(name), .free_bitmap = NULL, }

Definition at line 139 of file idr.h.

#define IDR_INIT (   name)
Value:
{ \
.top = NULL, \
.id_free = NULL, \
.layers = 0, \
.id_free_cnt = 0, \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
}

Definition at line 67 of file idr.h.

#define IDR_MASK   ((1 << IDR_BITS)-1)

Definition at line 39 of file idr.h.

#define IDR_NEED_TO_GROW   -2

Definition at line 78 of file idr.h.

#define IDR_NOMORE_SPACE   -3

Definition at line 79 of file idr.h.

#define IDR_SIZE   (1 << IDR_BITS)

Definition at line 38 of file idr.h.

#define MAX_IDR_BIT   (1U << MAX_IDR_SHIFT)

Definition at line 42 of file idr.h.

#define MAX_IDR_FREE   (MAX_IDR_LEVEL * 2)

Definition at line 49 of file idr.h.

#define MAX_IDR_LEVEL   ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS)

Definition at line 46 of file idr.h.

#define MAX_IDR_MASK   (MAX_IDR_BIT - 1)

Definition at line 43 of file idr.h.

#define MAX_IDR_SHIFT   (sizeof(int)*8 - 1)

Definition at line 41 of file idr.h.

Function Documentation

void ida_destroy ( struct ida ida)

ida_destroy - release all cached layers within an ida tree : ida handle

Definition at line 925 of file idr.c.

int ida_get_new ( struct ida ida,
int p_id 
)

ida_get_new - allocate new ID : idr handle : pointer to the allocated handle

Allocate new ID. It should be called with any required locks.

If memory is required, it will return %-EAGAIN, you should unlock and go back to the idr_pre_get() call. If the idr is full, it will return %-ENOSPC.

returns a value in the range %0 ... %0x7fffffff.

Definition at line 867 of file idr.c.

int ida_get_new_above ( struct ida ida,
int  starting_id,
int p_id 
)

ida_get_new_above - allocate new ID above or equal to a start id : ida handle : id to start search at : pointer to the allocated handle

Allocate new ID above or equal to . It should be called with any required locks.

If memory is required, it will return %-EAGAIN, you should unlock and go back to the ida_pre_get() call. If the ida is full, it will return %-ENOSPC.

returns a value in the range ... %0x7fffffff.

Definition at line 781 of file idr.c.

void ida_init ( struct ida ida)

ida_init - initialize ida handle : ida handle

This function is use to set up the handle () that you will pass to the rest of the functions.

Definition at line 1007 of file idr.c.

int ida_pre_get ( struct ida ida,
gfp_t  gfp_mask 
)

ida_pre_get - reserve resources for ida allocation : ida handle : memory allocation flag

This function should be called prior to locking and calling the following function. It preallocates enough memory to satisfy the worst possible allocation.

If the system is REALLY out of memory this function returns %0, otherwise %1.

Definition at line 745 of file idr.c.

void ida_remove ( struct ida ida,
int  id 
)

ida_remove - remove the given ID : ida handle : ID to free

Definition at line 878 of file idr.c.

int ida_simple_get ( struct ida ida,
unsigned int  start,
unsigned int  end,
gfp_t  gfp_mask 
)

ida_simple_get - get a new id. : the (initialized) ida. : the minimum id (inclusive, < 0x8000000) : the maximum id (exclusive, < 0x8000000 or 0) : memory allocation flags

Allocates an id in the range start <= id < end, or returns -ENOSPC. On memory allocation failure, returns -ENOMEM.

Use ida_simple_remove() to get rid of an id.

Definition at line 944 of file idr.c.

void ida_simple_remove ( struct ida ida,
unsigned int  id 
)

ida_simple_remove - remove an allocated id. : the (initialized) ida. : the id returned by ida_simple_get.

Definition at line 989 of file idr.c.

void idr_destroy ( struct idr idp)

idr_destroy - release all cached layers within an idr tree : idr handle

Definition at line 488 of file idr.c.

void* idr_find ( struct idr idp,
int  id 
)

DOC: idr sync idr synchronization (stolen from radix-tree.h)

idr_find() is able to be called locklessly, using RCU. The caller must ensure calls to this function are made within rcu_read_lock() regions. Other readers (lock-free or otherwise) and modifications may be running concurrently.

It is still required that the caller manage the synchronization and lifetimes of the items. So if RCU lock-free lookups are used, typically this would mean that the items have their own locks, or are amenable to lock-free access; and that the items are freed by RCU (or only freed after having been deleted from the idr tree and a synchronize_rcu() grace period).

idr_find - return pointer for given id : idr handle : lookup key

Return the pointer given the id it has been registered with. A NULL return indicates that is not valid or you passed NULL in idr_get_new().

This function can be called under rcu_read_lock(), given that the leaf pointers lifetimes are correctly managed.

Definition at line 509 of file idr.c.

int idr_for_each ( struct idr idp,
int(*)(int id, void *p, void *data fn,
void data 
)

Definition at line 553 of file idr.c.

int idr_get_new ( struct idr idp,
void ptr,
int id 
)

idr_get_new - allocate new idr entry : idr handle : pointer you want associated with the id : pointer to the allocated handle

If allocation from IDR's private freelist fails, idr_get_new_above() will return %-EAGAIN. The caller should retry the idr_pre_get() call to refill IDR's preallocation and then retry the idr_get_new_above() call.

If the idr is full idr_get_new_above() will return %-ENOSPC.

returns a value in the range %0 ... %0x7fffffff

Definition at line 334 of file idr.c.

int idr_get_new_above ( struct idr idp,
void ptr,
int  starting_id,
int id 
)

idr_get_new_above - allocate new idr entry above or equal to a start id : idr handle : pointer you want associated with the id : id to start search at : pointer to the allocated handle

This is the allocate id function. It should be called with any required locks.

If allocation from IDR's private freelist fails, idr_get_new_above() will return %-EAGAIN. The caller should retry the idr_pre_get() call to refill IDR's preallocation and then retry the idr_get_new_above() call.

If the idr is full idr_get_new_above() will return %-ENOSPC.

returns a value in the range ... %0x7fffffff

Definition at line 304 of file idr.c.

void* idr_get_next ( struct idr idp,
int nextidp 
)

idr_get_next - lookup next object of id to given id. : idr handle : pointer to lookup key

Returns pointer to registered object with id, which is next number to given id. After being looked up, * will be updated for the next iteration.

This function can be called under rcu_read_lock(), given that the leaf pointers lifetimes are correctly managed.

Definition at line 602 of file idr.c.

void idr_init ( struct idr idp)

idr_init - initialize idr handle : idr handle

This function is use to set up the handle () that you will pass to the rest of the functions.

Definition at line 697 of file idr.c.

void __init idr_init_cache ( void  )

Definition at line 684 of file idr.c.

int idr_pre_get ( struct idr idp,
gfp_t  gfp_mask 
)

idr_pre_get - reserve resources for idr allocation : idr handle : memory allocation flags

This function should be called prior to calling the idr_get_new* functions. It preallocates enough memory to satisfy the worst possible allocation. The caller should pass in GFP_KERNEL if possible. This of course requires that no spinning locks be held.

If the system is REALLY out of memory this function returns %0, otherwise %1.

Definition at line 123 of file idr.c.

void idr_remove ( struct idr idp,
int  id 
)

idr_remove - remove the given id and free its slot : idr handle : unique key

Definition at line 399 of file idr.c.

void idr_remove_all ( struct idr idp)

idr_remove_all - remove all ids from the given idr tree : idr handle

idr_destroy() only frees up unused, cached idp_layers, but this function will remove all id mappings and leave all idp_layers unused.

A typical clean-up sequence for objects stored in an idr tree will use idr_for_each() to free all objects, if necessay, then idr_remove_all() to remove all ids, and idr_destroy() to free up the cached idr_layers.

Definition at line 449 of file idr.c.

void* idr_replace ( struct idr idp,
void ptr,
int  id 
)

idr_replace - replace pointer for given id : idr handle : pointer you want associated with the id : lookup key

Replace the pointer registered with an id and return the old value. A %-ENOENT return indicates that was not found. A %-EINVAL return indicates that was not within valid constraints.

The caller must serialize with writers.

Definition at line 651 of file idr.c.