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
76STAILQ_HEAD(kxld_array_head, kxld_array_pool);
77
78struct 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
90struct 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
96typedef struct kxld_array KXLDArray;
97typedef struct kxld_array_head KXLDArrayHead;
98typedef 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 */
105kern_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 */
109kern_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 */
113void kxld_array_reset(KXLDArray *array)
114 __attribute__((visibility("hidden")));
115
116/* Zeroes out the array and sets nitems to 0 */
117void kxld_array_clear(KXLDArray *array)
118 __attribute__((visibility("hidden")));
119
120/* Frees the array's internal buffer */
121void 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 */
129void *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 */
133void *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 */
137kern_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 */
149kern_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 */
155kern_return_t kxld_array_remove(KXLDArray *array, u_int idx)
156 __attribute__((nonnull, visibility("hidden")));
157
158#endif /* _KXLD_ARRAY_H_ */
159