alist.c revision 1618:8c9a4f31d225 
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/*
23 * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27#pragma ident	"%Z%%M%	%I%	%E% SMI"
28
29#include <sgs.h>
30#include <string.h>
31
32/*
33 * Alist manipulation.  An Alist is a list of elements formed into an array.
34 * Traversal of the list is an array scan, which because of the locality of
35 * each reference is probably more efficient than a link-list traversal.
36 *
37 * The elements of an Alist are variable length.  They can be pointers to
38 * other data structures, or data structures themselves.  Traversal of an Alist
39 * thus returns a pointer to each data element.
40 *
41 * Alist elements can be deleted.  This involve sliding any following elements
42 * over the element being deleted.  ALIST_TRAVERSE() may be employed to traverse
43 * the list, at the same time elements are being deleted.  Therefore, the next
44 * element is always determined as an offset from the beginning of the list.
45 */
46void *
47alist_append(Alist ** alpp, const void * item, size_t size, int cnt)
48{
49	Alist *	alp = *alpp;
50	void *	new;
51
52	if (alp == 0) {
53		Aliste	bsize, esize = (Aliste)S_ROUND(size, sizeof (void *));
54
55		/*
56		 * First time here, allocate a new Alist.  Note that the Alist
57		 * al_desc[] entry accounts for one void * already.
58		 */
59		bsize = (Aliste)(sizeof (Alist) - sizeof (void *) +
60		    (size * cnt));
61		if ((alp = malloc((size_t)bsize)) == 0)
62			return (0);
63		alp->al_next = sizeof (Alist) - sizeof (void *);
64		alp->al_end = bsize;
65		alp->al_size = esize;
66
67	} else if (alp->al_next == alp->al_end) {
68		Aliste	bsize;
69
70		/*
71		 * The list is full, add another block of elements.  Determine
72		 * the present number of elements and double them.
73		 */
74		bsize = (Aliste)((alp->al_end * 2) - sizeof (Alist) +
75		    sizeof (void *));
76		if ((alp = realloc((void *)alp, (size_t)bsize)) == 0)
77			return (0);
78		alp->al_end = bsize;
79	}
80
81	new = (void *)((char *)alp + alp->al_next);
82	alp->al_next += alp->al_size;
83
84	/*
85	 * If a data item has been provided, initialize the current alist entry
86	 * with this item.  Otherwise, initialize the entry to zero, presumably
87	 * the caller will fill this in.
88	 */
89	if (item)
90		(void) memcpy(new, item, alp->al_size);
91	else
92		(void) memset(new, 0, alp->al_size);
93
94	*alpp = alp;
95	return (new);
96}
97
98/*
99 * Delete an element from an Alist.  If a count is provided then the caller
100 * already knows what element to remove.  Return a decremented count value so
101 * that the caller can continue an ALIST_TRAVERSE scan.
102 */
103int
104alist_delete(Alist *alp, const void *item, Aliste *offp)
105{
106	void	*addr;
107	Aliste	off;
108
109	if (offp) {
110		off = *offp;
111		addr = (void *)((char *)alp + off);
112	} else {
113		for (ALIST_TRAVERSE(alp, off, addr)) {
114			if (memcmp(addr, item, alp->al_size) == 0)
115				break;
116		}
117	}
118
119	if (off >= alp->al_next)
120		return (0);
121
122	/*
123	 * If the element to be removed is not the last entry of the array,
124	 * slide the following elements over the present element.
125	 */
126	if (off < (alp->al_next -= alp->al_size)) {
127		(void) memmove((void *)addr, (void *)((char *)addr +
128		    alp->al_size), (alp->al_next - off));
129	}
130
131	/*
132	 * Reset the new offset, and decrement the callers count control
133	 * variable if necessary.  Null out the old tail element.
134	 */
135	addr = (void *)((char *)alp + alp->al_next);
136	(void) memset(addr, 0, alp->al_size);
137
138	if (offp)
139		*offp -= alp->al_size;
140
141	return (1);
142}
143
144/*
145 * Generic alist test and append routine.
146 */
147int
148alist_test(Alist ** alpp, void * ip, size_t size, int cnt)
149{
150	Aliste	off;
151	void **	ipp;
152
153	for (ALIST_TRAVERSE(*alpp, off, ipp)) {
154		if (size == sizeof (uintptr_t)) {
155			if (ip == *ipp)
156				return (ALE_EXISTS);
157		} else {
158			if (memcmp(ip, *ipp, size) == 0)
159				return (ALE_EXISTS);
160		}
161	}
162
163	if (cnt) {
164		if (alist_append(alpp, &ip, size, cnt) == 0)
165			return (0);
166	}
167	return (ALE_CREATE);
168}
169