10Sstevel@tonic-gate /* 20Sstevel@tonic-gate * CDDL HEADER START 30Sstevel@tonic-gate * 40Sstevel@tonic-gate * The contents of this file are subject to the terms of the 51682Srie * Common Development and Distribution License (the "License"). 61682Srie * You may not use this file except in compliance with the License. 70Sstevel@tonic-gate * 80Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 90Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 100Sstevel@tonic-gate * See the License for the specific language governing permissions 110Sstevel@tonic-gate * and limitations under the License. 120Sstevel@tonic-gate * 130Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 140Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 150Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 160Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 170Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 180Sstevel@tonic-gate * 190Sstevel@tonic-gate * CDDL HEADER END 200Sstevel@tonic-gate */ 211682Srie 220Sstevel@tonic-gate /* 238645SRod.Evans@Sun.COM * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 240Sstevel@tonic-gate * Use is subject to license terms. 250Sstevel@tonic-gate * 260Sstevel@tonic-gate * Define an Alist, a list maintained as a reallocable array, and a for() loop 270Sstevel@tonic-gate * macro to generalize its traversal. Note that the array can be reallocated 280Sstevel@tonic-gate * as it is being traversed, thus the offset of each element is recomputed from 290Sstevel@tonic-gate * the start of the structure. 300Sstevel@tonic-gate */ 310Sstevel@tonic-gate 320Sstevel@tonic-gate #ifndef _ALIST_H 330Sstevel@tonic-gate #define _ALIST_H 340Sstevel@tonic-gate 350Sstevel@tonic-gate #ifdef __cplusplus 360Sstevel@tonic-gate extern "C" { 370Sstevel@tonic-gate #endif 380Sstevel@tonic-gate 390Sstevel@tonic-gate #include <sys/types.h> 400Sstevel@tonic-gate #include <sys/machelf.h> 410Sstevel@tonic-gate 425892Sab196087 /* 435892Sab196087 * An Alist implements array lists. The functionality is similar to 445892Sab196087 * that of a linked list. However, an Alist is represented by a single 455892Sab196087 * contigious allocation of memory. The head of the memory is a header 465892Sab196087 * that contains control information for the list. Following the header 475892Sab196087 * is an array used to hold the user data. In the type definitions that 485892Sab196087 * follow, we define these as an array with a single element, but when 495892Sab196087 * we allocate the memory, we actually allocate the amount of memory needed. 505892Sab196087 * 515892Sab196087 * There are two "flavors" of array list: 525892Sab196087 * 535892Sab196087 * Alist - Contain arbitrary data, usually structs. 545892Sab196087 * APlist - Contain pointers to data allocated elsewhere. 555892Sab196087 * 565892Sab196087 * This differentiation is useful, because pointer lists are heavily 575892Sab196087 * used, and support a slightly different set of operations that are 585892Sab196087 * unique to their purpose. 595892Sab196087 * 605892Sab196087 * Array lists are initially represented by a NULL pointer. The memory 615892Sab196087 * for the list is only allocated if an item is inserted. This is very 625892Sab196087 * efficient for data structures that may or may not be needed for a 635892Sab196087 * given linker operation --- you only pay for what you use. In addition: 645892Sab196087 * 655892Sab196087 * - Array lists grow as needed (memory is reallocated as necessary) 665892Sab196087 * - Data is kept contiguously (no unused holes in between elements) 675892Sab196087 * at the beginning of the data area. This locality has 685892Sab196087 * good cache behavior, as access to adjacent items are 695892Sab196087 * highly likely to be in the same page of memory. 705892Sab196087 * - Insert/Delete operations at the end of the list are very 715892Sab196087 * efficient. However, insert/delete operations elsewhere 725892Sab196087 * will cause a relatively expensive overlapped memory 735892Sab196087 * copy of the data following the insert/delete location. 745892Sab196087 * - As with any generic memory alloctor (i.e. malloc()/free()), 755892Sab196087 * array lists are not type safe for the data they contain. 765892Sab196087 * Data is managed as (void *) pointers to data of a given 775892Sab196087 * length, so the Alist module cannot prevent the caller from 785892Sab196087 * inserting/extracting the wrong type of data. The caller 795892Sab196087 * must guard against this. 805892Sab196087 * - To free an array list, simply call the standard free() function 815892Sab196087 * on the list pointer. 825892Sab196087 */ 835892Sab196087 845892Sab196087 855892Sab196087 865892Sab196087 /* 875892Sab196087 * Aliste is used to represent list indexes, offsets, and sizes. 885892Sab196087 */ 895892Sab196087 typedef size_t Aliste; 905892Sab196087 915892Sab196087 920Sstevel@tonic-gate 935892Sab196087 /* 945892Sab196087 * Alist is used to hold non-pointer items --- usually structs: 955892Sab196087 * - There must be an even number of Aliste fields before the 965892Sab196087 * al_data field. This ensures that al_data will have 975892Sab196087 * an alignment of 8, no matter whether sizeof(Aliste) 985892Sab196087 * is 4 or 8. That means that al_data will have sufficient 995892Sab196087 * alignment for any use, just like memory allocated via 1005892Sab196087 * malloc(). 1015892Sab196087 * - al_nitems and al_next are redundant, in that they are 1025892Sab196087 * directly related: 1035892Sab196087 * al_next = al_nitems * al_size 1045892Sab196087 * We do this to make ALIST_TRAVERSE_BYOFFSET maximally 1055892Sab196087 * efficient. This doesn't waste space, because of the 1065892Sab196087 * requirement to have an even # of Alist fields (above). 1075892Sab196087 * 1085892Sab196087 * Note that Alists allow the data to be referenced by 0 based array 1095892Sab196087 * index, or by their byte offset from the start of the Alist memory 1105892Sab196087 * allocation. The index form is preferred for most use, as it is simpler. 1115892Sab196087 * However, by-offset access is used by rtld link maps, and this ability 1125892Sab196087 * is convenient in that case. 1135892Sab196087 */ 1145892Sab196087 typedef struct { 1155892Sab196087 Aliste al_arritems; /* # of items in al_data allocation */ 1165892Sab196087 Aliste al_nitems; /* # items (index of next avail item) */ 1175892Sab196087 Aliste al_next; /* offset of next available al_data[] */ 1185892Sab196087 Aliste al_size; /* size of each al_data[] item */ 1195892Sab196087 void *al_data[1]; /* data (can grow) */ 1205892Sab196087 } Alist; 1215892Sab196087 1225892Sab196087 /* 1235892Sab196087 * APlist is a variant of Alist that contains pointers. There are several 1245892Sab196087 * benefits to this special type: 1255892Sab196087 * - API is simpler 1265892Sab196087 * - Pointers are used directly, instead of requiring a 1275892Sab196087 * pointer-to-pointer double indirection. 1285892Sab196087 * - The implementation is slightly more efficient. 1295892Sab196087 * - Operations that make particular sense for pointers 1305892Sab196087 * can be supported without confusing the API for the 1315892Sab196087 * regular Alists. 1325892Sab196087 */ 1335892Sab196087 typedef struct { 1345892Sab196087 Aliste apl_arritems; /* # of items in apl_data allocation */ 1355892Sab196087 Aliste apl_nitems; /* # items (index of next avail item) */ 1365892Sab196087 void *apl_data[1]; /* data area: (arrcnt * size) bytes */ 1375892Sab196087 } APlist; 1385892Sab196087 1399131SRod.Evans@Sun.COM #ifdef _SYSCALL32 /* required by librtld_db */ 1409131SRod.Evans@Sun.COM typedef struct { 1419131SRod.Evans@Sun.COM Elf32_Word apl_arritems; 1429131SRod.Evans@Sun.COM Elf32_Word apl_nitems; 1439131SRod.Evans@Sun.COM Elf32_Addr apl_data[1]; 1449131SRod.Evans@Sun.COM } APlist32; 1459131SRod.Evans@Sun.COM #endif /* _SYSCALL32 */ 1465892Sab196087 1475892Sab196087 /* 1485892Sab196087 * The ALIST_OFF_DATA and APLIST_OFF_DATA macros give the byte offset 1495892Sab196087 * from the start of an array list to the first byte of the data area 1505892Sab196087 * used to hold user data. The same trick used by the standard offsetof() 1515892Sab196087 * macro is used. 1525892Sab196087 */ 1535892Sab196087 #define ALIST_OFF_DATA ((size_t)(((Alist *)0)->al_data)) 1545892Sab196087 #define APLIST_OFF_DATA ((size_t)(((APlist *)0)->apl_data)) 1555892Sab196087 1565892Sab196087 1575892Sab196087 /* 1585892Sab196087 * The TRAVERSE macros are intended to be used within a for(), and 1595892Sab196087 * cause the resulting loop to iterate over each item in the loop, 1605892Sab196087 * in order. 1615892Sab196087 * ALIST_TRAVERSE: Traverse over the items in an Alist, 1625892Sab196087 * using the zero based item array index to refer to 1635892Sab196087 * each item. 1645892Sab196087 * ALIST_TRAVERSE_BY_OFFSET: Traverse over the items in an 1655892Sab196087 * Alist using the byte offset from the head of the 1665892Sab196087 * Alist pointer to refer to each item. It should be noted 1675892Sab196087 * that the first such offset is given by ALIST_OFF_DATA, 1685892Sab196087 * and as such, there will never be a 0 offset. Some code 1695892Sab196087 * uses this fact to treat 0 as a reserved value with 1705892Sab196087 * special meaning. 1715892Sab196087 * 1725892Sab196087 * By-offset access is convenient for some parts of 1735892Sab196087 * rtld, where a value of 0 is used to indicate an 1745892Sab196087 * uninitialized link map control. 1755892Sab196087 * 1765892Sab196087 * APLIST_TRAVERSE: Traverse over the pointers in an APlist, using 1775892Sab196087 * the zero based item array index to refer to each pointer. 1785892Sab196087 */ 1795892Sab196087 1805892Sab196087 /* 1815892Sab196087 * Within the loop: 1825892Sab196087 * 1835892Sab196087 * LIST - Pointer to Alist structure for list 1845892Sab196087 * IDX - The current item index 1855892Sab196087 * OFF - The current item offset 1865892Sab196087 * DATA - Pointer to item 1875892Sab196087 */ 1885892Sab196087 #define ALIST_TRAVERSE(LIST, IDX, DATA) \ 1895892Sab196087 (IDX) = 0, \ 1905892Sab196087 ((LIST) != NULL) && ((DATA) = (void *)(LIST)->al_data); \ 1915892Sab196087 \ 1925892Sab196087 ((LIST) != NULL) && ((IDX) < (LIST)->al_nitems); \ 1935892Sab196087 \ 1945892Sab196087 (IDX)++, \ 1955892Sab196087 (DATA) = (void *) (((LIST)->al_size * (IDX)) + (char *)(LIST)->al_data) 1965892Sab196087 1975892Sab196087 #define ALIST_TRAVERSE_BY_OFFSET(LIST, OFF, DATA) \ 1985892Sab196087 (((LIST) != NULL) && ((OFF) = ALIST_OFF_DATA) && \ 1990Sstevel@tonic-gate (((DATA) = (void *)((char *)(LIST) + (OFF))))); \ 2005892Sab196087 \ 2015892Sab196087 (((LIST) != NULL) && ((OFF) < (LIST)->al_next)); \ 2025892Sab196087 \ 2030Sstevel@tonic-gate (((OFF) += ((LIST)->al_size)), \ 2040Sstevel@tonic-gate ((DATA) = (void *)((char *)(LIST) + (OFF)))) 2050Sstevel@tonic-gate 2065892Sab196087 /* 2075892Sab196087 * Within the loop: 2085892Sab196087 * 2095892Sab196087 * LIST - Pointer to APlist structure for list 2105892Sab196087 * IDX - The current item index 2115892Sab196087 * PTR - item value 2125892Sab196087 * 2135892Sab196087 * Note that this macro is designed to ensure that PTR retains the 2145892Sab196087 * value of the final pointer in the list after exiting the for loop, 2155892Sab196087 * and to avoid dereferencing an out of range address. This is done by 2165892Sab196087 * doing the dereference in the middle expression, using the comma 2175892Sab196087 * operator to ensure that a NULL pointer won't stop the loop. 2185892Sab196087 */ 2195892Sab196087 #define APLIST_TRAVERSE(LIST, IDX, PTR) \ 2205892Sab196087 (IDX) = 0; \ 2215892Sab196087 \ 2225892Sab196087 ((LIST) != NULL) && ((IDX) < (LIST)->apl_nitems) && \ 2235892Sab196087 (((PTR) = ((LIST)->apl_data)[IDX]), 1); \ 2245892Sab196087 \ 2255892Sab196087 (IDX)++ 2260Sstevel@tonic-gate 2275892Sab196087 2285892Sab196087 /* 2295892Sab196087 * Possible values returned by aplist_test() 2305892Sab196087 */ 2315892Sab196087 typedef enum { 232*9577SRod.Evans@Sun.COM ALE_ALLOCFAIL = 0, /* memory allocation error */ 2335892Sab196087 ALE_EXISTS = 1, /* alist entry already exists */ 2345892Sab196087 ALE_NOTFND = 2, /* item not found and insert not required */ 2355892Sab196087 ALE_CREATE = 3 /* alist entry created */ 2365892Sab196087 } aplist_test_t; 2370Sstevel@tonic-gate 2380Sstevel@tonic-gate 2390Sstevel@tonic-gate /* 2405892Sab196087 * Access to an Alist item by index or offset. This is needed because the 2415892Sab196087 * size of an item in an Alist is not known by the C compiler, and we 2425892Sab196087 * have to do the indexing arithmetic explicitly. 2435892Sab196087 * 2445892Sab196087 * For an APlist, index the apl_data field directly --- No macro is needed. 2450Sstevel@tonic-gate */ 2465892Sab196087 #define alist_item(_lp, _idx) \ 2475892Sab196087 ((void *)(ALIST_OFF_DATA + ((_idx) * (_lp)->al_size) + (char *)(_lp))) 2485892Sab196087 #define alist_item_by_offset(_lp, _off) \ 2495892Sab196087 ((void *)((_off) + (char *)(_lp))) 2505892Sab196087 2515892Sab196087 /* 2528645SRod.Evans@Sun.COM * The number of items currently found in a list (nitems), and the total number 2538645SRod.Evans@Sun.COM * of slots in the current data allocation (arritems). These macros handle the 2548645SRod.Evans@Sun.COM * case where the list has not been allocated yet. 2555892Sab196087 */ 2568645SRod.Evans@Sun.COM #define alist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->al_nitems) 2578645SRod.Evans@Sun.COM #define aplist_nitems(_lp) (((_lp) == NULL) ? 0 : (_lp)->apl_nitems) 2588645SRod.Evans@Sun.COM #define alist_arritems(_lp) (((_lp) == NULL) ? 0 : (_lp)->al_arritems) 2598645SRod.Evans@Sun.COM #define aplist_arritems(_lp) (((_lp) == NULL) ? 0 : (_lp)->apl_arritems) 2600Sstevel@tonic-gate 2610Sstevel@tonic-gate 2625892Sab196087 extern void *alist_append(Alist **, const void *, size_t, Aliste); 2635892Sab196087 extern void alist_delete(Alist *, Aliste *); 2645892Sab196087 extern void alist_delete_by_offset(Alist *, Aliste *); 2655892Sab196087 extern void *alist_insert(Alist **, const void *, size_t, 2665892Sab196087 Aliste, Aliste); 2675892Sab196087 extern void *alist_insert_by_offset(Alist **, const void *, size_t, 2685892Sab196087 Aliste, Aliste); 2695892Sab196087 extern void alist_reset(Alist *); 2705892Sab196087 2715892Sab196087 2725892Sab196087 extern void *aplist_append(APlist **, const void *, Aliste); 2735892Sab196087 extern void aplist_delete(APlist *, Aliste *); 2745892Sab196087 extern int aplist_delete_value(APlist *, const void *); 2755892Sab196087 extern void *aplist_insert(APlist **, const void *, 2765892Sab196087 Aliste, Aliste idx); 2775892Sab196087 extern void aplist_reset(APlist *); 2785892Sab196087 extern aplist_test_t aplist_test(APlist **, const void *, Aliste); 2790Sstevel@tonic-gate 2800Sstevel@tonic-gate #ifdef __cplusplus 2810Sstevel@tonic-gate } 2820Sstevel@tonic-gate #endif 2830Sstevel@tonic-gate 2840Sstevel@tonic-gate #endif /* _ALIST_H */ 285