]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * include/linux/idr.h | |
3 | * | |
4 | * 2002-10-18 written by Jim Houston jim.houston@ccur.com | |
5 | * Copyright (C) 2002 by Concurrent Computer Corporation | |
6 | * Distributed under the GNU GPL license version 2. | |
7 | * | |
8 | * Small id to pointer translation service avoiding fixed sized | |
9 | * tables. | |
10 | */ | |
f668ab1a LT |
11 | |
12 | #ifndef __IDR_H__ | |
13 | #define __IDR_H__ | |
14 | ||
1da177e4 LT |
15 | #include <linux/types.h> |
16 | #include <linux/bitops.h> | |
199f0ca5 | 17 | #include <linux/init.h> |
2027d1ab | 18 | #include <linux/rcupdate.h> |
1da177e4 LT |
19 | |
20 | #if BITS_PER_LONG == 32 | |
21 | # define IDR_BITS 5 | |
22 | # define IDR_FULL 0xfffffffful | |
23 | /* We can only use two of the bits in the top level because there is | |
24 | only one possible bit in the top level (5 bits * 7 levels = 35 | |
25 | bits, but you only use 31 bits in the id). */ | |
26 | # define TOP_LEVEL_FULL (IDR_FULL >> 30) | |
27 | #elif BITS_PER_LONG == 64 | |
28 | # define IDR_BITS 6 | |
29 | # define IDR_FULL 0xfffffffffffffffful | |
30 | /* We can only use two of the bits in the top level because there is | |
31 | only one possible bit in the top level (6 bits * 6 levels = 36 | |
32 | bits, but you only use 31 bits in the id). */ | |
33 | # define TOP_LEVEL_FULL (IDR_FULL >> 62) | |
34 | #else | |
35 | # error "BITS_PER_LONG is not 32 or 64" | |
36 | #endif | |
37 | ||
38 | #define IDR_SIZE (1 << IDR_BITS) | |
39 | #define IDR_MASK ((1 << IDR_BITS)-1) | |
40 | ||
41 | #define MAX_ID_SHIFT (sizeof(int)*8 - 1) | |
42 | #define MAX_ID_BIT (1U << MAX_ID_SHIFT) | |
43 | #define MAX_ID_MASK (MAX_ID_BIT - 1) | |
44 | ||
45 | /* Leave the possibility of an incomplete final layer */ | |
46 | #define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS | |
47 | ||
48 | /* Number of id_layer structs to leave in free list */ | |
49 | #define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL | |
50 | ||
51 | struct idr_layer { | |
52 | unsigned long bitmap; /* A zero bit means "space here" */ | |
53 | struct idr_layer *ary[1<<IDR_BITS]; | |
54 | int count; /* When zero, we can release it */ | |
2027d1ab | 55 | struct rcu_head rcu_head; |
1da177e4 LT |
56 | }; |
57 | ||
58 | struct idr { | |
59 | struct idr_layer *top; | |
60 | struct idr_layer *id_free; | |
61 | int layers; | |
62 | int id_free_cnt; | |
63 | spinlock_t lock; | |
64 | }; | |
65 | ||
66 | #define IDR_INIT(name) \ | |
67 | { \ | |
68 | .top = NULL, \ | |
69 | .id_free = NULL, \ | |
70 | .layers = 0, \ | |
71 | .id_free_cnt = 0, \ | |
e4d91918 | 72 | .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ |
1da177e4 LT |
73 | } |
74 | #define DEFINE_IDR(name) struct idr name = IDR_INIT(name) | |
75 | ||
944ca05c ND |
76 | /* Actions to be taken after a call to _idr_sub_alloc */ |
77 | #define IDR_NEED_TO_GROW -2 | |
78 | #define IDR_NOMORE_SPACE -3 | |
79 | ||
80 | #define _idr_rc_to_errno(rc) ((rc) == -1 ? -EAGAIN : -ENOSPC) | |
81 | ||
1da177e4 LT |
82 | /* |
83 | * This is what we export. | |
84 | */ | |
85 | ||
86 | void *idr_find(struct idr *idp, int id); | |
fd4f2df2 | 87 | int idr_pre_get(struct idr *idp, gfp_t gfp_mask); |
1da177e4 LT |
88 | int idr_get_new(struct idr *idp, void *ptr, int *id); |
89 | int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id); | |
96d7fa42 KH |
90 | int idr_for_each(struct idr *idp, |
91 | int (*fn)(int id, void *p, void *data), void *data); | |
5806f07c | 92 | void *idr_replace(struct idr *idp, void *ptr, int id); |
1da177e4 | 93 | void idr_remove(struct idr *idp, int id); |
23936cc0 | 94 | void idr_remove_all(struct idr *idp); |
8d3b3591 | 95 | void idr_destroy(struct idr *idp); |
1da177e4 | 96 | void idr_init(struct idr *idp); |
f668ab1a | 97 | |
72dba584 TH |
98 | |
99 | /* | |
100 | * IDA - IDR based id allocator, use when translation from id to | |
101 | * pointer isn't necessary. | |
102 | */ | |
103 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ | |
104 | #define IDA_BITMAP_LONGS (128 / sizeof(long) - 1) | |
105 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) | |
106 | ||
107 | struct ida_bitmap { | |
108 | long nr_busy; | |
109 | unsigned long bitmap[IDA_BITMAP_LONGS]; | |
110 | }; | |
111 | ||
112 | struct ida { | |
113 | struct idr idr; | |
114 | struct ida_bitmap *free_bitmap; | |
115 | }; | |
116 | ||
117 | #define IDA_INIT(name) { .idr = IDR_INIT(name), .free_bitmap = NULL, } | |
118 | #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) | |
119 | ||
120 | int ida_pre_get(struct ida *ida, gfp_t gfp_mask); | |
121 | int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); | |
122 | int ida_get_new(struct ida *ida, int *p_id); | |
123 | void ida_remove(struct ida *ida, int id); | |
124 | void ida_destroy(struct ida *ida); | |
125 | void ida_init(struct ida *ida); | |
126 | ||
199f0ca5 AM |
127 | void __init idr_init_cache(void); |
128 | ||
f668ab1a | 129 | #endif /* __IDR_H__ */ |