aboutsummaryrefslogtreecommitdiff
path: root/cddl/contrib/opensolaris/cmd/sgs/include/alist.h
blob: 2b790b7151768d56bfaa028f3361ca3c811880f4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * Define an Alist, a list maintained as a reallocable array, and a for() loop
 * macro to generalize its traversal.  Note that the array can be reallocated
 * as it is being traversed, thus the offset of each element is recomputed from
 * the start of the structure.
 */

#ifndef	_ALIST_H
#define	_ALIST_H

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#ifdef	__cplusplus
extern "C" {
#endif

#include <sys/types.h>
#ifdef illumos
#include <sys/machelf.h>
#else
#include <sys/elf.h>
#endif

/*
 * An Alist implements array lists. The functionality is similar to
 * that of a linked list. However, an Alist is represented by a single
 * contigious allocation of memory. The head of the memory is a header
 * that contains control information for the list. Following the header
 * is an array used to hold the user data. In the type definitions that
 * follow, we define these as an array with a single element, but when
 * we allocate the memory, we actually allocate the amount of memory needed.
 *
 * There are two "flavors" of array list:
 *
 *	Alist - Contain arbitrary data, usually structs.
 *	APlist - Contain pointers to data allocated elsewhere.
 *
 * This differentiation is useful, because pointer lists are heavily
 * used, and support a slightly different set of operations that are
 * unique to their purpose.
 *
 * Array lists are initially represented by a NULL pointer. The memory
 * for the list is only allocated if an item is inserted. This is very
 * efficient for data structures that may or may not be needed for a
 * given linker operation --- you only pay for what you use. In addition:
 *
 *	- Array lists grow as needed (memory is reallocated as necessary)
 *	- Data is kept contiguously (no unused holes in between elements)
 *		at the beginning of the data area. This locality has
 *		good cache behavior, as access to adjacent items are
 *		highly likely to be in the same page of memory.
 *	- Insert/Delete operations at the end of the list are very
 *		efficient. However, insert/delete operations elsewhere
 *		will cause a relatively expensive overlapped memory
 *		copy of the data following the insert/delete location.
 *	- As with any generic memory alloctor (i.e. malloc()/free()),
 *		array lists are not type safe for the data they contain.
 *		Data is managed as (void *) pointers to data of a given
 *		length, so the Alist module cannot prevent the caller from
 *		inserting/extracting the wrong type of data. The caller
 *		must guard against this.
 *	- To free an array list, simply call the standard free() function
 *		on the list pointer.
 */



/*
 * Aliste is used to represent list indexes, offsets, and sizes.
 */
typedef	size_t	Aliste;



/*
 * Alist is used to hold non-pointer items --- usually structs:
 *	- There must be an even number of Aliste fields before the
 *		al_data field. This ensures that al_data will have
 *		an alignment of 8, no matter whether sizeof(Aliste)
 *		is 4 or 8. That means that al_data will have sufficient
 *		alignment for any use, just like memory allocated via
 *		malloc().
 *	- al_nitems and al_next are redundant, in that they are
 *		directly related:
 *			al_next = al_nitems * al_size
 *		We do this to make ALIST_TRAVERSE_BYOFFSET maximally
 *		efficient. This doesn't waste space, because of the
 *		requirement to have an even # of Alist fields (above).
 *
 * Note that Alists allow the data to be referenced by 0 based array
 * index, or by their byte offset from the start of the Alist memory
 * allocation. The index form is preferred for most use, as it is simpler.
 * However, by-offset access is used by rtld link maps, and this ability
 * is convenient in that case.
 */
typedef struct {
	Aliste 		al_arritems;	/* # of items in al_data allocation */
	Aliste 		al_nitems;	/* # items (index of next avail item) */
	Aliste 		al_next;	/* offset of next available al_data[] */
	Aliste		al_size;	/* size of each al_data[] item */
	void 		*al_data[1];	/* data (can grow) */
} Alist;

/*
 * APlist is a variant of Alist that contains pointers. There are several
 * benefits to this special type:
 *	- API is simpler
 *	- Pointers are used directly, instead of requiring a
 *		pointer-to-pointer double indirection.
 *	- The implementation is slightly more efficient.
 *	- Operations that make particular sense for pointers
 *		can be supported without confusing the API for the
 *		regular Alists.
 */
typedef struct {
	Aliste		apl_arritems;	/* # of items in apl_data allocation */
	Aliste 		apl_nitems;	/* # items (index of next avail item) */
	void		*apl_data[1];	/* data area: (arrcnt * size) bytes */
} APlist;


/*
 * The ALIST_OFF_DATA and APLIST_OFF_DATA macros give the byte offset
 * from the start of an array list to the first byte of the data area
 * used to hold user data. The same trick used by the standard offsetof()
 * macro is used.
 */
#define	ALIST_OFF_DATA	((size_t)(((Alist *)0)->al_data))
#define	APLIST_OFF_DATA	((size_t)(((APlist *)0)->apl_data))


/*
 * The TRAVERSE macros are intended to be used within a for(), and
 * cause the resulting loop to iterate over each item in the loop,
 * in order.
 *	ALIST_TRAVERSE: Traverse over the items in an Alist,
 *		using the zero based item array index to refer to
 *		each item.
 *	ALIST_TRAVERSE_BY_OFFSET: Traverse over the items in an
 *		Alist using the byte offset from the head of the
 *		Alist pointer to refer to each item. It should be noted
 *		that the first such offset is given by ALIST_OFF_DATA,
 *		and as such, there will never be a 0 offset. Some code
 *		uses this fact to treat 0 as a reserved value with
 *		special meaning.
 *
 *		By-offset access is convenient for some parts of
 *		rtld, where a value of 0 is used to indicate an
 *		uninitialized link map control.
 *
 *	APLIST_TRAVERSE: Traverse over the pointers in an APlist, using
 *		the zero based item array index to refer to each pointer.
 */

/*
 * Within the loop:
 *
 *	LIST - Pointer to Alist structure for list
 *	IDX - The current item index
 *	OFF - The current item offset
 *	DATA - Pointer to item
 */
#define	ALIST_TRAVERSE(LIST, IDX, DATA) \
	(IDX) = 0, \
	((LIST) != NULL) && ((DATA) = (void *)(LIST)->al_data); \
	\
	((LIST) != NULL) && ((IDX) < (LIST)->al_nitems); \
	\
	(IDX)++, \
	(DATA) = (void *) (((LIST)->al_size * (IDX)) + (char *)(LIST)->al_data)

#define	ALIST_TRAVERSE_BY_OFFSET(LIST, OFF, DATA) \
	(((LIST) != NULL) && ((OFF) = ALIST_OFF_DATA) && \
	(((DATA) = (void *)((char *)(LIST) + (OFF))))); \
	\
	(((LIST) != NULL) && ((OFF) < (LIST)->al_next)); \
	\
	(((OFF) += ((LIST)->al_size)), \
	((DATA) = (void *)((char *)(LIST) + (OFF))))

/*
 * Within the loop:
 *
 *	LIST - Pointer to APlist structure for list
 *	IDX - The current item index
 *	PTR - item value
 *
 * Note that this macro is designed to ensure that PTR retains the
 * value of the final pointer in the list after exiting the for loop,
 * and to avoid dereferencing an out of range address. This is done by
 * doing the dereference in the middle expression, using the comma
 * operator to ensure that a NULL pointer won't stop the loop.
 */
#define	APLIST_TRAVERSE(LIST, IDX, PTR) \
	(IDX) = 0; \
	\
	((LIST) != NULL) && ((IDX) < (LIST)->apl_nitems) && \
	(((PTR) = ((LIST)->apl_data)[IDX]), 1); \
	\
	(IDX)++


/*
 * Possible values returned by aplist_test()
 */
typedef enum {
	ALE_ALLOCFAIL = 0,	/* Memory allocation error */
	ALE_EXISTS =	1,	/* alist entry already exists */
	ALE_NOTFND =	2,	/* item not found and insert not required */
	ALE_CREATE =	3	/* alist entry created */
} aplist_test_t;


/*
 * Access to an Alist item by index or offset. This is needed because the
 * size of an item in an Alist is not known by the C compiler, and we
 * have to do the indexing arithmetic explicitly.
 *
 * For an APlist, index the apl_data field directly --- No macro is needed.
 */
#define	alist_item(_lp, _idx) \
	((void *)(ALIST_OFF_DATA + ((_idx) * (_lp)->al_size) + (char *)(_lp)))
#define	alist_item_by_offset(_lp, _off) \
	((void *)((_off) + (char *)(_lp)))

/*
 * # of items currently found in a list. These macros handle the case
 * where the list has not been allocated yet.
 */
#define	alist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->al_nitems)
#define	aplist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->apl_nitems)


extern void		*alist_append(Alist **, const void *, size_t, Aliste);
extern void		alist_delete(Alist *, Aliste *);
extern void		alist_delete_by_offset(Alist *, Aliste *);
extern void		*alist_insert(Alist **, const void *, size_t,
			    Aliste, Aliste);
extern void		*alist_insert_by_offset(Alist **, const void *, size_t,
			    Aliste, Aliste);
extern void		alist_reset(Alist *);


extern void		*aplist_append(APlist **, const void *, Aliste);
extern void		aplist_delete(APlist *, Aliste *);
extern int		aplist_delete_value(APlist *, const void *);
extern void		*aplist_insert(APlist **, const void *,
			    Aliste, Aliste idx);
extern void		aplist_reset(APlist *);
extern aplist_test_t	aplist_test(APlist **, const void *, Aliste);

#ifdef	__cplusplus
}
#endif

#endif /* _ALIST_H */