xref: /dragonfly/sys/dev/drm/include/linux/idr.h (revision 1f4dfa92)
1 /*
2  * Copyright (c) 2013-2016 François Tigeot
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice unmodified, this list of conditions, and the following
10  *    disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26 
27 #ifndef _LINUX_IDR_H_
28 #define _LINUX_IDR_H_
29 
30 #include <linux/slab.h>
31 
32 #include <sys/idr.h>
33 
34 #ifdef MALLOC_DECLARE
35 MALLOC_DECLARE(M_IDR);
36 #endif
37 
38 #define	IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
39 #define	IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long) - 1)
40 #define	IDA_BITMAP_BITS 	(IDA_BITMAP_LONGS * sizeof(long) * 8)
41 
42 struct ida_bitmap {
43 	long			nr_busy;
44 	unsigned long		bitmap[IDA_BITMAP_LONGS];
45 };
46 
47 struct ida {
48 	struct idr		idr;
49 	struct ida_bitmap	*free_bitmap;
50 };
51 
52 #define DEFINE_IDA(name)		\
53 	struct ida name = {		\
54 		.idr = { .idr_token = LWKT_TOKEN_INITIALIZER("idrtok") }, \
55 		.free_bitmap = NULL	\
56 	}				\
57 
58 static inline void
ida_init(struct ida * ida)59 ida_init(struct ida *ida)
60 {
61 	idr_init(&ida->idr);
62 }
63 
64 static inline void
ida_simple_remove(struct ida * ida,unsigned int id)65 ida_simple_remove(struct ida *ida, unsigned int id)
66 {
67 	idr_remove(&ida->idr, id);
68 }
69 
70 static inline void
ida_remove(struct ida * ida,int id)71 ida_remove(struct ida *ida, int id)
72 {
73 	idr_remove(&ida->idr, id);
74 }
75 
76 static inline void
ida_destroy(struct ida * ida)77 ida_destroy(struct ida *ida)
78 {
79 	idr_destroy(&ida->idr);
80 	if (ida->free_bitmap != NULL) {
81 		/* kfree() is a linux macro! Work around the cpp pass */
82 		_kfree(ida->free_bitmap, M_IDR);
83 	}
84 }
85 
86 static inline int
ida_simple_get(struct ida * ida,unsigned int start,unsigned int end,gfp_t gfp_mask)87 ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask)
88 {
89 	int id;
90 	unsigned int lim;
91 
92 	if ((end == 0) || (end > 0x80000000))
93 		lim = 0x80000000;
94 	else
95 		lim = end - 1;
96 
97 	idr_preload(gfp_mask);
98 	id = idr_alloc(&ida->idr, NULL, start, lim, gfp_mask);
99 	idr_preload_end();
100 
101 	return id;
102 }
103 
104 static inline void *
idr_get_next(struct idr * idp,int * nextid)105 idr_get_next(struct idr *idp, int *nextid)
106 {
107 	void *res = NULL;
108 
109 	lwkt_gettoken(&idp->idr_token);
110 
111 	for (int id = *nextid; id < idp->idr_count; id++) {
112 		res = idr_find(idp, id);
113 		if (res == NULL)
114 			continue;
115 		*nextid = id;
116 		break;
117 	}
118 
119 	lwkt_reltoken(&idp->idr_token);
120 	return res;
121 }
122 
123 #define idr_for_each_entry(idp, entry, id)			\
124 	for (id = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++id)
125 
126 #endif	/* _LINUX_IDR_H_ */
127