1 // © 2021 Qualcomm Innovation Center, Inc. All rights reserved.
2 //
3 // SPDX-License-Identifier: BSD-3-Clause
4 
5 // The list implementation consists of a circular double linked list and the
6 // list type contains a head pointer to the first element of the list.
7 
8 // All the following functions require the list to be locked if it may be
9 // accessed by other threads, unless noted otherwise.
10 
11 #include <atomic.h>
12 #include <util.h>
13 
14 void
15 list_init(list_t *list);
16 
17 list_node_t *
18 list_get_head(list_t *list);
19 
20 bool
21 list_is_empty(list_t *list);
22 
23 void
24 list_insert_at_head(list_t *list, list_node_t *node);
25 
26 void
27 list_insert_at_tail(list_t *list, list_node_t *node);
28 
29 // This function inserts a node in order, where the ordering is defined by the
30 // caller.
31 //
32 // If we want, for example, to insert a node in increasing order, then the
33 // caller needs to provide a function pointer that returns true if node a is
34 // smaller than node b, according to the caller's criteria.
35 //
36 // Returns true if the new node is placed at the head of the list, or false if
37 // the new node has been inserted after the head.
38 bool
39 list_insert_in_order(list_t *list, list_node_t *node,
40 		     bool (*compare_fn)(list_node_t *a, list_node_t *b));
41 
42 void
43 list_insert_after_node(list_t *list, list_node_t *prev, list_node_t *node);
44 
45 // The _release variants of insert must be used on any list that is iterated
46 // with a _consume iterator.
47 void
48 list_insert_at_tail_release(list_t *list, list_node_t *node);
49 
50 // This function returns true if node has been removed from head and the list is
51 // not empty after the deletion.
52 //
53 // If the list is ever iterated by a _consume iterator, then the specified node
54 // must not be either freed or added to another list until an RCU grace period
55 // has elapsed; i.e. rcu_enqueue() or rcu_sync() must be called after this
56 // function returns.
57 bool
58 list_delete_node(list_t *list, list_node_t *node);
59 
60 // Simple iterator. The list must be locked if other threads might modify it,
61 // and the iterator must not delete nodes.
62 #define list_foreach(node, list)                                               \
63 	for ((node) = atomic_load_relaxed(&(list)->head.next);                 \
64 	     (node) != &(list)->head;                                          \
65 	     (node) = atomic_load_relaxed(&(node)->next))
66 
67 #define list__foreach_container(container, list, cname, nname, n)              \
68 	list_node_t *n = atomic_load_relaxed(&list->head.next);                \
69 	container      = (n != &list->head) ? cname##_container_of_##nname(n)  \
70 					    : NULL;                            \
71 	for (; container != NULL;                                              \
72 	     n	       = atomic_load_relaxed(&n->next),                        \
73 	     container = (n != &list->head) ? cname##_container_of_##nname(n)  \
74 					    : NULL)
75 
76 // Simple container iterator. The list must be locked if other threads might
77 // modify it, and the iterator must not delete nodes.
78 #define list_foreach_container(container, list, cname, nname)                  \
79 	list__foreach_container((container), (list), cname, nname,             \
80 				util_cpp_unique_ident(node))
81 
82 #define list__foreach_container_safe(container, list, cname, nname, n, load)   \
83 	list_node_t *n = load(&list->head.next);                               \
84 	container      = (n != &list->head) ? cname##_container_of_##nname(n)  \
85 					    : NULL;                            \
86 	n	       = load(&n->next);                                       \
87 	for (; container != NULL;                                              \
88 	     container = (n != &list->head) ? cname##_container_of_##nname(n)  \
89 					    : NULL,                            \
90 	     n	       = load(&n->next))
91 
92 // Deletion-safe container iterator. The list must be locked if other threads
93 // might modify it. The iterator may delete the current node.
94 #define list_foreach_container_maydelete(container, list, cname, nname)        \
95 	list__foreach_container_safe((container), (list), cname, nname,        \
96 				     util_cpp_unique_ident(next),              \
97 				     atomic_load_relaxed)
98 
99 // RCU-safe container iterator. Must only be used within an RCU critical
100 // section. The list need not be locked, but other threads that insert nodes
101 // must use the _release variants of the insert functions, and any thread that
102 // deletes a node must allow an RCU grace period to elapse before either freeing
103 // the memory or adding it to a list again.
104 #define list_foreach_container_consume(container, list, cname, nname)          \
105 	list__foreach_container_safe((container), (list), cname, nname,        \
106 				     util_cpp_unique_ident(next),              \
107 				     atomic_load_consume)
108