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