/* ar.c - variable size arrays * **************************************************************** * Copyright (C) 1998, 2000 Thomas Lord * * See the file "COPYING" for further information about * the copyright and warranty status of this work. */ #include "hackerlab/machine/alignment.h" #include "hackerlab/mem/mem.h" #include "hackerlab/mem/talloc.h" #include "hackerlab/bugs/panic.h" #include "hackerlab/arrays/ar.h" /************************************************************************ *(h1 "Variable Size Arrays" * :include ("hackerlab/arrays/ar.h")) * * |array| * |variable size array| * |power of two size array| * |aparse array| * * A "variable size array" is a dynamically allocated block of memory, * similar to a block returned by `lim_malloc', except that a variable sized * array is tagged with its size, measured in the number of array elements. * * A null pointer counts as an array of 0 elements. For example, if * `ar_size', which returns the size of a variable sized arrary, is * passed `0', it returns 0. That means there is no special function * to allocate a new variable sized array -- instead, array pointers * should be initialized to 0. This example creates an array with ten * integers by using `ar_ref': * * { * int * the_array; * int * tenth_element; * * the_array = 0; * tenth_element = (int *)ar_ref (&the_array, * 9, * sizeof (int)); * } * * A variable size array can be used as a stack. (See `ar_push' and * `ar_pop'.) * * Array functions use the `lim_malloc' family of functions to allcoate * memory. (See xref:"Allocation With Limitations".) */ /*(menu) */ /************************************************************************ * (h2 "Variable Size Array Internals") * * A variable size array is represented by a malloced block of memory * approximately one word larger than the memory containing the * array's elements. The extra word contains the number of elements * in the array: * * * * __________________________________________________ * | padding | n-elements | elt0 | elt1 | elt2 | ... * -------------------------------------------------- * ^ * | `base' * * Pointers to the array point to element 0 (labeled `base'). The * size of each element is determined by the `szof' parameter to * functions like `ar_setsize' and `ar_ref'. It is not recorded as part * of the array. * * Padding is added as necessary to ensure that the alignment of `elt0' * is as would be returned from malloc. * * The amount of storage allocated to the array may be larger than is * indicated by `n-elements'. */ /************************************************************************ *(h2 "Basic Variable Size Array Functions") * * * */ #define SIZEOF_HEADER ((sizeof (int) > MACHINE_ALIGNMENT) ? sizeof (int) : MACHINE_ALIGNMENT) #define AR_TO_HEADER(B) ((int *)((char *)(B) - SIZEOF_HEADER)) #define HEADER_TO_AR(H) ((void *)((char *)(H) + SIZEOF_HEADER)) /*(c ar_size) * int ar_size (void * base); * * Return the number of elements in the array. If `base == 0', return * 0. */ int ar_size (void * base) { if (!base) return 0; else return *AR_TO_HEADER(base); } /*(c ar_ref) * void * ar_ref (void ** base, * int n, * int szof); * * Return the address of element `n' of an array, expanding the array * to `n+1' elements, if necessary. * * `base' is a pointer to a pointer to the array. * * `szof' is the size, in bytes, of one element of the array. * * If this function adds new elements to an array, those elements are * filled with 0 bytes. * * This function may resize and relocate the array. If it does, * `*base' is updated to point to the new location of the array. */ void * _ar_ref (void ** base, int n, int szof, char const * name) { int * size; void * m; char * b; if (!*base) { /* FIXME to do this typesafe with talloc we need a new macro so * we can get the overflow protection. */ m = talloc_array_size (NULL, 1, SIZEOF_HEADER + szof * (n + 1)); if (!m) return 0; talloc_set_name_const (m, name); b = HEADER_TO_AR (m); size = AR_TO_HEADER (b); mem_set0 (b, szof * (n + 1)); *size = n + 1; *base = b; } else { /* resize existing array */ b = (char *)*base; size = AR_TO_HEADER (b); if (*size < (n + 1)) { size_t old_size; old_size = *size; m = talloc_realloc_size (NULL, size, (SIZEOF_HEADER + szof * (n + 1))); if (!m) return 0; b = HEADER_TO_AR (m); size = AR_TO_HEADER (b); mem_set0 (b + old_size * szof, (n + 1 - old_size) * szof); *size = n + 1; *base = b; } } return b + szof * n; } /*(c ar_setsize) * void ar_setsize (void ** base, * int n, * size_t szof); * * Resize the array so that it contains exactly `n' elements. * * `base' is a pointer to a pointer to the array. * * `szof' is the size, in bytes, of one element. * * If this function adds new elements to an array, those elements are * filled with 0 bytes. * * This function can be used to make an array smaller, but doing so * does not reclaim any storage. (See `ar_compact'.) */ int _ar_setsize (void ** base, int n, size_t szof, char const * name) { int answer; answer = 0; if (!n && !*base) return 0; if (n > 0) { if (!_ar_ref (base, n - 1, szof, name)) answer = -1; } if (!answer && *base) { *AR_TO_HEADER (*base) = n; } return answer; } /*(c ar_compact) * void ar_compact (void ** base, * size_t szof); * * Resize an array so that it is only as large as it needs to be. * * `base' is a pointer to a pointer to the array. * * `szof' is the size, in bytes, of one element. * * This function may resize and relocate the array. If it does, * `*base' is updated to point to the new location of the array. * * Functions like `ar_setsize' can be used to make an array smaller, but * doing so does not reclaim any storage used by the array and does * not move the array in memory. * * This function does attempt to reclaim storage (by using * `lim_realloc'). If the array occupies significantly more memory * than needed, this function will move it to a smaller block. * If `lim_realloc' returns 0, this function has no effect. */ void ar_compact (void ** base, size_t szof) { size_t size; size = ar_size (*base); if (size == 0) { if (*base) ar_free (base); *base = 0; return; } *base = HEADER_TO_AR (talloc_realloc_size (NULL, (void *)AR_TO_HEADER (*base), SIZEOF_HEADER + size * szof)); } /*(c ar_free) * void ar_free (void ** base); * * Release storage associated with the array pointed to by `*base'. * Set `*base' to 0. */ void ar_free (void ** base) { talloc_free (ar_base(*base)); *base = 0; } /*(c ar_pop) * void * ar_pop (void ** base, * size_t szof); * * Return the address of the `n'th element in an array previously * containing `n' elements. Resize the array so that it contains * exactly `n-1' elements. * * `base' is a pointer to a pointer to the array. * * `szof' is the size, in bytes, of one element. * * This function may resize and relocate the array. If it does, * `*base' is updated to point to the new location of the array. */ void * ar_pop (void ** base, size_t szof) { int size; size = ar_size (*base); ar_setsize (base, size - 1, szof); return (void *)((char *)*base + ((size - 1) * szof)); } /*(c ar_copy) * void * ar_copy (void * base, * size_t szof); * * Create a new array which is a copy of the array pointed to by * `base'. */ void * ar_copy (void * base, size_t szof) { void * answer; answer = 0; ar_setsize (&answer, ar_size (base), szof); mem_move (answer, base, szof * ar_size (base)); return answer; } /** * \brief insert a row into an array * \param base pointer to the array variable * \param index the index to insert at (0-based) * \param szof the record size * \return pointer to the address in the array of the inserted row */ void * ar_insert (void **base, int index, int szof) { void *new_position; /* cheap way to extend the array */ ar_push (base, szof); new_position = ar_ref (base, index, szof); if (ar_size (*base) - 1 -index) mem_move (ar_ref (base, index +1, szof), new_position, szof * (ar_size (*base) -1 -index)); return new_position; } /** * \brief return the real base address of the array for use with memory routines * \param array the array to get the base address of * \return void * the real base */ void * ar_base (void *array) { if (array) return AR_TO_HEADER(array); return NULL; }