common/os/group.c

	group.c revision 0e7515250c8395f368aa45fb9acae7c4f8f8b786
/*
 * 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;

    /*
     * 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);
}