src/que.c

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