src/vec.c

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