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, type, member) \
  71         List_Entry((pos)->member.next, type, member)
  72
  73 /*
  74  * Get the prev element in the list
  75  */
  76 #define List_Prev_Entry(pos, type, member) \
  77         List_Entry((pos)->member.prev, type, 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 /*
 105  * Iterate over a list backwards, safe against removal of list entry
 106  */
 107 #define List_For_Each_Prev_Safe(pos, n, head) \
 108         for (pos = (head)->prev, n = pos->prev; \
 109              pos != (head); \
 110              pos = n, n = pos->prev)
 111
 112 /*
 113  * Test if the entry points to the head of the list
 114  */
 115 #define List_Entry_Is_Head(pos, head, member) \
 116         (&pos->member == (head))
 117
 118 /*
 119  * Iterate over a list of a given type
 120  */
 121 #define List_For_Each_Entry(pos, head, type, member) \
 122         for (pos = List_First_Entry(head, type, member); \
 123              !List_Entry_Is_Head(pos, head, member); \
 124              pos = List_Next_Entry(pos, type, member))
 125
 126 /*
 127  * Iterate over a list of a given type backwards
 128  */
 129 #define List_For_Each_Prev_Entry(pos, head, type, member) \
 130         for (pos = List_Last_Entry(head, type, member); \
 131              !List_Entry_Is_Head(pos, head, member); \
 132              pos = List_Prev_Entry(pos, type, member))
 133
 134 /*
 135  * Prepares a pos entry for use as a start point in List_For_Each_Entry_Continue()
 136  */
 137 #define List_Prepare_Entry(pos, head, type, member) \
 138         ((pos) ? : List_Entry(head, type, member))
 139
 140 /*
 141  * Continue iteration over a list of a given type, after the current position
 142  */
 143 #define List_For_Each_Entry_Continue(pos, head, type, member) \
 144         for (pos = List_Next_Entry(pos, type, member); \
 145              !List_Entry_Is_Head(pos, head, member); \
 146              pos = List_Next_Entry(pos, type, member))
 147
 148 /*
 149  * Continue iteration over a list of a given type backwards, after the current position
 150  */
 151 #define List_For_Each_Prev_Entry_Continue(pos, head, type, member) \
 152         for (pos = List_Prev_Entry(pos, type, member); \
 153              !List_Entry_Is_Head(pos, head, member); \
 154              pos = List_Prev_Entry(pos, type, member))
 155
 156 /*
 157  * Continue iteration over a list of a given type, from the current position
 158  */
 159 #define List_For_Each_Entry_From(pos, head, type, member) \
 160         for (; !List_Entry_Is_Head(pos, head, member); \
 161              pos = List_Next_Entry(pos, type, member))
 162
 163 /*
 164  * Continue iteration over a list of a given type backwards, from the current position
 165  */
 166 #define List_For_Each_Prev_Entry_From(pos, head, type, member) \
 167         for (; !List_Entry_Is_Head(pos, head, member); \
 168              pos = List_Prev_Entry(pos, type, member))
 169
 170 /*
 171  * Iterate over a list of a given type, safe against removal of list entry
 172  */
 173 #define List_For_Each_Entry_Safe(pos, n, head, type, member) \
 174         for (pos = List_First_Entry(head, type, member), \
 175              n = List_Next_Entry(pos, type, member); \
 176              !List_Entry_Is_Head(pos, head, member); \
 177              pos = n, n = List_Next_Entry(n, type, member))
 178
 179 /*
 180  * Continue iteration over a list of a given type, after the current position, safe against removal of list entry
 181  */
 182 #define List_For_Each_Entry_Safe_Continue(pos, n, head, type, member) \
 183         for (pos = List_Next_Entry(pos, type, member), \
 184              n = List_Next_Entry(pos, type, member); \
 185              !List_Entry_Is_Head(pos, head, member); \
 186              pos = n, n = List_Next_Entry(n, type, member))
 187
 188 /*
 189  * Continue iteration over a list of a given type, from the current position, safe against removal of list entry
 190  */
 191 #define List_For_Each_Entry_Safe_From(pos, n, head, type, member) \
 192         for (n = List_Next_Entry(pos, type, member); \
 193              !List_Entry_Is_Head(pos, head, member); \
 194              pos = n, n = List_Next_Entry(n, type, member))
 195
 196 /*
 197  * Iterate over a list of a given type backwards, safe against removal of list entry
 198  */
 199 #define List_For_Each_Prev_Entry_Safe(pos, n, head, type, member) \
 200         for (pos = List_Last_Entry(head, type, member), \
 201              n = List_Prev_Entry(pos, type, member); \
 202              !List_Entry_Is_Head(pos, head, member); \
 203              pos = n, n = List_Prev_Entry(n, type, member))
 204
 205 /*
 206  * Reset a stale List_For_Each_Entry_Safe loop
 207  */
 208 #define List_Safe_Reset_Next(pos, n, type, member) \
 209         n = List_Next_Entry(pos, type, member)
 210
 211 static inline qbool List_Is_Empty(const llist_t *list)
 212 {
 213         return list->next == list;
 214 }
 215
 216 /*
 217  * Creates a new linked list. Initializes the head to point to itself.
 218  * If it's a list header, the result is an empty list.
 219  */
 220 static inline void List_Create(llist_t *list)
 221 {
 222         list->next = list->prev = list;
 223 }
 224
 225 /*
 226  * Insert a node between two known nodes.
 227  *
 228  * Only use when prev and next are known.
 229  */
 230 static inline void __List_Add(llist_t *node, llist_t *prev, llist_t *next)
 231 {
 232         next->prev = node;
 233         node->next = next;
 234         node->prev = prev;
 235         prev->next = node;
 236 }
 237
 238 /*
 239  * Insert a node immediately after head.
 240  */
 241 static inline void List_Add(llist_t *node, llist_t *head)
 242 {
 243         __List_Add(node, head, head->next);
 244 }
 245
 246 /*
 247  * Insert a node immediately before head.
 248  */
 249 static inline void List_Add_Tail(llist_t *node, llist_t *head)
 250 {
 251         __List_Add(node, head->prev, head);
 252 }
 253
 254 /*
 255  * Bridge prev and next together, when removing the parent of them.
 256  */
 257 static inline void __List_Delete(llist_t *prev, llist_t *next)
 258 {
 259         next->prev = prev;
 260         prev->next = next;
 261 }
 262
 263 /*
 264  * Redundant?
 265  */
 266 static inline void __List_Delete_Node(llist_t *node)
 267 {
 268         __List_Delete(node->prev, node->next);
 269 }
 270
 271 /*
 272  * Removes a node from its list. Sets its pointers to NULL.
 273  */
 274 static inline void List_Delete(llist_t *node)
 275 {
 276         __List_Delete_Node(node);
 277         node->next = node->prev = NULL;
 278 }
 279
 280 /*
 281  * Removes a node from its list. Reinitialize it.
 282  */
 283 static inline void List_Delete_Init(llist_t *node)
 284 {
 285         __List_Delete_Node(node);
 286         node->next = node->prev = node;
 287 }
 288
 289 /*
 290  * Replace old with new. Old is overwritten if empty.
 291  */
 292 static inline void List_Replace(llist_t *old, llist_t *_new)
 293 {
 294         _new->next = old->next;
 295         _new->next->prev = _new;
 296         _new->prev = old->prev;
 297         _new->prev->next = _new;
 298         old->next = old->prev = old;
 299 }
 300
 301 /*
 302  * Replace old with new. Initialize old.
 303  * Old is overwritten if empty.
 304  */
 305 static inline void List_Replace_Init(llist_t *old, llist_t *_new)
 306 {
 307         List_Replace(old, _new);
 308         List_Create(old);
 309 }
 310
 311 /*
 312  * Swap node1 with node2 in place.
 313  */
 314 static inline void List_Swap(llist_t *node1, llist_t *node2)
 315 {
 316         llist_t *pos = node2->prev;
 317         List_Delete_Init(node2);
 318         List_Replace(node1, node2);
 319         if(pos == node1)
 320                 pos = node2;
 321         List_Add(node1, pos);
 322 }
 323
 324 /*
 325  * Delete list from its... list, then insert after head.
 326  */
 327 static inline void List_Move(llist_t *list, llist_t *head)
 328 {
 329         __List_Delete_Node(list);
 330         List_Add(list, head);
 331 }
 332
 333 /*
 334  * Delete list from its... list, then insert before head.
 335  */
 336 static inline void List_Move_Tail(llist_t *list, llist_t *head)
 337 {
 338         __List_Delete_Node(list);
 339         List_Add_Tail(list, head);
 340 }
 341
 342 /*
 343  * Move the first node of a range of nodes immediately after head.
 344  * All three parameters must belong to the same list.
 345  */
 346
 347 static inline void List_Bulk_Move_Tail(llist_t *head, llist_t *first, llist_t *last)
 348 {
 349         first->prev->next = last->next;
 350         last->next->prev = first->prev;
 351
 352         head->prev->next = first;
 353         first->prev = head->prev;
 354
 355         last->next = head;
 356         head->prev = last;
 357 }
 358
 359 /*
 360  * Shift the head to the right (like rotating a wheel counterclockwise).
 361  * The node immediately to the right becomes the new head.
 362  */
 363 static inline void List_Rotate_Left(llist_t *head)
 364 {
 365         llist_t *first;
 366
 367         if (!List_Is_Empty(head))
 368         {
 369                 first = head->next;
 370                 List_Move_Tail(first, head);
 371         }
 372 }
 373
 374 /*
 375  * Make list the new head.
 376  */
 377 static inline void List_Rotate_To_Front(llist_t *list, llist_t *head)
 378 {
 379         List_Move_Tail(head, list);
 380 }
 381
 382 /*
 383  * Concatenate two lists. The head of list will be discarded.
 384  */
 385 static inline void __List_Splice(const llist_t *list, llist_t *prev, llist_t *next)
 386 {
 387         llist_t *first = list->next;
 388         llist_t *last = list->prev;
 389
 390         first->prev = prev;
 391         prev->next = first;
 392
 393         last->next = next;
 394         next->prev = last;
 395 }
 396
 397 /*
 398  * Concatenate two lists. The first node of list will be inserted after head.
 399  */
 400 static inline void List_Splice(const llist_t *list, llist_t *head)
 401 {
 402         if(!List_Is_Empty(list))
 403                 __List_Splice(list, head, head->next);
 404 }
 405
 406 /*
 407  * Concatenate two lists. The tail of list will be inserted before head.
 408  */
 409 static inline void List_Splice_Tail(const llist_t *list, llist_t *head)
 410 {
 411         if (!List_Is_Empty(list))
 412                 __List_Splice(list, head->prev, head);
 413 }
 414
 415 static inline qbool List_Is_First(llist_t *list, llist_t *start)
 416 {
 417         return list->prev == start;
 418 }
 419
 420 static inline qbool List_Is_Last(llist_t *list, llist_t *start)
 421 {
 422         return list->next == start;
 423 }
 424
 425 #endif