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