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 2007 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26 #pragma ident "%Z%%M% %I% %E% SMI" 27 28 #include <sys/systm.h> 29 #include <sys/param.h> 30 #include <sys/debug.h> 31 #include <sys/kmem.h> 32 #include <sys/group.h> 33 34 35 #define GRP_SET_SIZE_DEFAULT 2 36 37 static void group_grow_set(group_t *); 38 static void group_shrink_set(group_t *); 39 static void group_pack_set(void **, uint_t); 40 41 /* 42 * Initialize a group_t 43 */ 44 void 45 group_create(group_t *g) 46 { 47 bzero(g, sizeof (group_t)); 48 } 49 50 /* 51 * Destroy a group_t 52 * The group must already be empty 53 */ 54 void 55 group_destroy(group_t *g) 56 { 57 ASSERT(g->grp_size == 0); 58 59 if (g->grp_capacity > 0) { 60 kmem_free(g->grp_set, g->grp_capacity * sizeof (void *)); 61 g->grp_capacity = 0; 62 } 63 g->grp_set = NULL; 64 } 65 66 /* 67 * Add element "e" to group "g" 68 * 69 * Returns -1 if addition would result in overcapacity, and 70 * resize operations aren't allowed, and 0 otherwise 71 */ 72 int 73 group_add(group_t *g, void *e, int gflag) 74 { 75 int entry; 76 77 if ((gflag & GRP_NORESIZE) && 78 g->grp_size == g->grp_capacity) 79 return (-1); 80 81 ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE)); 82 83 entry = g->grp_size++; 84 if (g->grp_size > g->grp_capacity) 85 group_grow_set(g); 86 87 ASSERT(g->grp_set[entry] == NULL); 88 g->grp_set[entry] = e; 89 90 return (0); 91 } 92 93 /* 94 * Remove element "e" from group "g" 95 * 96 * Returns -1 if "e" was not present in "g" and 0 otherwise 97 */ 98 int 99 group_remove(group_t *g, void *e, int gflag) 100 { 101 int i; 102 103 /* 104 * Find the element in the group's set 105 */ 106 for (i = 0; i < g->grp_size; i++) 107 if (g->grp_set[i] == e) 108 break; 109 if (g->grp_set[i] != e) 110 return (-1); 111 112 g->grp_set[i] = NULL; 113 group_pack_set(g->grp_set, g->grp_size); 114 g->grp_size--; 115 116 if ((gflag & GRP_RESIZE) && 117 g->grp_size > GRP_SET_SIZE_DEFAULT && 118 ((g->grp_size - 1) & g->grp_size) == 0) 119 group_shrink_set(g); 120 121 return (0); 122 } 123 124 /* 125 * Expand the capacity of group "g" so that it may 126 * contain at least "n" elements 127 */ 128 void 129 group_expand(group_t *g, uint_t n) 130 { 131 while (g->grp_capacity < n) 132 group_grow_set(g); 133 } 134 135 /* 136 * Upsize a group's holding capacity 137 */ 138 static void 139 group_grow_set(group_t *g) 140 { 141 uint_t cap_old, cap_new; 142 void **set_old, **set_new; 143 144 cap_old = g->grp_capacity; 145 set_old = g->grp_set; 146 147 /* 148 * The array size grows in powers of two 149 */ 150 if ((cap_new = (cap_old << 1)) == 0) { 151 /* 152 * The set is unallocated. 153 * Allocate a default sized set. 154 */ 155 cap_new = GRP_SET_SIZE_DEFAULT; 156 g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 157 g->grp_capacity = cap_new; 158 } else { 159 /* 160 * Allocate a newly sized array, 161 * copy the data, and free the old array. 162 */ 163 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 164 (void) kcopy(set_old, set_new, cap_old * sizeof (void *)); 165 g->grp_set = set_new; 166 g->grp_capacity = cap_new; 167 kmem_free(set_old, cap_old * sizeof (void *)); 168 } 169 /* 170 * The new array size should be a power of two 171 */ 172 ASSERT(((cap_new - 1) & cap_new) == 0); 173 } 174 175 /* 176 * Downsize a group's holding capacity 177 */ 178 static void 179 group_shrink_set(group_t *g) 180 { 181 uint_t cap_old, cap_new; 182 void **set_old, **set_new; 183 184 cap_old = g->grp_capacity; 185 set_old = g->grp_set; 186 187 /* 188 * The group's existing array size must already 189 * be a power of two 190 */ 191 ASSERT(((cap_old - 1) & cap_old) == 0); 192 cap_new = cap_old >> 1; 193 194 /* 195 * GRP_SET_SIZE_DEFAULT is the minumum set size. 196 */ 197 if (cap_new < GRP_SET_SIZE_DEFAULT) 198 return; 199 200 set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP); 201 (void) kcopy(set_old, set_new, cap_new * sizeof (void *)); 202 g->grp_capacity = cap_new; 203 g->grp_set = set_new; 204 205 ASSERT(((cap_new - 1) & cap_new) == 0); 206 kmem_free(set_old, cap_old * sizeof (void *)); 207 } 208 209 /* 210 * Pack a group's set 211 * Element order is not preserved 212 */ 213 static void 214 group_pack_set(void **set, uint_t sz) 215 { 216 uint_t i, j, free; 217 218 free = (uint_t)-1; 219 220 for (i = 0; i < sz; i++) { 221 if (set[i] == NULL && free == (uint_t)-1) { 222 /* 223 * Found a new free slot. 224 * Start packing from here. 225 */ 226 free = i; 227 } else if (set[i] != NULL && free != (uint_t)-1) { 228 /* 229 * Found a slot to pack into 230 * an earlier free slot. 231 */ 232 ASSERT(set[free] == NULL); 233 set[free] = set[i]; 234 set[i] = NULL; 235 236 /* 237 * Find the next free slot 238 */ 239 for (j = free + 1; set[j] != NULL; j++) { 240 ASSERT(j <= i); 241 if (j == i) 242 break; 243 } 244 if (set[j] == NULL) 245 free = j; 246 else 247 free = (uint_t)-1; 248 } 249 } 250 } 251 252 /* 253 * Initialize a group iterator cookie 254 */ 255 void 256 group_iter_init(group_iter_t *iter) 257 { 258 *iter = 0; 259 } 260 261 /* 262 * Iterate over the elements in a group 263 */ 264 void * 265 group_iterate(group_t *g, group_iter_t *iter) 266 { 267 uint_t idx = *iter; 268 void *data = NULL; 269 270 while (idx < g->grp_size) { 271 data = g->grp_set[idx++]; 272 if (data != NULL) 273 break; 274 } 275 *iter = idx; 276 277 return (data); 278 } 279 280 /* 281 * Indexed access to a group's elements 282 */ 283 void * 284 group_access_at(group_t *g, uint_t idx) 285 { 286 if (idx >= g->grp_capacity) 287 return (NULL); 288 289 return (g->grp_set[idx]); 290 } 291 292 /* 293 * Add a new ordered group element at specified 294 * index. The group must already be of sufficient 295 * capacity to hold an element at the specified index. 296 * 297 * Returns 0 if addition was sucessful, and -1 if the 298 * addition failed because the table was too small 299 */ 300 int 301 group_add_at(group_t *g, void *e, uint_t idx) 302 { 303 if (idx >= g->grp_capacity) 304 return (-1); 305 306 if (idx >= g->grp_size) 307 g->grp_size = idx + 1; 308 309 ASSERT(g->grp_set[idx] == NULL); 310 g->grp_set[idx] = e; 311 return (0); 312 } 313 314 /* 315 * Remove the entry at the specified index 316 */ 317 void 318 group_remove_at(group_t *g, uint_t idx) 319 { 320 ASSERT(idx < g->grp_capacity); 321 g->grp_set[idx] = NULL; 322 } 323