1 /* $NetBSD: idr.h,v 1.11 2023/07/11 10:42:36 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2013 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifndef _LINUX_IDR_H_
33 #define _LINUX_IDR_H_
34
35 #include <sys/types.h>
36 #include <sys/mutex.h>
37 #include <sys/rbtree.h>
38
39 #include <linux/gfp.h>
40
41 /* XXX Stupid expedient algorithm should be replaced by something better. */
42
43 struct idr {
44 kmutex_t idr_lock;
45 rb_tree_t idr_tree;
46 int idr_base;
47 };
48
49 /* XXX Make the nm output a little more greppable... */
50 #define idr_alloc linux_idr_alloc
51 #define idr_destroy linux_idr_destroy
52 #define idr_find linux_idr_find
53 #define idr_for_each linux_idr_for_each
54 #define idr_get_next linux_idr_get_next
55 #define idr_init linux_idr_init
56 #define idr_init_base linux_idr_init_base
57 #define idr_is_empty linux_idr_is_empty
58 #define idr_preload linux_idr_preload
59 #define idr_preload_end linux_idr_preload_end
60 #define idr_remove linux_idr_remove
61 #define idr_replace linux_idr_replace
62
63 int linux_idr_module_init(void);
64 void linux_idr_module_fini(void);
65
66 void idr_init(struct idr *);
67 void idr_init_base(struct idr *, int);
68 void idr_destroy(struct idr *);
69 bool idr_is_empty(struct idr *);
70 void *idr_find(struct idr *, int);
71 void *idr_get_next(struct idr *, int *);
72 void *idr_replace(struct idr *, void *, int);
73 void *idr_remove(struct idr *, int);
74 void idr_preload(gfp_t);
75 int idr_alloc(struct idr *, void *, int, int, gfp_t);
76 void idr_preload_end(void);
77 int idr_for_each(struct idr *, int (*)(int, void *, void *), void *);
78
79 #define idr_for_each_entry(IDR, ENTRY, ID) \
80 for ((ID) = 0; ((ENTRY) = idr_get_next((IDR), &(ID))) != NULL; (ID)++)
81
82 struct ida {
83 struct idr ida_idr;
84 };
85
86 static inline void
ida_init(struct ida * ida)87 ida_init(struct ida *ida)
88 {
89
90 idr_init(&ida->ida_idr);
91 }
92
93 static inline void
ida_destroy(struct ida * ida)94 ida_destroy(struct ida *ida)
95 {
96
97 idr_destroy(&ida->ida_idr);
98 }
99
100 static inline void
ida_free(struct ida * ida,int id)101 ida_free(struct ida *ida, int id)
102 {
103
104 idr_remove(&ida->ida_idr, id);
105 }
106
107 static inline int
ida_simple_get(struct ida * ida,unsigned start,unsigned end,gfp_t gfp)108 ida_simple_get(struct ida *ida, unsigned start, unsigned end, gfp_t gfp)
109 {
110 int id;
111
112 KASSERT(start <= INT_MAX);
113 KASSERT(end <= INT_MAX);
114
115 idr_preload(gfp);
116 id = idr_alloc(&ida->ida_idr, NULL, start, end, gfp);
117 idr_preload_end();
118
119 return id;
120 }
121
122 static inline int
ida_alloc_max(struct ida * ida,unsigned max,gfp_t gfp)123 ida_alloc_max(struct ida *ida, unsigned max, gfp_t gfp)
124 {
125
126 return ida_simple_get(ida, 0, max + 1, gfp);
127 }
128
129 static inline void
ida_simple_remove(struct ida * ida,unsigned int id)130 ida_simple_remove(struct ida *ida, unsigned int id)
131 {
132
133 KASSERT((int)id >= 0);
134 ida_free(ida, id);
135 }
136
137 #endif /* _LINUX_IDR_H_ */
138