← Back to branch summary

~ubuntu-branches/ubuntu/wily/openvswitch/wily

« back to all changes in this revision

Viewing changes to lib/list.h

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2015-08-10 11:35:15 UTC
  • mfrom: (1.1.30)
  • Revision ID: package-import@ubuntu.com-20150810113515-575vj06oq29emxsn
Tags: 2.4.0~git20150810.97bab95-0ubuntu1
* New upstream snapshot from 2.4 branch:
  - d/*: Align any relevant packaging changes with upstream.
* d/*: wrap-and-sort.
* d/openvswitch-{common,vswitch}.install: Correct install location for
  bash completion files.
* d/tests/openflow.py: Explicitly use ovs-testcontroller as provided
  by 2.4.0 release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/list.h
21
21
#include <stdbool.h>
22
22
#include <stddef.h>
23
23
#include "util.h"
24
 
 
25
 
/* Doubly linked list head or element. */
26
 
struct list {
27
 
    struct list *prev;     /* Previous list element. */
28
 
    struct list *next;     /* Next list element. */
29
 
};
30
 
 
31
 
#define LIST_INITIALIZER(LIST) { LIST, LIST }
32
 
 
33
 
void list_init(struct list *);
34
 
void list_poison(struct list *);
 
24
#include "openvswitch/list.h"
 
25
 
 
26
static inline void list_init(struct ovs_list *);
 
27
static inline void list_poison(struct ovs_list *);
35
28
 
36
29
/* List insertion. */
37
 
void list_insert(struct list *, struct list *);
38
 
void list_splice(struct list *before, struct list *first, struct list *last);
39
 
void list_push_front(struct list *, struct list *);
40
 
void list_push_back(struct list *, struct list *);
41
 
void list_replace(struct list *, const struct list *);
42
 
void list_moved(struct list *, const struct list *orig);
43
 
void list_move(struct list *dst, struct list *src);
 
30
static inline void list_insert(struct ovs_list *, struct ovs_list *);
 
31
static inline void list_splice(struct ovs_list *before, struct ovs_list *first,
 
32
                               struct ovs_list *last);
 
33
static inline void list_push_front(struct ovs_list *, struct ovs_list *);
 
34
static inline void list_push_back(struct ovs_list *, struct ovs_list *);
 
35
static inline void list_replace(struct ovs_list *, const struct ovs_list *);
 
36
static inline void list_moved(struct ovs_list *, const struct ovs_list *orig);
 
37
static inline void list_move(struct ovs_list *dst, struct ovs_list *src);
44
38
 
45
39
/* List removal. */
46
 
struct list *list_remove(struct list *);
47
 
struct list *list_pop_front(struct list *);
48
 
struct list *list_pop_back(struct list *);
 
40
static inline struct ovs_list *list_remove(struct ovs_list *);
 
41
static inline struct ovs_list *list_pop_front(struct ovs_list *);
 
42
static inline struct ovs_list *list_pop_back(struct ovs_list *);
49
43
 
50
44
/* List elements. */
51
 
struct list *list_front(const struct list *);
52
 
struct list *list_back(const struct list *);
 
45
static inline struct ovs_list *list_front(const struct ovs_list *);
 
46
static inline struct ovs_list *list_back(const struct ovs_list *);
53
47
 
54
48
/* List properties. */
55
 
size_t list_size(const struct list *);
56
 
bool list_is_empty(const struct list *);
57
 
bool list_is_singleton(const struct list *);
58
 
bool list_is_short(const struct list *);
 
49
static inline size_t list_size(const struct ovs_list *);
 
50
static inline bool list_is_empty(const struct ovs_list *);
 
51
static inline bool list_is_singleton(const struct ovs_list *);
 
52
static inline bool list_is_short(const struct ovs_list *);
59
53
 
60
54
#define LIST_FOR_EACH(ITER, MEMBER, LIST)                               \
61
 
    for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER);                  \
 
55
    for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER);                    \
62
56
         &(ITER)->MEMBER != (LIST);                                     \
63
57
         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER))
64
58
#define LIST_FOR_EACH_CONTINUE(ITER, MEMBER, LIST)                      \
65
 
    for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER);           \
 
59
    for (INIT_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER);             \
66
60
         &(ITER)->MEMBER != (LIST);                                     \
67
61
         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER))
68
62
#define LIST_FOR_EACH_REVERSE(ITER, MEMBER, LIST)                       \
69
 
    for (ASSIGN_CONTAINER(ITER, (LIST)->prev, MEMBER);                  \
 
63
    for (INIT_CONTAINER(ITER, (LIST)->prev, MEMBER);                    \
70
64
         &(ITER)->MEMBER != (LIST);                                     \
71
65
         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
72
66
#define LIST_FOR_EACH_REVERSE_CONTINUE(ITER, MEMBER, LIST)              \
74
68
         &(ITER)->MEMBER != (LIST);                                     \
75
69
         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
76
70
#define LIST_FOR_EACH_SAFE(ITER, NEXT, MEMBER, LIST)               \
77
 
    for (ASSIGN_CONTAINER(ITER, (LIST)->next, MEMBER);             \
 
71
    for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER);               \
78
72
         (&(ITER)->MEMBER != (LIST)                                \
79
 
          ? ASSIGN_CONTAINER(NEXT, (ITER)->MEMBER.next, MEMBER), 1 \
 
73
          ? INIT_CONTAINER(NEXT, (ITER)->MEMBER.next, MEMBER), 1   \
80
74
          : 0);                                                    \
81
75
         (ITER) = (NEXT))
 
76
#define LIST_FOR_EACH_POP(ITER, MEMBER, LIST)                      \
 
77
    while (!list_is_empty(LIST)                                    \
 
78
           && (INIT_CONTAINER(ITER, list_pop_front(LIST), MEMBER), 1))
 
79
 
 
80
/* Inline implementations. */
 
81
 
 
82
/* Initializes 'list' as an empty list. */
 
83
static inline void
 
84
list_init(struct ovs_list *list)
 
85
{
 
86
    list->next = list->prev = list;
 
87
}
 
88
 
 
89
/* Initializes 'list' with pointers that will (probably) cause segfaults if
 
90
 * dereferenced and, better yet, show up clearly in a debugger. */
 
91
static inline void
 
92
list_poison(struct ovs_list *list)
 
93
{
 
94
    memset(list, 0xcc, sizeof *list);
 
95
}
 
96
 
 
97
/* Inserts 'elem' just before 'before'. */
 
98
static inline void
 
99
list_insert(struct ovs_list *before, struct ovs_list *elem)
 
100
{
 
101
    elem->prev = before->prev;
 
102
    elem->next = before;
 
103
    before->prev->next = elem;
 
104
    before->prev = elem;
 
105
}
 
106
 
 
107
/* Removes elements 'first' though 'last' (exclusive) from their current list,
 
108
   then inserts them just before 'before'. */
 
109
static inline void
 
110
list_splice(struct ovs_list *before, struct ovs_list *first, struct ovs_list *last)
 
111
{
 
112
    if (first == last) {
 
113
        return;
 
114
    }
 
115
    last = last->prev;
 
116
 
 
117
    /* Cleanly remove 'first'...'last' from its current list. */
 
118
    first->prev->next = last->next;
 
119
    last->next->prev = first->prev;
 
120
 
 
121
    /* Splice 'first'...'last' into new list. */
 
122
    first->prev = before->prev;
 
123
    last->next = before;
 
124
    before->prev->next = first;
 
125
    before->prev = last;
 
126
}
 
127
 
 
128
/* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
 
129
   'list'. */
 
130
static inline void
 
131
list_push_front(struct ovs_list *list, struct ovs_list *elem)
 
132
{
 
133
    list_insert(list->next, elem);
 
134
}
 
135
 
 
136
/* Inserts 'elem' at the end of 'list', so that it becomes the back in
 
137
 * 'list'. */
 
138
static inline void
 
139
list_push_back(struct ovs_list *list, struct ovs_list *elem)
 
140
{
 
141
    list_insert(list, elem);
 
142
}
 
143
 
 
144
/* Puts 'elem' in the position currently occupied by 'position'.
 
145
 * Afterward, 'position' is not part of a list. */
 
146
static inline void
 
147
list_replace(struct ovs_list *element, const struct ovs_list *position)
 
148
{
 
149
    element->next = position->next;
 
150
    element->next->prev = element;
 
151
    element->prev = position->prev;
 
152
    element->prev->next = element;
 
153
}
 
154
 
 
155
/* Adjusts pointers around 'list' to compensate for 'list' having been moved
 
156
 * around in memory (e.g. as a consequence of realloc()), with original
 
157
 * location 'orig'.
 
158
 *
 
159
 * ('orig' likely points to freed memory, but this function does not
 
160
 * dereference 'orig', it only compares it to 'list'.  In a very pedantic
 
161
 * language lawyer sense, this still yields undefined behavior, but it works
 
162
 * with actual compilers.) */
 
163
static inline void
 
164
list_moved(struct ovs_list *list, const struct ovs_list *orig)
 
165
{
 
166
    if (list->next == orig) {
 
167
        list_init(list);
 
168
    } else {
 
169
        list->prev->next = list->next->prev = list;
 
170
    }
 
171
}
 
172
 
 
173
/* Initializes 'dst' with the contents of 'src', compensating for moving it
 
174
 * around in memory.  The effect is that, if 'src' was the head of a list, now
 
175
 * 'dst' is the head of a list containing the same elements. */
 
176
static inline void
 
177
list_move(struct ovs_list *dst, struct ovs_list *src)
 
178
{
 
179
    *dst = *src;
 
180
    list_moved(dst, src);
 
181
}
 
182
 
 
183
/* Removes 'elem' from its list and returns the element that followed it.
 
184
   Undefined behavior if 'elem' is not in a list. */
 
185
static inline struct ovs_list *
 
186
list_remove(struct ovs_list *elem)
 
187
{
 
188
    elem->prev->next = elem->next;
 
189
    elem->next->prev = elem->prev;
 
190
    return elem->next;
 
191
}
 
192
 
 
193
/* Removes the front element from 'list' and returns it.  Undefined behavior if
 
194
   'list' is empty before removal. */
 
195
static inline struct ovs_list *
 
196
list_pop_front(struct ovs_list *list)
 
197
{
 
198
    struct ovs_list *front = list->next;
 
199
 
 
200
    list_remove(front);
 
201
    return front;
 
202
}
 
203
 
 
204
/* Removes the back element from 'list' and returns it.
 
205
   Undefined behavior if 'list' is empty before removal. */
 
206
static inline struct ovs_list *
 
207
list_pop_back(struct ovs_list *list)
 
208
{
 
209
    struct ovs_list *back = list->prev;
 
210
 
 
211
    list_remove(back);
 
212
    return back;
 
213
}
 
214
 
 
215
/* Returns the front element in 'list_'.
 
216
   Undefined behavior if 'list_' is empty. */
 
217
static inline struct ovs_list *
 
218
list_front(const struct ovs_list *list_)
 
219
{
 
220
    struct ovs_list *list = CONST_CAST(struct ovs_list *, list_);
 
221
 
 
222
    ovs_assert(!list_is_empty(list));
 
223
 
 
224
    return list->next;
 
225
}
 
226
 
 
227
/* Returns the back element in 'list_'.
 
228
   Undefined behavior if 'list_' is empty. */
 
229
static inline struct ovs_list *
 
230
list_back(const struct ovs_list *list_)
 
231
{
 
232
    struct ovs_list *list = CONST_CAST(struct ovs_list *, list_);
 
233
 
 
234
    ovs_assert(!list_is_empty(list));
 
235
 
 
236
    return list->prev;
 
237
}
 
238
 
 
239
/* Returns the number of elements in 'list'.
 
240
   Runs in O(n) in the number of elements. */
 
241
static inline size_t
 
242
list_size(const struct ovs_list *list)
 
243
{
 
244
    const struct ovs_list *e;
 
245
    size_t cnt = 0;
 
246
 
 
247
    for (e = list->next; e != list; e = e->next) {
 
248
        cnt++;
 
249
    }
 
250
    return cnt;
 
251
}
 
252
 
 
253
/* Returns true if 'list' is empty, false otherwise. */
 
254
static inline bool
 
255
list_is_empty(const struct ovs_list *list)
 
256
{
 
257
    return list->next == list;
 
258
}
 
259
 
 
260
/* Returns true if 'list' has exactly 1 element, false otherwise. */
 
261
static inline bool
 
262
list_is_singleton(const struct ovs_list *list)
 
263
{
 
264
    return list_is_short(list) && !list_is_empty(list);
 
265
}
 
266
 
 
267
/* Returns true if 'list' has 0 or 1 elements, false otherwise. */
 
268
static inline bool
 
269
list_is_short(const struct ovs_list *list)
 
270
{
 
271
    return list->next == list->prev;
 
272
}
82
273
 
83
274
#endif /* list.h */