BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file LinkedList1.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 * @section DESCRIPTION
30 *
31 * Simple doubly linked list.
32 */
33  
34 #ifndef BADVPN_STRUCTURE_LINKEDLIST1_H
35 #define BADVPN_STRUCTURE_LINKEDLIST1_H
36  
37 #include <stddef.h>
38  
39 #include <misc/debug.h>
40  
41 /**
42 * Linked list node.
43 */
44 typedef struct LinkedList1Node_t
45 {
46 struct LinkedList1Node_t *p;
47 struct LinkedList1Node_t *n;
48 } LinkedList1Node;
49  
50 /**
51 * Simple doubly linked list.
52 */
53 typedef struct
54 {
55 LinkedList1Node *first;
56 LinkedList1Node *last;
57 } LinkedList1;
58  
59 /**
60 * Initializes the linked list.
61 *
62 * @param list list to initialize
63 */
64 static void LinkedList1_Init (LinkedList1 *list);
65  
66 /**
67 * Determines if the list is empty.
68 *
69 * @param list the list
70 * @return 1 if empty, 0 if not
71 */
72 static int LinkedList1_IsEmpty (LinkedList1 *list);
73  
74 /**
75 * Returns the first node of the list.
76 *
77 * @param list the list
78 * @return first node of the list, or NULL if the list is empty
79 */
80 static LinkedList1Node * LinkedList1_GetFirst (LinkedList1 *list);
81  
82 /**
83 * Returns the last node of the list.
84 *
85 * @param list the list
86 * @return last node of the list, or NULL if the list is empty
87 */
88 static LinkedList1Node * LinkedList1_GetLast (LinkedList1 *list);
89  
90 /**
91 * Inserts a node to the beginning of the list.
92 *
93 * @param list the list
94 * @param node uninitialized node to insert
95 */
96 static void LinkedList1_Prepend (LinkedList1 *list, LinkedList1Node *node);
97  
98 /**
99 * Inserts a node to the end of the list.
100 *
101 * @param list the list
102 * @param node uninitialized node to insert
103 */
104 static void LinkedList1_Append (LinkedList1 *list, LinkedList1Node *node);
105  
106 /**
107 * Inserts a node before a given node.
108 *
109 * @param list the list
110 * @param node uninitialized node to insert
111 * @param target node in the list to insert before
112 */
113 static void LinkedList1_InsertBefore (LinkedList1 *list, LinkedList1Node *node, LinkedList1Node *target);
114  
115 /**
116 * Inserts a node after a given node.
117 *
118 * @param list the list
119 * @param node uninitialized node to insert
120 * @param target node in the list to insert after
121 */
122 static void LinkedList1_InsertAfter (LinkedList1 *list, LinkedList1Node *node, LinkedList1Node *target);
123  
124 /**
125 * Removes a node from the list.
126 *
127 * @param list the list
128 * @param node node to remove
129 */
130 static void LinkedList1_Remove (LinkedList1 *list, LinkedList1Node *node);
131  
132 /**
133 * Inserts the nodes in the list \a ins_list into this list, after the node \a target.
134 * If \a target is NULL, the nodes are inserted to the beginning.
135 * Note that because the first and last node in \a ins_list are modified
136 * (unless the list is empty), \a ins_list is invalidated and must no longer
137 * be used to access the inserted nodes.
138 */
139 static void LinkedList1_InsertListAfter (LinkedList1 *list, LinkedList1 ins_list, LinkedList1Node *target);
140  
141 /**
142 * Returns the next node of a given node.
143 *
144 * @param node reference node
145 * @return next node, or NULL if none
146 */
147 static LinkedList1Node * LinkedList1Node_Next (LinkedList1Node *node);
148  
149 /**
150 * Returns the previous node of a given node.
151 *
152 * @param node reference node
153 * @return previous node, or NULL if none
154 */
155 static LinkedList1Node * LinkedList1Node_Prev (LinkedList1Node *node);
156  
157 void LinkedList1_Init (LinkedList1 *list)
158 {
159 list->first = NULL;
160 list->last = NULL;
161 }
162  
163 int LinkedList1_IsEmpty (LinkedList1 *list)
164 {
165 return (!list->first);
166 }
167  
168 LinkedList1Node * LinkedList1_GetFirst (LinkedList1 *list)
169 {
170 return (list->first);
171 }
172  
173 LinkedList1Node * LinkedList1_GetLast (LinkedList1 *list)
174 {
175 return (list->last);
176 }
177  
178 void LinkedList1_Prepend (LinkedList1 *list, LinkedList1Node *node)
179 {
180 node->p = NULL;
181 node->n = list->first;
182 if (list->first) {
183 list->first->p = node;
184 } else {
185 list->last = node;
186 }
187 list->first = node;
188 }
189  
190 void LinkedList1_Append (LinkedList1 *list, LinkedList1Node *node)
191 {
192 node->p = list->last;
193 node->n = NULL;
194 if (list->last) {
195 list->last->n = node;
196 } else {
197 list->first = node;
198 }
199 list->last = node;
200 }
201  
202 void LinkedList1_InsertBefore (LinkedList1 *list, LinkedList1Node *node, LinkedList1Node *target)
203 {
204 node->p = target->p;
205 node->n = target;
206 if (target->p) {
207 target->p->n = node;
208 } else {
209 list->first = node;
210 }
211 target->p = node;
212 }
213  
214 void LinkedList1_InsertAfter (LinkedList1 *list, LinkedList1Node *node, LinkedList1Node *target)
215 {
216 node->p = target;
217 node->n = target->n;
218 if (target->n) {
219 target->n->p = node;
220 } else {
221 list->last = node;
222 }
223 target->n = node;
224 }
225  
226 void LinkedList1_Remove (LinkedList1 *list, LinkedList1Node *node)
227 {
228 // remove from list
229 if (node->p) {
230 node->p->n = node->n;
231 } else {
232 list->first = node->n;
233 }
234 if (node->n) {
235 node->n->p = node->p;
236 } else {
237 list->last = node->p;
238 }
239 }
240  
241 void LinkedList1_InsertListAfter (LinkedList1 *list, LinkedList1 ins_list, LinkedList1Node *target)
242 {
243 if (!ins_list.first) {
244 return;
245 }
246  
247 LinkedList1Node *t_next = (target ? target->n : list->first);
248  
249 ins_list.first->p = target;
250 ins_list.last->n = t_next;
251  
252 if (target) {
253 target->n = ins_list.first;
254 } else {
255 list->first = ins_list.first;
256 }
257  
258 if (t_next) {
259 t_next->p = ins_list.last;
260 } else {
261 list->last = ins_list.last;
262 }
263 }
264  
265 LinkedList1Node * LinkedList1Node_Next (LinkedList1Node *node)
266 {
267 return node->n;
268 }
269  
270 LinkedList1Node * LinkedList1Node_Prev (LinkedList1Node *node)
271 {
272 return node->p;
273 }
274  
275 #endif