1 /*
2 * Copyright (C) Mellanox Technologies Ltd. 2001-2014. ALL RIGHTS RESERVED.
3 *
4 * See file LICENSE for terms.
5 */
6
7 #ifndef UCS_LIST_H_
8 #define UCS_LIST_H_
9
10 #include <ucs/sys/compiler_def.h>
11
12
13 BEGIN_C_DECLS
14
15 #define UCS_LIST_INITIALIZER(_prev, _next) \
16 { (_prev), (_next) }
17
18
19 /**
20 * Declare an empty list
21 */
22 #define UCS_LIST_HEAD(name) \
23 ucs_list_link_t name = UCS_LIST_INITIALIZER(&(name), &(name))
24
25
26 /**
27 * A link in a circular list.
28 */
29 typedef struct ucs_list_link {
30 struct ucs_list_link *prev;
31 struct ucs_list_link *next;
32 } ucs_list_link_t;
33
34
35 /**
36 * Initialize list head.
37 *
38 * @param head List head struct to initialize.
39 */
ucs_list_head_init(ucs_list_link_t * head)40 static inline void ucs_list_head_init(ucs_list_link_t *head)
41 {
42 head->prev = head->next = head;
43 }
44
45 /**
46 * Insert an element in-between to list elements. Any elements which were in this
47 * section will be discarded.
48 *
49 * @param prev Element to insert after
50 * @param next Element to insert before.
51 */
ucs_list_insert_replace(ucs_list_link_t * prev,ucs_list_link_t * next,ucs_list_link_t * elem)52 static inline void ucs_list_insert_replace(ucs_list_link_t *prev,
53 ucs_list_link_t *next,
54 ucs_list_link_t *elem)
55 {
56 elem->prev = prev;
57 elem->next = next;
58 prev->next = elem;
59 next->prev = elem;
60 }
61
62 /**
63 * Replace an element in a list with another element.
64 *
65 * @param elem Element in the list to replace.
66 * @param replacement New element to insert in place of 'elem'.
67 */
ucs_list_replace(ucs_list_link_t * elem,ucs_list_link_t * replacement)68 static inline void ucs_list_replace(ucs_list_link_t *elem,
69 ucs_list_link_t *replacement)
70 {
71 ucs_list_insert_replace(elem->prev, elem->next, replacement);
72 }
73
74 /**
75 * Insert an item to a list after another item.
76 *
77 * @param pos Item after which to insert.
78 * @param new_link Item to insert.
79 */
ucs_list_insert_after(ucs_list_link_t * pos,ucs_list_link_t * new_link)80 static inline void ucs_list_insert_after(ucs_list_link_t *pos,
81 ucs_list_link_t *new_link)
82 {
83 ucs_list_insert_replace(pos, pos->next, new_link);
84 }
85
86 /**
87 * Insert an item to a list before another item.
88 *
89 * @param pos Item before which to insert.
90 * @param new_link Item to insert.
91 */
ucs_list_insert_before(ucs_list_link_t * pos,ucs_list_link_t * new_link)92 static inline void ucs_list_insert_before(ucs_list_link_t *pos,
93 ucs_list_link_t *new_link)
94 {
95 ucs_list_insert_replace(pos->prev, pos, new_link);
96 }
97
98 /**
99 * Remove an item from its list.
100 *
101 * @param link Item to remove.
102 */
ucs_list_del(ucs_list_link_t * elem)103 static inline void ucs_list_del(ucs_list_link_t *elem)
104 {
105 elem->prev->next = elem->next;
106 elem->next->prev = elem->prev;
107 }
108
109 /**
110 * @return Whether the list is empty.
111 */
ucs_list_is_empty(ucs_list_link_t * head)112 static inline int ucs_list_is_empty(ucs_list_link_t *head)
113 {
114 return head->next == head;
115 }
116
117 /**
118 * Move the items from 'newlist' to the tail of the list pointed by 'head'
119 *
120 * @param head List to whose tail to add the items.
121 * @param newlist List of items to add.
122 *
123 * @note The contents of 'newlist' is left unmodified.
124 */
ucs_list_splice_tail(ucs_list_link_t * head,ucs_list_link_t * newlist)125 static inline void ucs_list_splice_tail(ucs_list_link_t *head,
126 ucs_list_link_t *newlist)
127 {
128 ucs_list_link_t *first, *last, *tail;
129
130 if (ucs_list_is_empty(newlist)) {
131 return;
132 }
133
134 first = newlist->next; /* First element in the new list */
135 last = newlist->prev; /* Last element in the new list */
136 tail = head->prev; /* Last element in the original list */
137
138 first->prev = tail;
139 tail->next = first;
140
141 last->next = head;
142 head->prev = last;
143 }
144
145 /**
146 * Count the members of the list
147 */
ucs_list_length(ucs_list_link_t * head)148 static inline unsigned long ucs_list_length(ucs_list_link_t *head)
149 {
150 unsigned long length;
151 ucs_list_link_t *ptr;
152
153 for (ptr = head->next, length = 0; ptr != head; ptr = ptr->next, ++length);
154 return length;
155 }
156
157 /*
158 * Convenience macros
159 */
160 #define ucs_list_add_head(_head, _item) \
161 ucs_list_insert_after(_head, _item)
162 #define ucs_list_add_tail(_head, _item) \
163 ucs_list_insert_before(_head, _item)
164
165 /**
166 * Get the previous element in the list
167 */
168 #define ucs_list_prev(_elem, _type, _member) \
169 (ucs_container_of((_elem)->prev, _type, _member))
170
171 /**
172 * Get the next element in the list
173 */
174 #define ucs_list_next(_elem, _type, _member) \
175 (ucs_container_of((_elem)->next, _type, _member))
176
177 /**
178 * Get the first element in the list
179 */
180 #define ucs_list_head ucs_list_next
181
182 /**
183 * Get the last element in the list
184 */
185 #define ucs_list_tail ucs_list_prev
186
187 /**
188 * Iterate over members of the list.
189 */
190 #define ucs_list_for_each(_elem, _head, _member) \
191 for (_elem = ucs_container_of((_head)->next, typeof(*_elem), _member); \
192 &(_elem)->_member != (_head); \
193 _elem = ucs_container_of((_elem)->_member.next, typeof(*_elem), _member))
194
195 /**
196 * Iterate over members of the list, the user may invalidate the current entry.
197 */
198 #define ucs_list_for_each_safe(_elem, _telem, _head, _member) \
199 for (_elem = ucs_container_of((_head)->next, typeof(*_elem), _member), \
200 _telem = ucs_container_of(_elem->_member.next, typeof(*_elem), _member); \
201 &_elem->_member != (_head); \
202 _elem = _telem, \
203 _telem = ucs_container_of(_telem->_member.next, typeof(*_telem), _member))
204
205 /**
206 * Extract list head
207 */
208 #define ucs_list_extract_head(_head, _type, _member) \
209 ({ \
210 ucs_list_link_t *tmp = (_head)->next; \
211 ucs_list_del(tmp); \
212 ucs_container_of(tmp, _type, _member); \
213 })
214
215 END_C_DECLS
216
217 #endif
218