usr/src/cmd/sgs/include/alist.h

   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 */