]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2008, 2009 Nicira Networks. | |
3 | * | |
4 | * Permission to use, copy, modify, and/or distribute this software for any | |
5 | * purpose with or without fee is hereby granted, provided that the above | |
6 | * copyright notice and this permission notice appear in all copies. | |
7 | * | |
8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
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 | /* Inserts 'elem' just before 'before'. */ | |
28 | void | |
29 | list_insert(struct list *before, struct list *elem) | |
30 | { | |
31 | elem->prev = before->prev; | |
32 | elem->next = before; | |
33 | before->prev->next = elem; | |
34 | before->prev = elem; | |
35 | } | |
36 | ||
37 | /* Removes elements 'first' though 'last' (exclusive) from their current list, | |
38 | then inserts them just before 'before'. */ | |
39 | void | |
40 | list_splice(struct list *before, struct list *first, struct list *last) | |
41 | { | |
42 | if (first == last) | |
43 | return; | |
44 | last = last->prev; | |
45 | ||
46 | /* Cleanly remove 'first'...'last' from its current list. */ | |
47 | first->prev->next = last->next; | |
48 | last->next->prev = first->prev; | |
49 | ||
50 | /* Splice 'first'...'last' into new list. */ | |
51 | first->prev = before->prev; | |
52 | last->next = before; | |
53 | before->prev->next = first; | |
54 | before->prev = last; | |
55 | } | |
56 | ||
57 | /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in | |
58 | 'list'. */ | |
59 | void | |
60 | list_push_front(struct list *list, struct list *elem) | |
61 | { | |
62 | list_insert(list->next, elem); | |
63 | } | |
64 | ||
65 | /* Inserts 'elem' at the end of 'list', so that it becomes the back in | |
66 | * 'list'. */ | |
67 | void | |
68 | list_push_back(struct list *list, struct list *elem) | |
69 | { | |
70 | list_insert(list, elem); | |
71 | } | |
72 | ||
73 | /* Puts 'elem' in the position currently occupied by 'position'. | |
74 | * Afterward, 'position' is not part of a list. */ | |
75 | void | |
76 | list_replace(struct list *element, const struct list *position) | |
77 | { | |
78 | element->next = position->next; | |
79 | element->next->prev = element; | |
80 | element->prev = position->prev; | |
81 | element->prev->next = element; | |
82 | } | |
83 | ||
84 | /* Adjusts pointers around 'list' to compensate for 'list' having been moved | |
85 | * around in memory (e.g. as a consequence of realloc()). */ | |
86 | void | |
87 | list_moved(struct list *list) | |
88 | { | |
89 | list->prev->next = list->next->prev = list; | |
90 | } | |
91 | ||
92 | /* Removes 'elem' from its list and returns the element that followed it. | |
93 | Undefined behavior if 'elem' is not in a list. */ | |
94 | struct list * | |
95 | list_remove(struct list *elem) | |
96 | { | |
97 | elem->prev->next = elem->next; | |
98 | elem->next->prev = elem->prev; | |
99 | return elem->next; | |
100 | } | |
101 | ||
102 | /* Removes the front element from 'list' and returns it. Undefined behavior if | |
103 | 'list' is empty before removal. */ | |
104 | struct list * | |
105 | list_pop_front(struct list *list) | |
106 | { | |
107 | struct list *front = list->next; | |
108 | list_remove(front); | |
109 | return front; | |
110 | } | |
111 | ||
112 | /* Removes the back element from 'list' and returns it. | |
113 | Undefined behavior if 'list' is empty before removal. */ | |
114 | struct list * | |
115 | list_pop_back(struct list *list) | |
116 | { | |
117 | struct list *back = list->prev; | |
118 | list_remove(back); | |
119 | return back; | |
120 | } | |
121 | ||
122 | /* Returns the front element in 'list'. | |
123 | Undefined behavior if 'list' is empty. */ | |
124 | struct list * | |
125 | list_front(struct list *list) | |
126 | { | |
127 | assert(!list_is_empty(list)); | |
128 | return list->next; | |
129 | } | |
130 | ||
131 | /* Returns the back element in 'list'. | |
132 | Undefined behavior if 'list' is empty. */ | |
133 | struct list * | |
134 | list_back(struct list *list) | |
135 | { | |
136 | assert(!list_is_empty(list)); | |
137 | return list->prev; | |
138 | } | |
139 | ||
140 | /* Returns the number of elements in 'list'. | |
141 | Runs in O(n) in the number of elements. */ | |
142 | size_t | |
143 | list_size(const struct list *list) | |
144 | { | |
145 | const struct list *e; | |
146 | size_t cnt = 0; | |
147 | ||
148 | for (e = list->next; e != list; e = e->next) | |
149 | cnt++; | |
150 | return cnt; | |
151 | } | |
152 | ||
153 | /* Returns true if 'list' is empty, false otherwise. */ | |
154 | bool | |
155 | list_is_empty(const struct list *list) | |
156 | { | |
157 | return list->next == list; | |
158 | } |