Mercurial > code
changeset 61:e1f3ed0bf507
Failed hg forgot
author | David Demelier <markand@malikania.fr> |
---|---|
date | Wed, 09 Nov 2011 19:25:35 +0100 |
parents | d6d8b753d7de |
children | d10ab6bc555d |
files | array.c array.h |
diffstat | 2 files changed, 0 insertions(+), 397 deletions(-) [+] |
line wrap: on
line diff
--- a/array.c Wed Nov 09 19:25:02 2011 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,314 +0,0 @@ -/* - * 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; -}
--- a/array.h Wed Nov 09 19:25:02 2011 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,83 +0,0 @@ -/* - * 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_ */