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