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 2009 Sun Microsystems, Inc.  All rights reserved.
23 * Use is subject to license terms.
24 */
25
26#include <sys/systm.h>
27#include <sys/param.h>
28#include <sys/debug.h>
29#include <sys/kmem.h>
30#include <sys/group.h>
31#include <sys/cmn_err.h>
32
33
34#define	GRP_SET_SIZE_DEFAULT 2
35
36static void group_grow_set(group_t *);
37static void group_shrink_set(group_t *);
38static void group_pack_set(void **, uint_t);
39
40/*
41 * Initialize a group_t
42 */
43void
44group_create(group_t *g)
45{
46	bzero(g, sizeof (group_t));
47}
48
49/*
50 * Destroy a group_t
51 * The group must already be empty
52 */
53void
54group_destroy(group_t *g)
55{
56	ASSERT(g->grp_size == 0);
57
58	if (g->grp_capacity > 0) {
59		kmem_free(g->grp_set, g->grp_capacity * sizeof (void *));
60		g->grp_capacity = 0;
61	}
62	g->grp_set = NULL;
63}
64
65/*
66 * Empty a group_t
67 * Capacity is preserved.
68 */
69void
70group_empty(group_t *g)
71{
72	int	i;
73	int	sz = g->grp_size;
74
75	g->grp_size = 0;
76	for (i = 0; i < sz; i++)
77		g->grp_set[i] = NULL;
78}
79
80/*
81 * Add element "e" to group "g"
82 *
83 * Returns -1 if addition would result in overcapacity, and
84 * resize operations aren't allowed, and 0 otherwise
85 */
86int
87group_add(group_t *g, void *e, int gflag)
88{
89	int	entry;
90
91	if ((gflag & GRP_NORESIZE) &&
92	    g->grp_size == g->grp_capacity)
93		return (-1);
94
95	ASSERT(g->grp_size != g->grp_capacity || (gflag & GRP_RESIZE));
96
97	entry = g->grp_size++;
98	if (g->grp_size > g->grp_capacity)
99		group_grow_set(g);
100
101	ASSERT(g->grp_set[entry] == NULL);
102	g->grp_set[entry] = e;
103
104	return (0);
105}
106
107/*
108 * Remove element "e" from group "g"
109 *
110 * Returns -1 if "e" was not present in "g" and 0 otherwise
111 */
112int
113group_remove(group_t *g, void *e, int gflag)
114{
115	int	i;
116
117	if (g->grp_size == 0)
118		return (-1);
119
120	/*
121	 * Find the element in the group's set
122	 */
123	for (i = 0; i < g->grp_size; i++)
124		if (g->grp_set[i] == e)
125			break;
126	if (g->grp_set[i] != e)
127		return (-1);
128
129	g->grp_set[i] = NULL;
130	group_pack_set(g->grp_set, g->grp_size);
131	g->grp_size--;
132
133	if ((gflag & GRP_RESIZE) &&
134	    g->grp_size > GRP_SET_SIZE_DEFAULT &&
135	    ((g->grp_size - 1) & g->grp_size) == 0)
136		group_shrink_set(g);
137
138	return (0);
139}
140
141/*
142 * Expand the capacity of group "g" so that it may
143 * contain at least "n" elements
144 */
145void
146group_expand(group_t *g, uint_t n)
147{
148	while (g->grp_capacity < n)
149		group_grow_set(g);
150}
151
152/*
153 * Upsize a group's holding capacity
154 */
155static void
156group_grow_set(group_t *g)
157{
158	uint_t		cap_old, cap_new;
159	void		**set_old, **set_new;
160
161	cap_old = g->grp_capacity;
162	set_old = g->grp_set;
163
164	/*
165	 * The array size grows in powers of two
166	 */
167	if ((cap_new = (cap_old << 1)) == 0) {
168		/*
169		 * The set is unallocated.
170		 * Allocate a default sized set.
171		 */
172		cap_new = GRP_SET_SIZE_DEFAULT;
173		g->grp_set = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
174		g->grp_capacity = cap_new;
175	} else {
176		/*
177		 * Allocate a newly sized array,
178		 * copy the data, and free the old array.
179		 */
180		set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
181		(void) kcopy(set_old, set_new, cap_old * sizeof (void *));
182		g->grp_set = set_new;
183		g->grp_capacity = cap_new;
184		kmem_free(set_old, cap_old * sizeof (void *));
185	}
186	/*
187	 * The new array size should be a power of two
188	 */
189	ASSERT(((cap_new - 1) & cap_new) == 0);
190}
191
192/*
193 * Downsize a group's holding capacity
194 */
195static void
196group_shrink_set(group_t *g)
197{
198	uint_t		cap_old, cap_new;
199	void		**set_old, **set_new;
200
201	cap_old = g->grp_capacity;
202	set_old = g->grp_set;
203
204	/*
205	 * The group's existing array size must already
206	 * be a power of two
207	 */
208	ASSERT(((cap_old - 1) & cap_old) == 0);
209	cap_new = cap_old >> 1;
210
211	/*
212	 * GRP_SET_SIZE_DEFAULT is the minumum set size.
213	 */
214	if (cap_new < GRP_SET_SIZE_DEFAULT)
215		return;
216
217	set_new = kmem_zalloc(cap_new * sizeof (void *), KM_SLEEP);
218	(void) kcopy(set_old, set_new, cap_new * sizeof (void *));
219	g->grp_capacity = cap_new;
220	g->grp_set = set_new;
221
222	ASSERT(((cap_new - 1) & cap_new) == 0);
223	kmem_free(set_old, cap_old * sizeof (void *));
224}
225
226/*
227 * Pack a group's set
228 * Element order is not preserved
229 */
230static void
231group_pack_set(void **set, uint_t sz)
232{
233	uint_t	i, j, free;
234
235	free = (uint_t)-1;
236
237	for (i = 0; i < sz; i++) {
238		if (set[i] == NULL && free == (uint_t)-1) {
239			/*
240			 * Found a new free slot.
241			 * Start packing from here.
242			 */
243			free = i;
244		} else if (set[i] != NULL && free != (uint_t)-1) {
245			/*
246			 * Found a slot to pack into
247			 * an earlier free slot.
248			 */
249			ASSERT(set[free] == NULL);
250			set[free] = set[i];
251			set[i] = NULL;
252
253			/*
254			 * Find the next free slot
255			 */
256			for (j = free + 1; set[j] != NULL; j++) {
257				ASSERT(j <= i);
258				if (j == i)
259					break;
260			}
261			if (set[j] == NULL)
262				free = j;
263			else
264				free = (uint_t)-1;
265		}
266	}
267}
268
269/*
270 * Initialize a group iterator cookie
271 */
272void
273group_iter_init(group_iter_t *iter)
274{
275	*iter = 0;
276}
277
278/*
279 * Iterate over the elements in a group
280 */
281void *
282group_iterate(group_t *g, group_iter_t *iter)
283{
284	uint_t	idx = *iter;
285	void	*data = NULL;
286
287	while (idx < g->grp_size) {
288		data = g->grp_set[idx++];
289		if (data != NULL)
290			break;
291	}
292	*iter = idx;
293
294	return (data);
295}
296
297/*
298 * Indexed access to a group's elements
299 */
300void *
301group_access_at(group_t *g, uint_t idx)
302{
303	if (idx >= g->grp_capacity)
304		return (NULL);
305
306	return (g->grp_set[idx]);
307}
308
309/*
310 * Add a new ordered group element at specified
311 * index. The group must already be of sufficient
312 * capacity to hold an element at the specified index.
313 *
314 * Returns 0 if addition was sucessful, and -1 if the
315 * addition failed because the table was too small
316 */
317int
318group_add_at(group_t *g, void *e, uint_t idx)
319{
320	if (idx >= g->grp_capacity)
321		return (-1);
322
323	if (idx >= g->grp_size)
324		g->grp_size = idx + 1;
325
326	ASSERT(g->grp_set[idx] == NULL);
327	g->grp_set[idx] = e;
328	return (0);
329}
330
331/*
332 * Remove the element at the specified index
333 */
334void
335group_remove_at(group_t *g, uint_t idx)
336{
337	ASSERT(idx < g->grp_capacity);
338	g->grp_set[idx] = NULL;
339}
340
341/*
342 * Find an element in the group, and return its index
343 * Returns -1 if the element could not be found.
344 */
345uint_t
346group_find(group_t *g, void *e)
347{
348	uint_t	idx;
349
350	for (idx = 0; idx < g->grp_capacity; idx++) {
351		if (g->grp_set[idx] == e)
352			return (idx);
353	}
354	return ((uint_t)-1);
355}
356
357/*
358 * Return a string in a given buffer with list of integer entries in a group.
359 * The string concatenates consecutive integer ranges ax x-y.
360 * The resulting string looks like "1,2-5,8"
361 *
362 * The convert argument is used to map group elements to integer IDs.
363 */
364char *
365group2intlist(group_t *group, char *buffer, size_t len, int (convert)(void*))
366{
367	char		*ptr = buffer;
368	void		*v;
369	group_iter_t	iter;
370	boolean_t	first_iteration = B_TRUE;
371	boolean_t	first_value = B_TRUE;
372	int		start = 0, end = 0;
373
374	/*
375	 * Allow for the terminating NULL-byte
376	 */
377	len = len -1;
378
379	group_iter_init(&iter);
380	while ((v = group_iterate(group, &iter)) != NULL && len > 0) {
381		int id = convert(v);
382		int nbytes = 0;
383
384		if (first_iteration) {
385			start = end = id;
386			first_iteration = B_FALSE;
387		} else if (end + 1 == id) {
388			/*
389			 * Got consecutive ID, so extend end of range without
390			 * doing anything since the range may extend further
391			 */
392			end = id;
393		} else {
394			if (first_value) {
395				first_value = B_FALSE;
396			} else {
397				*ptr++ = ',';
398				len--;
399			}
400
401			if (len == 0)
402				break;
403
404			/*
405			 * Next ID is not consecutive, so dump IDs gotten so
406			 * far.
407			 */
408			if (end > start + 1) /* range */
409				nbytes = snprintf(ptr, len, "%d-%d",
410				    start, end);
411			else if (end > start) /* different values */
412				nbytes = snprintf(ptr, len, "%d,%d",
413				    start, end);
414			else /* same value */
415				nbytes = snprintf(ptr, len, "%d", start);
416
417			if (nbytes <= 0) {
418				len = 0;
419				break;
420			}
421
422			/*
423			 * Advance position in the string
424			 */
425			ptr += nbytes;
426			len -= nbytes;
427
428			/*
429			 * Try finding consecutive range starting from current
430			 * ID.
431			 */
432			start = end = id;
433		}
434	}
435
436	if (!first_value) {
437		*ptr++ = ',';
438		len--;
439	}
440	/*
441	 * Print last ID(s)
442	 */
443	if (len > 0) {
444		if (end > start + 1) {
445			(void) snprintf(ptr, len, "%d-%d", start, end);
446		} else if (end != start) {
447			(void) snprintf(ptr, len, "%d,%d", start, end);
448		} else {
449			(void) snprintf(ptr, len, "%d", start);
450		}
451	}
452
453	return (buffer);
454}
455