xref: /illumos-gate/usr/src/uts/common/os/group.c (revision 5bbb4db2c3f208d12bf0fd11769728f9e5ba66a2)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include <sys/systm.h>
27 #include <sys/param.h>
28 #include <sys/debug.h>
29 #include <sys/kmem.h>
30 #include <sys/group.h>
31 
32 
33 #define	GRP_SET_SIZE_DEFAULT 2
34 
35 static void group_grow_set(group_t *);
36 static void group_shrink_set(group_t *);
37 static void group_pack_set(void **, uint_t);
38 
39 /*
40  * Initialize a group_t
41  */
42 void
43 group_create(group_t *g)
44 {
45 	bzero(g, sizeof (group_t));
46 }
47 
48 /*
49  * Destroy a group_t
50  * The group must already be empty
51  */
52 void
53 group_destroy(group_t *g)
54 {
55 	ASSERT(g->grp_size == 0);
56 
57 	if (g->grp_capacity > 0) {
58 		kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
59 		g->grp_capacity = 0;
60 	}
61 	g->grp_set = NULL;
62 }
63 
64 /*
65  * Empty a group_t
66  * Capacity is preserved.
67  */
68 void
69 group_empty(group_t *g)
70 {
71 	int	i;
72 	int	sz = g->grp_size;
73 
74 	g->grp_size = 0;
75 	for (i = 0; i < sz; i++)
76 		g->grp_set[i] = NULL;
77 }
78 
79 /*
80  * Add element "e" to group "g"
81  *
82  * Returns -1 if addition would result in overcapacity, and
83  * resize operations aren't allowed, and 0 otherwise
84  */
85 int
86 group_add(group_t *g, void *e, int gflag)
87 {
88 	int	entry;
89 
90 	if ((gflag & GRP_NORESIZE) &&
91 	    g->grp_size == g->grp_capacity)
92 		return (-1);
93 
94 	ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
95 
96 	entry = g->grp_size++;
97 	if (g->grp_size > g->grp_capacity)
98 		group_grow_set(g);
99 
100 	ASSERT(g->grp_set[entry] == NULL);
101 	g->grp_set[entry] = e;
102 
103 	return (0);
104 }
105 
106 /*
107  * Remove element "e" from group "g"
108  *
109  * Returns -1 if "e" was not present in "g" and 0 otherwise
110  */
111 int
112 group_remove(group_t *g, void *e, int gflag)
113 {
114 	int	i;
115 
116 	if (g->grp_size == 0)
117 		return (-1);
118 
119 	/*
120 	 * Find the element in the group's set
121 	 */
122 	for (i = 0; i < g->grp_size; i++)
123 		if (g->grp_set[i] == e)
124 			break;
125 	if (g->grp_set[i] != e)
126 		return (-1);
127 
128 	g->grp_set[i] = NULL;
129 	group_pack_set(g->grp_set, g->grp_size);
130 	g->grp_size--;
131 
132 	if ((gflag & GRP_RESIZE) &&
133 	    g->grp_size > GRP_SET_SIZE_DEFAULT &&
134 	    ((g->grp_size - 1) & g->grp_size) == 0)
135 		group_shrink_set(g);
136 
137 	return (0);
138 }
139 
140 /*
141  * Expand the capacity of group "g" so that it may
142  * contain at least "n" elements
143  */
144 void
145 group_expand(group_t *g, uint_t n)
146 {
147 	while (g->grp_capacity < n)
148 		group_grow_set(g);
149 }
150 
151 /*
152  * Upsize a group's holding capacity
153  */
154 static void
155 group_grow_set(group_t *g)
156 {
157 	uint_t		cap_old, cap_new;
158 	void		**set_old, **set_new;
159 
160 	cap_old = g->grp_capacity;
161 	set_old = g->grp_set;
162 
163 	/*
164 	 * The array size grows in powers of two
165 	 */
166 	if ((cap_new = (cap_old << 1)) == 0) {
167 		/*
168 		 * The set is unallocated.
169 		 * Allocate a default sized set.
170 		 */
171 		cap_new = GRP_SET_SIZE_DEFAULT;
172 		g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
173 		g->grp_capacity = cap_new;
174 	} else {
175 		/*
176 		 * Allocate a newly sized array,
177 		 * copy the data, and free the old array.
178 		 */
179 		set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
180 		(void) kcopy(set_old, set_new, cap_old * sizeof (void *));
181 		g->grp_set = set_new;
182 		g->grp_capacity = cap_new;
183 		kmem_free(set_old, cap_old * sizeof (void *));
184 	}
185 	/*
186 	 * The new array size should be a power of two
187 	 */
188 	ASSERT(((cap_new - 1) & cap_new) == 0);
189 }
190 
191 /*
192  * Downsize a group's holding capacity
193  */
194 static void
195 group_shrink_set(group_t *g)
196 {
197 	uint_t		cap_old, cap_new;
198 	void		**set_old, **set_new;
199 
200 	cap_old = g->grp_capacity;
201 	set_old = g->grp_set;
202 
203 	/*
204 	 * The group's existing array size must already
205 	 * be a power of two
206 	 */
207 	ASSERT(((cap_old - 1) & cap_old) == 0);
208 	cap_new = cap_old >> 1;
209 
210 	/*
211 	 * GRP_SET_SIZE_DEFAULT is the minumum set size.
212 	 */
213 	if (cap_new < GRP_SET_SIZE_DEFAULT)
214 		return;
215 
216 	set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
217 	(void) kcopy(set_old, set_new, cap_new * sizeof (void *));
218 	g->grp_capacity = cap_new;
219 	g->grp_set = set_new;
220 
221 	ASSERT(((cap_new - 1) & cap_new) == 0);
222 	kmem_free(set_old, cap_old * sizeof (void *));
223 }
224 
225 /*
226  * Pack a group's set
227  * Element order is not preserved
228  */
229 static void
230 group_pack_set(void **set, uint_t sz)
231 {
232 	uint_t	i, j, free;
233 
234 	free = (uint_t)-1;
235 
236 	for (i = 0; i < sz; i++) {
237 		if (set[i] == NULL && free == (uint_t)-1) {
238 			/*
239 			 * Found a new free slot.
240 			 * Start packing from here.
241 			 */
242 			free = i;
243 		} else if (set[i] != NULL && free != (uint_t)-1) {
244 			/*
245 			 * Found a slot to pack into
246 			 * an earlier free slot.
247 			 */
248 			ASSERT(set[free] == NULL);
249 			set[free] = set[i];
250 			set[i] = NULL;
251 
252 			/*
253 			 * Find the next free slot
254 			 */
255 			for (j = free + 1; set[j] != NULL; j++) {
256 				ASSERT(j <= i);
257 				if (j == i)
258 					break;
259 			}
260 			if (set[j] == NULL)
261 				free = j;
262 			else
263 				free = (uint_t)-1;
264 		}
265 	}
266 }
267 
268 /*
269  * Initialize a group iterator cookie
270  */
271 void
272 group_iter_init(group_iter_t *iter)
273 {
274 	*iter = 0;
275 }
276 
277 /*
278  * Iterate over the elements in a group
279  */
280 void *
281 group_iterate(group_t *g, group_iter_t *iter)
282 {
283 	uint_t	idx = *iter;
284 	void	*data = NULL;
285 
286 	while (idx < g->grp_size) {
287 		data = g->grp_set[idx++];
288 		if (data != NULL)
289 			break;
290 	}
291 	*iter = idx;
292 
293 	return (data);
294 }
295 
296 /*
297  * Indexed access to a group's elements
298  */
299 void *
300 group_access_at(group_t *g, uint_t idx)
301 {
302 	if (idx >= g->grp_capacity)
303 		return (NULL);
304 
305 	return (g->grp_set[idx]);
306 }
307 
308 /*
309  * Add a new ordered group element at specified
310  * index. The group must already be of sufficient
311  * capacity to hold an element at the specified index.
312  *
313  * Returns 0 if addition was sucessful, and -1 if the
314  * addition failed because the table was too small
315  */
316 int
317 group_add_at(group_t *g, void *e, uint_t idx)
318 {
319 	if (idx >= g->grp_capacity)
320 		return (-1);
321 
322 	if (idx >= g->grp_size)
323 		g->grp_size = idx + 1;
324 
325 	ASSERT(g->grp_set[idx] == NULL);
326 	g->grp_set[idx] = e;
327 	return (0);
328 }
329 
330 /*
331  * Remove the element at the specified index
332  */
333 void
334 group_remove_at(group_t *g, uint_t idx)
335 {
336 	ASSERT(idx < g->grp_capacity);
337 	g->grp_set[idx] = NULL;
338 }
339 
340 /*
341  * Find an element in the group, and return its index
342  * Returns -1 if the element could not be found.
343  */
344 uint_t
345 group_find(group_t *g, void *e)
346 {
347 	uint_t	idx;
348 
349 	for (idx = 0; idx < g->grp_capacity; idx++) {
350 		if (g->grp_set[idx] == e)
351 			return (idx);
352 	}
353 	return ((uint_t)-1);
354 }
355