diff options
Diffstat (limited to 'c_src')
| -rw-r--r-- | c_src/Makefile | 6 | ||||
| -rw-r--r-- | c_src/arlamath.c | 69 | ||||
| -rw-r--r-- | c_src/arlamath.h | 46 | ||||
| -rw-r--r-- | c_src/hash.c | 402 | ||||
| -rw-r--r-- | c_src/hash.h | 98 | ||||
| -rw-r--r-- | c_src/permdb.c | 1 | ||||
| -rw-r--r-- | c_src/pstring.h | 37 | ||||
| -rw-r--r-- | c_src/utarray.h | 237 |
8 files changed, 277 insertions, 619 deletions
diff --git a/c_src/Makefile b/c_src/Makefile index fc18e41..ecdb038 100644 --- a/c_src/Makefile +++ b/c_src/Makefile @@ -30,9 +30,9 @@ OTHER_BIN = permdb.so permdbtest common_OBJS = erlport.o net_read_write.o fsynchelper_OBJS = fsynchelper.o $(common_OBJS) hsmhelper_OBJS = hsmhelper.o pkcs11.o $(common_OBJS) -permdbport_OBJS = permdb.o permdbport.o arlamath.o hash.o filebuffer.o util.o $(common_OBJS) -permdbso_OBJS = permdb.o arlamath.o hash.o permdbpy.o filebuffer.o util.o $(common_OBJS) -permdbtest_OBJS = permdb.o arlamath.o hash.o permdbtest.o filebuffer.o util.o $(common_OBJS) +permdbport_OBJS = permdb.o permdbport.o filebuffer.o util.o $(common_OBJS) +permdbso_OBJS = permdb.o permdbpy.o filebuffer.o util.o $(common_OBJS) +permdbtest_OBJS = permdb.o permdbtest.o filebuffer.o util.o $(common_OBJS) all: $(PORTS) $(OTHER_BIN) diff --git a/c_src/arlamath.c b/c_src/arlamath.c deleted file mode 100644 index 99ff6f6..0000000 --- a/c_src/arlamath.c +++ /dev/null @@ -1,69 +0,0 @@ -/* - * Copyright (c) 2002 Kungliga Tekniska Högskolan - * (Royal Institute of Technology, Stockholm, Sweden). - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * 3. Neither the name of the Institute nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -/* - * a collection of math functions - */ - -/* $Id: arlamath.c,v 1.1 2002/05/12 16:00:24 lha Exp $ */ - -#include "arlamath.h" - -int -arlautil_isprime(int p) -{ - int q,i; - for(i=2 ; i < p; i++) { - q = p/i; - - if(i*q == p) - return 0; - if(i*i > p) - return 1; - } - return 1; -} - -int -arlautil_findprime(int p) -{ - if(p % 2 == 0) { - p++; - } - - while(!arlautil_isprime(p)) { - p+=2; - } - return p; -} - diff --git a/c_src/arlamath.h b/c_src/arlamath.h deleted file mode 100644 index c015949..0000000 --- a/c_src/arlamath.h +++ /dev/null @@ -1,46 +0,0 @@ -/* - * Copyright (c) 2002 Kungliga Tekniska Högskolan - * (Royal Institute of Technology, Stockholm, Sweden). - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * 3. Neither the name of the Institute nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -/* - * a collection of math functions - */ - -/* $Id: arlamath.h,v 1.1 2002/05/12 16:00:24 lha Exp $ */ - -#ifndef _ARLAMATH_H_ -#define _ARLAMATH_H_ 1 - -int arlautil_isprime(int p); /* predicate deciding if a number is prime */ -int arlautil_findprime(int p); /* returns the next prime following p */ - -#endif /* _ARLAMATH_H_ */ diff --git a/c_src/hash.c b/c_src/hash.c deleted file mode 100644 index 75d3999..0000000 --- a/c_src/hash.c +++ /dev/null @@ -1,402 +0,0 @@ -/* - * Copyright (c) 1995, 1996, 1997, 1998, 1999 Kungliga Tekniska Högskolan - * (Royal Institute of Technology, Stockholm, Sweden). - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * 3. Neither the name of the Institute nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -/* - * Hash table functions - */ - -#ifdef HAVE_CONFIG_H -#include <config.h> -RCSID("$Id: hash.c,v 1.18 2002/05/23 15:21:41 lha Exp $"); -#endif - -#include <assert.h> -#include <stdio.h> -#include <stdlib.h> -#include <limits.h> -#include <ctype.h> -//#include <bool.h> -#include "hash.h" -#include "arlamath.h" - - -struct ht_bucket { - Hashentry *e; - int len; -}; - - -struct hashtab { /* Hash table */ - int (*cmp)(void *, void *); /* Compare function */ - unsigned (*hash)(void *); /* hash function */ - int flags; /* flags */ - int sz; /* Size */ - int maxbucketlen; /* max bucket length */ - struct ht_bucket *tab; /* The table */ -}; - -struct hashentry { /* Entry in bucket */ - struct hashentry **prev; - struct hashentry *next; - void *ptr; -}; - -#define HASHTAB_INITAL_SIZE 17 -#define HASHTAB_MAX_BUCKET_LEN 20 - -static Hashentry *_search(Hashtab * htab, /* The hash table */ - void *ptr); /* And key */ -static void *_add(Hashtab * htab, - void *ptr, - int unique); - -static void _might_resize(Hashtab *htab, /* The hash table */ - int bucket_len); /* Hash bucket len */ - -Hashtab * -hashtabnew(int sz, - int (*cmp) (void *, void *), - unsigned (*hash) (void *)) -{ - return hashtabnewf(sz, cmp, hash, 0); -} - -Hashtab * -hashtabnewf(int sz, - int (*cmp) (void *, void *), - unsigned (*hash) (void *), - int flags) -{ - Hashtab *htab; - int i; - - assert(sz > 0 || (flags & HASHTAB_GROW)); - - htab = (Hashtab *) malloc(sizeof(Hashtab)); - - if (htab == NULL) - return NULL; - - if (sz == 0 && (flags & HASHTAB_GROW)) - sz = HASHTAB_INITAL_SIZE; - - htab->tab = malloc(sz * sizeof(struct ht_bucket)); - if (htab->tab == NULL){ - free(htab); - return NULL; - } - - for (i = 0; i < sz; ++i) { - htab->tab[i].e = NULL; - htab->tab[i].len = 0; - } - - htab->cmp = cmp; - htab->hash = hash; - htab->sz = sz; - htab->maxbucketlen = HASHTAB_MAX_BUCKET_LEN; - htab->flags = flags; - - return htab; -} - -/* Intern search function */ - -static Hashentry * -_search(Hashtab * htab, void *ptr) -{ - Hashentry *hptr; - - assert(htab && ptr); - - for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz].e; - hptr; - hptr = hptr->next) - if ((*htab->cmp) (ptr, hptr->ptr) == 0) - break; - return hptr; -} - -/* Interal resize function */ - -static int -_resize(void *ptr, void *arg) -{ - Hashtab *h = arg; - _add(h, ptr, TRUE); - return TRUE; -} - -static void -_might_resize(Hashtab *htab, int bucket_len) -{ - if (bucket_len > htab->maxbucketlen) { - Hashtab *nhtab; - struct ht_bucket *tab; - int new_size, old_size; - - new_size = arlautil_findprime(htab->sz * 2); - fprintf(stderr, "trying resize to %d\n", new_size); - assert (new_size > htab->sz); - - nhtab = hashtabnewf(new_size, htab->cmp, - htab->hash, htab->flags); - if (nhtab == NULL) - return; - - hashtabcleantab(htab, _resize, nhtab); - - /* switch place between the tab and size */ - tab = htab->tab; - htab->tab = nhtab->tab; - nhtab->tab = tab; - - old_size = htab->sz; - htab->sz = nhtab->sz; - nhtab->sz = old_size; - - hashtabrelease(nhtab); - } -} - - -/* Search for element in hash table */ - -void * -hashtabsearch(Hashtab * htab, void *ptr) -{ - Hashentry *tmp; - - tmp = _search(htab, ptr); - return tmp ? tmp->ptr : tmp; -} - -/* add element to hash table */ -/* if already there, set new value */ -/* !NULL if succesful */ - -static void * -_add(Hashtab * htab, void *ptr, int unique) -{ - Hashentry *h = _search(htab, ptr); - Hashentry **tabptr; - struct ht_bucket *hb; - - assert(htab && ptr); - - if (h) { - if (unique) - return NULL; - free((void *) h->ptr); - h->ptr = ptr; - } else { - h = (Hashentry *) malloc(sizeof(Hashentry)); - if (h == NULL) { - return NULL; - } - hb = &htab->tab[(*htab->hash) (ptr) % htab->sz]; - hb->len++; - tabptr = &hb->e; - h->next = *tabptr; - h->prev = tabptr; - if (h->next) - h->next->prev = &h->next; - h->ptr = ptr; - *tabptr = h; -#if 0 - if (hb->len > htab->maxbucketlen) { - struct nodecache { - uint32_t entries[4]; - char key[]; - }; - { - struct nodecache *node = (struct nodecache *)ptr; - - fprintf(stderr, "bucket %u full: %d, searching for %s\n", (*htab->hash) (ptr) % htab->sz, hb->len, node->key); - } - for (Hashentry *hptr = htab->tab[(*htab->hash) (ptr) % htab->sz].e; - hptr; - hptr = hptr->next) { - struct nodecache *node = (struct nodecache *)hptr->ptr; - fprintf(stderr, "\tothers in bucket: %s\n", node->key); - } - } -#endif - if (htab->flags & HASHTAB_GROW) - _might_resize(htab, hb->len); - } - return h; -} - -void * -hashtabaddreplace (Hashtab *htab, void *ptr) -{ - return _add (htab, ptr, FALSE); -} - -void * -hashtabadd (Hashtab *htab, void *ptr) -{ - return _add (htab, ptr, TRUE); -} - -/* delete element with key key. Iff freep, free Hashentry->ptr */ - -int -_hashtabdel(Hashtab * htab, void *ptr, int freep) -{ - Hashentry *h; - - assert(htab && ptr); - - h = _search(htab, ptr); - if (h) { - if (freep) - free(h->ptr); - if ((*(h->prev) = h->next)) - h->next->prev = h->prev; - free(h); - return 0; - } else - return -1; -} - -/* Do something for each element */ - -void -hashtabforeach(Hashtab * htab, int(*func) (void *ptr, void *arg), - void *arg) -{ - struct ht_bucket *h; - Hashentry *g, *next; - - assert(htab); - - for (h = htab->tab; h < &htab->tab[htab->sz]; ++h) - for (g = h->e; g; g = next) { - next = g->next; - if ((*func) (g->ptr, arg)) - return; - } -} - - -/* Clean out all elements that meet condition */ - -void -hashtabcleantab(Hashtab * htab, int(*cond) (void *ptr, void *arg), - void *arg) -{ - struct ht_bucket *h; - Hashentry *g, *f; - - assert(htab); - - for (h = htab->tab; h < &htab->tab[htab->sz]; ++h) { - for (g = h->e; g;) { - if ((*cond) (g->ptr, arg)) { - f = g ; - g = g->next ; - if ((*(f->prev) = f->next)) - f->next->prev = f->prev; - free(f); - assert(h->len > 0); - h->len--; - } else { - g = g->next; - } - } - } -} - -static int -true_cond(void *ptr, void *arg) -{ - return TRUE; -} - -/* Free the hashtab and all items in it */ - -void -hashtabrelease(Hashtab *htab) -{ - hashtabcleantab(htab, true_cond, NULL); - free(htab->tab); - free(htab); -} - - -/* standard hash-functions for strings */ - -unsigned -hashadd(const char *s) -{ /* Standard hash function */ - unsigned i; - - assert(s); - - for (i = 0; *s; ++s) - i += *s; - return i; -} - -unsigned -hashcaseadd(const char *s) -{ /* Standard hash function */ - unsigned i; - - assert(s); - - for (i = 0; *s; ++s) - i += toupper((unsigned char)*s); - return i; -} - -#define TWELVE (sizeof(unsigned)) -#define SEVENTYFIVE (6*sizeof(unsigned)) -#define HIGH_BITS (~((unsigned)(~0) >> TWELVE)) - -unsigned -hashjpw(const char *ss) -{ /* another hash function */ - unsigned h = 0; - unsigned g; - unsigned const char *s = (unsigned const char *) ss; - - for (; *s; ++s) { - h = (h << TWELVE) + *s; - if ((g = h & HIGH_BITS)) - h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS; - } - return h; -} diff --git a/c_src/hash.h b/c_src/hash.h deleted file mode 100644 index 55b81fb..0000000 --- a/c_src/hash.h +++ /dev/null @@ -1,98 +0,0 @@ -/* - * Copyright (c) 1995, 1996, 1997, 1998 Kungliga Tekniska Högskolan - * (Royal Institute of Technology, Stockholm, Sweden). - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * 3. Neither the name of the Institute nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -/* - * hash.h. Header file for hash table functions - */ - -/* $Id: hash.h,v 1.8 2002/05/12 16:02:33 lha Exp $ */ - -#define TRUE 1 -#define FALSE 0 - -#define HASHTAB_GROW 0x01 - -struct hashentry; -typedef struct hashentry Hashentry; - -struct hashtab; - -typedef struct hashtab Hashtab; -typedef int (*hashtabnew_arg2_t)(void *, void *); -typedef unsigned (*hashtabnew_arg3_t)(void *); - -/* prototypes */ - -Hashtab *hashtabnew(int sz, - int (*cmp)(void *, void *), - unsigned (*hash)(void *)); /* Make new hash table */ - -Hashtab *hashtabnewf(int sz, - int (*cmp)(void *, void *), - unsigned (*hash)(void *), - int flags); /* Make new hash table */ - -void *hashtabsearch(Hashtab *htab, /* The hash table */ - void *ptr); /* The key */ - - -void *hashtabaddreplace(Hashtab *htab, /* The hash table */ - void *ptr); /* The element */ - -void *hashtabadd(Hashtab *htab, - void *ptr); - -int _hashtabdel(Hashtab *htab, /* The table */ - void *ptr, /* Key */ - int freep); /* Free data part? */ - -void hashtabforeach(Hashtab *htab, - int (*func)(void *ptr, void *arg), - void *arg); - -void hashtabcleantab(Hashtab * htab, - int (*cond) (void *ptr, void *arg), - void *arg); - -void hashtabrelease(Hashtab *htab); - -unsigned hashadd(const char *s); /* Standard hash function */ -unsigned hashcaseadd(const char *s); /* Standard hash function */ -unsigned hashjpw(const char *s); /* another hash function */ - -/* macros */ - - /* Don't free space */ -#define hashtabdel(htab,key) _hashtabdel(htab,key,FALSE) - -#define hashtabfree(htab,key) _hashtabdel(htab,key,TRUE) /* Do! */ diff --git a/c_src/permdb.c b/c_src/permdb.c index 9221f45..29c38cc 100644 --- a/c_src/permdb.c +++ b/c_src/permdb.c @@ -17,7 +17,6 @@ #include <nettle/sha2.h> #include "erlport.h" #include "permdb.h" -#include "hash.h" #include "filebuffer.h" #include "util.h" diff --git a/c_src/pstring.h b/c_src/pstring.h new file mode 100644 index 0000000..3a8b602 --- /dev/null +++ b/c_src/pstring.h @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2015, NORDUnet A/S. + * See LICENSE for licensing information. + */ + +#ifndef PSTRING_H +#define PSTRING_H + +typedef struct ps_string { + unsigned char length; + char value[255]; +} ps_string; + +#define PS_STRING(s) (&(ps_string){strlen(s), s}) +#define PS_PRINTF(s) s->length, s->value + +static inline ps_string * +ps_strdup(const ps_string *s) +{ + size_t size = s->length + 1; + ps_string *copy = malloc(size); + memcpy(copy, s, size); + return copy; +} + +static inline ps_string * +ps_resize(const ps_string *s, size_t length) +{ + assert(length <= s->length); + size_t newsize = length + 1; + ps_string *copy = malloc(newsize); + memcpy(copy->value, s->value, length); + copy->length = length; + return copy; +} + +#endif diff --git a/c_src/utarray.h b/c_src/utarray.h new file mode 100644 index 0000000..bed96b7 --- /dev/null +++ b/c_src/utarray.h @@ -0,0 +1,237 @@ +/* +Copyright (c) 2008-2014, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a dynamic array implementation using macros + */ +#ifndef UTARRAY_H +#define UTARRAY_H + +#define UTARRAY_VERSION 1.9.9 + +#ifdef __GNUC__ +#define _UNUSED_ __attribute__ ((__unused__)) +#else +#define _UNUSED_ +#endif + +#include <stddef.h> /* size_t */ +#include <string.h> /* memset, etc */ +#include <stdlib.h> /* exit */ + +#ifndef oom +#define oom() exit(-1) +#endif + +typedef void (ctor_f)(void *dst, const void *src); +typedef void (dtor_f)(void *elt); +typedef void (init_f)(void *elt); +typedef struct { + size_t sz; + init_f *init; + ctor_f *copy; + dtor_f *dtor; +} UT_icd; + +typedef struct { + unsigned i,n;/* i: index of next available slot, n: num slots */ + UT_icd icd; /* initializer, copy and destructor functions */ + char *d; /* n slots of size icd->sz*/ +} UT_array; + +#define utarray_init(a,_icd) do { \ + memset(a,0,sizeof(UT_array)); \ + (a)->icd=*_icd; \ +} while(0) + +#define utarray_done(a) do { \ + if ((a)->n) { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + free((a)->d); \ + } \ + (a)->n=0; \ +} while(0) + +#define utarray_new(a,_icd) do { \ + a=(UT_array*)malloc(sizeof(UT_array)); \ + utarray_init(a,_icd); \ +} while(0) + +#define utarray_free(a) do { \ + utarray_done(a); \ + free(a); \ +} while(0) + +#define utarray_reserve(a,by) do { \ + if (((a)->i+(by)) > ((a)->n)) { \ + char *utarray_tmp; \ + while(((a)->i+(by)) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ + utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \ + if (utarray_tmp == NULL) oom(); \ + (a)->d=utarray_tmp; \ + } \ +} while(0) + +#define utarray_push_back(a,p) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ + else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ +} while(0) + +#define utarray_pop_back(a) do { \ + if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ + else { (a)->i--; } \ +} while(0) + +#define utarray_extend_back(a) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ + else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ + (a)->i++; \ +} while(0) + +#define utarray_len(a) ((a)->i) + +#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) +#define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) ))) + +#define utarray_insert(a,p,j) do { \ + if (j > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,1); \ + if ((j) < (a)->i) { \ + memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ + else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ + (a)->i++; \ +} while(0) + +#define utarray_inserta(a,w,j) do { \ + if (utarray_len(w) == 0) break; \ + if (j > (a)->i) utarray_resize(a,j); \ + utarray_reserve(a,utarray_len(w)); \ + if ((j) < (a)->i) { \ + memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ + _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { \ + size_t _ut_i; \ + for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ + (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \ + } \ + } else { \ + memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ + utarray_len(w)*((a)->icd.sz)); \ + } \ + (a)->i += utarray_len(w); \ +} while(0) + +#define utarray_resize(dst,num) do { \ + size_t _ut_i; \ + if (dst->i > (size_t)(num)) { \ + if ((dst)->icd.dtor) { \ + for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \ + (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \ + } \ + } \ + } else if (dst->i < (size_t)(num)) { \ + utarray_reserve(dst,num-dst->i); \ + if ((dst)->icd.init) { \ + for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \ + (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \ + } \ + } else { \ + memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \ + } \ + } \ + dst->i = num; \ +} while(0) + +#define utarray_concat(dst,src) do { \ + utarray_inserta((dst),(src),utarray_len(dst)); \ +} while(0) + +#define utarray_erase(a,pos,len) do { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < len; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \ + } \ + } \ + if ((a)->i > (pos+len)) { \ + memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \ + (((a)->i)-(pos+len))*((a)->icd.sz)); \ + } \ + (a)->i -= (len); \ +} while(0) + +#define utarray_renew(a,u) do { \ + if (a) utarray_clear(a); \ + else utarray_new((a),(u)); \ +} while(0) + +#define utarray_clear(a) do { \ + if ((a)->i > 0) { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + (a)->i = 0; \ + } \ +} while(0) + +#define utarray_sort(a,cmp) do { \ + qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ +} while(0) + +#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) + +#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) +#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : ((((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) +#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) +#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) +#define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(size_t)(a)->icd.sz) : -1) + +/* last we pre-define a few icd for common utarrays of ints and strings */ +static void utarray_str_cpy(void *dst, const void *src) { + char **_src = (char**)src, **_dst = (char**)dst; + *_dst = (*_src == NULL) ? NULL : strdup(*_src); +} +static void utarray_str_dtor(void *elt) { + char **eltc = (char**)elt; + if (*eltc) free(*eltc); +} +static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; +static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL}; +static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL}; + + +#endif /* UTARRAY_H */ |