include/urcu/hlist.h

   1 // SPDX-FileCopyrightText: 2009 Novell Inc.
   2 // SPDX-FileCopyrightText: 2010-2013 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   3 //
   4 // SPDX-License-Identifier: LGPL-2.1-only
   5
   6 #ifndef _KCOMPAT_HLIST_H
   7 #define _KCOMPAT_HLIST_H
   8
   9 /*
  10  * Kernel sourcecode compatible lightweight single pointer list head useful
  11  * for implementing hash tables
  12  *
  13  * Author: Jan Blunck <jblunck@suse.de>
  14  */
  15
  16 #include <stddef.h>
  17 #include <urcu/compiler.h>
  18
  19 struct cds_hlist_head {
  20         struct cds_hlist_node *next;
  21 };
  22
  23 struct cds_hlist_node {
  24         struct cds_hlist_node *next, *prev;
  25 };
  26
  27 /* Initialize a new list head. */
  28 static inline
  29 void CDS_INIT_HLIST_HEAD(struct cds_hlist_head *ptr)
  30 {
  31         ptr->next = NULL;
  32 }
  33
  34 #define CDS_HLIST_HEAD(name) \
  35         struct cds_hlist_head name = { NULL }
  36
  37 #define CDS_HLIST_HEAD_INIT(name) \
  38         { .next = NULL }
  39
  40 /* Get typed element from list at a given position. */
  41 #define cds_hlist_entry(ptr, type, member)      caa_container_of(ptr, type, member)
  42
  43 /* Get typed element from list at a given position, keeping NULL pointers. */
  44 #define cds_hlist_entry_safe(ptr, type, member)                                 \
  45         ({                                                                      \
  46                 __typeof__(ptr) ____ret = (ptr);                                \
  47                 ____ret ? cds_hlist_entry(____ret, type, member) : NULL;        \
  48         })
  49
  50 /* Add new element at the head of the list. */
  51 static inline
  52 void cds_hlist_add_head(struct cds_hlist_node *newp,
  53                 struct cds_hlist_head *head)
  54 {
  55         if (head->next)
  56                 head->next->prev = newp;
  57         newp->next = head->next;
  58         newp->prev = (struct cds_hlist_node *) head;
  59         head->next = newp;
  60 }
  61
  62 /* Remove element from list. */
  63 static inline
  64 void cds_hlist_del(struct cds_hlist_node *elem)
  65 {
  66         if (elem->next)
  67                 elem->next->prev = elem->prev;
  68         elem->prev->next = elem->next;
  69 }
  70
  71 #define cds_hlist_for_each(pos, head) \
  72         for (pos = (head)->next; (pos) != NULL; pos = (pos)->next)
  73
  74 #define cds_hlist_for_each_safe(pos, p, head) \
  75         for (pos = (head)->next; \
  76                 ((pos) != NULL) && (p = (pos)->next, 1); \
  77                 pos = (p))
  78
  79 /*
  80  * cds_hlist_for_each_entry and cds_hlist_for_each_entry_safe take
  81  * respectively 4 and 5 arguments, while the Linux kernel APIs take 3,
  82  * and 4. We implement cds_hlist_for_each_entry_2() and
  83  * cds_hlist_for_each_entry_safe_2() to follow the Linux kernel APIs.
  84  */
  85 #define cds_hlist_for_each_entry(entry, pos, head, member) \
  86         for (pos = (head)->next, \
  87                         entry = cds_hlist_entry(pos, __typeof__(*(entry)), member); \
  88                 (pos) != NULL; \
  89                 pos = (pos)->next, \
  90                         entry = cds_hlist_entry(pos, __typeof__(*(entry)), member))
  91
  92 #define cds_hlist_for_each_entry_safe(entry, pos, p, head, member) \
  93         for (pos = (head)->next, \
  94                         entry = cds_hlist_entry(pos, __typeof__(*(entry)), member); \
  95                 ((pos) != NULL) && (p = (pos)->next, 1); \
  96                 pos = (p), \
  97                         entry = cds_hlist_entry(pos, __typeof__(*entry), member))
  98
  99 #define cds_hlist_for_each_entry_2(entry, head, member) \
 100         for (entry = cds_hlist_entry_safe((head)->next, __typeof__(*(entry)), member); \
 101                 (entry) != NULL; \
 102                 entry = cds_hlist_entry_safe((entry)->member.next, __typeof__(*(entry)), member))
 103
 104 #define cds_hlist_for_each_entry_safe_2(entry, e, head, member) \
 105         for (entry = cds_hlist_entry_safe((head)->next, __typeof__(*(entry)), member); \
 106                 ((entry) != NULL) && (e = (cds_hlist_entry_safe((entry)->member.next, \
 107                                                 __typeof__(*(entry)), member)), 1); \
 108                 entry = e)
 109
 110 #endif  /* _KCOMPAT_HLIST_H */