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         a_size mem = ctx->mem_;
  28         do {
  29             mem += (mem >> 1) + 1;
  30         } while (mem < num);
  31         a_size const siz = a_size_up(sizeof(void *), ctx->siz_ * mem);
  32         void *ptr = a_alloc(ctx->ptr_, siz);
  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_byte *dst = (a_byte *)ctx->ptr_;
  86         a_byte *src = (a_byte *)obj->ptr_;
  87         for (a_size num = obj->num_; num; --num)
  88         {
  89             dup(dst, src);
  90             dst += ctx->siz_;
  91             src += ctx->siz_;
  92         }
  93     }
  94     else
  95     {
  96         a_copy(ctx->ptr_, obj->ptr_, obj->num_ * obj->siz_);
  97     }
  98     return A_SUCCESS;
  99 }
 100
 101 void a_vec_move(a_vec *ctx, a_vec *obj)
 102 {
 103     a_copy(ctx, obj, sizeof(*obj));
 104     a_zero(obj, sizeof(*obj));
 105 }
 106
 107 void a_vec_edit(a_vec *ctx, a_size size, void (*dtor)(void *))
 108 {
 109     if (!size) { size = sizeof(void *); }
 110     a_vec_drop_(ctx, 0, dtor);
 111     ctx->mem_ = ctx->mem_ * ctx->siz_ / size;
 112     ctx->siz_ = size;
 113 }
 114
 115 int a_vec_make(a_vec *ctx, a_size num, void (*dtor)(void *))
 116 {
 117     if (A_UNLIKELY(a_vec_alloc(ctx, num))) { return A_FAILURE; }
 118     a_vec_drop_(ctx, num, dtor);
 119     return A_SUCCESS;
 120 }
 121
 122 void a_vec_drop(a_vec *ctx, void (*dtor)(void *))
 123 {
 124     a_vec_drop_(ctx, 0, dtor);
 125 }
 126
 127 void a_vec_swap(a_vec const *ctx, a_size lhs, a_size rhs)
 128 {
 129     a_size const num = ctx->num_ - 1;
 130     lhs = lhs < ctx->num_ ? lhs : num;
 131     rhs = rhs < ctx->num_ ? rhs : num;
 132     if (lhs != rhs)
 133     {
 134         a_swap((a_byte *)ctx->ptr_ + lhs * ctx->siz_,
 135                (a_byte *)ctx->ptr_ + rhs * ctx->siz_,
 136                ctx->siz_);
 137     }
 138 }
 139
 140 void a_vec_sort(a_vec const *ctx, int (*cmp)(void const *, void const *))
 141 {
 142     qsort(ctx->ptr_, ctx->num_, ctx->siz_, cmp);
 143 }
 144
 145 void a_vec_sort_fore(a_vec const *ctx, int (*cmp)(void const *, void const *))
 146 {
 147     if (ctx->num_ > 1)
 148     {
 149         a_byte *const end = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
 150         a_byte *const top = end - ctx->siz_;
 151         a_byte *ptr = (a_byte *)ctx->ptr_;
 152         if (ctx->num_ < ctx->mem_)
 153         {
 154             a_byte *const pos = ptr;
 155             do {
 156                 a_byte *const cur = ptr + ctx->siz_;
 157                 if (cmp(pos, cur) <= 0) { break; }
 158                 ptr = cur;
 159             } while (ptr != top);
 160             if (ptr > pos)
 161             {
 162                 a_copy(end, pos, ctx->siz_);
 163                 a_move(pos, pos + ctx->siz_, (a_size)(ptr - pos));
 164                 a_copy(ptr, end, ctx->siz_);
 165             }
 166         }
 167         else
 168         {
 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 != top);
 178         }
 179     }
 180 }
 181
 182 void a_vec_sort_back(a_vec const *ctx, int (*cmp)(void const *, void const *))
 183 {
 184     if (ctx->num_ > 1)
 185     {
 186         a_byte *const end = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
 187         a_byte *ptr = end - ctx->siz_;
 188         if (ctx->num_ < ctx->mem_)
 189         {
 190             a_byte *const pos = ptr;
 191             do {
 192                 a_byte *const cur = ptr - ctx->siz_;
 193                 if (cmp(cur, pos) <= 0) { break; }
 194                 ptr = cur;
 195             } while (ptr != ctx->ptr_);
 196             if (ptr < pos)
 197             {
 198                 a_copy(end, pos, ctx->siz_);
 199                 a_move(ptr + ctx->siz_, ptr, (a_size)(pos - ptr));
 200                 a_copy(ptr, end, ctx->siz_);
 201             }
 202         }
 203         else
 204         {
 205             do {
 206                 a_byte *const cur = ptr - ctx->siz_;
 207                 if (cmp(cur, ptr) > 0)
 208                 {
 209                     a_swap(cur, ptr, ctx->siz_);
 210                 }
 211                 else { break; }
 212                 ptr = cur;
 213             } while (ptr != ctx->ptr_);
 214         }
 215     }
 216 }
 217
 218 void *a_vec_push_sort(a_vec *ctx, void const *key, int (*cmp)(void const *, void const *))
 219 {
 220     if (a_vec_alloc(ctx, ctx->num_) == A_SUCCESS)
 221     {
 222         a_byte *ptr = (a_byte *)a_vec_inc_(ctx);
 223         if (ctx->num_ > 1)
 224         {
 225             a_byte *const pos = ptr;
 226             do {
 227                 a_byte *const cur = ptr - ctx->siz_;
 228                 if (cmp(cur, key) <= 0) { break; }
 229                 ptr = cur;
 230             } while (ptr != ctx->ptr_);
 231             if (ptr < pos)
 232             {
 233                 a_move(ptr + ctx->siz_, ptr, (a_size)(pos - ptr));
 234             }
 235         }
 236         return ptr;
 237     }
 238     return A_NULL;
 239 }
 240
 241 void *a_vec_search(a_vec const *ctx, void const *obj, int (*cmp)(void const *, void const *))
 242 {
 243     return bsearch(obj, ctx->ptr_, ctx->num_, ctx->siz_, cmp);
 244 }
 245
 246 void *a_vec_insert(a_vec *ctx, a_size idx)
 247 {
 248     if (A_UNLIKELY(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 249     if (idx < ctx->num_)
 250     {
 251         a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 252         a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 253         a_move(dst, src, (ctx->num_ - idx) * ctx->siz_);
 254         ++ctx->num_;
 255         return src;
 256     }
 257     return a_vec_inc_(ctx);
 258 }
 259
 260 void *a_vec_push_fore(a_vec *ctx) { return a_vec_insert(ctx, 0); }
 261
 262 void *a_vec_push_back(a_vec *ctx)
 263 {
 264     if (A_UNLIKELY(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 265     return a_vec_inc_(ctx);
 266 }
 267
 268 void *a_vec_remove(a_vec *ctx, a_size idx)
 269 {
 270     if (ctx->num_ && idx < ctx->num_ - 1)
 271     {
 272         if (A_UNLIKELY(a_vec_alloc(ctx, ctx->num_))) { return A_NULL; }
 273         a_byte *const ptr = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
 274         a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 275         a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 276         a_copy(ptr, dst, ctx->siz_);
 277         a_move(dst, src, (a_size)(ptr - src));
 278         --ctx->num_;
 279         return ptr;
 280     }
 281     return ctx->num_ ? a_vec_dec_(ctx) : A_NULL;
 282 }
 283
 284 void *a_vec_pull_fore(a_vec *ctx) { return a_vec_remove(ctx, 0); }
 285
 286 void *a_vec_pull_back(a_vec *ctx)
 287 {
 288     return ctx->num_ ? a_vec_dec_(ctx) : A_NULL;
 289 }