fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER START
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The contents of this file are subject to the terms of the
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Common Development and Distribution License (the "License").
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * You may not use this file except in compliance with the License.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * or http://www.opensolaris.org/os/licensing.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * See the License for the specific language governing permissions
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * and limitations under the License.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * When distributing Covered Code, include this CDDL HEADER in each
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * If applicable, add the following below this CDDL HEADER, with the
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * fields enclosed by brackets "[]" replaced with your own identifying
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * information: Portions Copyright [yyyy] [name of copyright owner]
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER END
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Use is subject to license terms.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
de710d24d2fae4468e64da999e1d952a247f142cJosef 'Jeff' Sipek#include <sys/sysmacros.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/systm.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/param.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/debug.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/kmem.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/group.h>
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov#include <sys/cmn_err.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#define GRP_SET_SIZE_DEFAULT 2
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void group_grow_set(group_t *);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void group_shrink_set(group_t *);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void group_pack_set(void **, uint_t);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Initialize a group_t
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_create(group_t *g)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bzero(g, sizeof (group_t));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Destroy a group_t
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The group must already be empty
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_destroy(group_t *g)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(g->grp_size == 0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (g->grp_capacity > 0) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_capacity = 0;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe/*
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Empty a group_t
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Capacity is preserved.
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe */
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxevoid
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxegroup_empty(group_t *g)
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe{
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe int i;
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe int sz = g->grp_size;
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe g->grp_size = 0;
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe for (i = 0; i < sz; i++)
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe g->grp_set[i] = NULL;
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe}
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Add element "e" to group "g"
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Returns -1 if addition would result in overcapacity, and
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * resize operations aren't allowed, and 0 otherwise
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeint
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_add(group_t *g, void *e, int gflag)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe int entry;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if ((gflag & GRP_NORESIZE) &&
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_size == g->grp_capacity)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (-1);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe entry = g->grp_size++;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (g->grp_size > g->grp_capacity)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe group_grow_set(g);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(g->grp_set[entry] == NULL);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set[entry] = e;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Remove element "e" from group "g"
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Returns -1 if "e" was not present in "g" and 0 otherwise
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeint
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_remove(group_t *g, void *e, int gflag)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe int i;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
1a77c24bc3a54fb48592de0041508561c5781501Eric Saxe if (g->grp_size == 0)
1a77c24bc3a54fb48592de0041508561c5781501Eric Saxe return (-1);
1a77c24bc3a54fb48592de0041508561c5781501Eric Saxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Find the element in the group's set
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe for (i = 0; i < g->grp_size; i++)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (g->grp_set[i] == e)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe break;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (g->grp_set[i] != e)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (-1);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set[i] = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe group_pack_set(g->grp_set, g->grp_size);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_size--;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if ((gflag & GRP_RESIZE) &&
de710d24d2fae4468e64da999e1d952a247f142cJosef 'Jeff' Sipek g->grp_size > GRP_SET_SIZE_DEFAULT && ISP2(g->grp_size))
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe group_shrink_set(g);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Expand the capacity of group "g" so that it may
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * contain at least "n" elements
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_expand(group_t *g, uint_t n)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe while (g->grp_capacity < n)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe group_grow_set(g);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Upsize a group's holding capacity
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_grow_set(group_t *g)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe uint_t cap_old, cap_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe void **set_old, **set_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe cap_old = g->grp_capacity;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set_old = g->grp_set;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The array size grows in powers of two
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if ((cap_new = (cap_old << 1)) == 0) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The set is unallocated.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Allocate a default sized set.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe cap_new = GRP_SET_SIZE_DEFAULT;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_capacity = cap_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe } else {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Allocate a newly sized array,
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * copy the data, and free the old array.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe (void) kcopy(set_old, set_new, cap_old * sizeof (void *));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set = set_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_capacity = cap_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe kmem_free(set_old, cap_old * sizeof (void *));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The new array size should be a power of two
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(((cap_new - 1) & cap_new) == 0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Downsize a group's holding capacity
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_shrink_set(group_t *g)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe uint_t cap_old, cap_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe void **set_old, **set_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe cap_old = g->grp_capacity;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set_old = g->grp_set;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The group's existing array size must already
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * be a power of two
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(((cap_old - 1) & cap_old) == 0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe cap_new = cap_old >> 1;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * GRP_SET_SIZE_DEFAULT is the minumum set size.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (cap_new < GRP_SET_SIZE_DEFAULT)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe (void) kcopy(set_old, set_new, cap_new * sizeof (void *));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_capacity = cap_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set = set_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(((cap_new - 1) & cap_new) == 0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe kmem_free(set_old, cap_old * sizeof (void *));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Pack a group's set
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Element order is not preserved
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxestatic void
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_pack_set(void **set, uint_t sz)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe uint_t i, j, free;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe free = (uint_t)-1;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe for (i = 0; i < sz; i++) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (set[i] == NULL && free == (uint_t)-1) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Found a new free slot.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Start packing from here.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe free = i;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe } else if (set[i] != NULL && free != (uint_t)-1) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Found a slot to pack into
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * an earlier free slot.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(set[free] == NULL);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set[free] = set[i];
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe set[i] = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Find the next free slot
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe for (j = free + 1; set[j] != NULL; j++) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(j <= i);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (j == i)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe break;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (set[j] == NULL)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe free = j;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe else
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe free = (uint_t)-1;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Initialize a group iterator cookie
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_iter_init(group_iter_t *iter)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *iter = 0;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Iterate over the elements in a group
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_iterate(group_t *g, group_iter_t *iter)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe uint_t idx = *iter;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe void *data = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe while (idx < g->grp_size) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe data = g->grp_set[idx++];
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (data != NULL)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe break;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *iter = idx;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (data);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Indexed access to a group's elements
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_access_at(group_t *g, uint_t idx)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (idx >= g->grp_capacity)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (NULL);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (g->grp_set[idx]);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Add a new ordered group element at specified
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * index. The group must already be of sufficient
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * capacity to hold an element at the specified index.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Returns 0 if addition was sucessful, and -1 if the
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * addition failed because the table was too small
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeint
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_add_at(group_t *g, void *e, uint_t idx)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (idx >= g->grp_capacity)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (-1);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (idx >= g->grp_size)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_size = idx + 1;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(g->grp_set[idx] == NULL);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set[idx] = e;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Remove the element at the specified index
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxegroup_remove_at(group_t *g, uint_t idx)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ASSERT(idx < g->grp_capacity);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe g->grp_set[idx] = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe/*
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Find an element in the group, and return its index
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe * Returns -1 if the element could not be found.
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe */
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxeuint_t
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxegroup_find(group_t *g, void *e)
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe{
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe uint_t idx;
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe for (idx = 0; idx < g->grp_capacity; idx++) {
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe if (g->grp_set[idx] == e)
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe return (idx);
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe }
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe return ((uint_t)-1);
0e7515250c8395f368aa45fb9acae7c4f8f8b786Eric Saxe}
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov/*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Return a string in a given buffer with list of integer entries in a group.
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * The string concatenates consecutive integer ranges ax x-y.
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * The resulting string looks like "1,2-5,8"
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov *
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * The convert argument is used to map group elements to integer IDs.
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasovchar *
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasovgroup2intlist(group_t *group, char *buffer, size_t len, int (convert)(void*))
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov{
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov char *ptr = buffer;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov void *v;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov group_iter_t iter;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov boolean_t first_iteration = B_TRUE;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov boolean_t first_value = B_TRUE;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov int start = 0, end = 0;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Allow for the terminating NULL-byte
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov len = len -1;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov group_iter_init(&iter);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov while ((v = group_iterate(group, &iter)) != NULL && len > 0) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov int id = convert(v);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov int nbytes = 0;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (first_iteration) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov start = end = id;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov first_iteration = B_FALSE;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov } else if (end + 1 == id) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Got consecutive ID, so extend end of range without
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * doing anything since the range may extend further
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov end = id;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov } else {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (first_value) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov first_value = B_FALSE;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov } else {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov *ptr++ = ',';
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov len--;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (len == 0)
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov break;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Next ID is not consecutive, so dump IDs gotten so
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * far.
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (end > start + 1) /* range */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov nbytes = snprintf(ptr, len, "%d-%d",
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov start, end);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov else if (end > start) /* different values */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov nbytes = snprintf(ptr, len, "%d,%d",
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov start, end);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov else /* same value */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov nbytes = snprintf(ptr, len, "%d", start);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (nbytes <= 0) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov len = 0;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov break;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Advance position in the string
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov ptr += nbytes;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov len -= nbytes;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Try finding consecutive range starting from current
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * ID.
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov start = end = id;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (!first_value) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov *ptr++ = ',';
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov len--;
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov /*
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov * Print last ID(s)
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov */
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (len > 0) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov if (end > start + 1) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov (void) snprintf(ptr, len, "%d-%d", start, end);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov } else if (end != start) {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov (void) snprintf(ptr, len, "%d,%d", start, end);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov } else {
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov (void) snprintf(ptr, len, "%d", start);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov }
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov return (buffer);
b885580b43755ee4ea1e280b85428893d2ba9291Alexander Kolbasov}