Mercurial > code
changeset 6:25cc379de564
Added array.c and array.h:
Various function to manipulate dynamic array. This let you adding as
much as you want object into the array. You may add object to the head,
end or at a specified index.
author | David Demelier <markand@malikania.fr> |
---|---|
date | Tue, 06 Sep 2011 22:19:18 +0200 |
parents | 0ed27735fa87 |
children | e8829146ebc7 |
files | array.c array.h |
diffstat | 2 files changed, 319 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/array.c Tue Sep 06 22:19:18 2011 +0200 @@ -0,0 +1,262 @@ +/* + * array.h -- manipulate dymanic array + * + * Copyright (c) 2011, David Demelier <markand@malikania.fr> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "array.h" + +#define SIZE(x) (sizeof (void *) * (x)) + +static int array_grow(struct array *); + +struct array * +array_new(const void *data, size_t bsize, int flags) +{ + struct array *arr; + + if (!(arr = malloc(sizeof (struct array)))) + return NULL; + + memset(arr, 0, sizeof (struct array)); + arr->bsize = (bsize == 0) ? ARRAY_DEFAULT_BSIZE : bsize; + arr->size = bsize + 1; + arr->flags = flags; + + if (!(arr->data = calloc(bsize + 1, sizeof (void *)))) { + free(arr); + return NULL; + } + + if (data) + arr->data[arr->length++] = (void *) data; + + return arr; +} + +/* + * Add to the head of array. NOTE: this may be very slow when adding a lot + * of object (about 100000). If you need to add a lot of data please consider + * using linked list instead or use array_append and then use reverse foreach + * functions. + */ + +int +array_push(struct array *arr, const void *data) +{ + if (array_grow(arr) < 0) + return -1; + + memmove(arr->data + 1, arr->data, SIZE(arr->length++)); + arr->data[0] = (void *) data; + + return 0; +} + +/* + * Insert the data to the specified index. The function returns -1 on + * allocation failure if the array need to grow or when the index is out + * of bounds otherwise 0 is returned. + */ + +int +array_insert(struct array *arr, const void *data, int index) +{ + if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0) + return -1; + + memmove(arr->data + index + 1, arr->data + index, + SIZE(arr->length++ - index)); + arr->data[index] = (void *) data; + + return 0; +} + +/* + * Append the data to the end of array. + */ + +int +array_append(struct array *arr, const void *data) +{ + if (array_grow(arr) < 0) + return -1; + + arr->data[arr->length++] = (void *) data; + + return 0; +} + +/* + * Remove the array's head and return the object or NULL if + * the array is empty. + */ + +void * +array_pop(struct array *arr) +{ + void *data; + + if (arr->length == 0) + return NULL; + + data = arr->data[0]; + memmove(arr->data, arr->data + 1, SIZE(arr->length)); + arr->data[--arr->length] = NULL; + + return data; +} + +/* + * Remove the array's queue and return the object or NULL + * if the array is empty. + */ + +void * +array_unqueue(struct array *arr) +{ + void *data; + + if (arr->length == 0) + return NULL; + + data = arr->data[--arr->length]; + arr->data[arr->length] = NULL; + + return data; +} + +/* + * Remove the entry at the specified index and return it. If the index is out of + * bounds or the list is empty the functions returns NULL. + */ + +void * +array_remove(struct array *arr, int index) +{ + void *data; + + if (arr->length == 0 || index < 0 || index > arr->length - 1) + return NULL; + + data = arr->data[index]; + memmove(arr->data + index, arr->data + index + 1, + SIZE(arr->length - index)); + arr->data[--arr->length] = NULL; + + return data; +} + +/* + * Apply the function `fn' on each object and give the optional `udata' + * argument to the function too. + */ + +void +array_map(struct array *arr, void (*fn)(void *, void *), void *udata) +{ + size_t i; + + for (i = 0; arr->data[i]; ++i) + fn(arr->data[i], udata); +} + +/* + * Compare each object with the user supplied function. If the `fn' function + * returns 1 then the data is returned. Optional idx argument can be set to + * indicate the data position. If the data was not found the function returns + * NULL. + */ + +void * +array_find(struct array *arr, int (*fn)(void *, void *), void *udata, int *idx) +{ + size_t i; + int st; + void *data; + + for (i = st = 0; arr->data[i] && !st; ++i) + st = fn(arr->data[i], udata); + + if (st) { + data = arr->data[--i]; + if (idx) + *idx = i; + } else + data = NULL; + + return data; +} + +/* + * Reset the array, if the trash argument is set it will free the object + * too, otherwise the array is just truncated to 0 length. + */ + +void +array_clear(struct array *arr, int trashit) +{ + if (trashit) { + size_t i; + + for (i = 0; arr->data[i]; ++i) + free(arr->data[i]); + } + + memset(arr->data, 0, SIZE(arr->size)); + arr->length = 0; +} + +/* + * Same as array_clear except it also free the array object. + */ + +void +array_free(struct array *arr, int trashit) +{ + array_clear(arr, trashit); + + free(arr->data); + free(arr); +} + +/* + * Increate the array storage when it is full. If the buffer is fixed size + * it returns -1 on full buffer otherwise 0 is returned if allocation + * succeeded. + */ + +static int +array_grow(struct array *arr) +{ + if (arr->size - 1 > arr->length) + return 0; + + if (arr->flags & ARRAY_AUTO) { + if (!(arr->data = realloc(arr->data, SIZE(arr->size + arr->bsize)))) + return -1; + + arr->size += arr->bsize; + } else + return (arr->size - 1 == arr->length) ? -1 : 0; + + memset(arr->data + arr->length, 0, SIZE(arr->size - arr->length)); + + return 0; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/array.h Tue Sep 06 22:19:18 2011 +0200 @@ -0,0 +1,57 @@ +/* + * array.h -- manipulate dymanic array + * + * Copyright (c) 2011, David Demelier <markand@malikania.fr> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _ARRAY_H_ +#define _ARRAY_H_ + +#define ARRAY_DEFAULT_BSIZE 128 + +struct array { + void **data; /* array of data */ + size_t length; /* number of element in array */ + +#define ARRAY_FIXED 0x00000000 +#define ARRAY_AUTO 0x00000001 + int flags; /* array's flags (default FIXED) */ + + /* Private should not be modified by user */ + size_t size; /* current buffer size */ + size_t bsize; /* block size */ +}; + +struct array *array_new(const void *, size_t, int); +#define array_new_auto(size) array_new(NULL, size, ARRAY_AUTO) +#define array_new_fixed(max) array_new(NULL, max, ARRAY_FIXED) + +int array_push(struct array *, const void *); +int array_insert(struct array *, const void *, int); +int array_append(struct array *, const void *); +void *array_pop(struct array *); +void *array_unqueue(struct array *); +void *array_remove(struct array *, int); +void array_map(struct array *, void (*fn)(void *, void *), void *); +void *array_find(struct array *, int (*fn)(void *, void *), void *, int *); +void array_clear(struct array *, int); +void array_free(struct array *, int); + +#define ARRAY_FOREACH(array, entry, tmp, type) \ + for ((tmp) = (type **) (array)->data, entry = *tmp; \ + (entry) != NULL; \ + ++(tmp), (entry) = (*tmp)) + +#endif /* _ARRAY_H */