group.c revision 8906:e559381f1e2b
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 35static void group_grow_set(group_t *); 36static void group_shrink_set(group_t *); 37static void group_pack_set(void **, uint_t); 38 39/* 40 * Initialize a group_t 41 */ 42void 43group_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 */ 52void 53group_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 */ 68void 69group_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 */ 85int 86group_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 */ 111int 112group_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 */ 141void 142group_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 */ 151static void 152group_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 */ 191static void 192group_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 */ 226static void 227group_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 */ 268void 269group_iter_init(group_iter_t *iter) 270{ 271 *iter = 0; 272} 273 274/* 275 * Iterate over the elements in a group 276 */ 277void * 278group_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 */ 296void * 297group_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 */ 313int 314group_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 */ 330void 331group_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 */ 341uint_t 342group_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