- iterator for linked list implemented
[strongswan.git] / Source / charon / linked_list.c
1 /**
2 * @file linked_list.c
3 *
4 * @brief Generic Double Linked List
5 *
6 */
7
8 /*
9 * Copyright (C) 2005 Jan Hutter, Martin Willi
10 * Hochschule fuer Technik Rapperswil
11 *
12 * This program is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 2 of the License, or (at your
15 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
16 *
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 * for more details.
21 */
22
23 #include <stdlib.h>
24 #include <freeswan.h>
25 #include <pluto/constants.h>
26 #include <pluto/defs.h>
27
28 #include "linked_list.h"
29
30
31 typedef struct private_linked_list_element_s private_linked_list_element_t;
32
33
34 /**
35 * Private Data of a linked list element
36 *
37 */
38 struct private_linked_list_element_s{
39 /**
40 * public data of element
41 */
42 linked_list_element_t public;
43
44 /**
45 * previous list element
46 * NULL if first element in list
47 */
48 private_linked_list_element_t *previous;
49 /**
50 * next list element
51 * NULL if last element in list
52 */
53 private_linked_list_element_t *next;
54 };
55
56 /**
57 * @brief implements function destroy of linked_list_item_t
58 */
59 static status_t linked_list_element_destroy(private_linked_list_element_t *this)
60 {
61 if (this == NULL)
62 {
63 return FAILED;
64 }
65 pfree(this);
66 return SUCCESS;
67 }
68
69 /*
70 * Creates an empty linked list (described in header-file)
71 */
72 linked_list_element_t *linked_list_element_create(void *value)
73 {
74 private_linked_list_element_t *this = alloc_thing(private_linked_list_element_t, "private_linked_list_element_t");
75
76 if (this == NULL)
77 {
78 return NULL;
79 }
80
81 this->public.destroy = (status_t (*) (linked_list_element_t *this) ) linked_list_element_destroy;
82
83 this->previous=NULL;
84 this->next=NULL;
85 this->public.value = value;
86
87 return (&this->public);
88 }
89
90 /**
91 * Private variables and functions of linked list
92 *
93 */
94 typedef struct private_linked_list_s private_linked_list_t;
95
96 struct private_linked_list_s{
97 /**
98 * Public part of linked list
99 */
100 linked_list_t public;
101
102 /**
103 * number of items in the list
104 */
105 int count;
106
107 /**
108 * First element in list
109 * NULL if no elements in list
110 */
111 private_linked_list_element_t *first;
112 /**
113 * Last element in list
114 * NULL if no elements in list
115 */
116 private_linked_list_element_t *last;
117 };
118
119
120 /**
121 * Private variables and functions of linked list iterator
122 *
123 */
124 typedef struct private_linked_list_iterator_s private_linked_list_iterator_t;
125
126 struct private_linked_list_iterator_s{
127 /**
128 * Public part of linked list iterator
129 */
130 linked_list_iterator_t public;
131
132 /**
133 * associated linked list
134 */
135 private_linked_list_t * list;
136
137 /**
138 * current element of the iterator
139 */
140 private_linked_list_element_t *current;
141
142 /**
143 * direction of iterator
144 */
145 bool forward;
146 };
147
148 /**
149 * Implements function has_next of linked_list_iteratr
150 */
151 static status_t iterator_has_next(private_linked_list_iterator_t *this, bool * has_next)
152 {
153 if (this->list->count == 0)
154 {
155 *has_next = FALSE;
156 return SUCCESS;
157 }
158 if (this->current == NULL)
159 {
160 this->current = (this->forward) ? this->list->first : this->list->last;
161 *has_next = TRUE;
162 return SUCCESS;
163 }
164 if (this->forward)
165 {
166 if (this->current->next == NULL)
167 {
168 *has_next = FALSE;
169 return SUCCESS;
170 }
171 this->current = this->current->next;
172 *has_next = TRUE;
173 return SUCCESS;
174 }
175 /* backward */
176 if (this->current->previous == NULL)
177 {
178 *has_next = FALSE;
179 return SUCCESS;
180 }
181 this->current = this->current->previous;
182 *has_next = TRUE;
183 return SUCCESS;
184 }
185
186 /**
187 * Implements function current of linked_list_iteratr
188 */
189 static status_t iterator_current(private_linked_list_iterator_t *this, linked_list_element_t **element)
190 {
191 *element = &(this->current->public);
192 return SUCCESS;
193 }
194
195 /**
196 * Implements function current of linked_list_iteratr
197 */
198 static status_t iterator_reset(private_linked_list_iterator_t *this)
199 {
200 this->current = NULL;
201 return SUCCESS;
202 }
203
204 /**
205 * Implements function destroy of linked_list_iteratr
206 */
207 static status_t iterator_destroy(private_linked_list_iterator_t *this)
208 {
209 pfree(this);
210 return SUCCESS;
211 }
212
213 /**
214 * @brief implements function get_count of linked_list_t
215 */
216 static status_t get_count(private_linked_list_t *this, int *count)
217 {
218 *count = this->count;
219 return SUCCESS;
220 }
221
222
223 static status_t create_iterator (private_linked_list_t *linked_list, linked_list_iterator_t **iterator,bool forward)
224 {
225 private_linked_list_iterator_t *this = alloc_thing(private_linked_list_iterator_t, "private_linked_list_iterator_t");
226
227 if (this == NULL)
228 {
229 return FAILED;
230 }
231
232 this->public.has_next = (status_t (*) (linked_list_iterator_t *this, bool * has_next)) iterator_has_next;
233 this->public.current = (status_t (*) (linked_list_iterator_t *this, linked_list_element_t **element)) iterator_current;
234 this->public.reset = (status_t (*) (linked_list_iterator_t *this)) iterator_reset;
235 this->public.destroy = (status_t (*) (linked_list_iterator_t *this)) iterator_destroy;
236
237
238 this->forward = forward;
239 this->current = NULL;
240 this->list = linked_list;
241
242 *iterator = &(this->public);
243
244 return (SUCCESS);
245 }
246
247
248 /**
249 * @brief implements function insert_first of linked_list_t
250 */
251 static status_t insert_first(private_linked_list_t *this, void *item)
252 {
253 private_linked_list_element_t *element =(private_linked_list_element_t *) linked_list_element_create(item);
254
255 if (element == NULL)
256 {
257 return FAILED;
258 }
259
260 if (this->count == 0)
261 {
262 /* first entry in list */
263 this->first = element;
264 this->last = element;
265 element->previous = NULL;
266 element->next = NULL;
267 }
268 else
269 {
270 if ((this->first == NULL) || (this->last == NULL))
271 {
272 /* should never happen */
273 element->public.destroy(&(element->public));
274 return FAILED;
275 }
276 private_linked_list_element_t *old_first_element = this->first;
277 element->next = old_first_element;
278 element->previous = NULL;
279 old_first_element->previous = element;
280 this->first = element;
281 }
282
283 this->count++;
284
285 return SUCCESS;
286 }
287
288 /**
289 * @brief implements function remove_first of linked_list_t
290 */
291 static status_t remove_first(private_linked_list_t *this, void **item)
292 {
293 if (this->count == 0)
294 {
295 return FAILED;
296 }
297
298 if (this->first == NULL)
299 {
300 return FAILED;
301 }
302
303 private_linked_list_element_t *element = this->first;
304
305 if (element->next != NULL)
306 {
307 element->next->previous = NULL;
308 }
309 this->first = element->next;
310
311 *item = element->public.value;
312
313 this->count--;
314
315 return (element->public.destroy(&(element->public)));
316 }
317
318 /**
319 * @brief implements function get_first of linked_list_t
320 */
321 static status_t get_first(private_linked_list_t *this, void **item)
322 {
323 if (this->count == 0)
324 {
325 return FAILED;
326 }
327
328 if (this->first == NULL)
329 {
330 return FAILED;
331 }
332
333 *item = this->first->public.value;
334
335 return SUCCESS;
336 }
337
338 /**
339 * @brief implements function insert_last of linked_list_t
340 */
341 static status_t insert_last(private_linked_list_t *this, void *item)
342 {
343 private_linked_list_element_t *element = (private_linked_list_element_t *) linked_list_element_create(item);
344
345 if (element == NULL)
346 {
347 return FAILED;
348 }
349
350 if (this->count == 0)
351 {
352 /* first entry in list */
353 this->first = element;
354 this->last = element;
355 element->previous = NULL;
356 element->next = NULL;
357 }else
358 {
359 if ((this->first == NULL) || (this->last == NULL))
360 {
361 /* should never happen */
362 element->public.destroy(&(element->public));
363 return FAILED;
364 }
365 private_linked_list_element_t *old_last_element = this->last;
366 element->previous = old_last_element;
367 element->next = NULL;
368 old_last_element->next = element;
369 this->last = element;
370 }
371
372 this->count++;
373
374 return SUCCESS;
375 }
376
377 /**
378 * @brief implements function remove_last of linked_list_t
379 */
380 static status_t remove_last(private_linked_list_t *this, void **item)
381 {
382 if (this->count == 0)
383 {
384 return FAILED;
385 }
386
387 if (this->last == NULL)
388 {
389 return FAILED;
390 }
391
392 private_linked_list_element_t *element = this->last;
393
394 if (element->previous != NULL)
395 {
396 element->previous->next = NULL;
397 }
398 this->last = element->previous;
399
400 *item = element->public.value;
401
402 this->count--;
403
404 return (element->public.destroy(&(element->public)));
405 }
406
407 /**
408 * @brief implements function get_last of linked_list_t
409 */
410 static status_t get_last(private_linked_list_t *this, void **item)
411 {
412 if (this->count == 0)
413 {
414 return FAILED;
415 }
416
417 if (this->last == NULL)
418 {
419 return FAILED;
420 }
421
422 *item = this->last->public.value;
423
424 return SUCCESS;
425 }
426
427 /**
428 * @brief implements function destroy of linked_list_t
429 */
430 static status_t linked_list_destroy(private_linked_list_t *this)
431 {
432 /* Remove all list items before destroying list */
433 while (this->count > 0)
434 {
435 void * value;
436 /* values are not destroyed so memory leaks are possible
437 * if list is not empty when deleting */
438 if (this->public.remove_first(&(this->public),&value) != SUCCESS)
439 {
440 pfree(this);
441 return FAILED;
442 }
443 }
444 pfree(this);
445 return SUCCESS;
446 }
447
448 /*
449 * Described in header
450 */
451 linked_list_t *linked_list_create()
452 {
453 private_linked_list_t *this = alloc_thing(private_linked_list_t, "private_linked_list_t");
454
455 this->public.get_count = (status_t (*) (linked_list_t *linked_list, int *count)) get_count;
456 this->public.create_iterator = (status_t (*) (linked_list_t *linked_list, linked_list_iterator_t **iterator,bool forward)) create_iterator;
457 this->public.get_first = (status_t (*) (linked_list_t *linked_list, void **item)) get_first;
458 this->public.get_last = (status_t (*) (linked_list_t *linked_list, void **item)) get_last;
459 this->public.insert_first = (status_t (*) (linked_list_t *linked_list, void *item))insert_first;
460 this->public.insert_last = (status_t (*) (linked_list_t *linked_list, void *item))insert_last;
461 this->public.remove_first = (status_t (*) (linked_list_t *linked_list, void **item)) remove_first;
462 this->public.remove_last = (status_t (*) (linked_list_t *linked_list, void **item)) remove_last;
463 this->public.destroy = (status_t (*) (linked_list_t *linked_list)) linked_list_destroy;
464
465 this->count = 0;
466 this->first = NULL;
467 this->last = NULL;
468
469 return (&(this->public));
470 }