utarray.h revision 1.2.8.2
1/* $NetBSD: utarray.h,v 1.2.8.2 2014/08/19 23:46:44 tls Exp $ */ 2 3/* 4Copyright (c) 2008-2013, Troy D. Hanson http://uthash.sourceforge.net 5All rights reserved. 6 7Redistribution and use in source and binary forms, with or without 8modification, are permitted provided that the following conditions are met: 9 10 * Redistributions of source code must retain the above copyright 11 notice, this list of conditions and the following disclaimer. 12 13THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 14IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 15TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 16PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 17OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 21LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 22NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 23SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24*/ 25 26/* Id: utarray.h 2694 2012-11-24 17:11:58Z kaiwang27 */ 27 28/* a dynamic array implementation using macros 29 * see http://uthash.sourceforge.net/utarray 30 */ 31#ifndef UTARRAY_H 32#define UTARRAY_H 33 34#define UTARRAY_VERSION 1.9.7 35 36#ifdef __GNUC__ 37#define _UNUSED_ __attribute__ ((__unused__)) 38#else 39#define _UNUSED_ 40#endif 41 42#include <stddef.h> /* size_t */ 43#include <string.h> /* memset, etc */ 44#include <stdlib.h> /* exit */ 45 46#ifndef oom 47#define oom() exit(-1) 48#endif 49 50typedef void (ctor_f)(void *dst, const void *src); 51typedef void (dtor_f)(void *elt); 52typedef void (init_f)(void *elt); 53typedef struct { 54 size_t sz; 55 init_f *init; 56 ctor_f *copy; 57 dtor_f *dtor; 58} UT_icd; 59 60typedef struct { 61 unsigned i,n;/* i: index of next available slot, n: num slots */ 62 UT_icd icd; /* initializer, copy and destructor functions */ 63 char *d; /* n slots of size icd->sz*/ 64} UT_array; 65 66#define utarray_init(a,_icd) do { \ 67 memset(a,0,sizeof(UT_array)); \ 68 (a)->icd=*_icd; \ 69} while(0) 70 71#define utarray_done(a) do { \ 72 if ((a)->n) { \ 73 if ((a)->icd.dtor) { \ 74 size_t _ut_i; \ 75 for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ 76 (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ 77 } \ 78 } \ 79 free((a)->d); \ 80 } \ 81 (a)->n=0; \ 82} while(0) 83 84#define utarray_new(a,_icd) do { \ 85 a=(UT_array*)malloc(sizeof(UT_array)); \ 86 utarray_init(a,_icd); \ 87} while(0) 88 89#define utarray_free(a) do { \ 90 utarray_done(a); \ 91 free(a); \ 92} while(0) 93 94#define utarray_reserve(a,by) do { \ 95 if (((a)->i+by) > ((a)->n)) { \ 96 while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ 97 if ( ((a)->d=(char*)realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) oom(); \ 98 } \ 99} while(0) 100 101#define utarray_push_back(a,p) do { \ 102 utarray_reserve(a,1); \ 103 if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ 104 else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ 105} while(0) 106 107#define utarray_pop_back(a) do { \ 108 if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ 109 else { (a)->i--; } \ 110} while(0) 111 112#define utarray_extend_back(a) do { \ 113 utarray_reserve(a,1); \ 114 if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ 115 else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ 116 (a)->i++; \ 117} while(0) 118 119#define utarray_len(a) ((a)->i) 120 121#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) 122#define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) ))) 123 124#define utarray_insert(a,p,j) do { \ 125 utarray_reserve(a,1); \ 126 if (j > (a)->i) break; \ 127 if ((j) < (a)->i) { \ 128 memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ 129 ((a)->i - (j))*((a)->icd.sz)); \ 130 } \ 131 if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ 132 else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ 133 (a)->i++; \ 134} while(0) 135 136#define utarray_inserta(a,w,j) do { \ 137 if (utarray_len(w) == 0) break; \ 138 if (j > (a)->i) break; \ 139 utarray_reserve(a,utarray_len(w)); \ 140 if ((j) < (a)->i) { \ 141 memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ 142 _utarray_eltptr(a,j), \ 143 ((a)->i - (j))*((a)->icd.sz)); \ 144 } \ 145 if ((a)->icd.copy) { \ 146 size_t _ut_i; \ 147 for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ 148 (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \ 149 } \ 150 } else { \ 151 memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ 152 utarray_len(w)*((a)->icd.sz)); \ 153 } \ 154 (a)->i += utarray_len(w); \ 155} while(0) 156 157#define utarray_resize(dst,num) do { \ 158 size_t _ut_i; \ 159 if (dst->i > (size_t)(num)) { \ 160 if ((dst)->icd.dtor) { \ 161 for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \ 162 (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \ 163 } \ 164 } \ 165 } else if (dst->i < (size_t)(num)) { \ 166 utarray_reserve(dst,num-dst->i); \ 167 if ((dst)->icd.init) { \ 168 for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \ 169 (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \ 170 } \ 171 } else { \ 172 memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \ 173 } \ 174 } \ 175 dst->i = num; \ 176} while(0) 177 178#define utarray_concat(dst,src) do { \ 179 utarray_inserta((dst),(src),utarray_len(dst)); \ 180} while(0) 181 182#define utarray_erase(a,pos,len) do { \ 183 if ((a)->icd.dtor) { \ 184 size_t _ut_i; \ 185 for(_ut_i=0; _ut_i < len; _ut_i++) { \ 186 (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \ 187 } \ 188 } \ 189 if ((a)->i > (pos+len)) { \ 190 memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \ 191 (((a)->i)-(pos+len))*((a)->icd.sz)); \ 192 } \ 193 (a)->i -= (len); \ 194} while(0) 195 196#define utarray_renew(a,u) do { \ 197 if (a) utarray_clear(a); \ 198 else utarray_new((a),(u)); \ 199} while(0) 200 201#define utarray_clear(a) do { \ 202 if ((a)->i > 0) { \ 203 if ((a)->icd.dtor) { \ 204 size_t _ut_i; \ 205 for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ 206 (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ 207 } \ 208 } \ 209 (a)->i = 0; \ 210 } \ 211} while(0) 212 213#define utarray_sort(a,cmp) do { \ 214 qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ 215} while(0) 216 217#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) 218 219#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) 220#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((int)((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) 221#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) 222#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) 223#define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (int)(((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1) 224 225/* last we pre-define a few icd for common utarrays of ints and strings */ 226static void utarray_str_cpy(void *dst, const void *src) { 227 char *const*_src = (char*const*)src, **_dst = (char**)dst; 228 *_dst = (*_src == NULL) ? NULL : strdup(*_src); 229} 230static void utarray_str_dtor(void *elt) { 231 char **eltc = (char**)elt; 232 if (*eltc) free(*eltc); 233} 234static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; 235static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL}; 236static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL}; 237 238 239#endif /* UTARRAY_H */ 240