# HG changeset patch # User David Demelier # Date 1317542116 -7200 # Node ID fdc3736ff806785dc4567881ab48192e45289d04 # Parent b972758ddcd59512682baf34b13ab19b91774a85 Added parray.c and parray.h: Functions similar to array.c but use pointers instead of memory blocks. diff -r b972758ddcd5 -r fdc3736ff806 parray.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/parray.c Sun Oct 02 09:55:16 2011 +0200 @@ -0,0 +1,273 @@ +/* + * parray.c -- manipulate dynamic pointer arrays + * + * Copyright (c) 2011, David Demelier + * + * 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 +#include +#include + +#include "parray.h" + +#define LENGTH(x) ((x) * (sizeof (void *))) + +static int parray_grow(struct parray *); + +struct parray * +parray_new(void *data, int bsize, int type) +{ + struct parray *arr; + + if ((arr = malloc(sizeof (struct parray))) == NULL) + return NULL; + + memset(arr, 0, sizeof (struct parray)); + + arr->type = type; + arr->bsize = (bsize == 0) ? PARRAY_DEFAULT_BSIZE : bsize; + arr->size = LENGTH(arr->bsize); + + if ((arr->datas = calloc(arr->bsize, sizeof (void *))) == NULL) { + free(arr); + return NULL; + } + + if (data) + arr->datas[0] = 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. + */ + +int +parray_push(struct parray *arr, void *data) +{ + if (parray_grow(arr) < 0) + return -1; + + memmove(&arr->datas[1], &arr->datas[0], LENGTH(arr->length++)); + arr->datas[0] = data; + + 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 +parray_insert(struct parray *arr, void *data, int index) +{ + if (index > arr->length - 1 || index < 0 || parray_grow(arr) < 0) + return -1; + + memmove(&arr->datas[index + 1], &arr->datas[index], + LENGTH(arr->length++ - index)); + arr->datas[index] = data; + + return 0; +} + +/* + * Append the data to the end of array. + */ + +int +parray_append(struct parray *arr, void *data) +{ + if (parray_grow(arr) < 0) + return -1; + + arr->datas[arr->length++] = data; + + return 0; +} + +/* + * Remove the array's head. + */ + +void +parray_pop(struct parray *arr) +{ + if (arr->length > 0) { + memmove(&arr->datas[0], &arr->datas[1], LENGTH(--arr->length)); + arr->datas[arr->length] = NULL; + } +} + +/* + * Remove the array's tail. + */ + +void +parray_unqueue(struct parray *arr) +{ + if (arr->length > 0) + arr->datas[--arr->length] = NULL; +} + +/* + * Remove the data at the specified index. Bounds are checked. + */ + +void +parray_remove(struct parray *arr, int index) +{ + if (arr->length > 0 && index >= 0 && index < arr->length) { + memmove(&arr->datas[index], &arr->datas[index + 1], + LENGTH(arr->length - index - 1)); + arr->datas[--arr->length] = NULL; + } +} + +/* + * Remove the object referenced by the `data' argument. Useful when you + * don't know the index. + */ + +void +parray_unref(struct parray *arr, const void *data) +{ + void *elm; + int i; + + for (i = 0; i < arr->length; ++i) { + elm = PARRAY_INDEX(arr, i); + + if (elm == data) + parray_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 +parray_swap(struct parray *arr, int i1, int i2) +{ + void *tmp; + + /* Out of bounds */ + if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0) + return -1; + + tmp = arr->datas[i1]; + arr->datas[i1] = arr->datas[i2]; + arr->datas[i2] = tmp; + + return 0; +} + +/* + * Apply the function `fn' on each object and give the optional `udata' + * argument to the function too. + */ + +void +parray_map(const struct parray *arr, void (*fn)(void *, void *), void *udata) +{ + int i; + + for (i = 0; i < arr->length; ++i) + fn(arr->datas[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 * +parray_find(const struct parray *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(arr->datas[i], u); + + if (st) { + data = arr->datas[--i]; + if (ix) + *ix = 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 +parray_clear(struct parray *arr) +{ + memset(arr->datas, 0, arr->size); + arr->length = 0; +} + +/* + * Same as parray_clear except it also free the array object. + */ + +void +parray_free(struct parray *arr) +{ + parray_clear(arr); + + if (arr->datas) + free(arr->datas); + + 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 +parray_grow(struct parray *arr) +{ + if ((arr->size / sizeof (void *)) > (size_t) arr->length - 1) + return 0; + + if (arr->type == PARRAY_AUTO) { + if ((arr->datas = realloc(arr->datas, arr->size + + LENGTH(arr->bsize))) == NULL) + return -1; + + arr->size += LENGTH(arr->bsize); + } else + return -1; + + return 0; +} diff -r b972758ddcd5 -r fdc3736ff806 parray.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/parray.h Sun Oct 02 09:55:16 2011 +0200 @@ -0,0 +1,73 @@ +/* + * array.h -- manipulate dynamic pointer arrays + * + * Copyright (c) 2011, David Demelier + * + * 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_ + +#define PARRAY_DEFAULT_BSIZE 128 + +#define PARRAY_FIXED 0x00 +#define PARRAY_AUTO 0x01 + +struct parray { + void **datas; /* array of data */ + int length; /* number of element inside */ + int type; /* array's flags (default FIXED) */ + size_t size; /* current buffer size (allocated memory) */ + int bsize; /* block size (used when growing array) */ + + /* Private, do not modify */ + int _i; /* only for PARRAY_FOREACH(_R) */ +}; + +struct parray *parray_new(void *, int, int); +#define parray_new_auto() parray_new(NULL, 0, PARRAY_AUTO) +#define parray_new_fixed(max) parray_new(NULL, max, PARRAY_FIXED) + +int parray_push(struct parray *, void *); +int parray_insert(struct parray *, void *, int); +int parray_append(struct parray *, void *); +void parray_pop(struct parray *); +void parray_unqueue(struct parray *); +void parray_remove(struct parray *, int); +void parray_unref(struct parray *, const void *); +int parray_swap(struct parray *, int, int); +void parray_map(const struct parray *, void (*fn)(void *, void *), void *); +void *parray_find(const struct parray *, int (*fn)(void *, void *), int *, void *); +void parray_clear(struct parray *); +void parray_free(struct parray *); + +#define PARRAY_FOREACH(a, var) \ + for ((a)->_i = 0, var = (a)->datas[0]; \ + (a)->_i < (a)->length; ++(a)->_i, \ + var = (a)->datas[((a)->_i >= (a)->length) ? \ + (a)->length - 1 : (a)->_i]) + +#define PARRAY_FOREACH_R(a, var) \ + for ((a)->_i = (a)->length - 1, var = (a)->datas[(a)->_i]; \ + (a)->_i >= 0; \ + --(a)->_i, var = (a)->datas[((a)->_i < 0) ? 0 : (a)->_i]) + +#define PARRAY_HEAD(a) \ + a->datas[0] +#define PARRAY_TAIL(a) \ + a->datas[a->length - 1] +#define PARRAY_INDEX(a, i) \ + a->datas[(i >= a->length) ? (a->length - 1) : i] + +#endif /* _PARRAY_H_ */