Home | History | Annotate | Download | only in os
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License (the "License").
      6  * You may not use this file except in compliance with the License.
      7  *
      8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
      9  * or http://www.opensolaris.org/os/licensing.
     10  * See the License for the specific language governing permissions
     11  * and limitations under the License.
     12  *
     13  * When distributing Covered Code, include this CDDL HEADER in each
     14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     15  * If applicable, add the following below this CDDL HEADER, with the
     16  * fields enclosed by brackets "[]" replaced with your own identifying
     17  * information: Portions Copyright [yyyy] [name of copyright owner]
     18  *
     19  * CDDL HEADER END
     20  */
     21 /*
     22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
     23  * Use is subject to license terms.
     24  */
     25 
     26 #pragma ident	"@(#)group.c	1.1	07/01/17 SMI"
     27 
     28 #include <sys/systm.h>
     29 #include <sys/param.h>
     30 #include <sys/debug.h>
     31 #include <sys/kmem.h>
     32 #include <sys/group.h>
     33 
     34 
     35 #define	GRP_SET_SIZE_DEFAULT 2
     36 
     37 static void group_grow_set(group_t *);
     38 static void group_shrink_set(group_t *);
     39 static void group_pack_set(void **, uint_t);
     40 
     41 /*
     42  * Initialize a group_t
     43  */
     44 void
     45 group_create(group_t *g)
     46 {
     47 	bzero(g, sizeof (group_t));
     48 }
     49 
     50 /*
     51  * Destroy a group_t
     52  * The group must already be empty
     53  */
     54 void
     55 group_destroy(group_t *g)
     56 {
     57 	ASSERT(g->grp_size == 0);
     58 
     59 	if (g->grp_capacity > 0) {
     60 		kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
     61 		g->grp_capacity = 0;
     62 	}
     63 	g->grp_set = NULL;
     64 }
     65 
     66 /*
     67  * Add element "e" to group "g"
     68  *
     69  * Returns -1 if addition would result in overcapacity, and
     70  * resize operations aren't allowed, and 0 otherwise
     71  */
     72 int
     73 group_add(group_t *g, void *e, int gflag)
     74 {
     75 	int	entry;
     76 
     77 	if ((gflag & GRP_NORESIZE) &&
     78 	    g->grp_size == g->grp_capacity)
     79 		return (-1);
     80 
     81 	ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
     82 
     83 	entry = g->grp_size++;
     84 	if (g->grp_size > g->grp_capacity)
     85 		group_grow_set(g);
     86 
     87 	ASSERT(g->grp_set[entry] == NULL);
     88 	g->grp_set[entry] = e;
     89 
     90 	return (0);
     91 }
     92 
     93 /*
     94  * Remove element "e" from group "g"
     95  *
     96  * Returns -1 if "e" was not present in "g" and 0 otherwise
     97  */
     98 int
     99 group_remove(group_t *g, void *e, int gflag)
    100 {
    101 	int	i;
    102 
    103 	/*
    104 	 * Find the element in the group's set
    105 	 */
    106 	for (i = 0; i < g->grp_size; i++)
    107 		if (g->grp_set[i] == e)
    108 			break;
    109 	if (g->grp_set[i] != e)
    110 		return (-1);
    111 
    112 	g->grp_set[i] = NULL;
    113 	group_pack_set(g->grp_set, g->grp_size);
    114 	g->grp_size--;
    115 
    116 	if ((gflag & GRP_RESIZE) &&
    117 	    g->grp_size > GRP_SET_SIZE_DEFAULT &&
    118 	    ((g->grp_size - 1) & g->grp_size) == 0)
    119 		group_shrink_set(g);
    120 
    121 	return (0);
    122 }
    123 
    124 /*
    125  * Expand the capacity of group "g" so that it may
    126  * contain at least "n" elements
    127  */
    128 void
    129 group_expand(group_t *g, uint_t n)
    130 {
    131 	while (g->grp_capacity < n)
    132 		group_grow_set(g);
    133 }
    134 
    135 /*
    136  * Upsize a group's holding capacity
    137  */
    138 static void
    139 group_grow_set(group_t *g)
    140 {
    141 	uint_t		cap_old, cap_new;
    142 	void		**set_old, **set_new;
    143 
    144 	cap_old = g->grp_capacity;
    145 	set_old = g->grp_set;
    146 
    147 	/*
    148 	 * The array size grows in powers of two
    149 	 */
    150 	if ((cap_new = (cap_old << 1)) == 0) {
    151 		/*
    152 		 * The set is unallocated.
    153 		 * Allocate a default sized set.
    154 		 */
    155 		cap_new = GRP_SET_SIZE_DEFAULT;
    156 		g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
    157 		g->grp_capacity = cap_new;
    158 	} else {
    159 		/*
    160 		 * Allocate a newly sized array,
    161 		 * copy the data, and free the old array.
    162 		 */
    163 		set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
    164 		(void) kcopy(set_old, set_new, cap_old * sizeof (void *));
    165 		g->grp_set = set_new;
    166 		g->grp_capacity = cap_new;
    167 		kmem_free(set_old, cap_old * sizeof (void *));
    168 	}
    169 	/*
    170 	 * The new array size should be a power of two
    171 	 */
    172 	ASSERT(((cap_new - 1) & cap_new) == 0);
    173 }
    174 
    175 /*
    176  * Downsize a group's holding capacity
    177  */
    178 static void
    179 group_shrink_set(group_t *g)
    180 {
    181 	uint_t		cap_old, cap_new;
    182 	void		**set_old, **set_new;
    183 
    184 	cap_old = g->grp_capacity;
    185 	set_old = g->grp_set;
    186 
    187 	/*
    188 	 * The group's existing array size must already
    189 	 * be a power of two
    190 	 */
    191 	ASSERT(((cap_old - 1) & cap_old) == 0);
    192 	cap_new = cap_old >> 1;
    193 
    194 	/*
    195 	 * GRP_SET_SIZE_DEFAULT is the minumum set size.
    196 	 */
    197 	if (cap_new < GRP_SET_SIZE_DEFAULT)
    198 		return;
    199 
    200 	set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
    201 	(void) kcopy(set_old, set_new, cap_new * sizeof (void *));
    202 	g->grp_capacity = cap_new;
    203 	g->grp_set = set_new;
    204 
    205 	ASSERT(((cap_new - 1) & cap_new) == 0);
    206 	kmem_free(set_old, cap_old * sizeof (void *));
    207 }
    208 
    209 /*
    210  * Pack a group's set
    211  * Element order is not preserved
    212  */
    213 static void
    214 group_pack_set(void **set, uint_t sz)
    215 {
    216 	uint_t	i, j, free;
    217 
    218 	free = (uint_t)-1;
    219 
    220 	for (i = 0; i < sz; i++) {
    221 		if (set[i] == NULL && free == (uint_t)-1) {
    222 			/*
    223 			 * Found a new free slot.
    224 			 * Start packing from here.
    225 			 */
    226 			free = i;
    227 		} else if (set[i] != NULL && free != (uint_t)-1) {
    228 			/*
    229 			 * Found a slot to pack into
    230 			 * an earlier free slot.
    231 			 */
    232 			ASSERT(set[free] == NULL);
    233 			set[free] = set[i];
    234 			set[i] = NULL;
    235 
    236 			/*
    237 			 * Find the next free slot
    238 			 */
    239 			for (j = free + 1; set[j] != NULL; j++) {
    240 				ASSERT(j <= i);
    241 				if (j == i)
    242 					break;
    243 			}
    244 			if (set[j] == NULL)
    245 				free = j;
    246 			else
    247 				free = (uint_t)-1;
    248 		}
    249 	}
    250 }
    251 
    252 /*
    253  * Initialize a group iterator cookie
    254  */
    255 void
    256 group_iter_init(group_iter_t *iter)
    257 {
    258 	*iter = 0;
    259 }
    260 
    261 /*
    262  * Iterate over the elements in a group
    263  */
    264 void *
    265 group_iterate(group_t *g, group_iter_t *iter)
    266 {
    267 	uint_t	idx = *iter;
    268 	void	*data = NULL;
    269 
    270 	while (idx < g->grp_size) {
    271 		data = g->grp_set[idx++];
    272 		if (data != NULL)
    273 			break;
    274 	}
    275 	*iter = idx;
    276 
    277 	return (data);
    278 }
    279 
    280 /*
    281  * Indexed access to a group's elements
    282  */
    283 void *
    284 group_access_at(group_t *g, uint_t idx)
    285 {
    286 	if (idx >= g->grp_capacity)
    287 		return (NULL);
    288 
    289 	return (g->grp_set[idx]);
    290 }
    291 
    292 /*
    293  * Add a new ordered group element at specified
    294  * index. The group must already be of sufficient
    295  * capacity to hold an element at the specified index.
    296  *
    297  * Returns 0 if addition was sucessful, and -1 if the
    298  * addition failed because the table was too small
    299  */
    300 int
    301 group_add_at(group_t *g, void *e, uint_t idx)
    302 {
    303 	if (idx >= g->grp_capacity)
    304 		return (-1);
    305 
    306 	if (idx >= g->grp_size)
    307 		g->grp_size = idx + 1;
    308 
    309 	ASSERT(g->grp_set[idx] == NULL);
    310 	g->grp_set[idx] = e;
    311 	return (0);
    312 }
    313 
    314 /*
    315  * Remove the entry at the specified index
    316  */
    317 void
    318 group_remove_at(group_t *g, uint_t idx)
    319 {
    320 	ASSERT(idx < g->grp_capacity);
    321 	g->grp_set[idx] = NULL;
    322 }
    323