queue: Get rid of ovs_queue data structure.
[sliver-openvswitch.git] / lib / list.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 #include <config.h>
17 #include "list.h"
18 #include <assert.h>
19
20 /* Initializes 'list' as an empty list. */
21 void
22 list_init(struct list *list)
23 {
24     list->next = list->prev = list;
25 }
26
27 /* Initializes 'list' with pointers that will (probably) cause segfaults if
28  * dereferenced and, better yet, show up clearly in a debugger. */
29 void
30 list_poison(struct list *list)
31 {
32     memset(list, 0xcc, sizeof *list);
33 }
34
35 /* Inserts 'elem' just before 'before'. */
36 void
37 list_insert(struct list *before, struct list *elem)
38 {
39   elem->prev = before->prev;
40   elem->next = before;
41   before->prev->next = elem;
42   before->prev = elem;
43 }
44
45 /* Removes elements 'first' though 'last' (exclusive) from their current list,
46    then inserts them just before 'before'. */
47 void
48 list_splice(struct list *before, struct list *first, struct list *last)
49 {
50   if (first == last)
51     return;
52   last = last->prev;
53
54   /* Cleanly remove 'first'...'last' from its current list. */
55   first->prev->next = last->next;
56   last->next->prev = first->prev;
57
58   /* Splice 'first'...'last' into new list. */
59   first->prev = before->prev;
60   last->next = before;
61   before->prev->next = first;
62   before->prev = last;
63 }
64
65 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
66    'list'. */
67 void
68 list_push_front(struct list *list, struct list *elem)
69 {
70   list_insert(list->next, elem);
71 }
72
73 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
74  * 'list'. */
75 void
76 list_push_back(struct list *list, struct list *elem)
77 {
78   list_insert(list, elem);
79 }
80
81 /* Puts 'elem' in the position currently occupied by 'position'.
82  * Afterward, 'position' is not part of a list. */
83 void
84 list_replace(struct list *element, const struct list *position)
85 {
86     element->next = position->next;
87     element->next->prev = element;
88     element->prev = position->prev;
89     element->prev->next = element;
90 }
91
92 /* Adjusts pointers around 'list' to compensate for 'list' having been moved
93  * around in memory (e.g. as a consequence of realloc()). */
94 void
95 list_moved(struct list *list)
96 {
97     list->prev->next = list->next->prev = list;
98 }
99
100 /* Removes 'elem' from its list and returns the element that followed it.
101    Undefined behavior if 'elem' is not in a list. */
102 struct list *
103 list_remove(struct list *elem)
104 {
105   elem->prev->next = elem->next;
106   elem->next->prev = elem->prev;
107   return elem->next;
108 }
109
110 /* Removes the front element from 'list' and returns it.  Undefined behavior if
111    'list' is empty before removal. */
112 struct list *
113 list_pop_front(struct list *list)
114 {
115   struct list *front = list->next;
116   list_remove(front);
117   return front;
118 }
119
120 /* Removes the back element from 'list' and returns it.
121    Undefined behavior if 'list' is empty before removal. */
122 struct list *
123 list_pop_back(struct list *list)
124 {
125   struct list *back = list->prev;
126   list_remove(back);
127   return back;
128 }
129
130 /* Returns the front element in 'list'.
131    Undefined behavior if 'list' is empty. */
132 struct list *
133 list_front(struct list *list)
134 {
135   assert(!list_is_empty(list));
136   return list->next;
137 }
138
139 /* Returns the back element in 'list'.
140    Undefined behavior if 'list' is empty. */
141 struct list *
142 list_back(struct list *list)
143 {
144   assert(!list_is_empty(list));
145   return list->prev;
146 }
147
148 /* Returns the number of elements in 'list'.
149    Runs in O(n) in the number of elements. */
150 size_t
151 list_size(const struct list *list)
152 {
153   const struct list *e;
154   size_t cnt = 0;
155
156   for (e = list->next; e != list; e = e->next)
157     cnt++;
158   return cnt;
159 }
160
161 /* Returns true if 'list' is empty, false otherwise. */
162 bool
163 list_is_empty(const struct list *list)
164 {
165   return list->next == list;
166 }