qcsrc/lib/linkedlist.qh

   1 #ifndef LINKEDLIST_H
   2 #define LINKEDLIST_H
   3
   4 CLASS(LinkedListNode, Object)
   5         ATTRIB(LinkedListNode, ll_data, entity, NULL)
   6         ATTRIB(LinkedListNode, ll_prev, LinkedListNode, NULL)
   7         ATTRIB(LinkedListNode, ll_next, LinkedListNode, NULL)
   8 ENDCLASS(LinkedListNode)
   9
  10 CLASS(LinkedList, Object)
  11         ATTRIB(LinkedList, ll_head, LinkedListNode, NULL);
  12         ATTRIB(LinkedList, ll_tail, LinkedListNode, NULL);
  13 ENDCLASS(LinkedList)
  14
  15 #define LL_NEW() NEW(LinkedList)
  16
  17 #define LL_EMPTY(ll) (ll.ll_head == NULL)
  18
  19 /**
  20  * Push to tail
  21  */
  22 entity LL_PUSH(LinkedList this, entity e)
  23 {
  24         assert(this);
  25         LinkedListNode n = NEW(LinkedListNode);
  26         n.ll_data = e;
  27         LinkedListNode tail = n.ll_prev = this.ll_tail;
  28         this.ll_tail = (tail) ? tail.ll_next = n : this.ll_head = n;
  29         return e;
  30 }
  31
  32 /**
  33  * Pop from tail
  34  */
  35 entity LL_POP(LinkedList this)
  36 {
  37         assert(this);
  38         if (!this.ll_tail) return NULL;
  39         LinkedListNode n = this.ll_tail;
  40         entity e = n.ll_data;
  41         LinkedListNode prev = n.ll_prev;
  42         if (prev) (this.ll_tail = prev).ll_next = NULL;
  43         else this.ll_head = this.ll_tail = NULL;
  44         remove(n);
  45         return e;
  46 }
  47
  48 #define LL_CLEAR(...) EVAL(OVERLOAD(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                         remove(it); \
  61                 } \
  62         } MACRO_END
  63
  64 #define LL_DELETE(...) EVAL(OVERLOAD(LL_DELETE, __VA_ARGS__))
  65 #define LL_DELETE_1(this) LL_DELETE_2(this, LAMBDA())
  66 #define LL_DELETE_2(this, dtor) \
  67         MACRO_BEGIN \
  68         { \
  69                 LL_CLEAR(this, dtor); \
  70                 remove(this); \
  71                 this = NULL; \
  72         } MACRO_END
  73
  74 #define LL_EACH(list, cond, body) \
  75         MACRO_BEGIN                                                         \
  76         {                                                                   \
  77                 noref int i = 0;                                                \
  78                 for (entity _it = list.ll_head; _it; (_it = _it.ll_next, ++i))  \
  79                 {                                                               \
  80                         noref entity it = _it.ll_data;                              \
  81                         if (cond) { body }                                          \
  82                 }                                                               \
  83         } MACRO_END
  84
  85 #endif