libkern/kxld/kxld_array.h

   1 /*
   2  * Copyright (c) 2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 #ifndef _KXLD_ARRAY_H_
  29 #define _KXLD_ARRAY_H_
  30
  31 #include <sys/queue.h>
  32 #include <sys/types.h>
  33 #if KERNEL
  34     #include <libkern/kxld_types.h>
  35 #else
  36     #include "kxld_types.h"
  37 #endif
  38
  39 /*******************************************************************************
  40 * This is a resizeable array implementation designed primarily to maximize
  41 * memory reuse.  The array should only be allocated once, but it can be
  42 * initialized many times.  It persists its memory across initializations, and
  43 * reallocates only if it needs to grow the internal array, such that memory
  44 * allocation churn is eliminated.  Growth is accomodated by building a linked
  45 * list of identically sized arrays.  These arrays can be consolidated into
  46 * one large array in the init function.
  47 *
  48 * A technique commonly used in kxld is to make an array of objects that
  49 * themselves contain kxld_arrays.  To minimize memory churn across links, only
  50 * the individual objects contained in an array should be cleared at the end of
  51 * each link, such that they are in a state ready for reinitialization with the
  52 * memory they have already allocated.  The array that contains them should not
  53 * be cleared.  After all links are complete, to ensure that all memory is
  54 * properly freed, one should call kxld_array_get_slot to walk the entire
  55 * allocated space of the array and clean up all potential instances contained
  56 * therein.  Since this technique is somewhat fragile, there are certain
  57 * requirements that must be met, and guarantees that the array implementation
  58 * provides.
  59 *
  60 * Requirements:
  61 *   - A newly allocated, uninitialized array object must be zeroed out before
  62 *     it is initialized
  63 *   - The objects stored in the array that will be reused must consider
  64 *     being bzeroed a valid initial state.  Specifially, they must check that
  65 *     pointers they contain are nonnull before they are freed or followed
  66 *     at both construction and destruction time.
  67 *
  68 * Guarantees:
  69 *   - The init function will always bzero newly allocated memory.  If memory
  70 *     is added by resizing, it will bzero only the newly allocated portion.
  71 *   - clear, deinit, and copy are the only functions that will change the
  72 *     contents of initialized memory.
  73 *   - The reset, clear, deinit functions will accept a NULL pointer to an array.
  74 *******************************************************************************/
  75
  76 STAILQ_HEAD(kxld_array_head, kxld_array_pool);
  77
  78 struct kxld_array {
  79     struct kxld_array_head pools;
  80     size_t itemsize;            /* The size of the items that the array contains */
  81     size_t pool_capacity;       /* The size of each pool's internal buffer */
  82     u_int pool_maxitems;        /* The maximum number of items each pool can hold
  83                                  * given the current size of each pool's buffer.
  84                                  */
  85     u_int nitems;               /* The current number of items this array contains */
  86     u_int maxitems;             /* The maximum number of items this array can contain */
  87     u_int npools;               /* The number of pools in the pool list */
  88 };
  89
  90 struct kxld_array_pool {
  91     STAILQ_ENTRY(kxld_array_pool) entries;
  92     u_char *buffer;             /* The internal memory buffer */
  93     u_int nitems;               /* The number of items the array contains */
  94 };
  95
  96 typedef struct kxld_array KXLDArray;
  97 typedef struct kxld_array_head KXLDArrayHead;
  98 typedef struct kxld_array_pool KXLDArrayPool;
  99
 100 /*******************************************************************************
 101 * Constructors and Destructors
 102 *******************************************************************************/
 103
 104 /* Initializes the array's capacity to a minimum of nitems * itemsize */
 105 kern_return_t kxld_array_init(KXLDArray *array, size_t itemsize, u_int nitems)
 106     __attribute__((nonnull, visibility("hidden")));
 107
 108 /* Performs a deep copy of the array */
 109 kern_return_t kxld_array_copy(KXLDArray *array, const KXLDArray *src)
 110     __attribute__((nonnull, visibility("hidden")));
 111
 112 /* Sets the number of items in the array to 0 */
 113 void kxld_array_reset(KXLDArray *array)
 114     __attribute__((visibility("hidden")));
 115
 116 /* Zeroes out the array and sets nitems to 0 */
 117 void kxld_array_clear(KXLDArray *array)
 118     __attribute__((visibility("hidden")));
 119
 120 /* Frees the array's internal buffer */
 121 void kxld_array_deinit(KXLDArray *array)
 122     __attribute__((visibility("hidden")));
 123
 124 /*******************************************************************************
 125 * Accessors
 126 *******************************************************************************/
 127
 128 /* Returns the item at the specified index, or NULL if idx > nitems */
 129 void *kxld_array_get_item(const KXLDArray *array, u_int idx)
 130     __attribute__((pure, nonnull, visibility("hidden")));
 131
 132 /* Returns the item at the specified index, or NULL if idx > maxitems */
 133 void *kxld_array_get_slot(const KXLDArray *array, u_int idx)
 134     __attribute__((pure, nonnull, visibility("hidden")));
 135
 136 /* Returns the index of a specified item in the array */
 137 kern_return_t kxld_array_get_index(const KXLDArray *array, const void *item,
 138     u_int *idx)
 139     __attribute__((nonnull, visibility("hidden")));
 140
 141 /*******************************************************************************
 142 * Modifiers
 143 *******************************************************************************/
 144
 145 /* Grows the array to contain a minimum of nitems.  If extra memory is needed,
 146  * it will allocate a pool and add it to the list of pools maintained by this
 147  * array.
 148  */
 149 kern_return_t kxld_array_resize(KXLDArray *array, u_int nitems)
 150     __attribute__((nonnull, visibility("hidden")));
 151
 152 /* Removes an element from the array.  This is only supported for arrays with
 153  * a single pool.
 154  */
 155 kern_return_t kxld_array_remove(KXLDArray *array, u_int idx)
 156     __attribute__((nonnull, visibility("hidden")));
 157
 158 #endif /* _KXLD_ARRAY_H_ */