NAME
array.h - a generic array type that grows as needed
SYNOPSIS
Use this for stacks, queues, or linear lists of any type. The bounds will grow transparently, so you never need to be concerned about hard coded limits.
#include <array.h>
void array_prepend_ptr(ARRAY *array,
char *ptr,
size_t sz);
void array_append_ptr(ARRAY *array,
char *ptr,
size_t sz);
void *array_to_pointer(ARRAY *array);
void array_destroy_index(ARRAY *a, unsigned index);
void array_destroy(ARRAY *a);
#define array_create(size, type) ...
#define array_size(a) ...
#define array_access(a, index, type) ...
#define array_fast_access(a, index, type) ...
#define array_prepend(a, elem, type) ...
#define array_append(a, elem, type) ...
#define array_insert_index(a, elem, type, index) ...
#define array_remove_front(a, type) ...
#define array_remove_back(a, type) ...
#define array_remove_index(a, type, index) ...
#define array_destroy_front(a) ...
#define array_destroy_back(a) ...
#define array_clear(a) ...
#define array_shrink(a) ...
#define array_push(a, elem, type) ...
#define array_pop(a, type) ...
#define array_first_addr(a, type) ...
#define array_last_addr(a, type) ...
DESCRIPTION
This package provides a pseudo-array type that will automatically grow as you insert more elements into it. Most of the provided routines are macros, so you must be very careful to avoid side-effects.
If you never have to access elements by index then you may be better off using a linked list implementation. However, if you do need to access elements by an index, or if you are only interested in creating a stack or a queue, then these routines may work quite well for you.
In most of the macro descriptions that follow, the argument type refers to the element type. Any macro that inserts or returns elements must be provided with a type.
Type Declarations
The following types are defined in the header file array.h.
ARRAY
typedef struct ARRAY {
unsigned alloced;
unsigned origin;
unsigned lindex;
unsigned rindex;
unsigned elemsz;
char *data;
char *hole;
} ARRAY;
This section should be skipped by users who don't care about the implementation specifics of this package.
We store the elements of an ARRAY with three indices: origin, lindex, and rindex. origin is the offset from 0 in which lindex and rindex are defined. lindex is the location of the first element in the array relative to the left of origin. rindex is the location of the last element relative to the right of origin. As an example:
+-----+-----+-----+-----+-----+-----+-----+-----+ memory: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |-----|-----|-----|-----|-----|-----|-----|-----| data: | F | | | | B | C | D | E | +-----+-----+-----+-----+-----+-----+-----+-----+
Here we have an ARRAY with 5 elements in it. We'll denote the elements as A-D, as if they are to be in some sorted order. One possible set of values for the the structure fields is: alloced = 8, origin = 5, lindex = 1, and rindex = 3.
On array_prepend(ARRAY, A, TYPE) we would place 'A' into memory location 3, while incrementing lindex. On array_append(ARRAY, G, TYPE) we would place 'G' into memory location 1, while incrementing rindex.
Obviously, from this example, we allow the elements to wrap around. Because of this we can guarantee that a queue implementation correctly coded as an ARRAY will never have more than twice the maximum number of elements in the queue of memory allocated.
If lindex is 0 and you remove the front, then origin will be incremented. If rindex is 0 and you remove the back then origin will be decremented. This means that your origin may shift in unfavorable ways, but things should still work if you only use the provided macros and you heed the warning below about mixing push and pop calls with the other routines.
The hole field is used for some macro trickery. Ignore it.
Function Definitions
The following function prototypes are given in the header file array.h.
void array_prepend_ptr(ARRAY *array,
char *ptr,
size_t sz);
Given the ARRAY, array, copy the sz elements pointed to by ptr into the front of array. The paramater sz represents the number of elements, not the number of bytes.
void array_append_ptr(ARRAY *array,
char *ptr,
size_t sz);
Given the ARRAY, array, copy the sz elements pointed to by ptr into the rear of array. The paramater sz represents the number of elements, not the number of bytes.
void *array_to_pointer(ARRAY *array);
Given the ARRAY, array, copy all of the data to a new chunk of memory and return the new pointer. The caller of this function "owns" the newly allocated data in the sense that it has the responsibility for freeing the returned pointer later on.
void array_destroy_index(ARRAY *a, unsigned index);
Removes the index'th item in the ARRAY, a. This is rather involved, so it is written as a function.
void array_destroy(ARRAY *a);
Free up all memory used by the ARRAY a.
Macro Definitions
The following macros are defined in the header file array.h.
#define array_create(size, type) ...
Create an ARRAY with a requested size and a given type.
#define array_size(a) ...
Returns the number of elements in the ARRAY a, not the amount of memory allocated.
#define array_access(a, index, type) ...
This is a fairly safe method for accessing elements of array. The result of the macro expansion can be used as an lvalue, thus array_access(a, 5, int) = 36 is perfectly legal. The supplied index is checked for valid bounds. If index is invalid, then a warning message is produced.
#define array_fast_access(a, index, type) ...
This macro is much faster then array_access(), but index is not checked. Only use this is you are certain of your index bounds.
#define array_prepend(a, elem, type) ...
This macro shoves a new element into the first position of a, making sure that there is enough space, and wrapping indices as needed.
#define array_append(a, elem, type) ...
This macro shoves a new element into the last position of a, making sure that there is enough space, and wrapping indices as needed.
#define array_insert_index(a, elem, type, index) ...
This macro will insert elem into the index'th position in the ARRAY a and allocate any space that is needed. It calls a helper function to do the bulk of the work.
#define array_remove_front(a, type) ...
This macro removes the first element from the array and can be used as the right-hand side of an assignment to get the removed element, similar to a stack pop or a queue dequeue.
#define array_remove_back(a, type) ...
This macro removes the last element from the array and can be used as the right-hand side of an assignment to get the removed element, similar to a stack pop or a queue dequeue.
#define array_remove_index(a, type, index) ...
This behaves similarly to array_destroy_index() but it will return the element to destroyed as an R-value.
#define array_destroy_front(a) ...
This macro removes the first element similarly to array_remove_front() but does not return a valid rvalue, thus it cannot be used to retrieve the first element. This macro may be trivially faster than the "remove" version.
#define array_destroy_back(a) ...
This macro removes the last element similarly to array_remove_back() but does not return to a valid rvalue, thus it cannot be used to retrieve the last element. This macro may be trivially faster than the "remove" version.
#define array_clear(a) ...
This macro will not free any memory, but it will set all of the array's internals to an empty state.
#define array_shrink(a) ...
Shrink the allocated array to the smallest amount possible considering the elements that are currently in use.
#define array_push(a, elem, type) ...
This macro expression is identical to a call to array_append() except that it is much faster. The down side is that you can only use this call by itself and with calls to array_pop(). If you mix these calls with any of the other array insertion and deletion routines we guarantee that your program will crash. If you just need a stack module then this the ideal thing for you to use.
#define array_pop(a, type) ...
This is the counterpart to array_push(). Underflow is not checked, so let the buyer beware.
#define array_first_addr(a, type) ...
This macro returns the address of the first element of the array. Use this with caution.
#define array_last_addr(a, type) ...
This macro returns the address of the last element of the array. Use this with caution. If result of this macro is greater than array_first_addr() then you are guaranteed that the array does not "wrap" around.
AUTHOR
Gary William Flake (gary.flake@usa.net).