qcsrc/lib/linkedlist.qh

   1 #pragma once
   2
   3 CLASS(LinkedListNode, Object)
   4         ATTRIB(LinkedListNode, ll_data, entity, NULL)
   5         ATTRIB(LinkedListNode, ll_prev, LinkedListNode, NULL)
   6         ATTRIB(LinkedListNode, ll_next, LinkedListNode, NULL)
   7 ENDCLASS(LinkedListNode)
   8
   9 CLASS(LinkedList, Object)
  10         ATTRIB(LinkedList, ll_head, LinkedListNode, NULL);
  11         ATTRIB(LinkedList, ll_tail, LinkedListNode, NULL);
  12 ENDCLASS(LinkedList)
  13
  14 #define LL_NEW() NEW(LinkedList)
  15
  16 #define LL_EMPTY(ll) (ll.ll_head == NULL)
  17
  18 /**
  19  * Push to tail
  20  */
  21 entity LL_PUSH(LinkedList this, entity e)
  22 {
  23         assert(this);
  24         LinkedListNode n = NEW(LinkedListNode);
  25         n.ll_data = e;
  26         LinkedListNode tail = n.ll_prev = this.ll_tail;
  27         this.ll_tail = (tail) ? tail.ll_next = n : this.ll_head = n;
  28         return e;
  29 }
  30
  31 /**
  32  * Pop from tail
  33  */
  34 entity LL_POP(LinkedList this)
  35 {
  36         assert(this);
  37         if (!this.ll_tail) return NULL;
  38         LinkedListNode n = this.ll_tail;
  39         entity e = n.ll_data;
  40         LinkedListNode prev = n.ll_prev;
  41         if (prev) (this.ll_tail = prev).ll_next = NULL;
  42         else this.ll_head = this.ll_tail = NULL;
  43         delete(n);
  44         return e;
  45 }
  46
  47 #define LL_CLEAR(...) EVAL_LL_CLEAR(OVERLOAD(LL_CLEAR, __VA_ARGS__))
  48 #define EVAL_LL_CLEAR(...) __VA_ARGS__
  49 #define LL_CLEAR_1(this) LL_CLEAR_2(this, LAMBDA())
  50 #define LL_CLEAR_2(this, dtor) \
  51         MACRO_BEGIN \
  52         { \
  53                 LinkedList _ll = this; \
  54                 assert(_ll); \
  55                 while (_ll.ll_tail) \
  56                 { \
  57                         entity it = LL_POP(_ll); \
  58                         if (!it) continue; \
  59                         dtor \
  60                         delete(it); \
  61                 } \
  62         } MACRO_END
  63
  64 #define LL_DELETE(...) EVAL_LL_DELETE(OVERLOAD(LL_DELETE, __VA_ARGS__))
  65 #define EVAL_LL_DELETE(...) __VA_ARGS__
  66 #define LL_DELETE_1(this) LL_DELETE_2(this, LAMBDA())
  67 #define LL_DELETE_2(this, dtor) \
  68         MACRO_BEGIN \
  69         { \
  70                 LL_CLEAR_2(this, dtor); \
  71                 delete(this); \
  72                 this = NULL; \
  73         } MACRO_END
  74
  75 #define LL_EACH(list, cond, body) \
  76         MACRO_BEGIN                                                         \
  77         {                                                                   \
  78                 noref int i = 0;                                                \
  79                 for (entity _it = list.ll_head; _it; (_it = _it.ll_next, ++i))  \
  80                 {                                                               \
  81                         ITER_CONST noref entity it = _it.ll_data;                   \
  82                         if (cond) { body }                                          \
  83                 }                                                               \
  84         } MACRO_END