usr/src/uts/common/os/group.c

   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/sysmacros.h>
  27 #include <sys/systm.h>
  28 #include <sys/param.h>
  29 #include <sys/debug.h>
  30 #include <sys/kmem.h>
  31 #include <sys/group.h>
  32 #include <sys/cmn_err.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  * Empty a group_t
  68  * Capacity is preserved.
  69  */
  70 void
  71 group_empty(group_t *g)
  72 {
  73         int     i;
  74         int     sz = g->grp_size;
  75
  76         g->grp_size = 0;
  77         for (i = 0; i < sz; i++)
  78                 g->grp_set[i] = NULL;
  79 }
  80
  81 /*
  82  * Add element "e" to group "g"
  83  *
  84  * Returns -1 if addition would result in overcapacity, and
  85  * resize operations aren't allowed, and 0 otherwise
  86  */
  87 int
  88 group_add(group_t *g, void *e, int gflag)
  89 {
  90         int     entry;
  91
  92         if ((gflag & GRP_NORESIZE) &&
  93             g->grp_size == g->grp_capacity)
  94                 return (-1);
  95
  96         ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
  97
  98         entry = g->grp_size++;
  99         if (g->grp_size > g->grp_capacity)
 100                 group_grow_set(g);
 101
 102         ASSERT(g->grp_set[entry] == NULL);
 103         g->grp_set[entry] = e;
 104
 105         return (0);
 106 }
 107
 108 /*
 109  * Remove element "e" from group "g"
 110  *
 111  * Returns -1 if "e" was not present in "g" and 0 otherwise
 112  */
 113 int
 114 group_remove(group_t *g, void *e, int gflag)
 115 {
 116         int     i;
 117
 118         if (g->grp_size == 0)
 119                 return (-1);
 120
 121         /*
 122          * Find the element in the group's set
 123          */
 124         for (i = 0; i < g->grp_size; i++)
 125                 if (g->grp_set[i] == e)
 126                         break;
 127         if (g->grp_set[i] != e)
 128                 return (-1);
 129
 130         g->grp_set[i] = NULL;
 131         group_pack_set(g->grp_set, g->grp_size);
 132         g->grp_size--;
 133
 134         if ((gflag & GRP_RESIZE) &&
 135             g->grp_size > GRP_SET_SIZE_DEFAULT && ISP2(g->grp_size))
 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 }