src/shl_dlist.h

   1 /*
   2  * shl - Double Linked List
   3  *
   4  * Copyright (c) 2011-2012 David Herrmann <dh.herrmann@googlemail.com>
   5  * Copyright (c) 2011 University of Tuebingen
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files
   9  * (the "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be included
  16  * in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  21  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  22  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 /*
  28  * A simple double linked list implementation
  29  */
  30
  31 #ifndef SHL_DLIST_H
  32 #define SHL_DLIST_H
  33
  34 #include <stdbool.h>
  35 #include <stddef.h>
  36 #include <stdint.h>
  37 #include <stdlib.h>
  38
  39 /* miscellaneous */
  40
  41 #define shl_offsetof(pointer, type, member) ({ \
  42                 const typeof(((type*)0)->member) *__ptr = (pointer); \
  43                 (type*)(((char*)__ptr) - offsetof(type, member)); \
  44         })
  45
  46 /* double linked list */
  47
  48 struct shl_dlist {
  49         struct shl_dlist *next;
  50         struct shl_dlist *prev;
  51 };
  52
  53 #define SHL_DLIST_INIT(head) { &(head), &(head) }
  54
  55 static inline void shl_dlist_init(struct shl_dlist *list)
  56 {
  57         list->next = list;
  58         list->prev = list;
  59 }
  60
  61 static inline void shl_dlist__link(struct shl_dlist *prev,
  62                                         struct shl_dlist *next,
  63                                         struct shl_dlist *n)
  64 {
  65         next->prev = n;
  66         n->next = next;
  67         n->prev = prev;
  68         prev->next = n;
  69 }
  70
  71 static inline void shl_dlist_link(struct shl_dlist *head,
  72                                         struct shl_dlist *n)
  73 {
  74         return shl_dlist__link(head, head->next, n);
  75 }
  76
  77 static inline void shl_dlist_link_tail(struct shl_dlist *head,
  78                                         struct shl_dlist *n)
  79 {
  80         return shl_dlist__link(head->prev, head, n);
  81 }
  82
  83 static inline void shl_dlist__unlink(struct shl_dlist *prev,
  84                                         struct shl_dlist *next)
  85 {
  86         next->prev = prev;
  87         prev->next = next;
  88 }
  89
  90 static inline void shl_dlist_unlink(struct shl_dlist *e)
  91 {
  92         shl_dlist__unlink(e->prev, e->next);
  93         e->prev = NULL;
  94         e->next = NULL;
  95 }
  96
  97 static inline bool shl_dlist_empty(struct shl_dlist *head)
  98 {
  99         return head->next == head;
 100 }
 101
 102 #define shl_dlist_entry(ptr, type, member) \
 103         shl_offsetof((ptr), type, member)
 104
 105 #define shl_dlist_first(head, type, member) \
 106         shl_dlist_entry((head)->next, type, member)
 107
 108 #define shl_dlist_last(head, type, member) \
 109         shl_dlist_entry((head)->prev, type, member)
 110
 111 #define shl_dlist_for_each(iter, head) \
 112         for (iter = (head)->next; iter != (head); iter = iter->next)
 113
 114 #define shl_dlist_for_each_but_one(iter, start, head) \
 115         for (iter = ((start)->next == (head)) ? \
 116                                 (start)->next->next : \
 117                                 (start)->next; \
 118              iter != (start); \
 119              iter = (iter->next == (head) && (start) != (head)) ? \
 120                                 iter->next->next : \
 121                                 iter->next)
 122
 123 #define shl_dlist_for_each_safe(iter, tmp, head) \
 124         for (iter = (head)->next, tmp = iter->next; iter != (head); \
 125                 iter = tmp, tmp = iter->next)
 126
 127 #define shl_dlist_for_each_reverse(iter, head) \
 128         for (iter = (head)->prev; iter != (head); iter = iter->prev)
 129
 130 #define shl_dlist_for_each_reverse_but_one(iter, start, head) \
 131         for (iter = ((start)->prev == (head)) ? \
 132                                 (start)->prev->prev : \
 133                                 (start)->prev; \
 134              iter != (start); \
 135              iter = (iter->prev == (head) && (start) != (head)) ? \
 136                                 iter->prev->prev : \
 137                                 iter->prev)
 138
 139 #define shl_dlist_for_each_reverse_safe(iter, tmp, head) \
 140         for (iter = (head)->prev, tmp = iter->prev; iter != (head); \
 141                 iter = tmp, tmp = iter->prev)
 142
 143 #endif /* SHL_DLIST_H */