xref: /xnu-10002.1.13/libkern/kxld/kxld_array.h (revision 1031c584a5e37aff177559b9f69dbd3c8c3fd30a)

/*
 * Copyright (c) 2008 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
#ifndef _KXLD_ARRAY_H_
#define _KXLD_ARRAY_H_

#include <sys/queue.h>
#include <sys/types.h>
#if KERNEL
    #include <libkern/kxld_types.h>
#else
    #include "kxld_types.h"
#endif

/*******************************************************************************
* This is a resizeable array implementation designed primarily to maximize
* memory reuse.  The array should only be allocated once, but it can be
* initialized many times.  It persists its memory across initializations, and
* reallocates only if it needs to grow the internal array, such that memory
* allocation churn is eliminated.  Growth is accomodated by building a linked
* list of identically sized arrays.  These arrays can be consolidated into
* one large array in the init function.
*
* A technique commonly used in kxld is to make an array of objects that
* themselves contain kxld_arrays.  To minimize memory churn across links, only
* the individual objects contained in an array should be cleared at the end of
* each link, such that they are in a state ready for reinitialization with the
* memory they have already allocated.  The array that contains them should not
* be cleared.  After all links are complete, to ensure that all memory is
* properly freed, one should call kxld_array_get_slot to walk the entire
* allocated space of the array and clean up all potential instances contained
* therein.  Since this technique is somewhat fragile, there are certain
* requirements that must be met, and guarantees that the array implementation
* provides.
*
* Requirements:
*   - A newly allocated, uninitialized array object must be zeroed out before
*     it is initialized
*   - The objects stored in the array that will be reused must consider
*     being bzeroed a valid initial state.  Specifially, they must check that
*     pointers they contain are nonnull before they are freed or followed
*     at both construction and destruction time.
*
* Guarantees:
*   - The init function will always bzero newly allocated memory.  If memory
*     is added by resizing, it will bzero only the newly allocated portion.
*   - clear, deinit, and copy are the only functions that will change the
*     contents of initialized memory.
*   - The reset, clear, deinit functions will accept a NULL pointer to an array.
*******************************************************************************/

STAILQ_HEAD(kxld_array_head, kxld_array_pool);

struct kxld_array {
	struct kxld_array_head pools;
	size_t itemsize;        /* The size of the items that the array contains */
	size_t pool_capacity;   /* The size of each pool's internal buffer */
	u_int pool_maxitems;    /* The maximum number of items each pool can hold
	                         * given the current size of each pool's buffer.
	                         */
	u_int nitems;           /* The current number of items this array contains */
	u_int maxitems;         /* The maximum number of items this array can contain */
	u_int npools;           /* The number of pools in the pool list */
};

struct kxld_array_pool {
	STAILQ_ENTRY(kxld_array_pool) entries;
	u_char *buffer;         /* The internal memory buffer */
	u_int nitems;           /* The number of items the array contains */
};

typedef struct kxld_array KXLDArray;
typedef struct kxld_array_head KXLDArrayHead;
typedef struct kxld_array_pool KXLDArrayPool;

/*******************************************************************************
* Constructors and Destructors
*******************************************************************************/

/* Initializes the array's capacity to a minimum of nitems * itemsize */
kern_return_t kxld_array_init(KXLDArray *array, size_t itemsize, u_int nitems)
__attribute__((nonnull, visibility("hidden")));

/* Performs a deep copy of the array */
kern_return_t kxld_array_copy(KXLDArray *array, const KXLDArray *src)
__attribute__((nonnull, visibility("hidden")));

/* Sets the number of items in the array to 0 */
void kxld_array_reset(KXLDArray *array)
__attribute__((visibility("hidden")));

/* Zeroes out the array and sets nitems to 0 */
void kxld_array_clear(KXLDArray *array)
__attribute__((visibility("hidden")));

/* Frees the array's internal buffer */
void kxld_array_deinit(KXLDArray *array)
__attribute__((visibility("hidden")));

/*******************************************************************************
* Accessors
*******************************************************************************/

/* Returns the item at the specified index, or NULL if idx > nitems */
void *kxld_array_get_item(const KXLDArray *array, u_int idx)
__attribute__((pure, nonnull, visibility("hidden")));

/* Returns the item at the specified index, or NULL if idx > maxitems */
void *kxld_array_get_slot(const KXLDArray *array, u_int idx)
__attribute__((pure, nonnull, visibility("hidden")));

/* Returns the index of a specified item in the array */
kern_return_t kxld_array_get_index(const KXLDArray *array, const void *item,
    u_int *idx)
__attribute__((nonnull, visibility("hidden")));

/*******************************************************************************
* Modifiers
*******************************************************************************/

/* Grows the array to contain a minimum of nitems.  If extra memory is needed,
 * it will allocate a pool and add it to the list of pools maintained by this
 * array.
 */
kern_return_t kxld_array_resize(KXLDArray *array, u_int nitems)
__attribute__((nonnull, visibility("hidden")));

/* Removes an element from the array.  This is only supported for arrays with
 * a single pool.
 */
kern_return_t kxld_array_remove(KXLDArray *array, u_int idx)
__attribute__((nonnull, visibility("hidden")));

#endif /* _KXLD_ARRAY_H_ */