src/vec.c

   1 #include "a/vec.h"
   2 #include <stdlib.h>
   3
   4 #undef a_vec_at
   5 #undef a_vec_at_
   6 #undef a_vec_idx
   7 #undef a_vec_ptr
   8 #undef a_vec_end
   9 #undef a_vec_top
  10 #undef a_vec_end_
  11 #undef a_vec_top_
  12 #undef a_vec_push
  13 #undef a_vec_pull
  14 #undef a_vec_search
  15 #undef a_vec_insert
  16 #undef a_vec_remove
  17 #undef a_vec_push_fore
  18 #undef a_vec_push_back
  19 #undef a_vec_pull_fore
  20 #undef a_vec_pull_back
  21
  22 static A_INLINE void *a_vec_inc_(a_vec *ctx)
  23 {
  24     return (a_byte *)ctx->_ptr + ctx->_siz * ctx->_num++;
  25 }
  26
  27 static A_INLINE void *a_vec_dec_(a_vec *ctx)
  28 {
  29     return (a_byte *)ctx->_ptr + ctx->_siz * --ctx->_num;
  30 }
  31
  32 static void a_vec_drop_(a_vec *ctx, a_size bot, void (*dtor)(void *))
  33 {
  34     if (dtor)
  35     {
  36         while (ctx->_num > bot) { dtor(a_vec_dec_(ctx)); }
  37     }
  38     ctx->_num = bot;
  39 }
  40
  41 static int a_vec_alloc(a_vec *ctx, a_size num)
  42 {
  43     if (ctx->_mem <= num)
  44     {
  45         a_size mem = ctx->_mem;
  46         do {
  47             mem += (mem >> 1) + 1;
  48         } while (mem < num);
  49         a_size const siz = a_size_up(sizeof(void *), ctx->_siz * mem);
  50         void *ptr = a_alloc(ctx->_ptr, siz);
  51         if (a_unlikely(!ptr)) { return A_FAILURE; }
  52         ctx->_ptr = ptr;
  53         ctx->_mem = mem;
  54     }
  55     return A_SUCCESS;
  56 }
  57
  58 a_vec *a_vec_new(a_size size)
  59 {
  60     a_vec *const ctx = (a_vec *)a_alloc(A_NULL, sizeof(a_vec));
  61     if (ctx) { a_vec_ctor(ctx, size); }
  62     return ctx;
  63 }
  64
  65 void a_vec_die(a_vec *ctx, void (*dtor)(void *))
  66 {
  67     if (ctx)
  68     {
  69         a_vec_dtor(ctx, dtor);
  70         a_alloc(ctx, 0);
  71     }
  72 }
  73
  74 void a_vec_ctor(a_vec *ctx, a_size size)
  75 {
  76     ctx->_siz = size ? size : sizeof(a_cast);
  77     ctx->_ptr = A_NULL;
  78     ctx->_num = 0;
  79     ctx->_mem = 0;
  80 }
  81
  82 void a_vec_dtor(a_vec *ctx, void (*dtor)(void *))
  83 {
  84     if (ctx->_ptr)
  85     {
  86         a_vec_drop_(ctx, 0, dtor);
  87         ctx->_ptr = a_alloc(ctx->_ptr, 0);
  88     }
  89     ctx->_mem = 0;
  90     ctx->_siz = 0;
  91 }
  92
  93 int a_vec_copy(a_vec *ctx, a_vec const *obj, int (*dup)(void *, void const *))
  94 {
  95     ctx->_ptr = a_alloc(A_NULL, obj->_mem * obj->_siz);
  96     if (a_unlikely(!ctx->_ptr)) { return A_FAILURE; }
  97     ctx->_num = obj->_num;
  98     ctx->_mem = obj->_mem;
  99     ctx->_siz = obj->_siz;
 100     if (dup)
 101     {
 102         a_byte *dst = (a_byte *)ctx->_ptr;
 103         a_byte *src = (a_byte *)obj->_ptr;
 104         for (a_size num = obj->_num; num; --num)
 105         {
 106             dup(dst, src);
 107             dst += ctx->_siz;
 108             src += ctx->_siz;
 109         }
 110     }
 111     else
 112     {
 113         a_copy(ctx->_ptr, obj->_ptr, obj->_num * obj->_siz);
 114     }
 115     return A_SUCCESS;
 116 }
 117
 118 void a_vec_move(a_vec *ctx, a_vec *obj)
 119 {
 120     a_copy(ctx, obj, sizeof(*obj));
 121     a_zero(obj, sizeof(*obj));
 122 }
 123
 124 void a_vec_edit(a_vec *ctx, a_size size, void (*dtor)(void *))
 125 {
 126     size = size ? size : sizeof(a_cast);
 127     a_vec_drop_(ctx, 0, dtor);
 128     ctx->_mem = ctx->_mem * ctx->_siz / size;
 129     ctx->_siz = size;
 130 }
 131
 132 int a_vec_make(a_vec *ctx, a_size num, void (*dtor)(void *))
 133 {
 134     if (a_unlikely(a_vec_alloc(ctx, num))) { return A_FAILURE; }
 135     a_vec_drop_(ctx, num, dtor);
 136     return A_SUCCESS;
 137 }
 138
 139 void a_vec_drop(a_vec *ctx, void (*dtor)(void *))
 140 {
 141     a_vec_drop_(ctx, 0, dtor);
 142 }
 143
 144 void a_vec_swap(a_vec const *ctx, a_size lhs, a_size rhs)
 145 {
 146     a_size const num = ctx->_num - 1;
 147     lhs = lhs < ctx->_num ? lhs : num;
 148     rhs = rhs < ctx->_num ? rhs : num;
 149     if (lhs != rhs)
 150     {
 151         a_swap((a_byte *)ctx->_ptr + lhs * ctx->_siz,
 152                (a_byte *)ctx->_ptr + rhs * ctx->_siz,
 153                ctx->_siz);
 154     }
 155 }
 156
 157 void a_vec_sort(a_vec const *ctx, int (*cmp)(void const *, void const *))
 158 {
 159     qsort(ctx->_ptr, ctx->_num, ctx->_siz, cmp);
 160 }
 161
 162 void a_vec_sort_fore(a_vec const *ctx, int (*cmp)(void const *, void const *))
 163 {
 164     if (ctx->_num > 1)
 165     {
 166         a_byte *ptr = (a_byte *)ctx->_ptr;
 167         a_byte *const end = (a_byte *)ctx->_ptr + ctx->_siz * ctx->_num - ctx->_siz;
 168         do {
 169             a_byte *const cur = ptr + ctx->_siz;
 170             if (cmp(ptr, cur) > 0)
 171             {
 172                 a_swap(cur, ptr, ctx->_siz);
 173             }
 174             else { break; }
 175             ptr = cur;
 176         } while (ptr != end);
 177     }
 178 }
 179
 180 void a_vec_sort_back(a_vec const *ctx, int (*cmp)(void const *, void const *))
 181 {
 182     if (ctx->_num > 1)
 183     {
 184         a_byte *ptr = (a_byte *)ctx->_ptr + ctx->_siz * ctx->_num - ctx->_siz;
 185         do {
 186             a_byte *const cur = ptr - ctx->_siz;
 187             if (cmp(cur, ptr) > 0)
 188             {
 189                 a_swap(cur, ptr, ctx->_siz);
 190             }
 191             else { break; }
 192             ptr = cur;
 193         } while (ptr != ctx->_ptr);
 194     }
 195 }
 196
 197 void *a_vec_search(a_vec const *ctx, void const *obj, int (*cmp)(void const *, void const *))
 198 {
 199     return bsearch(obj, ctx->_ptr, ctx->_num, ctx->_siz, cmp);
 200 }
 201
 202 void *a_vec_insert(a_vec *ctx, a_size idx)
 203 {
 204     if (a_unlikely(a_vec_alloc(ctx, ctx->_num))) { return A_NULL; }
 205     if (idx < ctx->_num)
 206     {
 207         a_byte *const src = (a_byte *)ctx->_ptr + ctx->_siz * (idx + 0);
 208         a_byte *const dst = (a_byte *)ctx->_ptr + ctx->_siz * (idx + 1);
 209         a_move(dst, src, (ctx->_num - idx) * ctx->_siz);
 210         ++ctx->_num;
 211         return src;
 212     }
 213     return a_vec_inc_(ctx);
 214 }
 215
 216 void *a_vec_push_fore(a_vec *ctx) { return a_vec_insert(ctx, 0); }
 217
 218 void *a_vec_push_back(a_vec *ctx)
 219 {
 220     if (a_unlikely(a_vec_alloc(ctx, ctx->_num))) { return A_NULL; }
 221     return a_vec_inc_(ctx);
 222 }
 223
 224 void *a_vec_remove(a_vec *ctx, a_size idx)
 225 {
 226     if (ctx->_num && idx < ctx->_num - 1)
 227     {
 228         if (a_unlikely(a_vec_alloc(ctx, ctx->_num))) { return A_NULL; }
 229         a_byte *const ptr = (a_byte *)ctx->_ptr + ctx->_siz * ctx->_num;
 230         a_byte *const dst = (a_byte *)ctx->_ptr + ctx->_siz * (idx + 0);
 231         a_byte *const src = (a_byte *)ctx->_ptr + ctx->_siz * (idx + 1);
 232         a_copy(ptr, dst, ctx->_siz);
 233         a_move(dst, src, (a_size)(ptr - src));
 234         --ctx->_num;
 235         return ptr;
 236     }
 237     return a_likely(ctx->_num) ? a_vec_dec_(ctx) : A_NULL;
 238 }
 239
 240 void *a_vec_pull_fore(a_vec *ctx) { return a_vec_remove(ctx, 0); }
 241
 242 void *a_vec_pull_back(a_vec *ctx)
 243 {
 244     return a_likely(ctx->_num) ? a_vec_dec_(ctx) : A_NULL;
 245 }