]>
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 | { | |
47ab7668 BP |
39 | elem->prev = before->prev; |
40 | elem->next = before; | |
41 | before->prev->next = elem; | |
42 | before->prev = elem; | |
064af421 BP |
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 | { | |
47ab7668 BP |
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; | |
064af421 BP |
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 | { | |
47ab7668 | 70 | list_insert(list->next, elem); |
064af421 BP |
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 | { | |
47ab7668 | 78 | list_insert(list, elem); |
064af421 BP |
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 | { | |
47ab7668 BP |
105 | elem->prev->next = elem->next; |
106 | elem->next->prev = elem->prev; | |
107 | return elem->next; | |
064af421 BP |
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 | { | |
47ab7668 BP |
115 | struct list *front = list->next; |
116 | list_remove(front); | |
117 | return front; | |
064af421 BP |
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 | { | |
47ab7668 BP |
125 | struct list *back = list->prev; |
126 | list_remove(back); | |
127 | return back; | |
064af421 BP |
128 | } |
129 | ||
0574c613 BP |
130 | /* Returns the front element in 'list_'. |
131 | Undefined behavior if 'list_' is empty. */ | |
064af421 | 132 | struct list * |
0574c613 | 133 | list_front(const struct list *list_) |
064af421 | 134 | { |
0574c613 BP |
135 | struct list *list = (struct list *) list_; |
136 | ||
47ab7668 BP |
137 | assert(!list_is_empty(list)); |
138 | return list->next; | |
064af421 BP |
139 | } |
140 | ||
0574c613 BP |
141 | /* Returns the back element in 'list_'. |
142 | Undefined behavior if 'list_' is empty. */ | |
064af421 | 143 | struct list * |
0574c613 | 144 | list_back(const struct list *list_) |
064af421 | 145 | { |
0574c613 BP |
146 | struct list *list = (struct list *) list_; |
147 | ||
47ab7668 BP |
148 | assert(!list_is_empty(list)); |
149 | return list->prev; | |
064af421 BP |
150 | } |
151 | ||
152 | /* Returns the number of elements in 'list'. | |
153 | Runs in O(n) in the number of elements. */ | |
154 | size_t | |
155 | list_size(const struct list *list) | |
156 | { | |
47ab7668 BP |
157 | const struct list *e; |
158 | size_t cnt = 0; | |
064af421 | 159 | |
47ab7668 BP |
160 | for (e = list->next; e != list; e = e->next) |
161 | cnt++; | |
162 | return cnt; | |
064af421 BP |
163 | } |
164 | ||
165 | /* Returns true if 'list' is empty, false otherwise. */ | |
166 | bool | |
167 | list_is_empty(const struct list *list) | |
168 | { | |
47ab7668 | 169 | return list->next == list; |
064af421 | 170 | } |