common/os/group.c

/*
 * 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 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#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;
}

/*
 * Empty a group_t
 * Capacity is preserved.
 */
void
group_empty(group_t *g)
{
	int	i;
	int	sz = g->grp_size;

	g->grp_size = 0;
	for (i = 0; i < sz; i++)
		g->grp_set[i] = 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;

	if (g->grp_size == 0)
		return (-1);

	/*
	 * 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 element at the specified index
 */
void
group_remove_at(group_t *g, uint_t idx)
{
	ASSERT(idx < g->grp_capacity);
	g->grp_set[idx] = NULL;
}

/*
 * Find an element in the group, and return its index
 * Returns -1 if the element could not be found.
 */
uint_t
group_find(group_t *g, void *e)
{
	uint_t	idx;

	for (idx = 0; idx < g->grp_capacity; idx++) {
		if (g->grp_set[idx] == e)
			return (idx);
	}
	return ((uint_t)-1);
}