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/sysmacros.h>
27 #include <sys/systm.h>
28 #include <sys/param.h>
29 #include <sys/debug.h>
30 #include <sys/kmem.h>
31 #include <sys/group.h>
32 #include <sys/cmn_err.h>
33
34
35 #define GRP_SET_SIZE_DEFAULT 2
36
37 static void group_grow_set(group_t *);
38 static void group_shrink_set(group_t *);
39 static void group_pack_set(void **, uint_t);
40
41 /*
42 * Initialize a group_t
43 */
44 void
group_create(group_t * g)45 group_create(group_t *g)
46 {
47 bzero(g, sizeof (group_t));
48 }
49
50 /*
51 * Destroy a group_t
52 * The group must already be empty
53 */
54 void
group_destroy(group_t * g)55 group_destroy(group_t *g)
56 {
57 ASSERT(g->grp_size == 0);
58
59 if (g->grp_capacity > 0) {
60 kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
61 g->grp_capacity = 0;
62 }
63 g->grp_set = NULL;
64 }
65
66 /*
67 * Empty a group_t
68 * Capacity is preserved.
69 */
70 void
group_empty(group_t * g)71 group_empty(group_t *g)
72 {
73 int i;
74 int sz = g->grp_size;
75
76 g->grp_size = 0;
77 for (i = 0; i < sz; i++)
78 g->grp_set[i] = NULL;
79 }
80
81 /*
82 * Add element "e" to group "g"
83 *
84 * Returns -1 if addition would result in overcapacity, and
85 * resize operations aren't allowed, and 0 otherwise
86 */
87 int
group_add(group_t * g,void * e,int gflag)88 group_add(group_t *g, void *e, int gflag)
89 {
90 int entry;
91
92 if ((gflag & GRP_NORESIZE) &&
93 g->grp_size == g->grp_capacity)
94 return (-1);
95
96 ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
97
98 entry = g->grp_size++;
99 if (g->grp_size > g->grp_capacity)
100 group_grow_set(g);
101
102 ASSERT(g->grp_set[entry] == NULL);
103 g->grp_set[entry] = e;
104
105 return (0);
106 }
107
108 /*
109 * Remove element "e" from group "g"
110 *
111 * Returns -1 if "e" was not present in "g" and 0 otherwise
112 */
113 int
group_remove(group_t * g,void * e,int gflag)114 group_remove(group_t *g, void *e, int gflag)
115 {
116 int i;
117
118 if (g->grp_size == 0)
119 return (-1);
120
121 /*
122 * Find the element in the group's set
123 */
124 for (i = 0; i < g->grp_size; i++)
125 if (g->grp_set[i] == e)
126 break;
127 if (g->grp_set[i] != e)
128 return (-1);
129
130 g->grp_set[i] = NULL;
131 group_pack_set(g->grp_set, g->grp_size);
132 g->grp_size--;
133
134 if ((gflag & GRP_RESIZE) &&
135 g->grp_size > GRP_SET_SIZE_DEFAULT && ISP2(g->grp_size))
136 group_shrink_set(g);
137
138 return (0);
139 }
140
141 /*
142 * Expand the capacity of group "g" so that it may
143 * contain at least "n" elements
144 */
145 void
group_expand(group_t * g,uint_t n)146 group_expand(group_t *g, uint_t n)
147 {
148 while (g->grp_capacity < n)
149 group_grow_set(g);
150 }
151
152 /*
153 * Upsize a group's holding capacity
154 */
155 static void
group_grow_set(group_t * g)156 group_grow_set(group_t *g)
157 {
158 uint_t cap_old, cap_new;
159 void **set_old, **set_new;
160
161 cap_old = g->grp_capacity;
162 set_old = g->grp_set;
163
164 /*
165 * The array size grows in powers of two
166 */
167 if ((cap_new = (cap_old << 1)) == 0) {
168 /*
169 * The set is unallocated.
170 * Allocate a default sized set.
171 */
172 cap_new = GRP_SET_SIZE_DEFAULT;
173 g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
174 g->grp_capacity = cap_new;
175 } else {
176 /*
177 * Allocate a newly sized array,
178 * copy the data, and free the old array.
179 */
180 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
181 (void) kcopy(set_old, set_new, cap_old * sizeof (void *));
182 g->grp_set = set_new;
183 g->grp_capacity = cap_new;
184 kmem_free(set_old, cap_old * sizeof (void *));
185 }
186 /*
187 * The new array size should be a power of two
188 */
189 ASSERT(((cap_new - 1) & cap_new) == 0);
190 }
191
192 /*
193 * Downsize a group's holding capacity
194 */
195 static void
group_shrink_set(group_t * g)196 group_shrink_set(group_t *g)
197 {
198 uint_t cap_old, cap_new;
199 void **set_old, **set_new;
200
201 cap_old = g->grp_capacity;
202 set_old = g->grp_set;
203
204 /*
205 * The group's existing array size must already
206 * be a power of two
207 */
208 ASSERT(((cap_old - 1) & cap_old) == 0);
209 cap_new = cap_old >> 1;
210
211 /*
212 * GRP_SET_SIZE_DEFAULT is the minumum set size.
213 */
214 if (cap_new < GRP_SET_SIZE_DEFAULT)
215 return;
216
217 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
218 (void) kcopy(set_old, set_new, cap_new * sizeof (void *));
219 g->grp_capacity = cap_new;
220 g->grp_set = set_new;
221
222 ASSERT(((cap_new - 1) & cap_new) == 0);
223 kmem_free(set_old, cap_old * sizeof (void *));
224 }
225
226 /*
227 * Pack a group's set
228 * Element order is not preserved
229 */
230 static void
group_pack_set(void ** set,uint_t sz)231 group_pack_set(void **set, uint_t sz)
232 {
233 uint_t i, j, free;
234
235 free = (uint_t)-1;
236
237 for (i = 0; i < sz; i++) {
238 if (set[i] == NULL && free == (uint_t)-1) {
239 /*
240 * Found a new free slot.
241 * Start packing from here.
242 */
243 free = i;
244 } else if (set[i] != NULL && free != (uint_t)-1) {
245 /*
246 * Found a slot to pack into
247 * an earlier free slot.
248 */
249 ASSERT(set[free] == NULL);
250 set[free] = set[i];
251 set[i] = NULL;
252
253 /*
254 * Find the next free slot
255 */
256 for (j = free + 1; set[j] != NULL; j++) {
257 ASSERT(j <= i);
258 if (j == i)
259 break;
260 }
261 if (set[j] == NULL)
262 free = j;
263 else
264 free = (uint_t)-1;
265 }
266 }
267 }
268
269 /*
270 * Initialize a group iterator cookie
271 */
272 void
group_iter_init(group_iter_t * iter)273 group_iter_init(group_iter_t *iter)
274 {
275 *iter = 0;
276 }
277
278 /*
279 * Iterate over the elements in a group
280 */
281 void *
group_iterate(group_t * g,group_iter_t * iter)282 group_iterate(group_t *g, group_iter_t *iter)
283 {
284 uint_t idx = *iter;
285 void *data = NULL;
286
287 while (idx < g->grp_size) {
288 data = g->grp_set[idx++];
289 if (data != NULL)
290 break;
291 }
292 *iter = idx;
293
294 return (data);
295 }
296
297 /*
298 * Indexed access to a group's elements
299 */
300 void *
group_access_at(group_t * g,uint_t idx)301 group_access_at(group_t *g, uint_t idx)
302 {
303 if (idx >= g->grp_capacity)
304 return (NULL);
305
306 return (g->grp_set[idx]);
307 }
308
309 /*
310 * Add a new ordered group element at specified
311 * index. The group must already be of sufficient
312 * capacity to hold an element at the specified index.
313 *
314 * Returns 0 if addition was sucessful, and -1 if the
315 * addition failed because the table was too small
316 */
317 int
group_add_at(group_t * g,void * e,uint_t idx)318 group_add_at(group_t *g, void *e, uint_t idx)
319 {
320 if (idx >= g->grp_capacity)
321 return (-1);
322
323 if (idx >= g->grp_size)
324 g->grp_size = idx + 1;
325
326 ASSERT(g->grp_set[idx] == NULL);
327 g->grp_set[idx] = e;
328 return (0);
329 }
330
331 /*
332 * Remove the element at the specified index
333 */
334 void
group_remove_at(group_t * g,uint_t idx)335 group_remove_at(group_t *g, uint_t idx)
336 {
337 ASSERT(idx < g->grp_capacity);
338 g->grp_set[idx] = NULL;
339 }
340
341 /*
342 * Find an element in the group, and return its index
343 * Returns -1 if the element could not be found.
344 */
345 uint_t
group_find(group_t * g,void * e)346 group_find(group_t *g, void *e)
347 {
348 uint_t idx;
349
350 for (idx = 0; idx < g->grp_capacity; idx++) {
351 if (g->grp_set[idx] == e)
352 return (idx);
353 }
354 return ((uint_t)-1);
355 }
356
357 /*
358 * Return a string in a given buffer with list of integer entries in a group.
359 * The string concatenates consecutive integer ranges ax x-y.
360 * The resulting string looks like "1,2-5,8"
361 *
362 * The convert argument is used to map group elements to integer IDs.
363 */
364 char *
group2intlist(group_t * group,char * buffer,size_t len,int (convert)(void *))365 group2intlist(group_t *group, char *buffer, size_t len, int (convert)(void*))
366 {
367 char *ptr = buffer;
368 void *v;
369 group_iter_t iter;
370 boolean_t first_iteration = B_TRUE;
371 boolean_t first_value = B_TRUE;
372 int start = 0, end = 0;
373
374 /*
375 * Allow for the terminating NULL-byte
376 */
377 len = len -1;
378
379 group_iter_init(&iter);
380 while ((v = group_iterate(group, &iter)) != NULL && len > 0) {
381 int id = convert(v);
382 int nbytes = 0;
383
384 if (first_iteration) {
385 start = end = id;
386 first_iteration = B_FALSE;
387 } else if (end + 1 == id) {
388 /*
389 * Got consecutive ID, so extend end of range without
390 * doing anything since the range may extend further
391 */
392 end = id;
393 } else {
394 if (first_value) {
395 first_value = B_FALSE;
396 } else {
397 *ptr++ = ',';
398 len--;
399 }
400
401 if (len == 0)
402 break;
403
404 /*
405 * Next ID is not consecutive, so dump IDs gotten so
406 * far.
407 */
408 if (end > start + 1) /* range */
409 nbytes = snprintf(ptr, len, "%d-%d",
410 start, end);
411 else if (end > start) /* different values */
412 nbytes = snprintf(ptr, len, "%d,%d",
413 start, end);
414 else /* same value */
415 nbytes = snprintf(ptr, len, "%d", start);
416
417 if (nbytes <= 0) {
418 len = 0;
419 break;
420 }
421
422 /*
423 * Advance position in the string
424 */
425 ptr += nbytes;
426 len -= nbytes;
427
428 /*
429 * Try finding consecutive range starting from current
430 * ID.
431 */
432 start = end = id;
433 }
434 }
435
436 if (!first_value) {
437 *ptr++ = ',';
438 len--;
439 }
440 /*
441 * Print last ID(s)
442 */
443 if (len > 0) {
444 if (end > start + 1) {
445 (void) snprintf(ptr, len, "%d-%d", start, end);
446 } else if (end != start) {
447 (void) snprintf(ptr, len, "%d,%d", start, end);
448 } else {
449 (void) snprintf(ptr, len, "%d", start);
450 }
451 }
452
453 return (buffer);
454 }
455