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     if (!size) { size = sizeof(a_cast); }
  77     ctx->ptr_ = A_NULL;
  78     ctx->siz_ = size;
  79     ctx->num_ = 0;
  80     ctx->mem_ = 0;
  81 }
  82
  83 void a_vec_dtor(a_vec *ctx, void (*dtor)(void *))
  84 {
  85     if (ctx->ptr_)
  86     {
  87         a_vec_drop_(ctx, 0, dtor);
  88         ctx->ptr_ = a_alloc(ctx->ptr_, 0);
  89     }
  90     ctx->siz_ = 0;
  91     ctx->mem_ = 0;
  92 }
  93
  94 int a_vec_copy(a_vec *ctx, a_vec const *obj, int (*dup)(void *, void const *))
  95 {
  96     ctx->ptr_ = a_alloc(A_NULL, obj->mem_ * obj->siz_);
  97     if (a_unlikely(!ctx->ptr_)) { return A_FAILURE; }
  98     ctx->num_ = obj->num_;
  99     ctx->mem_ = obj->mem_;
 100     ctx->siz_ = obj->siz_;
 101     if (dup)
 102     {
 103         a_byte *dst = (a_byte *)ctx->ptr_;
 104         a_byte *src = (a_byte *)obj->ptr_;
 105         for (a_size num = obj->num_; num; --num)
 106         {
 107             dup(dst, src);
 108             dst += ctx->siz_;
 109             src += ctx->siz_;
 110         }
 111     }
 112     else
 113     {
 114         a_copy(ctx->ptr_, obj->ptr_, obj->num_ * obj->siz_);
 115     }
 116     return A_SUCCESS;
 117 }
 118
 119 void a_vec_move(a_vec *ctx, a_vec *obj)
 120 {
 121     a_copy(ctx, obj, sizeof(*obj));
 122     a_zero(obj, sizeof(*obj));
 123 }
 124
 125 void a_vec_edit(a_vec *ctx, a_size size, void (*dtor)(void *))
 126 {
 127     if (!size) { size = sizeof(a_cast); }
 128     a_vec_drop_(ctx, 0, dtor);
 129     ctx->mem_ = ctx->mem_ * ctx->siz_ / size;
 130     ctx->siz_ = size;
 131 }
 132
 133 int a_vec_make(a_vec *ctx, a_size num, void (*dtor)(void *))
 134 {
 135     if (a_unlikely(a_vec_alloc(ctx, num))) { return A_FAILURE; }
 136     a_vec_drop_(ctx, num, dtor);
 137     return A_SUCCESS;
 138 }
 139
 140 void a_vec_drop(a_vec *ctx, void (*dtor)(void *))
 141 {
 142     a_vec_drop_(ctx, 0, dtor);
 143 }
 144
 145 void a_vec_swap(a_vec const *ctx, a_size lhs, a_size rhs)
 146 {
 147     a_size const num = ctx->num_ - 1;
 148     lhs = lhs < ctx->num_ ? lhs : num;
 149     rhs = rhs < ctx->num_ ? rhs : num;
 150     if (lhs != rhs)
 151     {
 152         a_swap((a_byte *)ctx->ptr_ + lhs * ctx->siz_,
 153                (a_byte *)ctx->ptr_ + rhs * ctx->siz_,
 154                ctx->siz_);
 155     }
 156 }
 157
 158 void a_vec_sort(a_vec const *ctx, int (*cmp)(void const *, void const *))
 159 {
 160     qsort(ctx->ptr_, ctx->num_, ctx->siz_, cmp);
 161 }
 162
 163 void a_vec_sort_fore(a_vec const *ctx, int (*cmp)(void const *, void const *))
 164 {
 165     if (ctx->num_ > 1)
 166     {
 167         a_byte *ptr = (a_byte *)ctx->ptr_;
 168         a_byte *const end = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_ - ctx->siz_;
 169         do {
 170             a_byte *const cur = ptr + ctx->siz_;
 171             if (cmp(ptr, cur) > 0)
 172             {
 173                 a_swap(cur, ptr, ctx->siz_);
 174             }
 175             else { break; }
 176             ptr = cur;
 177         } while (ptr != end);
 178     }
 179 }
 180
 181 void a_vec_sort_back(a_vec const *ctx, int (*cmp)(void const *, void const *))
 182 {
 183     if (ctx->num_ > 1)
 184     {
 185         a_byte *ptr = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_ - ctx->siz_;
 186         do {
 187             a_byte *const cur = ptr - ctx->siz_;
 188             if (cmp(cur, ptr) > 0)
 189             {
 190                 a_swap(cur, ptr, ctx->siz_);
 191             }
 192             else { break; }
 193             ptr = cur;
 194         } while (ptr != ctx->ptr_);
 195     }
 196 }
 197
 198 void *a_vec_search(a_vec const *ctx, void const *obj, int (*cmp)(void const *, void const *))
 199 {
 200     return bsearch(obj, ctx->ptr_, ctx->num_, ctx->siz_, cmp);
 201 }
 202
 203 void *a_vec_insert(a_vec *ctx, a_size idx)
 204 {
 205     if (a_unlikely(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 206     if (idx < ctx->num_)
 207     {
 208         a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 209         a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 210         a_move(dst, src, (ctx->num_ - idx) * ctx->siz_);
 211         ++ctx->num_;
 212         return src;
 213     }
 214     return a_vec_inc_(ctx);
 215 }
 216
 217 void *a_vec_push_fore(a_vec *ctx) { return a_vec_insert(ctx, 0); }
 218
 219 void *a_vec_push_back(a_vec *ctx)
 220 {
 221     if (a_unlikely(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 222     return a_vec_inc_(ctx);
 223 }
 224
 225 void *a_vec_remove(a_vec *ctx, a_size idx)
 226 {
 227     if (ctx->num_ && idx < ctx->num_ - 1)
 228     {
 229         if (a_unlikely(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 230         a_byte *const ptr = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
 231         a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 232         a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 233         a_copy(ptr, dst, ctx->siz_);
 234         a_move(dst, src, (a_size)(ptr - src));
 235         --ctx->num_;
 236         return ptr;
 237     }
 238     return a_likely(ctx->num_) ? a_vec_dec_(ctx) : A_NULL;
 239 }
 240
 241 void *a_vec_pull_fore(a_vec *ctx) { return a_vec_remove(ctx, 0); }
 242
 243 void *a_vec_pull_back(a_vec *ctx)
 244 {
 245     return a_likely(ctx->num_) ? a_vec_dec_(ctx) : A_NULL;
 246 }