xref: /titanic_41/usr/src/cmd/sgs/include/alist.h (revision f998c95e3b7029fe5f7542e115f7474ddb8024d7)
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 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  * Define an Alist, a list maintained as a reallocable array, and a for() loop
27  * macro to generalize its traversal.  Note that the array can be reallocated
28  * as it is being traversed, thus the offset of each element is recomputed from
29  * the start of the structure.
30  */
31 
32 #ifndef	_ALIST_H
33 #define	_ALIST_H
34 
35 #pragma ident	"%Z%%M%	%I%	%E% SMI"
36 
37 #ifdef	__cplusplus
38 extern "C" {
39 #endif
40 
41 #include <sys/types.h>
42 #include <sys/machelf.h>
43 
44 /*
45  * An Alist implements array lists. The functionality is similar to
46  * that of a linked list. However, an Alist is represented by a single
47  * contigious allocation of memory. The head of the memory is a header
48  * that contains control information for the list. Following the header
49  * is an array used to hold the user data. In the type definitions that
50  * follow, we define these as an array with a single element, but when
51  * we allocate the memory, we actually allocate the amount of memory needed.
52  *
53  * There are two "flavors" of array list:
54  *
55  *	Alist - Contain arbitrary data, usually structs.
56  *	APlist - Contain pointers to data allocated elsewhere.
57  *
58  * This differentiation is useful, because pointer lists are heavily
59  * used, and support a slightly different set of operations that are
60  * unique to their purpose.
61  *
62  * Array lists are initially represented by a NULL pointer. The memory
63  * for the list is only allocated if an item is inserted. This is very
64  * efficient for data structures that may or may not be needed for a
65  * given linker operation --- you only pay for what you use. In addition:
66  *
67  *	- Array lists grow as needed (memory is reallocated as necessary)
68  *	- Data is kept contiguously (no unused holes in between elements)
69  *		at the beginning of the data area. This locality has
70  *		good cache behavior, as access to adjacent items are
71  *		highly likely to be in the same page of memory.
72  *	- Insert/Delete operations at the end of the list are very
73  *		efficient. However, insert/delete operations elsewhere
74  *		will cause a relatively expensive overlapped memory
75  *		copy of the data following the insert/delete location.
76  *	- As with any generic memory alloctor (i.e. malloc()/free()),
77  *		array lists are not type safe for the data they contain.
78  *		Data is managed as (void *) pointers to data of a given
79  *		length, so the Alist module cannot prevent the caller from
80  *		inserting/extracting the wrong type of data. The caller
81  *		must guard against this.
82  *	- To free an array list, simply call the standard free() function
83  *		on the list pointer.
84  */
85 
86 
87 
88 /*
89  * Aliste is used to represent list indexes, offsets, and sizes.
90  */
91 typedef	size_t	Aliste;
92 
93 
94 
95 /*
96  * Alist is used to hold non-pointer items --- usually structs:
97  *	- There must be an even number of Aliste fields before the
98  *		al_data field. This ensures that al_data will have
99  *		an alignment of 8, no matter whether sizeof(Aliste)
100  *		is 4 or 8. That means that al_data will have sufficient
101  *		alignment for any use, just like memory allocated via
102  *		malloc().
103  *	- al_nitems and al_next are redundant, in that they are
104  *		directly related:
105  *			al_next = al_nitems * al_size
106  *		We do this to make ALIST_TRAVERSE_BYOFFSET maximally
107  *		efficient. This doesn't waste space, because of the
108  *		requirement to have an even # of Alist fields (above).
109  *
110  * Note that Alists allow the data to be referenced by 0 based array
111  * index, or by their byte offset from the start of the Alist memory
112  * allocation. The index form is preferred for most use, as it is simpler.
113  * However, by-offset access is used by rtld link maps, and this ability
114  * is convenient in that case.
115  */
116 typedef struct {
117 	Aliste 		al_arritems;	/* # of items in al_data allocation */
118 	Aliste 		al_nitems;	/* # items (index of next avail item) */
119 	Aliste 		al_next;	/* offset of next available al_data[] */
120 	Aliste		al_size;	/* size of each al_data[] item */
121 	void 		*al_data[1];	/* data (can grow) */
122 } Alist;
123 
124 /*
125  * APlist is a variant of Alist that contains pointers. There are several
126  * benefits to this special type:
127  *	- API is simpler
128  *	- Pointers are used directly, instead of requiring a
129  *		pointer-to-pointer double indirection.
130  *	- The implementation is slightly more efficient.
131  *	- Operations that make particular sense for pointers
132  *		can be supported without confusing the API for the
133  *		regular Alists.
134  */
135 typedef struct {
136 	Aliste		apl_arritems;	/* # of items in apl_data allocation */
137 	Aliste 		apl_nitems;	/* # items (index of next avail item) */
138 	void		*apl_data[1];	/* data area: (arrcnt * size) bytes */
139 } APlist;
140 
141 
142 /*
143  * The ALIST_OFF_DATA and APLIST_OFF_DATA macros give the byte offset
144  * from the start of an array list to the first byte of the data area
145  * used to hold user data. The same trick used by the standard offsetof()
146  * macro is used.
147  */
148 #define	ALIST_OFF_DATA	((size_t)(((Alist *)0)->al_data))
149 #define	APLIST_OFF_DATA	((size_t)(((APlist *)0)->apl_data))
150 
151 
152 /*
153  * The TRAVERSE macros are intended to be used within a for(), and
154  * cause the resulting loop to iterate over each item in the loop,
155  * in order.
156  *	ALIST_TRAVERSE: Traverse over the items in an Alist,
157  *		using the zero based item array index to refer to
158  *		each item.
159  *	ALIST_TRAVERSE_BY_OFFSET: Traverse over the items in an
160  *		Alist using the byte offset from the head of the
161  *		Alist pointer to refer to each item. It should be noted
162  *		that the first such offset is given by ALIST_OFF_DATA,
163  *		and as such, there will never be a 0 offset. Some code
164  *		uses this fact to treat 0 as a reserved value with
165  *		special meaning.
166  *
167  *		By-offset access is convenient for some parts of
168  *		rtld, where a value of 0 is used to indicate an
169  *		uninitialized link map control.
170  *
171  *	APLIST_TRAVERSE: Traverse over the pointers in an APlist, using
172  *		the zero based item array index to refer to each pointer.
173  */
174 
175 /*
176  * Within the loop:
177  *
178  *	LIST - Pointer to Alist structure for list
179  *	IDX - The current item index
180  *	OFF - The current item offset
181  *	DATA - Pointer to item
182  */
183 #define	ALIST_TRAVERSE(LIST, IDX, DATA) \
184 	(IDX) = 0, \
185 	((LIST) != NULL) && ((DATA) = (void *)(LIST)->al_data); \
186 	\
187 	((LIST) != NULL) && ((IDX) < (LIST)->al_nitems); \
188 	\
189 	(IDX)++, \
190 	(DATA) = (void *) (((LIST)->al_size * (IDX)) + (char *)(LIST)->al_data)
191 
192 #define	ALIST_TRAVERSE_BY_OFFSET(LIST, OFF, DATA) \
193 	(((LIST) != NULL) && ((OFF) = ALIST_OFF_DATA) && \
194 	(((DATA) = (void *)((char *)(LIST) + (OFF))))); \
195 	\
196 	(((LIST) != NULL) && ((OFF) < (LIST)->al_next)); \
197 	\
198 	(((OFF) += ((LIST)->al_size)), \
199 	((DATA) = (void *)((char *)(LIST) + (OFF))))
200 
201 /*
202  * Within the loop:
203  *
204  *	LIST - Pointer to APlist structure for list
205  *	IDX - The current item index
206  *	PTR - item value
207  *
208  * Note that this macro is designed to ensure that PTR retains the
209  * value of the final pointer in the list after exiting the for loop,
210  * and to avoid dereferencing an out of range address. This is done by
211  * doing the dereference in the middle expression, using the comma
212  * operator to ensure that a NULL pointer won't stop the loop.
213  */
214 #define	APLIST_TRAVERSE(LIST, IDX, PTR) \
215 	(IDX) = 0; \
216 	\
217 	((LIST) != NULL) && ((IDX) < (LIST)->apl_nitems) && \
218 	(((PTR) = ((LIST)->apl_data)[IDX]), 1); \
219 	\
220 	(IDX)++
221 
222 
223 /*
224  * Possible values returned by aplist_test()
225  */
226 typedef enum {
227 	ALE_ALLOCFAIL = 0,	/* Memory allocation error */
228 	ALE_EXISTS =	1,	/* alist entry already exists */
229 	ALE_NOTFND =	2,	/* item not found and insert not required */
230 	ALE_CREATE =	3	/* alist entry created */
231 } aplist_test_t;
232 
233 
234 /*
235  * Access to an Alist item by index or offset. This is needed because the
236  * size of an item in an Alist is not known by the C compiler, and we
237  * have to do the indexing arithmetic explicitly.
238  *
239  * For an APlist, index the apl_data field directly --- No macro is needed.
240  */
241 #define	alist_item(_lp, _idx) \
242 	((void *)(ALIST_OFF_DATA + ((_idx) * (_lp)->al_size) + (char *)(_lp)))
243 #define	alist_item_by_offset(_lp, _off) \
244 	((void *)((_off) + (char *)(_lp)))
245 
246 /*
247  * # of items currently found in a list. These macros handle the case
248  * where the list has not been allocated yet.
249  */
250 #define	alist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->al_nitems)
251 #define	aplist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->apl_nitems)
252 
253 
254 extern void		*alist_append(Alist **, const void *, size_t, Aliste);
255 extern void		alist_delete(Alist *, Aliste *);
256 extern void		alist_delete_by_offset(Alist *, Aliste *);
257 extern void		*alist_insert(Alist **, const void *, size_t,
258 			    Aliste, Aliste);
259 extern void		*alist_insert_by_offset(Alist **, const void *, size_t,
260 			    Aliste, Aliste);
261 extern void		alist_reset(Alist *);
262 
263 
264 extern void		*aplist_append(APlist **, const void *, Aliste);
265 extern void		aplist_delete(APlist *, Aliste *);
266 extern int		aplist_delete_value(APlist *, const void *);
267 extern void		*aplist_insert(APlist **, const void *,
268 			    Aliste, Aliste idx);
269 extern void		aplist_reset(APlist *);
270 extern aplist_test_t	aplist_test(APlist **, const void *, Aliste);
271 
272 #ifdef	__cplusplus
273 }
274 #endif
275 
276 #endif /* _ALIST_H */
277