com_list.h

   1 /*
   2 Copyright (C) 2020-2021 David Knapp (Cloudwalk)
   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 static inline qbool List_Is_Empty(const llist_t *list)
 210 {
 211         return list->next == list;
 212 }
 213
 214 /*
 215  * Creates a new linked list. Initializes the head to point to itself.
 216  * If it's a list header, the result is an empty list.
 217  */
 218 static inline void List_Create(llist_t *list)
 219 {
 220         list->next = list->prev = NULL;
 221 }
 222
 223 /*
 224  * Insert a node between two known nodes.
 225  *
 226  * Only use when prev and next are known.
 227  */
 228 static inline void __List_Add(llist_t *node, llist_t *prev, llist_t *next)
 229 {
 230         next->prev = node;
 231         node->next = next;
 232         node->prev = prev;
 233         prev->next = node;
 234 }
 235
 236 /*
 237  * Insert a node immediately after head.
 238  */
 239 static inline void List_Add(llist_t *node, llist_t *head)
 240 {
 241         __List_Add(node, head, head->next);
 242 }
 243
 244 /*
 245  * Insert a node immediately before head.
 246  */
 247 static inline void List_Add_Tail(llist_t *node, llist_t *head)
 248 {
 249         __List_Add(node, head->prev, head);
 250 }
 251
 252 /*
 253  * Bridge prev and next together, when removing the parent of them.
 254  */
 255 static inline void __List_Delete(llist_t *prev, llist_t *next)
 256 {
 257         next->prev = prev;
 258         prev->next = next;
 259 }
 260
 261 /*
 262  * Redundant?
 263  */
 264 static inline void __List_Delete_Node(llist_t *node)
 265 {
 266         __List_Delete(node->prev, node->next);
 267 }
 268
 269 /*
 270  * Removes a node from its list. Sets its pointers to NULL.
 271  */
 272 static inline void List_Delete(llist_t *node)
 273 {
 274         __List_Delete_Node(node);
 275         node->next = node->prev = NULL;
 276 }
 277
 278 /*
 279  * Removes a node from its list. Reinitialize it.
 280  */
 281 static inline void List_Delete_Init(llist_t *node)
 282 {
 283         __List_Delete_Node(node);
 284         node->next = node->prev = node;
 285 }
 286
 287 /*
 288  * Replace old with new. Old is overwritten if empty.
 289  */
 290 static inline void List_Replace(llist_t *old, llist_t *_new)
 291 {
 292         _new->next = old->next;
 293         _new->next->prev = _new;
 294         _new->prev = old->prev;
 295         _new->prev->next = _new;
 296         old->next = old->prev = old;
 297 }
 298
 299 /*
 300  * Replace old with new. Initialize old.
 301  * Old is overwritten if empty.
 302  */
 303 static inline void List_Replace_Init(llist_t *old, llist_t *_new)
 304 {
 305         List_Replace(old, _new);
 306         List_Create(old);
 307 }
 308
 309 /*
 310  * Swap node1 with node2 in place.
 311  */
 312 static inline void List_Swap(llist_t *node1, llist_t *node2)
 313 {
 314         llist_t *pos = node2->prev;
 315         List_Delete_Init(node2);
 316         List_Replace(node1, node2);
 317         if(pos == node1)
 318                 pos = node2;
 319         List_Add(node1, pos);
 320 }
 321
 322 /*
 323  * Delete list from its... list, then insert after head.
 324  */
 325 static inline void List_Move(llist_t *list, llist_t *head)
 326 {
 327         __List_Delete_Node(list);
 328         List_Add(list, head);
 329 }
 330
 331 /*
 332  * Delete list from its... list, then insert before head.
 333  */
 334 static inline void List_Move_Tail(llist_t *list, llist_t *head)
 335 {
 336         __List_Delete_Node(list);
 337         List_Add_Tail(list, head);
 338 }
 339
 340 /*
 341  * Move the first node of a range of nodes immediately after head.
 342  * All three parameters must belong to the same list.
 343  */
 344
 345 static inline void List_Bulk_Move_Tail(llist_t *head, llist_t *first, llist_t *last)
 346 {
 347         first->prev->next = last->next;
 348         last->next->prev = first->prev;
 349
 350         head->prev->next = first;
 351         first->prev = head->prev;
 352
 353         last->next = head;
 354         head->prev = last;
 355 }
 356
 357 /*
 358  * Shift the head to the right (like rotating a wheel counterclockwise).
 359  * The node immediately to the right becomes the new head.
 360  */
 361 static inline void List_Rotate_Left(llist_t *head)
 362 {
 363         llist_t *first;
 364
 365         if (!List_Is_Empty(head))
 366         {
 367                 first = head->next;
 368                 List_Move_Tail(first, head);
 369         }
 370 }
 371
 372 /*
 373  * Make list the new head.
 374  */
 375 static inline void List_Rotate_To_Front(llist_t *list, llist_t *head)
 376 {
 377         List_Move_Tail(head, list);
 378 }
 379
 380 /*
 381  * Concatenate two lists. The head of list will be discarded.
 382  */
 383 static inline void __List_Splice(const llist_t *list, llist_t *prev, llist_t *next)
 384 {
 385         llist_t *first = list->next;
 386         llist_t *last = list->prev;
 387
 388         first->prev = prev;
 389         prev->next = first;
 390
 391         last->next = next;
 392         next->prev = last;
 393 }
 394
 395 /*
 396  * Concatenate two lists. The first node of list will be inserted after head.
 397  */
 398 static inline void List_Splice(const llist_t *list, llist_t *head)
 399 {
 400         if(!List_Is_Empty(list))
 401                 __List_Splice(list, head, head->next);
 402 }
 403
 404 /*
 405  * Concatenate two lists. The tail of list will be inserted before head.
 406  */
 407 static inline void List_Splice_Tail(const llist_t *list, llist_t *head)
 408 {
 409         if (!List_Is_Empty(list))
 410                 __List_Splice(list, head->prev, head);
 411 }
 412
 413 static inline qbool List_Is_First(llist_t *list, llist_t *start)
 414 {
 415         return list->prev == start;
 416 }
 417
 418 static inline qbool List_Is_Last(llist_t *list, llist_t *start)
 419 {
 420         return list->next == start;
 421 }
 422
 423 #endif