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