/* * 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 2009 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 #ifdef __cplusplus extern "C" { #endif #include <sys/types.h> #include <sys/machelf.h> /* * 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; #ifdef _SYSCALL32 /* required by librtld_db */ typedef struct { Elf32_Word apl_arritems; Elf32_Word apl_nitems; Elf32_Addr apl_data[1]; } APlist32; #endif /* _SYSCALL32 */ /* * 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))) /* * The number of items currently found in a list (nitems), and the total number * of slots in the current data allocation (arritems). 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) #define alist_arritems(_lp) (((_lp) == NULL) ? 0 : (_lp)->al_arritems) #define aplist_arritems(_lp) (((_lp) == NULL) ? 0 : (_lp)->apl_arritems) 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 */
