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 #include <sys/cmn_err.h> 32 33 34 #define GRP_SET_SIZE_DEFAULT 2 35 36 static void group_grow_set(group_t *); 37 static void group_shrink_set(group_t *); 38 static void group_pack_set(void **, uint_t); 39 40 /* 41 * Initialize a group_t 42 */ 43 void 44 group_create(group_t *g) 45 { 46 bzero(g, sizeof (group_t)); 47 } 48 49 /* 50 * Destroy a group_t 51 * The group must already be empty 52 */ 53 void 54 group_destroy(group_t *g) 55 { 56 ASSERT(g->grp_size == 0); 57 58 if (g->grp_capacity > 0) { 59 kmem_free(g->grp_set, g->grp_capacity * sizeof (void *)); 60 g->grp_capacity = 0; 61 } 62 g->grp_set = NULL; 63 } 64 65 /* 66 * Empty a group_t 67 * Capacity is preserved. 68 */ 69 void 70 group_empty(group_t *g) 71 { 72 int i; 73 int sz = g->grp_size; 74 75 g->grp_size = 0; 76 for (i = 0; i < sz; i++) 77 g->grp_set[i] = NULL; 78 } 79 80 /* 81 * Add element "e" to group "g" 82 * 83 * Returns -1 if addition would result in overcapacity, and 84 * resize operations aren't allowed, and 0 otherwise 85 */ 86 int 87 group_add(group_t *g, void *e, int gflag) 88 { 89 int entry; 90 91 if ((gflag & GRP_NORESIZE) && 92 g->grp_size == g->grp_capacity) 93 return (-1); 94 95 ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE)); 96 97 entry = g->grp_size++; 98 if (g->grp_size > g->grp_capacity) 99 group_grow_set(g); 100 101 ASSERT(g->grp_set[entry] == NULL); 102 g->grp_set[entry] = e; 103 104 return (0); 105 } 106 107 /* 108 * Remove element "e" from group "g" 109 * 110 * Returns -1 if "e" was not present in "g" and 0 otherwise 111 */ 112 int 113 group_remove(group_t *g, void *e, int gflag) 114 { 115 int i; 116 117 if (g->grp_size == 0) 118 return (-1); 119 120 /* 121 * Find the element in the group's set 122 */ 123 for (i = 0; i < g->grp_size; i++) 124 if (g->grp_set[i] == e) 125 break; 126 if (g->grp_set[i] != e) 127 return (-1); 128 129 g->grp_set[i] = NULL; 130 group_pack_set(g->grp_set, g->grp_size); 131 g->grp_size--; 132 133 if ((gflag & GRP_RESIZE) && 134 g->grp_size > GRP_SET_SIZE_DEFAULT && 135 ((g->grp_size - 1) & g->grp_size) == 0) 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 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 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 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 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 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 * 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 * 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 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 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 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 * 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