path: root/usr/src/uts/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/sysmacros.h>
#include <sys/systm.h>
#include <sys/param.h>
#include <sys/debug.h>
#include <sys/kmem.h>
#include <sys/group.h>
#include <sys/cmn_err.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 && ISP2(g->grp_size))
		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);
}

/*
 * Return a string in a given buffer with list of integer entries in a group.
 * The string concatenates consecutive integer ranges ax x-y.
 * The resulting string looks like "1,2-5,8"
 *
 * The convert argument is used to map group elements to integer IDs.
 */
char *
group2intlist(group_t *group, char *buffer, size_t len, int (convert)(void*))
{
	char		*ptr = buffer;
	void		*v;
	group_iter_t	iter;
	boolean_t	first_iteration = B_TRUE;
	boolean_t	first_value = B_TRUE;
	int		start = 0, end = 0;

	/*
	 * Allow for the terminating NULL-byte
	 */
	len = len -1;

	group_iter_init(&iter);
	while ((v = group_iterate(group, &iter)) != NULL && len > 0) {
		int id = convert(v);
		int nbytes = 0;

		if (first_iteration) {
			start = end = id;
			first_iteration = B_FALSE;
		} else if (end + 1 == id) {
			/*
			 * Got consecutive ID, so extend end of range without
			 * doing anything since the range may extend further
			 */
			end = id;
		} else {
			if (first_value) {
				first_value = B_FALSE;
			} else {
				*ptr++ = ',';
				len--;
			}

			if (len == 0)
				break;

			/*
			 * Next ID is not consecutive, so dump IDs gotten so
			 * far.
			 */
			if (end > start + 1) /* range */
				nbytes = snprintf(ptr, len, "%d-%d",
				    start, end);
			else if (end > start) /* different values */
				nbytes = snprintf(ptr, len, "%d,%d",
				    start, end);
			else /* same value */
				nbytes = snprintf(ptr, len, "%d", start);

			if (nbytes <= 0) {
				len = 0;
				break;
			}

			/*
			 * Advance position in the string
			 */
			ptr += nbytes;
			len -= nbytes;

			/*
			 * Try finding consecutive range starting from current
			 * ID.
			 */
			start = end = id;
		}
	}

	if (!first_value) {
		*ptr++ = ',';
		len--;
	}
	/*
	 * Print last ID(s)
	 */
	if (len > 0) {
		if (end > start + 1) {
			(void) snprintf(ptr, len, "%d-%d", start, end);
		} else if (end != start) {
			(void) snprintf(ptr, len, "%d,%d", start, end);
		} else {
			(void) snprintf(ptr, len, "%d", start);
		}
	}

	return (buffer);
}