]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
b3907fbc | 2 | * Copyright (c) 2008, 2009, 2010 Nicira Networks. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
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 | ||
b3907fbc BP |
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 | ||
064af421 BP |
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 | } |