- message encryption verification fully changed
[strongswan.git] / Source / charon / utils / linked_list.c
1 /**
2 * @file linked_list.c
3 *
4 * @brief Implementation of linked_list_t.
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
25 #include "linked_list.h"
26
27 #include <utils/allocator.h>
28
29
30 typedef struct linked_list_element_t linked_list_element_t;
31
32 /**
33 * @brief Element of the linked_list.
34 *
35 * This element holds a pointer to the value of the list item itself.
36 */
37 struct linked_list_element_t {
38 /**
39 * Value of a list item.
40 */
41 void *value;
42
43 /**
44 * previous list element
45 * NULL if first element in list
46 */
47 linked_list_element_t *previous;
48
49 /**
50 * next list element
51 * NULL if last element in list
52 */
53 linked_list_element_t *next;
54
55 /**
56 * Destroys a linked_list_element object.
57 *
58 * @param linked_list_element_t calling object
59 */
60 void (*destroy) (linked_list_element_t *this);
61 };
62
63 /**
64 * Implementation of linked_list_element_t.destroy.
65 */
66 static void linked_list_element_destroy(linked_list_element_t *this)
67 {
68 allocator_free(this);
69 }
70
71 /**
72 * @brief Creates an empty linked list object.
73 *
74 * @warning Only the pointer to the value is stored.
75 *
76 * @param[in] value value of item to be set
77 * @return linked_list_element_t object
78 */
79
80 linked_list_element_t *linked_list_element_create(void *value)
81 {
82 linked_list_element_t *this = allocator_alloc_thing(linked_list_element_t);
83
84 this->destroy = linked_list_element_destroy;
85
86 this->previous=NULL;
87 this->next=NULL;
88 this->value = value;
89
90 return (this);
91 }
92
93
94 typedef struct private_linked_list_t private_linked_list_t;
95 /**
96 * Private variables and functions of linked list.
97 *
98 */
99 struct private_linked_list_t {
100 /**
101 * Public part of linked list.
102 */
103 linked_list_t public;
104
105 /**
106 * Number of items in the list.
107 */
108 int count;
109
110 /**
111 * First element in list.
112 * NULL if no elements in list.
113 */
114 linked_list_element_t *first;
115
116 /**
117 * Last element in list.
118 * NULL if no elements in list.
119 */
120 linked_list_element_t *last;
121 };
122
123
124 typedef struct private_iterator_t private_iterator_t;
125
126 /**
127 * Private variables and functions of linked list iterator.
128 */
129 struct private_iterator_t {
130 /**
131 * Public part of linked list iterator.
132 */
133 iterator_t public;
134
135 /**
136 * Associated linked list.
137 */
138 private_linked_list_t * list;
139
140 /**
141 * Current element of the iterator.
142 */
143 linked_list_element_t *current;
144
145 /**
146 * Direction of iterator.
147 */
148 bool forward;
149 };
150
151 /**
152 * Implementation of iterator_t.has_next.
153 */
154 bool iterator_has_next(private_iterator_t *this)
155 {
156 if (this->list->count == 0)
157 {
158 return FALSE;
159 }
160 if (this->current == NULL)
161 {
162 this->current = (this->forward) ? this->list->first : this->list->last;
163 return TRUE;
164 }
165 if (this->forward)
166 {
167 if (this->current->next == NULL)
168 {
169 return FALSE;
170 }
171 this->current = this->current->next;
172 return TRUE;
173 }
174 /* backward */
175 if (this->current->previous == NULL)
176 {
177 return FALSE;
178 }
179 this->current = this->current->previous;
180 return TRUE;
181 }
182
183 /**
184 * Implementation of iterator_t.current.
185 */
186 static status_t iterator_current(private_iterator_t *this, void **value)
187 {
188 if (this->current == NULL)
189 {
190 return NOT_FOUND;
191 }
192 *value = this->current->value;
193 return SUCCESS;
194 }
195
196 /**
197 * Implementation of iterator_t.reset.
198 */
199 static void iterator_reset(private_iterator_t *this)
200 {
201 this->current = NULL;
202 }
203
204 /**
205 * Implementation of iterator_t.remove.
206 */
207 static status_t remove(private_iterator_t *this)
208 {
209 linked_list_element_t *new_current;
210
211 if (this->current == NULL)
212 {
213 return NOT_FOUND;
214 }
215
216 if (this->list->count == 0)
217 {
218 return NOT_FOUND;
219 }
220 /* find out the new iterator position */
221 if (this ->current->previous != NULL)
222 {
223 new_current = this->current->previous;
224 }
225 else if (this->current->next != NULL)
226 {
227 new_current = this->current->next;
228 }
229 else
230 {
231 new_current = NULL;
232 }
233
234 /* now delete the entry :-) */
235 if (this->current->previous == NULL)
236 {
237 if (this->current->next == NULL)
238 {
239 this->list->first = NULL;
240 this->list->last = NULL;
241 }
242 else
243 {
244 this->current->next->previous = NULL;
245 this->list->first = this->current->next;
246 }
247 }
248 else if (this->current->next == NULL)
249 {
250 this->current->previous->next = NULL;
251 this->list->last = this->current->previous;
252 }
253 else
254 {
255 this->current->previous->next = this->current->next;
256 this->current->next->previous = this->current->previous;
257 }
258
259 this->list->count--;
260 this->current->destroy(this->current);
261 /* set the new iterator position */
262 this->current = new_current;
263 return SUCCESS;
264 }
265
266 /**
267 * Implementation of iterator_t.insert_before.
268 */
269 static void insert_before(private_iterator_t * iterator, void *item)
270 {
271 if (iterator->current == NULL)
272 {
273 iterator->list->public.insert_first(&(iterator->list->public), item);
274 }
275
276 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
277
278 if (iterator->current->previous == NULL)
279 {
280 iterator->current->previous = element;
281 element->next = iterator->current;
282 iterator->list->first = element;
283 }
284 else
285 {
286 iterator->current->previous->next = element;
287 element->previous = iterator->current->previous;
288 iterator->current->previous = element;
289 element->next = iterator->current;
290 }
291
292 iterator->list->count++;
293 }
294
295 /**
296 * Implementation of iterator_t.replace.
297 */
298 status_t replace (private_iterator_t *this, void **old_item, void *new_item)
299 {
300 if (this->current == NULL)
301 {
302 return NOT_FOUND;
303 }
304 if (old_item != NULL)
305 {
306 *old_item = this->current->value;
307 }
308 this->current->value = new_item;
309
310 return SUCCESS;
311 }
312
313 /**
314 * Implementation of iterator_t.insert_after.
315 */
316 static void insert_after(private_iterator_t * iterator, void *item)
317 {
318 if (iterator->current == NULL)
319 {
320 iterator->list->public.insert_first(&(iterator->list->public),item);
321 return;
322 }
323
324 linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item);
325
326 if (iterator->current->next == NULL)
327 {
328 iterator->current->next = element;
329 element->previous = iterator->current;
330 iterator->list->last = element;
331 }
332 else
333 {
334 iterator->current->next->previous = element;
335 element->next = iterator->current->next;
336 iterator->current->next = element;
337 element->previous = iterator->current;
338 }
339 iterator->list->count++;
340 }
341
342 /**
343 * Implementation of iterator_t.destroy.
344 */
345 static void iterator_destroy(private_iterator_t *this)
346 {
347 allocator_free(this);
348 }
349
350 /**
351 * Implementation of linked_list_t.get_count.
352 */
353 static int get_count(private_linked_list_t *this)
354 {
355 return this->count;
356 }
357
358
359 /**
360 * Implementation of linked_list_t.insert_first.
361 */
362 static void insert_first(private_linked_list_t *this, void *item)
363 {
364 linked_list_element_t *element;
365
366 element =(linked_list_element_t *) linked_list_element_create(item);
367
368 if (this->count == 0)
369 {
370 /* first entry in list */
371 this->first = element;
372 this->last = element;
373 element->previous = NULL;
374 element->next = NULL;
375 }
376 else
377 {
378 linked_list_element_t *old_first_element = this->first;
379 element->next = old_first_element;
380 element->previous = NULL;
381 old_first_element->previous = element;
382 this->first = element;
383 }
384
385 this->count++;
386 }
387
388 /**
389 * Implementation of linked_list_t.remove_first.
390 */
391 static status_t remove_first(private_linked_list_t *this, void **item)
392 {
393 if (this->count == 0)
394 {
395 return NOT_FOUND;
396 }
397
398 linked_list_element_t *element = this->first;
399
400 if (element->next != NULL)
401 {
402 element->next->previous = NULL;
403 }
404 this->first = element->next;
405
406 *item = element->value;
407
408 this->count--;
409
410 element->destroy(element);
411
412 return SUCCESS;
413 }
414
415 /**
416 * Implementation of linked_list_t.get_first.
417 */
418 static status_t get_first(private_linked_list_t *this, void **item)
419 {
420 if (this->count == 0)
421 {
422 return NOT_FOUND;
423 }
424
425 *item = this->first->value;
426
427 return SUCCESS;
428 }
429
430 /**
431 * Implementation of linked_list_t.insert_last.
432 */
433 static void insert_last(private_linked_list_t *this, void *item)
434 {
435 linked_list_element_t *element = (linked_list_element_t *) linked_list_element_create(item);
436
437 if (this->count == 0)
438 {
439 /* first entry in list */
440 this->first = element;
441 this->last = element;
442 element->previous = NULL;
443 element->next = NULL;
444 }
445 else
446 {
447
448 linked_list_element_t *old_last_element = this->last;
449 element->previous = old_last_element;
450 element->next = NULL;
451 old_last_element->next = element;
452 this->last = element;
453 }
454
455 this->count++;
456 }
457
458 /**
459 * Implementation of linked_list_t.remove_last.
460 */
461 static status_t remove_last(private_linked_list_t *this, void **item)
462 {
463 if (this->count == 0)
464 {
465 return NOT_FOUND;
466 }
467
468 linked_list_element_t *element = this->last;
469
470 if (element->previous != NULL)
471 {
472 element->previous->next = NULL;
473 }
474 this->last = element->previous;
475
476 *item = element->value;
477
478 this->count--;
479
480 element->destroy(element);
481
482 return SUCCESS;
483 }
484
485 /**
486 * Implementation of linked_list_t.get_last.
487 */
488 static status_t get_last(private_linked_list_t *this, void **item)
489 {
490 if (this->count == 0)
491 {
492 return NOT_FOUND;
493 }
494
495 *item = this->last->value;
496
497 return SUCCESS;
498 }
499
500 /**
501 * Implementation of linked_list_t.create_iterator.
502 */
503 static iterator_t *create_iterator (private_linked_list_t *linked_list,bool forward)
504 {
505 private_iterator_t *this = allocator_alloc_thing(private_iterator_t);
506
507 this->public.has_next = (bool (*) (iterator_t *this)) iterator_has_next;
508 this->public.current = (status_t (*) (iterator_t *this, void **value)) iterator_current;
509 this->public.insert_before = (void (*) (iterator_t *this, void *item)) insert_before;
510 this->public.insert_after = (void (*) (iterator_t *this, void *item)) insert_after;
511 this->public.replace = (status_t (*) (iterator_t *, void **, void *)) replace;
512 this->public.remove = (status_t (*) (iterator_t *this)) remove;
513 this->public.reset = (void (*) (iterator_t *this)) iterator_reset;
514 this->public.destroy = (void (*) (iterator_t *this)) iterator_destroy;
515
516 this->forward = forward;
517 this->current = NULL;
518 this->list = linked_list;
519
520 return &(this->public);
521 }
522
523 /**
524 * Implementation of linked_list_t.destroy.
525 */
526 static void linked_list_destroy(private_linked_list_t *this)
527 {
528 void * value;
529 /* Remove all list items before destroying list */
530
531 while (this->public.remove_first(&(this->public),&value) != NOT_FOUND)
532 {
533 /* values are not destroyed so memory leaks are possible
534 * if list is not empty when deleting */
535 }
536 allocator_free(this);
537 }
538
539 /*
540 * Described in header
541 */
542 linked_list_t *linked_list_create()
543 {
544 private_linked_list_t *this = allocator_alloc_thing(private_linked_list_t);
545
546 this->public.get_count = (int (*) (linked_list_t *linked_list)) get_count;
547 this->public.create_iterator = (iterator_t * (*) (linked_list_t *linked_list,bool forward)) create_iterator;
548 this->public.get_first = (status_t (*) (linked_list_t *linked_list, void **item)) get_first;
549 this->public.get_last = (status_t (*) (linked_list_t *linked_list, void **item)) get_last;
550 this->public.insert_first = (void (*) (linked_list_t *linked_list, void *item)) insert_first;
551 this->public.insert_last = (void (*) (linked_list_t *linked_list, void *item)) insert_last;
552 this->public.remove_first = (status_t (*) (linked_list_t *linked_list, void **item)) remove_first;
553 this->public.remove_last = (status_t (*) (linked_list_t *linked_list, void **item)) remove_last;
554 this->public.destroy = (void (*) (linked_list_t *linked_list)) linked_list_destroy;
555
556 this->count = 0;
557 this->first = NULL;
558 this->last = NULL;
559
560 return (&(this->public));
561 }