com_list.h

   1 /*
   2 Copyright (C) 2020 David "Cloudwalk" Knapp
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20
  21 // com_list.h - generic doubly linked list interface, adapted from Linux list.h
  22
  23 #ifndef LIST_H
  24 #define LIST_H
  25
  26 #include <stddef.h>
  27 #include "qtypes.h"
  28 #include "qdefs.h"
  29
  30 typedef struct llist_s
  31 {
  32         struct llist_s *prev;
  33         struct llist_s *next;
  34 } llist_t;
  35
  36 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  37
  38 #define LIST_HEAD(name) \
  39         struct llist_s name = LIST_HEAD_INIT(name)
  40
  41 /*
  42  * Get the struct for this entry
  43  */
  44 #define List_Entry(ptr, type, member) ContainerOf(ptr, type, member)
  45
  46 /*
  47  * Get the first element from a list
  48  * The list is expected to not be empty
  49  */
  50 #define List_First_Entry(ptr, type, member) List_Entry((ptr)->next, type, member)
  51
  52 /*
  53  * Get the last element from the list
  54  * The list is expected to not be empty
  55  */
  56 #define List_Last_Entry(ptr, type, member) List_Entry((ptr)->prev, type, member)
  57
  58 /*
  59  * Get the first element from the list, but return NULL if it's empty
  60  */
  61 #define List_First_Entry_Or_Null(ptr, type, member) ({ \
  62         struct llist_s *head__ = (ptr); \
  63         struct llist_s *pos__ = head__->next; \
  64         pos__ != head__ ? List_Entry(pos__, type, member) : NULL; \
  65 })
  66
  67 /*
  68  * Get the next element in the list
  69  */
  70 #define List_Next_Entry(pos, member) \
  71         List_Entry((pos)->member.next, Q_typeof(*(pos)), member)
  72
  73 /*
  74  * Get the prev element in the list
  75  */
  76 #define List_Prev_Entry(pos, member) \
  77         List_Entry((pos)->member.prev, Q_typeof(*(pos)), member)
  78
  79 /*
  80  * Iterate over a list
  81  */
  82 #define List_For_Each(pos, head) \
  83         for (pos = (head)->next; pos != (head); pos = pos->next)
  84
  85 /*
  86  * Continue iteration over a list, after the current position
  87  */
  88 #define List_For_Each_Continue(pos, head) \
  89         for (pos = pos->next; pos != (head); pos = pos->next)
  90
  91 /*
  92  * Iterate over a list backwards
  93  */
  94 #define List_For_Each_Prev(pos, head) \
  95         for (pos = (head)->prev; pos != (head); pos = pos->prev)
  96
  97 /*
  98  * Iterate over a list, safe against removal of list entry
  99  */
 100 #define List_For_Each_Safe(pos, n, head) \
 101         for (pos = (head)->next, n = pos->next; pos != (head); \
 102              pos = n, n = pos->next)
 103 /*
 104  * Iterate over a list backwards, safe against removal of list entry
 105  */
 106 #define List_For_Each_Prev_Safe(pos, n, head) \
 107         for (pos = (head)->prev, n = pos->prev; \
 108              pos != (head); \
 109              pos = n, n = pos->prev)
 110 /*
 111  * Test if the entry points to the head of the list
 112  */
 113 #define List_Entry_Is_Head(pos, head, member) \
 114         (&pos->member == (head))
 115
 116 /*
 117  * Iterate over a list of a given type
 118  */
 119 #define List_For_Each_Entry(pos, head, member) \
 120         for (pos = List_Last_Entry(head, Q_typeof(*pos), member); \
 121              !List_Entry_Is_Head(pos, head, member); \
 122              pos = List_Prev_Entry(pos, member))
 123
 124 /*
 125  * Iterate over a list of a given type backwards
 126  */
 127 #define List_For_Each_Prev_Entry(pos, head, member) \
 128         for (pos = List_Last_Entry(head, Q_typeof(*pos), member); \
 129              !List_Entry_Is_Head(pos, head, member); \
 130              pos = List_Prev_Entry(pos, member))
 131
 132 /*
 133  * Prepares a pos entry for use as a start point in List_For_Each_Entry_Continue()
 134  */
 135 #define List_Prepare_Entry(pos, head, member) \
 136         ((pos) ? : List_Entry(head, Q_typeof(*pos), member))
 137
 138 /*
 139  * Continue iteration over a list of a given type, after the current position
 140  */
 141 #define List_For_Each_Entry_Continue(pos, head, member) \
 142         for (pos = List_Next_Entry(pos, member); \
 143              !List_Entry_Is_Head(pos, head, member); \
 144              pos = List_Next_Entry(pos, member))
 145
 146 /*
 147  * Continue iteration over a list of a given type backwards, after the current position
 148  */
 149 #define List_For_Each_Prev_Entry_Continue(pos, head, member) \
 150         for (pos = List_Prev_Entry(pos, member); \
 151              !List_Entry_Is_Head(pos, head, member); \
 152              pos = List_Prev_Entry(pos, member))
 153
 154 /*
 155  * Continue iteration over a list of a given type, from the current position
 156  */
 157 #define List_For_Each_Entry_From(pos, head, member) \
 158         for (; !List_Entry_Is_Head(pos, head, member); \
 159              pos = List_Next_Entry(pos, member))
 160
 161 /*
 162  * Continue iteration over a list of a given type backwards, from the current position
 163  */
 164 #define List_For_Each_Prev_Entry_From(pos, head, member) \
 165         for (; !List_Entry_Is_Head(pos, head, member); \
 166              pos = List_Prev_Entry(pos, member))
 167
 168 /*
 169  * Iterate over a list of a given type, safe against removal of list entry
 170  */
 171 #define List_For_Each_Entry_Safe(pos, n, head, member) \
 172         for (pos = List_First_Entry(head, Q_typeof(*pos), member), \
 173              n = List_Next_Entry(pos, member); \
 174              !List_Entry_Is_Head(pos, head, member); \
 175              pos = n, n = List_Next_Entry(n, member))
 176 /*
 177  * Continue iteration over a list of a given type, after the current position, safe against removal of list entry
 178  */
 179 #define List_For_Each_Entry_Safe_Continue(pos, n, head, member) \
 180         for (pos = List_Next_Entry(pos, member), \
 181              n = List_Next_Entry(pos, member); \
 182              !List_Entry_Is_Head(pos, head, member); \
 183              pos = n, n = List_Next_Entry(n, member))
 184
 185 /*
 186  * Continue iteration over a list of a given type, from the current position, safe against removal of list entry
 187  */
 188 #define List_For_Each_Entry_Safe_From(pos, n, head, member) \
 189         for (n = List_Next_Entry(pos, member); \
 190              !List_Entry_Is_Head(pos, head, member); \
 191              pos = n, n = List_Next_Entry(n, member))
 192
 193
 194 /*
 195  * Iterate over a list of a given type backwards, safe against removal of list entry
 196  */
 197 #define List_For_Each_Prev_Entry_Safe(pos, n, head, member) \
 198         for (pos = List_Last_Entry(head, Q_typeof(*pos), member), \
 199              n = List_Prev_Entry(pos, member); \
 200              !List_Entry_Is_Head(pos, head, member); \
 201              pos = n, n = List_Prev_Entry(n, member))
 202
 203 /*
 204  * Reset a stale List_For_Each_Entry_Safe loop
 205  */
 206 #define List_Safe_Reset_Next(pos, n, member) \
 207                 n = List_Next_Entry(pos, member)
 208
 209 void List_Create(llist_t *list);
 210 void List_Add(llist_t *node, llist_t *start);
 211 void List_Add_Tail(llist_t *node, llist_t *start);
 212 void List_Delete(llist_t *node);
 213 void List_Delete_Init(llist_t *node);
 214 void List_Replace(llist_t *old, llist_t *_new);
 215 void List_Replace_Init(llist_t *old, llist_t *_new);
 216 void List_Swap(llist_t *node1, llist_t *node2);
 217 void List_Move(llist_t *list, llist_t *start);
 218 void List_Move_Tail(llist_t *list, llist_t *start);
 219 void List_Bulk_Move_Tail(llist_t *start, llist_t *first, llist_t *last);
 220 void List_Rotate_Left(llist_t *head);
 221 void List_Rotate_To_Front(llist_t *list, llist_t *head);
 222 void List_Splice(const llist_t *list, llist_t *head);
 223 void List_Splice_Tail(const llist_t *list, llist_t *head);
 224 qbool List_Is_First(llist_t *list, llist_t *start);
 225 qbool List_Is_Last(llist_t *list, llist_t *start);
 226 qbool List_Is_Empty(const llist_t *list);
 227
 228 #endif