Import from old repository commit 61ef2b42a9c4ba8e1600f15bb0236765edc2ad45.
[openvswitch] / lib / list.c
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 }