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