src/que.c

   1 #include "a/que.h"
   2
   3 #undef a_que_at
   4 #undef a_que_fore
   5 #undef a_que_back
   6 #undef a_que_fore_
   7 #undef a_que_back_
   8 #undef a_que_insert
   9 #undef a_que_remove
  10 #undef a_que_push_fore
  11 #undef a_que_push_back
  12 #undef a_que_pull_fore
  13 #undef a_que_pull_back
  14
  15 static a_list *a_que_new_(a_que *ctx)
  16 {
  17     a_list *node = A_NULL;
  18     if (ctx->cur_)
  19     {
  20         node = ctx->ptr_[--ctx->cur_];
  21     }
  22     else
  23     {
  24         node = (a_list *)a_alloc(A_NULL, sizeof(a_list) + ctx->siz_);
  25         if (a_unlikely(!node)) { return node; }
  26     }
  27     ++ctx->num_;
  28     return node;
  29 }
  30
  31 static int a_que_die_(a_que *ctx, a_list *node)
  32 {
  33     if (a_unlikely(!node)) { return A_INVALID; }
  34     if (ctx->mem_ <= ctx->cur_)
  35     {
  36         a_size const mem = ctx->mem_ + (ctx->mem_ >> 1) + 1;
  37         a_list **const ptr = (a_list **)a_alloc(ctx->ptr_, sizeof(void *) * mem);
  38         if (a_unlikely(!ptr)) { return A_FAILURE; }
  39         ctx->ptr_ = ptr;
  40         ctx->mem_ = mem;
  41     }
  42     ctx->ptr_[ctx->cur_++] = node;
  43     --ctx->num_;
  44     return A_SUCCESS;
  45 }
  46
  47 a_que *a_que_new(a_size size)
  48 {
  49     a_que *const ctx = (a_que *)a_alloc(A_NULL, sizeof(a_que));
  50     if (ctx) { a_que_ctor(ctx, size); }
  51     return ctx;
  52 }
  53
  54 void a_que_die(a_que *ctx, void (*dtor)(void *))
  55 {
  56     if (ctx)
  57     {
  58         a_que_dtor(ctx, dtor);
  59         a_alloc(ctx, 0);
  60     }
  61 }
  62
  63 void a_que_ctor(a_que *ctx, a_size size)
  64 {
  65     if (!size) { size = sizeof(a_cast); }
  66     a_list_ctor(&ctx->head_);
  67     ctx->ptr_ = A_NULL;
  68     ctx->siz_ = size;
  69     ctx->num_ = 0;
  70     ctx->cur_ = 0;
  71     ctx->mem_ = 0;
  72 }
  73
  74 void a_que_dtor(a_que *ctx, void (*dtor)(void *))
  75 {
  76     if (dtor)
  77     {
  78         for (a_list **node = ctx->ptr_; ctx->cur_; --ctx->cur_)
  79         {
  80             dtor(*node + 1);
  81             a_alloc(*node++, 0);
  82         }
  83         a_list_forsafe_next(node, next, &ctx->head_)
  84         {
  85             dtor(node + 1);
  86             a_alloc(node, 0);
  87         }
  88     }
  89     else
  90     {
  91         for (a_list **node = ctx->ptr_; ctx->cur_; --ctx->cur_)
  92         {
  93             a_alloc(*node++, 0);
  94         }
  95         a_list_forsafe_next(node, next, &ctx->head_)
  96         {
  97             a_alloc(node, 0);
  98         }
  99     }
 100     a_alloc(ctx->ptr_, 0);
 101     ctx->ptr_ = A_NULL;
 102     ctx->siz_ = 0;
 103     ctx->mem_ = 0;
 104 }
 105
 106 void a_que_move(a_que *ctx, a_que *obj)
 107 {
 108     a_copy(ctx, obj, sizeof(*obj));
 109     a_zero(obj, sizeof(*obj));
 110 }
 111
 112 void *a_que_at(a_que const *ctx, a_imax idx)
 113 {
 114     a_imax cur = 0;
 115     if (idx >= 0)
 116     {
 117         a_list_foreach_next(it, &ctx->head_)
 118         {
 119             if (cur++ == idx) { return it + 1; }
 120         }
 121     }
 122     else
 123     {
 124         a_list_foreach_prev(it, &ctx->head_)
 125         {
 126             if (--cur == idx) { return it + 1; }
 127         }
 128     }
 129     return A_NULL;
 130 }
 131
 132 int a_que_drop(a_que *ctx, void (*dtor)(void *))
 133 {
 134     a_list *const head = &ctx->head_;
 135     for (a_list *node = head->next; node != head; node = head->next)
 136     {
 137         if (a_que_die_(ctx, node) == A_SUCCESS)
 138         {
 139             a_list_del_node(node);
 140             a_list_dtor(node);
 141         }
 142         else { return A_FAILURE; }
 143     }
 144     if (dtor)
 145     {
 146         a_size cur = ctx->cur_;
 147         a_list **node = ctx->ptr_;
 148         for (; cur; ++node, --cur)
 149         {
 150             dtor(*node + 1);
 151         }
 152     }
 153     return A_SUCCESS;
 154 }
 155
 156 int a_que_edit(a_que *ctx, a_size size, void (*dtor)(void *))
 157 {
 158     int ok = a_que_drop(ctx, dtor);
 159     if (ok == A_SUCCESS)
 160     {
 161         if (!size) { size = sizeof(a_cast); }
 162         if (size > ctx->siz_)
 163         {
 164             a_size cur = ctx->cur_;
 165             a_list **node = ctx->ptr_;
 166             for (; cur; ++node, --cur)
 167             {
 168                 void *const ptr = a_alloc(*node, sizeof(a_list) + size);
 169                 if (a_unlikely(!ptr)) { return A_FAILURE; }
 170                 *node = (a_list *)ptr;
 171             }
 172         }
 173         ctx->siz_ = size;
 174     }
 175     return ok;
 176 }
 177
 178 int a_que_swap(a_que const *ctx, a_size lhs, a_size rhs)
 179 {
 180     a_size cur = 0;
 181     int ok = A_FAILURE;
 182     a_list *at = A_NULL;
 183     a_size const num = ctx->num_ - 1;
 184     lhs = lhs < ctx->num_ ? lhs : num;
 185     rhs = rhs < ctx->num_ ? rhs : num;
 186     if (lhs == rhs) { return A_SUCCESS; }
 187     a_list_foreach_next(it, &ctx->head_)
 188     {
 189         if (cur == lhs || cur == rhs)
 190         {
 191             if (at)
 192             {
 193                 a_list_swap_node(it, at);
 194                 ok = A_SUCCESS;
 195                 break;
 196             }
 197             else { at = it; }
 198         }
 199         ++cur;
 200     }
 201     return ok;
 202 }
 203
 204 void a_que_sort_fore(a_que const *ctx, int (*cmp)(void const *, void const *))
 205 {
 206     if (ctx->num_ > 1)
 207     {
 208         a_list *ok = A_NULL;
 209         a_list *const it = ctx->head_.next;
 210         for (a_list *at = it->next; at != &ctx->head_; at = at->next)
 211         {
 212             if (cmp(it + 1, at + 1) > 0) { ok = at; }
 213             else { break; }
 214         }
 215         if (ok)
 216         {
 217             /* a-it-b-at-a => a-b-at-it-a */
 218             a_list_link(it->prev, it->next); // a-b
 219             a_list_link(it, ok->next); // it-a
 220             a_list_link(ok, it); // at-it
 221         }
 222     }
 223 }
 224
 225 void a_que_sort_back(a_que const *ctx, int (*cmp)(void const *, void const *))
 226 {
 227     if (ctx->num_ > 1)
 228     {
 229         a_list *ok = A_NULL;
 230         a_list *const it = ctx->head_.prev;
 231         for (a_list *at = it->prev; at != &ctx->head_; at = at->prev)
 232         {
 233             if (cmp(at + 1, it + 1) > 0) { ok = at; }
 234             else { break; }
 235         }
 236         if (ok)
 237         {
 238             /* a-at-b-it-a => a-it-at-b-a */
 239             a_list_link(it->prev, it->next); // b-a
 240             a_list_link(ok->prev, it); // a-it
 241             a_list_link(it, ok); // it-at
 242         }
 243     }
 244 }
 245
 246 void *a_que_push_fore(a_que *ctx)
 247 {
 248     a_list *const node = a_que_new_(ctx);
 249     if (a_unlikely(!node)) { return node; }
 250     a_list_add_next(&ctx->head_, node);
 251     return node + 1;
 252 }
 253
 254 void *a_que_push_back(a_que *ctx)
 255 {
 256     a_list *const node = a_que_new_(ctx);
 257     if (a_unlikely(!node)) { return node; }
 258     a_list_add_prev(&ctx->head_, node);
 259     return node + 1;
 260 }
 261
 262 void *a_que_pull_fore(a_que *ctx)
 263 {
 264     if (ctx->head_.next != &ctx->head_)
 265     {
 266         a_list *const node = (a_list *)ctx->head_.next;
 267         if (a_que_die_(ctx, node) == A_SUCCESS)
 268         {
 269             a_list_del_node(node);
 270             a_list_dtor(node);
 271             return node + 1;
 272         }
 273     }
 274     return A_NULL;
 275 }
 276
 277 void *a_que_pull_back(a_que *ctx)
 278 {
 279     if (ctx->head_.prev != &ctx->head_)
 280     {
 281         a_list *const node = (a_list *)ctx->head_.prev;
 282         if (a_que_die_(ctx, node) == A_SUCCESS)
 283         {
 284             a_list_del_node(node);
 285             a_list_dtor(node);
 286             return node + 1;
 287         }
 288     }
 289     return A_NULL;
 290 }
 291
 292 void *a_que_insert(a_que *ctx, a_size idx)
 293 {
 294     if (idx < ctx->num_)
 295     {
 296         a_size cur = 0;
 297         a_list *const node = a_que_new_(ctx);
 298         if (node)
 299         {
 300             a_list_foreach_next(it, &ctx->head_)
 301             {
 302                 if (cur++ == idx)
 303                 {
 304                     a_list_add_prev(it, node);
 305                     break;
 306                 }
 307             }
 308             return node + 1;
 309         }
 310         return A_NULL;
 311     }
 312     return a_que_push_back(ctx);
 313 }
 314
 315 void *a_que_remove(a_que *ctx, a_size idx)
 316 {
 317     if (idx < ctx->num_)
 318     {
 319         a_size cur = 0;
 320         a_list *node = A_NULL;
 321         a_list_foreach_next(it, &ctx->head_)
 322         {
 323             if (cur++ == idx)
 324             {
 325                 node = it;
 326                 break;
 327             }
 328         }
 329         if (a_que_die_(ctx, node) == A_SUCCESS)
 330         {
 331             a_list_del_node(node);
 332             a_list_dtor(node);
 333             return node + 1;
 334         }
 335         return A_NULL;
 336     }
 337     return a_que_pull_back(ctx);
 338 }