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