src/buf.c

   1 #include "a/buf.h"
   2 #include <stdlib.h>
   3
   4 static A_INLINE void *a_buf_inc_(a_buf *ctx)
   5 {
   6     return (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_++;
   7 }
   8
   9 static A_INLINE void *a_buf_dec_(a_buf *ctx)
  10 {
  11     return (a_byte *)ctx->ptr_ + ctx->siz_ * --ctx->num_;
  12 }
  13
  14 static void a_buf_drop_(a_buf *ctx, a_size bot, void (*dtor)(void *))
  15 {
  16     if (dtor)
  17     {
  18         while (ctx->num_ > bot) { dtor(a_buf_dec_(ctx)); }
  19     }
  20     ctx->num_ = bot;
  21 }
  22
  23 void a_buf_ctor(a_buf *ctx, void *ptr, a_size siz, a_size num)
  24 {
  25     ctx->ptr_ = ptr;
  26     ctx->siz_ = siz;
  27     ctx->mem_ = num;
  28     ctx->num_ = 0;
  29 }
  30
  31 void a_buf_dtor(a_buf *ctx, void (*dtor)(void *))
  32 {
  33     if (ctx->ptr_)
  34     {
  35         a_buf_drop_(ctx, 0, dtor);
  36         ctx->ptr_ = A_NULL;
  37     }
  38     ctx->siz_ = 0;
  39     ctx->mem_ = 0;
  40 }
  41
  42 void a_buf_move(a_buf *ctx, a_buf *obj)
  43 {
  44     a_copy(ctx, obj, sizeof(*obj));
  45     a_zero(obj, sizeof(*obj));
  46 }
  47
  48 void a_buf_drop(a_buf *ctx, void (*dtor)(void *))
  49 {
  50     a_buf_drop_(ctx, 0, dtor);
  51 }
  52
  53 void a_buf_swap(a_buf const *ctx, a_size lhs, a_size rhs)
  54 {
  55     a_size const num = ctx->num_ - 1;
  56     lhs = lhs < ctx->num_ ? lhs : num;
  57     rhs = rhs < ctx->num_ ? rhs : num;
  58     if (lhs != rhs)
  59     {
  60         a_swap((a_byte *)ctx->ptr_ + lhs * ctx->siz_,
  61                (a_byte *)ctx->ptr_ + rhs * ctx->siz_,
  62                ctx->siz_);
  63     }
  64 }
  65
  66 void a_buf_sort(a_buf const *ctx, int (*cmp)(void const *, void const *))
  67 {
  68     qsort(ctx->ptr_, ctx->num_, ctx->siz_, cmp);
  69 }
  70
  71 void a_buf_sort_fore(a_buf const *ctx, int (*cmp)(void const *, void const *))
  72 {
  73     if (ctx->num_ > 1)
  74     {
  75         a_byte *const end = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
  76         a_byte *const top = end - ctx->siz_;
  77         a_byte *ptr = (a_byte *)ctx->ptr_;
  78         if (ctx->num_ < ctx->mem_)
  79         {
  80             a_byte *const pos = ptr;
  81             do {
  82                 a_byte *const cur = ptr + ctx->siz_;
  83                 if (cmp(pos, cur) <= 0) { break; }
  84                 ptr = cur;
  85             } while (ptr != top);
  86             if (ptr > pos)
  87             {
  88                 a_copy(end, pos, ctx->siz_);
  89                 a_move(pos, pos + ctx->siz_, (a_size)(ptr - pos));
  90                 a_copy(ptr, end, ctx->siz_);
  91             }
  92         }
  93         else
  94         {
  95             do {
  96                 a_byte *const cur = ptr + ctx->siz_;
  97                 if (cmp(ptr, cur) > 0)
  98                 {
  99                     a_swap(cur, ptr, ctx->siz_);
 100                 }
 101                 else { break; }
 102                 ptr = cur;
 103             } while (ptr != top);
 104         }
 105     }
 106 }
 107
 108 void a_buf_sort_back(a_buf const *ctx, int (*cmp)(void const *, void const *))
 109 {
 110     if (ctx->num_ > 1)
 111     {
 112         a_byte *const end = (a_byte *)ctx->ptr_ + ctx->siz_ * ctx->num_;
 113         a_byte *ptr = end - ctx->siz_;
 114         if (ctx->num_ < ctx->mem_)
 115         {
 116             a_byte *const pos = ptr;
 117             do {
 118                 a_byte *const cur = ptr - ctx->siz_;
 119                 if (cmp(cur, pos) <= 0) { break; }
 120                 ptr = cur;
 121             } while (ptr != ctx->ptr_);
 122             if (ptr < pos)
 123             {
 124                 a_copy(end, pos, ctx->siz_);
 125                 a_move(ptr + ctx->siz_, ptr, (a_size)(pos - ptr));
 126                 a_copy(ptr, end, ctx->siz_);
 127             }
 128         }
 129         else
 130         {
 131             do {
 132                 a_byte *const cur = ptr - ctx->siz_;
 133                 if (cmp(cur, ptr) > 0)
 134                 {
 135                     a_swap(cur, ptr, ctx->siz_);
 136                 }
 137                 else { break; }
 138                 ptr = cur;
 139             } while (ptr != ctx->ptr_);
 140         }
 141     }
 142 }
 143
 144 void *a_buf_push_sort(a_buf *ctx, void const *key, int (*cmp)(void const *, void const *))
 145 {
 146     if (ctx->num_ < ctx->mem_)
 147     {
 148         a_byte *ptr = (a_byte *)a_buf_inc_(ctx);
 149         if (ctx->num_ > 1)
 150         {
 151             a_byte *const pos = ptr;
 152             do {
 153                 a_byte *const cur = ptr - ctx->siz_;
 154                 if (cmp(cur, key) <= 0) { break; }
 155                 ptr = cur;
 156             } while (ptr != ctx->ptr_);
 157             if (ptr < pos)
 158             {
 159                 a_move(ptr + ctx->siz_, ptr, (a_size)(pos - ptr));
 160             }
 161         }
 162         return ptr;
 163     }
 164     return A_NULL;
 165 }
 166
 167 void *a_buf_search(a_buf const *ctx, void const *obj, int (*cmp)(void const *, void const *))
 168 {
 169     return bsearch(obj, ctx->ptr_, ctx->num_, ctx->siz_, cmp);
 170 }
 171
 172 void *a_buf_insert(a_buf *ctx, a_size idx)
 173 {
 174     if (ctx->num_ < ctx->mem_)
 175     {
 176         if (idx < ctx->num_)
 177         {
 178             a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 179             a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 180             a_move(dst, src, (ctx->num_ - idx) * ctx->siz_);
 181             ++ctx->num_;
 182             return src;
 183         }
 184         return a_buf_inc_(ctx);
 185     }
 186     return A_NULL;
 187 }
 188
 189 void *a_buf_push_fore(a_buf *ctx) { return a_buf_insert(ctx, 0); }
 190
 191 void *a_buf_push_back(a_buf *ctx)
 192 {
 193     return ctx->num_ < ctx->mem_ ? a_buf_inc_(ctx) : A_NULL;
 194 }
 195
 196 void *a_buf_remove(a_buf *ctx, a_size idx)
 197 {
 198     a_size const num = ctx->num_ - 1;
 199     if (ctx->num_ && idx < num)
 200     {
 201         a_byte *const ptr = (a_byte *)ctx->ptr_ + ctx->siz_ * num;
 202         a_byte *const dst = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 0);
 203         a_byte *const src = (a_byte *)ctx->ptr_ + ctx->siz_ * (idx + 1);
 204         a_swap(dst, src, (a_size)(ptr - dst));
 205         --ctx->num_;
 206         return ptr;
 207     }
 208     return ctx->num_ ? a_buf_dec_(ctx) : A_NULL;
 209 }
 210
 211 void *a_buf_pull_fore(a_buf *ctx) { return a_buf_remove(ctx, 0); }
 212
 213 void *a_buf_pull_back(a_buf *ctx)
 214 {
 215     return ctx->num_ ? a_buf_dec_(ctx) : A_NULL;
 216 }