tglist.h

   1 #ifndef TGLIST_H
   2 #define TGLIST_H
   3
   4 #ifdef __cplusplus
   5 extern "C" {
   6 #endif
   7
   8 #include <stddef.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 #ifdef __GNUC__
  13 #pragma GCC diagnostic ignored "-Wunused-value"
  14 #endif
  15
  16 /*
  17  * type generic list (dynamic array).
  18  *
  19  * unlike sblist, doesn't do any bounds check.
  20  * so you can e.g. only delete positions that are valid,
  21  * without causing memory corruption.
  22  *
  23  * this implementation is header-only, so it is easy
  24  * to embed elsewhere, however there's some overhead
  25  * if it's used in different TUs.
  26  * however the code is pretty slim, the static funcs
  27  * compile to about 400 byte total on x86_64.
  28  *
  29  * right now, this is in the testing stage.
  30  * functions/macros ending in _impl are not supposed
  31  * to be used by the user.
  32  *
  33  * the advantage of using a typed container is
  34  * A) the declaration of the type already documents the use
  35  *    (like e.g. List<int> in java)
  36  * B) no casts required when accessing the elements.
  37  * C) added type safety
  38  *
  39  * use like tglist(somename_or_id, int) *l = tglist_new();
  40  * the name or id can be anything that produces a valid token
  41  * when concatenated to "tglist_". it simply serves to give
  42  * the struct declaration a unique name.
  43  *
  44  * the code was designed such that the type/id is only required
  45  * for the declaration of the struct, not for every function call.
  46  * therefore unfortunately the static funcs have to resort to
  47  * use void* at times.
  48  */
  49
  50 #define tglist_impl(NAME, TYPE) \
  51         struct NAME { \
  52                 size_t count; \
  53                 size_t capa; \
  54                 TYPE* items; \
  55                 union { \
  56                         TYPE* vt; \
  57                         size_t s; \
  58                 } tmp; \
  59         }
  60
  61 #define tglist(TYPE) tglist_impl(, TYPE)
  62 /* use tglist_decl if you need a named struct, e.g. to put in a header */
  63 #define tglist_decl(ID, TYPE) tglist_impl(tglist_ ## ID, TYPE)
  64 #define tglist_proto tglist_impl(, void*)
  65
  66 #define tglist_getsize(X) ((X)->count)
  67 #define tglist_get_count(X) ((X)->count)
  68 #define tglist_empty(X) ((X)->count == 0)
  69
  70 /* --- for dynamic style --- */
  71 // allocate and initialize a new tglist
  72 #define tglist_new() calloc(1, sizeof(tglist_proto))
  73
  74 // free dynamically allocated list and its internal buffers
  75 #define tglist_free(X) do {free((X)->items); free(X);} while(0)
  76
  77 /* --- for static style --- */
  78 // initialize existing list in user-allocated storage (e.g. stack-allocated)
  79 #define tglist_init(X) memset(X, 0, sizeof(*(X)))
  80
  81 // free internal buffers of the list
  82 #define tglist_free_items(X) free((X)->items)
  83
  84 /* in case your list contains pointers to heap-allocated mem,
  85    not values, this will iterate over all list entries and
  86    free them */
  87 /* the casts here serve to suppress warnings when the macro
  88    is expanded on a non-pointer list, (but using it would be
  89    bogus anyway) */
  90 #define tglist_free_values(X) \
  91         if(tglist_itemsize(X) == sizeof(void*)) while((X)->count > 0) \
  92         {free(*(void**)(((char*)(X)->items)+ ( (--((X)->count)) *tglist_itemsize(X) ) ) \
  93         );}else{}
  94
  95 // accessors
  96 #define tglist_get(L, POS) ((L)->items[POS])
  97
  98 #define tglist_set(X, ITEM, POS) \
  99         ((X)->items[POS] = ITEM, 1)
 100
 101 #define tglist_itemsize(X) sizeof( (X)->items[0] )
 102
 103 #define tglist_foreach(X, ITER) for(ITER=0;ITER<tglist_getsize(X);++ITER)
 104
 105 // returns 1 on success, 0 on OOM
 106 #define tglist_prepare_addition(X) ( \
 107                 tglist_grow_if_needed( X, tglist_itemsize(X) ) ? \
 108                 !!(++(X)->count) : 0 \
 109         )
 110
 111 #define tglist_add(X, ITEM) ( \
 112         tglist_prepare_addition(X) ? \
 113         tglist_set(X, ITEM, (X)->count-1) : \
 114         0 )
 115
 116 #define tglist_ptr_from_index_impl(L, POS, ITEMSZ) \
 117         ( (char*) ((L)->items) + (POS * ITEMSZ) )
 118
 119 /* void */
 120 #define tglist_delete(X, POS) \
 121         tglist_memmove_impl(X, POS, +1, tglist_itemsize(X)) &&  \
 122         ( --((X)->count) , 1 )
 123
 124 /* int : 0=err, 1=success. */
 125 #define tglist_insert(X, ITEM, POS) ( \
 126         (((X)->tmp.s = (POS)), 1) && \
 127         tglist_grow_if_needed( X, tglist_itemsize(X) ) ? \
 128         tglist_memmove_impl(X, ((X)->tmp.s)+1, -1, tglist_itemsize(X)) && \
 129                 ++((X)->count) && \
 130                 tglist_set(X, ITEM, (X)->tmp.s) \
 131         : 0 )
 132
 133 /* internal */
 134 #define tglist_insert_memcpy(X, ITEMPTR, POS, ITEMSIZE) ( \
 135         tglist_grow_if_needed( X, ITEMSIZE ) ? \
 136         tglist_memmove_impl(X, (POS)+1, -1, ITEMSIZE) && \
 137                 ++((X)->count) && \
 138                 memcpy(tglist_ptr_from_index_impl(X, POS, ITEMSIZE), ITEMPTR, ITEMSIZE) \
 139         : 0 )
 140
 141 /* the compare func for all sort-related stuff is qsort-style.
 142    note that if the list contains pointers, the compare func will get
 143    pointers to pointers. so to use e.g. strcmp, you need a wrapper to
 144    deref the const char** pointers before passing them to strcmp. */
 145
 146 #define tglist_sort(X, COMPAREFUNC) \
 147         qsort((X)->items, (X)->count, tglist_itemsize(X), COMPAREFUNC)
 148
 149 /* insert element into presorted list, returns listindex of new entry or -1
 150 */
 151 #define tglist_insert_sorted(X, ITEM, COMPAREFUNC) (\
 152         ((X)->tmp.vt = (void*)&(ITEM)), \
 153         tglist_insert_sorted_impl(X, (X)->tmp.vt, tglist_itemsize(X), COMPAREFUNC))
 154
 155 #ifndef MAX
 156 #define MAX(x, y) ((x) > (y) ? (x) : (y))
 157 #endif
 158
 159 static int tglist_grow_if_needed(void* lst, size_t itemsize) {
 160         tglist_proto *l = lst;
 161         void* temp;
 162         if(l->count == l->capa) {
 163                 size_t newsz = l->capa == 0 ? 4 : l->capa*2;
 164                 temp = realloc(l->items, newsz * itemsize);
 165                 if(!temp) return 0;
 166                 l->capa = newsz;
 167                 l->items = temp;
 168         }
 169         return 1;
 170 }
 171
 172 static int tglist_memmove_impl(void *lst, size_t pos1, int pos2diff, size_t itemsz) {
 173         tglist_proto *l = lst;
 174         char* dst = tglist_ptr_from_index_impl(l, pos1, itemsz);
 175         const char* src = dst + (itemsz*pos2diff);
 176         return !!memmove(dst, src, (tglist_getsize(l) - (pos1 + pos2diff))*itemsz);
 177 }
 178
 179 static size_t tglist_sorted_insert_pos_impl(void* lst, void* o, size_t itemsz, int (*compar)(const void *, const void *)) {
 180         tglist_proto *l = lst;
 181         size_t hi, lo;
 182         lo = tglist_getsize(l);
 183         if(!lo) return 0;
 184         lo--;
 185         hi = 0;
 186         while(1) {
 187                 size_t c = hi + ((lo - hi) / 2);
 188                 void *p = tglist_ptr_from_index_impl(l, c, itemsz);
 189                 int r = compar(o, p);
 190                 if(hi == lo) {
 191                         if(r > 0) lo++;
 192                         return lo;
 193                 }
 194                 if(r < 0) lo = c ? c-1 : 0;
 195                 else if(r > 0) hi = c+1;
 196                 else hi = lo = c;
 197                 if(hi > lo) hi = lo;
 198         }
 199 }
 200
 201 static size_t tglist_insert_sorted_impl(void *lst, void *ptr_to_item, size_t itemsz, int (*compar)(const void *, const void *)) {
 202         size_t idx = tglist_sorted_insert_pos_impl(lst, ptr_to_item, itemsz, compar);
 203         if(idx == (size_t) -1) return idx;
 204         if(tglist_insert_memcpy((tglist_proto*) lst, ptr_to_item, idx, itemsz)) return idx;
 205         return (size_t) -1;
 206 }
 207
 208 #ifdef __cplusplus
 209 }
 210 #endif
 211
 212 #endif