1 files changed, 322 insertions, 0 deletions
diff --git a/usr/src/uts/common/os/group.c b/usr/src/uts/common/os/group.c
new file mode 100644
index 0000000000..b15dff181f
--- /dev/null
+++ b/usr/src/uts/common/os/group.c
@@ -0,0 +1,322 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+#include <sys/systm.h>
+#include <sys/param.h>
+#include <sys/debug.h>
+#include <sys/kmem.h>
+#include <sys/group.h>
+
+
+#define	GRP_SET_SIZE_DEFAULT 2
+
+static void group_grow_set(group_t *);
+static void group_shrink_set(group_t *);
+static void group_pack_set(void **, uint_t);
+
+/*
+ * Initialize a group_t
+ */
+void
+group_create(group_t *g)
+{
+	bzero(g, sizeof (group_t));
+}
+
+/*
+ * Destroy a group_t
+ * The group must already be empty
+ */
+void
+group_destroy(group_t *g)
+{
+	ASSERT(g->grp_size == 0);
+
+	if (g->grp_capacity > 0) {
+		kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
+		g->grp_capacity = 0;
+	}
+	g->grp_set = NULL;
+}
+
+/*
+ * Add element "e" to group "g"
+ *
+ * Returns -1 if addition would result in overcapacity, and
+ * resize operations aren't allowed, and 0 otherwise
+ */
+int
+group_add(group_t *g, void *e, int gflag)
+{
+	int	entry;
+
+	if ((gflag & GRP_NORESIZE) &&
+	    g->grp_size == g->grp_capacity)
+		return (-1);
+
+	ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
+
+	entry = g->grp_size++;
+	if (g->grp_size > g->grp_capacity)
+		group_grow_set(g);
+
+	ASSERT(g->grp_set[entry] == NULL);
+	g->grp_set[entry] = e;
+
+	return (0);
+}
+
+/*
+ * Remove element "e" from group "g"
+ *
+ * Returns -1 if "e" was not present in "g" and 0 otherwise
+ */
+int
+group_remove(group_t *g, void *e, int gflag)
+{
+	int	i;
+
+	/*
+	 * Find the element in the group's set
+	 */
+	for (i = 0; i < g->grp_size; i++)
+		if (g->grp_set[i] == e)
+			break;
+	if (g->grp_set[i] != e)
+		return (-1);
+
+	g->grp_set[i] = NULL;
+	group_pack_set(g->grp_set, g->grp_size);
+	g->grp_size--;
+
+	if ((gflag & GRP_RESIZE) &&
+	    g->grp_size > GRP_SET_SIZE_DEFAULT &&
+	    ((g->grp_size - 1) & g->grp_size) == 0)
+		group_shrink_set(g);
+
+	return (0);
+}
+
+/*
+ * Expand the capacity of group "g" so that it may
+ * contain at least "n" elements
+ */
+void
+group_expand(group_t *g, uint_t n)
+{
+	while (g->grp_capacity < n)
+		group_grow_set(g);
+}
+
+/*
+ * Upsize a group's holding capacity
+ */
+static void
+group_grow_set(group_t *g)
+{
+	uint_t		cap_old, cap_new;
+	void		**set_old, **set_new;
+
+	cap_old = g->grp_capacity;
+	set_old = g->grp_set;
+
+	/*
+	 * The array size grows in powers of two
+	 */
+	if ((cap_new = (cap_old << 1)) == 0) {
+		/*
+		 * The set is unallocated.
+		 * Allocate a default sized set.
+		 */
+		cap_new = GRP_SET_SIZE_DEFAULT;
+		g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
+		g->grp_capacity = cap_new;
+	} else {
+		/*
+		 * Allocate a newly sized array,
+		 * copy the data, and free the old array.
+		 */
+		set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
+		(void) kcopy(set_old, set_new, cap_old * sizeof (void *));
+		g->grp_set = set_new;
+		g->grp_capacity = cap_new;
+		kmem_free(set_old, cap_old * sizeof (void *));
+	}
+	/*
+	 * The new array size should be a power of two
+	 */
+	ASSERT(((cap_new - 1) & cap_new) == 0);
+}
+
+/*
+ * Downsize a group's holding capacity
+ */
+static void
+group_shrink_set(group_t *g)
+{
+	uint_t		cap_old, cap_new;
+	void		**set_old, **set_new;
+
+	cap_old = g->grp_capacity;
+	set_old = g->grp_set;
+
+	/*
+	 * The group's existing array size must already
+	 * be a power of two
+	 */
+	ASSERT(((cap_old - 1) & cap_old) == 0);
+	cap_new = cap_old >> 1;
+
+	/*
+	 * GRP_SET_SIZE_DEFAULT is the minumum set size.
+	 */
+	if (cap_new < GRP_SET_SIZE_DEFAULT)
+		return;
+
+	set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
+	(void) kcopy(set_old, set_new, cap_new * sizeof (void *));
+	g->grp_capacity = cap_new;
+	g->grp_set = set_new;
+
+	ASSERT(((cap_new - 1) & cap_new) == 0);
+	kmem_free(set_old, cap_old * sizeof (void *));
+}
+
+/*
+ * Pack a group's set
+ * Element order is not preserved
+ */
+static void
+group_pack_set(void **set, uint_t sz)
+{
+	uint_t	i, j, free;
+
+	free = (uint_t)-1;
+
+	for (i = 0; i < sz; i++) {
+		if (set[i] == NULL && free == (uint_t)-1) {
+			/*
+			 * Found a new free slot.
+			 * Start packing from here.
+			 */
+			free = i;
+		} else if (set[i] != NULL && free != (uint_t)-1) {
+			/*
+			 * Found a slot to pack into
+			 * an earlier free slot.
+			 */
+			ASSERT(set[free] == NULL);
+			set[free] = set[i];
+			set[i] = NULL;
+
+			/*
+			 * Find the next free slot
+			 */
+			for (j = free + 1; set[j] != NULL; j++) {
+				ASSERT(j <= i);
+				if (j == i)
+					break;
+			}
+			if (set[j] == NULL)
+				free = j;
+			else
+				free = (uint_t)-1;
+		}
+	}
+}
+
+/*
+ * Initialize a group iterator cookie
+ */
+void
+group_iter_init(group_iter_t *iter)
+{
+	*iter = 0;
+}
+
+/*
+ * Iterate over the elements in a group
+ */
+void *
+group_iterate(group_t *g, group_iter_t *iter)
+{
+	uint_t	idx = *iter;
+	void	*data = NULL;
+
+	while (idx < g->grp_size) {
+		data = g->grp_set[idx++];
+		if (data != NULL)
+			break;
+	}
+	*iter = idx;
+
+	return (data);
+}
+
+/*
+ * Indexed access to a group's elements
+ */
+void *
+group_access_at(group_t *g, uint_t idx)
+{
+	if (idx >= g->grp_capacity)
+		return (NULL);
+
+	return (g->grp_set[idx]);
+}
+
+/*
+ * Add a new ordered group element at specified
+ * index. The group must already be of sufficient
+ * capacity to hold an element at the specified index.
+ *
+ * Returns 0 if addition was sucessful, and -1 if the
+ * addition failed because the table was too small
+ */
+int
+group_add_at(group_t *g, void *e, uint_t idx)
+{
+	if (idx >= g->grp_capacity)
+		return (-1);
+
+	if (idx >= g->grp_size)
+		g->grp_size = idx + 1;
+
+	ASSERT(g->grp_set[idx] == NULL);
+	g->grp_set[idx] = e;
+	return (0);
+}
+
+/*
+ * Remove the entry at the specified index
+ */
+void
+group_remove_at(group_t *g, uint_t idx)
+{
+	ASSERT(idx < g->grp_capacity);
+	g->grp_set[idx] = NULL;
+}