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