Mercurial > code
changeset 62:d10ab6bc555d
HG self failure
author | David Demelier <markand@malikania.fr> |
---|---|
date | Wed, 09 Nov 2011 19:26:09 +0100 |
parents | e1f3ed0bf507 |
children | d78c4d9fad13 |
files | array.c array.h parray.h |
diffstat | 3 files changed, 491 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/array.c Wed Nov 09 19:26:09 2011 +0100 @@ -0,0 +1,314 @@ +/* + * array.c -- manipulate dynamic arrays + * + * 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 OFFSET(x) (arr->unit * (x)) + +static int array_grow(struct array *); + +struct array * +array_new(enum array_type type, size_t unit, int length) +{ + struct array *arr; + + if (unit == 0 || (arr = malloc(sizeof (struct array))) == NULL) + return NULL; + + memset(arr, 0, sizeof (struct array)); + arr->type = type; + arr->bsize = (length == 0) ? ARRAY_DEFAULT_BSIZE : length; + arr->unit = unit; + arr->size = OFFSET(arr->bsize); + + if ((arr->data = malloc(arr->size)) == NULL) { + free(arr); + return NULL; + } + + 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. + */ + +int +array_push(struct array *arr, const void *data) +{ + if (array_grow(arr) < 0) + return -1; + + memmove((char *) arr->data + arr->unit, arr->data, OFFSET(arr->length++)); + memcpy((char *) arr->data, data, arr->unit); + + return 0; +} + +/* + * Insert the data at the specified index. The function returns -1 on + * allocation failure or when the index is outof 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((char *) arr->data + OFFSET(index + 1), + (char *) arr->data + OFFSET(index), OFFSET(arr->length++ - index)); + memcpy((char *) arr->data + OFFSET(index), data, arr->unit); + + 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; + + memcpy((char *) arr->data + OFFSET(arr->length++), data, arr->unit); + + return 0; +} + +/* + * Remove the array's head. + */ + +void +array_pop(struct array *arr) +{ + if (arr->length > 0) { + memmove((char *) arr->data, (char *) arr->data + OFFSET(1), + OFFSET(--arr->length)); + memset((char *) arr->data + OFFSET(arr->length), 0, arr->unit); + } +} + +/* + * Remove the array's tail. + */ + +void +array_unqueue(struct array *arr) +{ + if (arr->length > 0) + memset((char *) arr->data + OFFSET(--arr->length), 0, arr->unit); +} + +/* + * Remove the data at the specified index. Bounds are checked. + */ + +void +array_remove(struct array *arr, int index) +{ + if (arr->length > 0 && index >= 0 && index < arr->length) { + memmove((char *) arr->data + OFFSET(index), + (char *) arr->data + OFFSET(index + 1), + OFFSET(arr->length - index - 1)); + memset((char *) arr->data + OFFSET(--arr->length), 0, arr->unit); + } +} + +/* + * Remove the object referenced by the `data' argument. Useful when you + * don't know the index. + */ + +void +array_unref(struct array *arr, const void *data) +{ + void *elm; + int i; + + for (i = 0; i < arr->length; ++i) { + elm = (char *) arr->data + OFFSET(i); + + if (memcmp(elm, data, arr->unit) == 0) + array_remove(arr, i); + } +} + +/* + * Swap the two elements referenced by index `i1' and `i2'. This function needs + * to allocate data to swap elements thus if the functions fails it returns -1 + * otherwise 0 is returned. + */ + +int +array_iswap(struct array *arr, int i1, int i2) +{ + void *tmp; + + /* Out of bounds */ + if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0) + return -1; + + /* + * Only allocate at this time, the user may do not want to use this + * function. + */ + + if ((tmp = malloc(arr->unit)) == NULL) + return -1; + + memcpy((char *) tmp, (char *) arr->data + OFFSET(i1), arr->unit); + memcpy((char *) arr->data + OFFSET(i1), (char *) arr->data + OFFSET(i2), + arr->unit); + memcpy((char *) arr->data + OFFSET(i2), (char *) tmp, arr->unit); + + /* + * Clear bytes for safety you probably don't want a password or + * secure data to be left somewhere in the memory. + */ + + memset(tmp, 0, arr->unit); + free(tmp); + + return 0; +} + +/* + * Swap the two elements referenced by data `o1' and `o2'. This function + * may be slow on large arrays since it must travel all the object + * to find the indexes. + */ + +int +array_pswap(struct array *arr, const void *o1, const void *o2) +{ + int found, i1, i2; + + for (i1 = found = 0; !found && i1 < arr->length; ++i1) + found = memcmp(arr->data + OFFSET(i1), o1, arr->unit) == 0; + + if (!found) + return -1; + + for (i2 = found = 0; !found && i2 < arr->length; ++i2) + found = memcmp(arr->data + OFFSET(i2), o2, arr->unit) == 0; + + if (!found) + return -1; + + return array_iswap(arr, --i1, --i2); +} + +/* + * Apply the function `fn' on each object and give the optional `udata' + * argument to the function too. + */ + +void +array_map(const struct array *arr, void (*fn)(void *, void *), void *udata) +{ + int i; + + for (i = 0; i < arr->length; ++i) + fn((char *) arr->data + OFFSET(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(const struct array *arr, int (*fn)(void *, void *), int *ix, void *u) +{ + int st, i; + void *data; + + for (i = st = 0; i < arr->length && st != 1; ++i) + st = fn((char *) arr->data + OFFSET(i), u); + + if (st) { + data = (char *) arr->data + OFFSET(--i); + if (ix) + *ix = i; + } else + data = NULL; + + return data; +} + +/* + * Erase every bytes and set the length to 0. + */ + +void +array_clear(struct array *arr) +{ + memset(arr->data, 0, arr->size); + arr->length = 0; +} + +/* + * Same as array_clear except it also free the array object. + */ + +void +array_free(struct array *arr) +{ + array_clear(arr); + + if (arr->data) + 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 / arr->unit) > (size_t) arr->length) + return 0; + + if (arr->type == ARRAY_AUTO) { + if ((arr->data = realloc(arr->data, arr->size + + OFFSET(arr->bsize))) == NULL) + return -1; + + arr->size += OFFSET(arr->bsize); + } else + return -1; + + return 0; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/array.h Wed Nov 09 19:26:09 2011 +0100 @@ -0,0 +1,83 @@ +/* + * array.h -- manipulate dynamic arrays + * + * 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_ + +/* Add some nonnull attributes for gcc/clang */ +#ifdef __GNUC__ +# define __at_malloc __attribute__ ((malloc)) +# define __at_nonnull(...) __attribute__ ((nonnull (__VA_ARGS__))) +#else +# define __at_malloc +# define __at_nonnull(...) +#endif + +#define ARRAY_DEFAULT_BSIZE 128 + +enum array_type { + ARRAY_FIXED = 0, + ARRAY_AUTO = 1 +}; + +struct array { + enum array_type type; /* array's type (default FIXED) */ + void *data; /* array of data */ + int length; /* number of element inside */ + size_t size; /* current buffer size (allocated memory) */ + size_t unit; /* unit size (sizeof the object) */ + int bsize; /* block size (used when growing array) */ + int i; /* only for ARRAY_FOREACH(_R) */ +}; + +typedef void (*array_map_fn)(void *, void *); +typedef int (*array_cmp_fn)(void *, void *); + +struct array *array_new(enum array_type, size_t, int) __at_malloc; +int array_push(struct array *, const void *) __at_nonnull(1, 2); +int array_insert(struct array *, const void *, int) __at_nonnull(1, 2); +int array_append(struct array *, const void *) __at_nonnull(1, 2); +void array_pop(struct array *) __at_nonnull(1); +void array_unqueue(struct array *) __at_nonnull(1); +void array_remove(struct array *, int) __at_nonnull(1); +void array_unref(struct array *, const void *) __at_nonnull(1); +int array_iswap(struct array *, int, int) __at_nonnull(1); +int array_pswap(struct array *, const void *, const void *) __at_nonnull(1); +void array_map(const struct array *, array_map_fn, void *) __at_nonnull(1, 2); +void *array_find(const struct array *, array_cmp_fn, int *, void *) __at_nonnull(1, 2); +void array_clear(struct array *) __at_nonnull(1); +void array_free(struct array *) __at_nonnull(1); + +#define ARRAY_HEAD(a, type) \ + (((type *)a->data)[0]) +#define ARRAY_TAIL(a, type) \ + (((type *)a->data)[(a->length == 0) ? 0 : a->length - 1]) +#define ARRAY_INDEX(a, i, type) \ + ((type *)(a)->data)[((i) < 0) \ + ? 0 : ((i) >= (a)->length) ? (a)->length - 1 : (i)] + +#define ARRAY_FOREACH_R(a, var) \ + for ((a)->i = 0, var = ARRAY_TAIL((a)); \ + (a)->i < (a)->length; ++(a)->i, --var) + +#define ARRAY_FOREACH(a, var, type) \ + for ((a)->i = 0, var = ARRAY_HEAD((a), type); \ + (a)->i < (a)->length; \ + ++(a)->i, var = ARRAY_INDEX((a), (a)->i, type)) + +#endif /* _ARRAY_H_ */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/parray.h Wed Nov 09 19:26:09 2011 +0100 @@ -0,0 +1,94 @@ +/* + * array.h -- manipulate dynamic pointer arrays + * + * 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 _PARRAY_H_ +#define _PARRAY_H_ + +/* Add some nonnull attributes for gcc/clang */ +#ifdef __GNUC__ +# define __at_malloc __attribute__ ((malloc)) +# define __at_nonnull(...) __attribute__ ((nonnull (__VA_ARGS__))) +#else +# define __at_malloc +# define __at_nonnull(...) +#endif + +#define PARRAY_DEFAULT_BSIZE 128 + +enum parray_type { + PARRAY_FIXED = 0, + PARRAY_AUTO = 1 +}; + +struct parray { + enum parray_type type; /* array type (default FIXED) */ + void **datas; /* array of data */ + int length; /* number of element inside */ + size_t size; /* current buffer size (allocated memory) */ + int bsize; /* block size (used when growing array) */ + int i; /* only for PARRAY_FOREACH(_R) */ +}; + +typedef void (*parray_map_fn)(void *, void *); +typedef int (*parray_cmp_fn)(void *, void *); + +struct parray *parray_new(enum parray_type, int) __at_malloc; +int parray_push(struct parray *, void *) __at_nonnull(1); +int parray_insert(struct parray *, void *, int) __at_nonnull(1); +int parray_append(struct parray *, void *) __at_nonnull(1); +void parray_pop(struct parray *) __at_nonnull(1); +void parray_unqueue(struct parray *) __at_nonnull(1); +void parray_remove(struct parray *, int) __at_nonnull(1); +void parray_unref(struct parray *, const void *) __at_nonnull(1); +int parray_iswap(struct parray *, int, int) __at_nonnull(1); +int parray_pswap(struct parray *, const void *, const void *) __at_nonnull(1); +void parray_map(const struct parray *, parray_map_fn, void *) __at_nonnull(1, 2); +void *parray_find(const struct parray *, parray_cmp_fn, int *, void *) __at_nonnull(1, 2); +void parray_clear(struct parray *) __at_nonnull(1); +void parray_free(struct parray *) __at_nonnull(1); + +#define PARRAY_HEAD(a) \ + (a->datas[0]) +#define PARRAY_TAIL(a) \ + (a->datas[(a->length == 0) ? 0 : a->length - 1]) +#define PARRAY_INDEX(a, i) \ + (((i) < 0 || (a)->length == 0) ? (PARRAY_HEAD((a))) /* < 0 head */ \ + : ((i) >= (a)->length) ? (PARRAY_TAIL((a))) /* > l tail */ \ + : ((a)->datas[i])) /* correct */ + +#define PARRAY_FOREACH_R(a, var) \ + for ((a)->i = 0, var = PARRAY_TAIL((a)); \ + (a)->i < (a)->length; ++(a)->i, var = PARRAY_INDEX((a), (a)->i)) + +#define PARRAY_FOREACH(a, var) \ + for ((a)->i = 0, var = PARRAY_INDEX((a), (a)->i); \ + (a)->i < (a)->length; ++(a)->i, var = PARRAY_INDEX((a), (a)->i)) + +#define PARRAY_FLUSH(a) \ +do { \ + void *i; \ + \ + PARRAY_FOREACH_R(a, i) { \ + free(i); \ + parray_unqueue((a)); \ + } \ + \ + (a)->length = 0; \ +} while (/* CONSTCOND */ 0); + +#endif /* _PARRAY_H_ */