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