external/bsd/elftoolchain/dist/common/utarray.h

   1 /*      $NetBSD: utarray.h,v 1.2 2014/03/09 16:58:03 christos Exp $     */
   2
   3 /*
   4 Copyright (c) 2008-2013, Troy D. Hanson   http://uthash.sourceforge.net
   5 All rights reserved.
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, 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
  13 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  14 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  15 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  16 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
  17 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  21 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  22 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  23 SOFTWARE, 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
  50 typedef void (ctor_f)(void *dst, const void *src);
  51 typedef void (dtor_f)(void *elt);
  52 typedef void (init_f)(void *elt);
  53 typedef struct {
  54     size_t sz;
  55     init_f *init;
  56     ctor_f *copy;
  57     dtor_f *dtor;
  58 } UT_icd;
  59
  60 typedef 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 */
 226 static 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 }
 230 static void utarray_str_dtor(void *elt) {
 231   char **eltc = (char**)elt;
 232   if (*eltc) free(*eltc);
 233 }
 234 static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
 235 static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL};
 236 static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL};
 237
 238
 239 #endif /* UTARRAY_H */