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 /* 117 * Find the element in the group's set 118 */ 119 for (i = 0; i < g->grp_size; i++) 120 if (g->grp_set[i] == e) 121 break; 122 if (g->grp_set[i] != e) 123 return (-1); 124 125 g->grp_set[i] = NULL; 126 group_pack_set(g->grp_set, g->grp_size); 127 g->grp_size--; 128 129 if ((gflag & GRP_RESIZE) && 130 g->grp_size > GRP_SET_SIZE_DEFAULT && 131 ((g->grp_size - 1) & g->grp_size) == 0) 132 group_shrink_set(g); 133 134 return (0); 135 } 136 137 /* 138 * Expand the capacity of group "g" so that it may 139 * contain at least "n" elements 140 */ 141 void 142 group_expand(group_t *g, uint_t n) 143 { 144 while (g->grp_capacity < n) 145 group_grow_set(g); 146 } 147 148 /* 149 * Upsize a group's holding capacity 150 */ 151 static void 152 group_grow_set(group_t *g) 153 { 154 uint_t cap_old, cap_new; 155 void **set_old, **set_new; 156 157 cap_old = g->grp_capacity; 158 set_old = g->grp_set; 159 160 /* 161 * The array size grows in powers of two 162 */ 163 if ((cap_new = (cap_old << 1)) == 0) { 164 /* 165 * The set is unallocated. 166 * Allocate a default sized set. 167 */ 168 cap_new = GRP_SET_SIZE_DEFAULT; 169 g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 170 g->grp_capacity = cap_new; 171 } else { 172 /* 173 * Allocate a newly sized array, 174 * copy the data, and free the old array. 175 */ 176 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 177 (void) kcopy(set_old, set_new, cap_old * sizeof (void *)); 178 g->grp_set = set_new; 179 g->grp_capacity = cap_new; 180 kmem_free(set_old, cap_old * sizeof (void *)); 181 } 182 /* 183 * The new array size should be a power of two 184 */ 185 ASSERT(((cap_new - 1) & cap_new) == 0); 186 } 187 188 /* 189 * Downsize a group's holding capacity 190 */ 191 static void 192 group_shrink_set(group_t *g) 193 { 194 uint_t cap_old, cap_new; 195 void **set_old, **set_new; 196 197 cap_old = g->grp_capacity; 198 set_old = g->grp_set; 199 200 /* 201 * The group's existing array size must already 202 * be a power of two 203 */ 204 ASSERT(((cap_old - 1) & cap_old) == 0); 205 cap_new = cap_old >> 1; 206 207 /* 208 * GRP_SET_SIZE_DEFAULT is the minumum set size. 209 */ 210 if (cap_new < GRP_SET_SIZE_DEFAULT) 211 return; 212 213 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 214 (void) kcopy(set_old, set_new, cap_new * sizeof (void *)); 215 g->grp_capacity = cap_new; 216 g->grp_set = set_new; 217 218 ASSERT(((cap_new - 1) & cap_new) == 0); 219 kmem_free(set_old, cap_old * sizeof (void *)); 220 } 221 222 /* 223 * Pack a group's set 224 * Element order is not preserved 225 */ 226 static void 227 group_pack_set(void **set, uint_t sz) 228 { 229 uint_t i, j, free; 230 231 free = (uint_t)-1; 232 233 for (i = 0; i < sz; i++) { 234 if (set[i] == NULL && free == (uint_t)-1) { 235 /* 236 * Found a new free slot. 237 * Start packing from here. 238 */ 239 free = i; 240 } else if (set[i] != NULL && free != (uint_t)-1) { 241 /* 242 * Found a slot to pack into 243 * an earlier free slot. 244 */ 245 ASSERT(set[free] == NULL); 246 set[free] = set[i]; 247 set[i] = NULL; 248 249 /* 250 * Find the next free slot 251 */ 252 for (j = free + 1; set[j] != NULL; j++) { 253 ASSERT(j <= i); 254 if (j == i) 255 break; 256 } 257 if (set[j] == NULL) 258 free = j; 259 else 260 free = (uint_t)-1; 261 } 262 } 263 } 264 265 /* 266 * Initialize a group iterator cookie 267 */ 268 void 269 group_iter_init(group_iter_t *iter) 270 { 271 *iter = 0; 272 } 273 274 /* 275 * Iterate over the elements in a group 276 */ 277 void * 278 group_iterate(group_t *g, group_iter_t *iter) 279 { 280 uint_t idx = *iter; 281 void *data = NULL; 282 283 while (idx < g->grp_size) { 284 data = g->grp_set[idx++]; 285 if (data != NULL) 286 break; 287 } 288 *iter = idx; 289 290 return (data); 291 } 292 293 /* 294 * Indexed access to a group's elements 295 */ 296 void * 297 group_access_at(group_t *g, uint_t idx) 298 { 299 if (idx >= g->grp_capacity) 300 return (NULL); 301 302 return (g->grp_set[idx]); 303 } 304 305 /* 306 * Add a new ordered group element at specified 307 * index. The group must already be of sufficient 308 * capacity to hold an element at the specified index. 309 * 310 * Returns 0 if addition was sucessful, and -1 if the 311 * addition failed because the table was too small 312 */ 313 int 314 group_add_at(group_t *g, void *e, uint_t idx) 315 { 316 if (idx >= g->grp_capacity) 317 return (-1); 318 319 if (idx >= g->grp_size) 320 g->grp_size = idx + 1; 321 322 ASSERT(g->grp_set[idx] == NULL); 323 g->grp_set[idx] = e; 324 return (0); 325 } 326 327 /* 328 * Remove the element at the specified index 329 */ 330 void 331 group_remove_at(group_t *g, uint_t idx) 332 { 333 ASSERT(idx < g->grp_capacity); 334 g->grp_set[idx] = NULL; 335 } 336 337 /* 338 * Find an element in the group, and return its index 339 * Returns -1 if the element could not be found. 340 */ 341 uint_t 342 group_find(group_t *g, void *e) 343 { 344 uint_t idx; 345 346 for (idx = 0; idx < g->grp_capacity; idx++) { 347 if (g->grp_set[idx] == e) 348 return (idx); 349 } 350 return ((uint_t)-1); 351 } 352