Hello GNUlib authors, I wrote an "extensible array" code as part of a larger project, and thought it could be of some interest to GNUlib. However, I'm not sure it does not fall into the category of "stuff that would be better packaged separately", so I'm inquiring here first, before wrapping it up properly as a patch.
The "XARRAY" macro creates an array of any given C type (plus some optional headers), and defines functions to append/remove/insert elements into the array. Documentation is in the attached C header file; the test case shows a usage sample. Best regards, Riccardo
/** * @file xarray.h * * Definitions for module @c xarray * * @author [email protected] * @version $Revision$ */ /* * Copyright (c) 2010 [email protected]. All rights reserved. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * */ #ifndef XARRAY_H #define XARRAY_H #include <xalloc.h> #include <assert.h> #include <string.h> // memmove #include <stdlib.h> // malloc, realloc, free #define _inline static inline /** @def XARRAY_CREATE(aname, elt_t, extra) * * Declare an xarray-like type @c aname_t and functions to operate on * it. An xarray is a (malloc'd) contiguous block of memory holding * instances of elements of type @a elt_t; functions are provided to * allocate a new xarray (@c aname_alloc), append elements at the end of * the array, automatically relocating it if needed (@c aname_extend), * access/insert/remove elements at specific positions (@c aname_at, * @c aname_insert, @c aname_erase), wipe off all elements from an * array (@c aname_clear) or dispose of it and return the storage to * the system. * */ #define XARRAY_DECLARE(aname, elt_t, extra) \ \ typedef struct { \ /** user defined extra info that is fitted into the array */ \ extra; \ /** number of elements that can be stored in the xarray before \ * realloc() must take place. */ \ size_t allocated; \ /** number of elements stored in the xarray */ \ size_t count; \ /** memory space where xarray elements are stored */ \ elt_t storage[]; \ } aname##_t; \ \ \ /** Return a newly-allocated xarray, or @c NULL if the allocation \ failed. The xarray is initially sized to contain @c nmemb elements \ without the need to resize. */ \ _inline aname##_t* aname##_alloc(const size_t nmemb) { \ aname##_t* xa = (aname##_t*)xmalloc(sizeof(aname##_t) \ + sizeof(elt_t)*nmemb); \ if (NULL == xa) \ return NULL; \ \ xa->allocated = nmemb; \ xa->count = 0; \ \ assert(NULL != xa); \ assert(xa->count <= xa->allocated); \ return xa; \ }; \ \ \ /** Initialize a new xarray placed at address @a ptr and fitting within\ @a size bytes. Return pointer to the start of the xarray, or \ @c NULL if there was some error (e.g., @a size is insufficient). */\ _inline aname##_t* aname##_alloc_placed(void* xa, const size_t size) { \ assert(NULL != xa); \ assert(size > sizeof(aname##_t)); \ if(size < sizeof(aname##_t)) \ return NULL; \ \ aname##_t* xa_ = (aname##_t*)xa; \ xa_->allocated = (size - sizeof(aname##_t)) / sizeof(elt_t); \ xa_->count = 0; \ \ assert(xa_->count <= xa_->allocated); \ return xa_; \ }; \ \ \ /** Return a pointer to the element in the xarray at position @c pos. \ Xarray positions follow the usual C convention, ranging from 0 to @c \ xa->count-1. */ \ _inline size_t aname##_size(const aname##_t* const xa) { \ assert(NULL != xa); \ return xa->count; \ }; \ \ \ /** Return a pointer to the first byte in the xarray. */ \ _inline void* aname##_lb(const aname##_t* const xa) { \ assert(NULL != xa); \ return (void*)xa; \ }; \ \ \ /** Return a pointer past the last used byte in the xarray. */ \ _inline void* aname##_ub(const aname##_t* const xa) { \ assert(NULL != xa); \ return (void*) &(xa->storage[xa->count]); \ }; \ \ \ /** Return a pointer to the element in the xarray at position @c pos. \ Xarray positions follow the usual C convention, ranging from 0 to @c \ xa->count-1. */ \ _inline elt_t* aname##_at(aname##_t* const xa, size_t pos) { \ assert(NULL != xa); \ assert(pos < xa->count); \ return &(xa->storage[pos]); \ }; \ \ \ /** Ensure that xarray @c xa can be extended by appending @c nmemb \ elements at the end of the array without incurring in any \ relocation; return a pointer to the first newly-added place, or @c \ NULL on failure. Note that the newly-added positions are not \ initialized. */ \ _inline void aname##_reserve(aname##_t** xa, const size_t nmemb) { \ assert(NULL != xa); \ assert(NULL != *xa); \ assert((*xa)->count <= (*xa)->allocated); \ \ const long more = nmemb - ((*xa)->allocated - (*xa)->count); \ if (more > 0) { \ /* resize xarray->storage */ \ aname##_t* new_xa = xrealloc((*xa), sizeof(aname##_t) + \ sizeof(elt_t) * (more + (*xa)->allocated)); \ if (NULL == new_xa) \ return; \ (*xa) = new_xa; \ (*xa)->allocated += more; \ } \ assert((*xa)->count <= (*xa)->allocated); \ }; \ \ \ /** Extend xarray @c xa by adding @c nmemb elements at the end of the \ array; return a pointer to the first newly-added place, or @c \ NULL on failure. Note that the newly-added positions are not \ initialized. */ \ _inline elt_t* aname##_extend(aname##_t** xa, size_t nmemb) { \ assert(NULL != xa); \ assert(NULL != *xa); \ assert(0 < nmemb); \ \ aname##_reserve(xa, nmemb); \ (*xa)->count += nmemb; \ \ assert((*xa)->count <= (*xa)->allocated); \ return aname##_at(*xa, (*xa)->count - nmemb); \ }; \ \ \ /** Extend xarray @c xa by adding 1 element at the end of the array, \ and return a pointer to the newly-added place, or @c NULL on \ failure. */ \ _inline elt_t* aname##_extend1(aname##_t** xa) { \ return aname##_extend(xa, 1); \ }; \ \ \ /** Shorten @c xa by removing @a nmemb elements from the end of the array. */\ _inline void aname##_shorten(aname##_t** const xa, const size_t nmemb){\ assert(NULL != xa); \ assert(NULL != *xa); \ \ (*xa)->count -= nmemb; \ if((*xa)->count < 0) \ (*xa)->count = 0; \ }; \ \ \ /** Shorten @c xa by removing one element from the end of the array. */\ _inline void aname##_shorten1(aname##_t** const xa) { \ assert(NULL != xa); \ assert(NULL != *xa); \ \ if((*xa)->count > 0) \ (*xa)->count--; \ }; \ \ \ /** Insert one element in the array at position @c pos and return \ pointer to the newly-added place, or @c NULL if some error occurred. \ Array positions follow the usual C convention, ranging from 0 to @c \ xa->count-1. Note that the new location is not initialized. */ \ _inline elt_t* aname##_insert(aname##_t** const xa, const size_t pos) {\ assert(NULL != xa); \ assert(NULL != *xa); \ assert(pos < (*xa)->count); \ \ elt_t* p = aname##_extend1(xa); \ if(NULL == p) \ return NULL; \ \ elt_t* src = aname##_at(*xa, pos); \ elt_t* dst = aname##_at(*xa, pos+1); \ memmove(dst, src, sizeof(elt_t) * ((*xa)->count - pos)); \ return src; \ }; \ \ \ /** Remove the element at position @c pos from the xarray. Array \ positions follow the usual C convention, ranging from 0 to @c \ xa->count-1. */ \ _inline void aname##_erase(aname##_t** const xa, const size_t pos) { \ assert(NULL != xa); \ assert(NULL != *xa); \ assert(pos < (*xa)->count); \ \ if (pos == (*xa)->count - 1) { \ /* remove last element */ \ aname##_shorten1(xa); \ } \ else { \ void* src = aname##_at(*xa, pos+1); \ void* dst = aname##_at(*xa, pos); \ memmove(dst, src, sizeof(elt_t) * ((*xa)->count - pos - 1)); \ (*xa)->count -= 1; \ } \ }; \ \ \ /** Forget all the contents and return @c xa to 0 size. The memory \ allocated to the array is *not* freed. */ \ _inline void aname##_clear(aname##_t** const xa) { \ assert(NULL != xa); \ assert(NULL != *xa); \ (*xa)->count = 0; \ }; \ \ \ /** Free array @c xa and return allocated memory to the system. */ \ _inline void aname##_free(aname##_t *xa) { \ free(xa); \ }; \ #endif // XARRAY_H
/** * @file test-xarray.c * * Test cases for module @c xarray * * @author [email protected] * @version $Revision$ */ /* * Copyright (c) 2010 [email protected]. All rights reserved. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * */ #include "xarray.h" #include <stdio.h> #include <assert.h> typedef struct { int coord; double val; } entry_t; XARRAY_DECLARE(row, entry_t, int a; float b; char c); /* check that `r` is an array of (n,n+1) pairs, sorted in ascending order. */ void check_row(row_t* r) { for (int n = 0; n < row_size(r); ++n) { assert(n == r->storage[n].coord); assert(n+1 == r->storage[n].val); assert(n == row_at(r, n)->coord); assert(n+1 == row_at(r, n)->val); }; }; int main(int argc, char** argv) { /* create new row */ row_t* r = row_alloc(2); assert(row_size(r) == 0); assert(r->allocated == 2); /* add one element */ entry_t* p = row_extend1(&r); assert(row_size(r) == 1); p->coord = 0; p->val = 1; /* check it back */ p = row_at(r, 0); assert(0 == p->coord); assert(1.0 == p->val); /* request more storage space */ row_reserve(&r, 3); assert(row_size(r) == 1); assert(r->allocated >= 4); /* add more items one at a time */ for (int n = 1; n < 10; ++n) { p = row_extend1(&r); assert(row_size(r) == n+1); p->coord = n; p->val = n+1; }; check_row(r); row_shorten1(&r); assert(row_size(r) == 9); check_row(r); row_shorten(&r, 4); assert(row_size(r) == 5); check_row(r); row_clear(&r); assert(row_size(r) == 0); /* now try adding back 5 elements at a time */ p = row_extend(&r, 5); assert(row_size(r) == 5); for (int n = 0; n < 5; ++n) { p->coord = n; p->val = n+1; ++p; }; check_row(r); /* replace them and then insert some more */ p = r->storage; for (int n = 0; n < 5; ++n) { p->coord = 2*n; p->val = 2*n+1; ++p; }; for (int n = 3; n >= 0; --n) { p = row_insert(&r, n+1); p->coord = 2*n+1; p->val = 2*n+2; } assert(row_size(r) == 9); check_row(r); /* erase elements in even position */ for (int n = 4; n >= 0; --n) row_erase(&r, 2*n); assert(row_size(r) == 4); for (int n = 0; n < 4; ++n) { p = row_at(r, n); assert(2*n+1 == p->coord); assert(2*n+2 == p->val); } /* finally, free it */ row_free(r); /* now, do the same checks, but allocated the buffer separately with malloc */ void* buf = malloc(256); assert(NULL != buf); r = row_alloc_placed(buf, 256); assert(row_size(r) == 0); assert(r->allocated >= 0); /* add one element */ p = row_extend1(&r); assert(row_size(r) == 1); p->coord = 0; p->val = 1; /* check it back */ p = row_at(r, 0); assert(0 == p->coord); assert(1.0 == p->val); /* request more storage space */ row_reserve(&r, 3); assert(row_size(r) == 1); assert(r->allocated >= 4); /* add more items one at a time */ for (int n = 1; n < 10; ++n) { p = row_extend1(&r); assert(row_size(r) == n+1); p->coord = n; p->val = n+1; }; check_row(r); row_shorten1(&r); assert(row_size(r) == 9); check_row(r); row_shorten(&r, 4); assert(row_size(r) == 5); check_row(r); row_clear(&r); assert(row_size(r) == 0); /* now try adding back 5 elements at a time */ p = row_extend(&r, 5); assert(row_size(r) == 5); for (int n = 0; n < 5; ++n) { p->coord = n; p->val = n+1; ++p; }; check_row(r); /* replace them and then insert some more */ p = r->storage; for (int n = 0; n < 5; ++n) { p->coord = 2*n; p->val = 2*n+1; ++p; }; for (int n = 3; n >= 0; --n) { p = row_insert(&r, n+1); p->coord = 2*n+1; p->val = 2*n+2; } assert(row_size(r) == 9); check_row(r); /* erase elements in even position */ for (int n = 4; n >= 0; --n) row_erase(&r, 2*n); assert(row_size(r) == 4); for (int n = 0; n < 4; ++n) { p = row_at(r, n); assert(2*n+1 == p->coord); assert(2*n+2 == p->val); } /* finally, free it */ row_free(r); return 0; }
