1 : /*
2 : * This file is part of MIN Test Framework. Copyright © 2008 Nokia Corporation
3 : * and/or its subsidiary(-ies).
4 : * Contact: Konrad Marek Zapalowicz
5 : * Contact e-mail: DG.MIN-Support@nokia.com
6 : *
7 : * This program is free software: you can redistribute it and/or modify it
8 : * under the terms of the GNU General Public License as published by the Free
9 : * Software Foundation, version 2 of the License.
10 : *
11 : * This program is distributed in the hope that it will be useful, but WITHOUT
12 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 : * more details. You should have received a copy of the GNU General Public
15 : * License along with this program. If not, see
16 : * <http://www.gnu.org/licenses/>.
17 : */
18 :
19 :
20 : /**
21 : * @file dllist.c
22 : * @version 0.1
23 : * @brief This file contains implementation of Doubly Linked List
24 : */
25 :
26 : /* ------------------------------------------------------------------------- */
27 : /* INCLUDE FILES */
28 : #include <dllist.h>
29 :
30 : /* ------------------------------------------------------------------------- */
31 : /* EXTERNAL DATA STRUCTURES */
32 : /* None */
33 :
34 : /* ------------------------------------------------------------------------- */
35 : /* EXTERNAL GLOBAL VARIABLES */
36 : /* None */
37 :
38 : /* ------------------------------------------------------------------------- */
39 : /* EXTERNAL FUNCTION PROTOTYPES */
40 : /* None */
41 :
42 : /* ------------------------------------------------------------------------- */
43 : /* GLOBAL VARIABLES */
44 : /* None */
45 :
46 : /* ------------------------------------------------------------------------- */
47 : /* CONSTANTS */
48 : /* None */
49 :
50 : /* ------------------------------------------------------------------------- */
51 : /* MACROS */
52 :
53 : /* ------------------------------------------------------------------------- */
54 : /* LOCAL GLOBAL VARIABLES */
55 : /* None */
56 :
57 : /* ------------------------------------------------------------------------- */
58 : /* LOCAL CONSTANTS AND MACROS */
59 : /* None */
60 :
61 : /* ------------------------------------------------------------------------- */
62 : /* MODULE DATA STRUCTURES */
63 : /* None */
64 :
65 : /* ------------------------------------------------------------------------- */
66 : /* LOCAL FUNCTION PROTOTYPES */
67 : /* None */
68 :
69 : /* ------------------------------------------------------------------------- */
70 : /* FORWARD DECLARATIONS */
71 : /* None */
72 :
73 : /* ==================== LOCAL FUNCTIONS ==================================== */
74 : /* None */
75 :
76 : /* ======================== FUNCTIONS ====================================== */
77 :
78 : /* ------------------------------------------------------------------------- */
79 : /** Creates a new doubly linked list.
80 : * @return pointer to created list, or NULL along with setting the global
81 : * errno variable.
82 : *
83 : * Possible errors:
84 : * - ENOMEM not enough memory to create list.
85 : */
86 : DLList *dl_list_create ()
87 13374 : {
88 13374 : DLList *new_list = (DLList *) malloc (sizeof (DLList));
89 13374 : if (new_list != NULL) {
90 13374 : new_list->head_ = INITPTR;
91 13374 : new_list->tail_ = new_list->head_;
92 : } else {
93 0 : errno = ENOMEM;
94 0 : new_list = INITPTR;
95 : }
96 13374 : return new_list;
97 : }
98 :
99 : /* ------------------------------------------------------------------------- */
100 : /** Frees memory allocated for doubly linked list.
101 : * NOTE: Does not free memory allocated for data stored on the list!
102 : * @param list_handle adress of the pointer to the doubly linked list.
103 : */
104 : void dl_list_free (DLList ** list_handle)
105 11780 : {
106 11780 : DLListItem *current = INITPTR;
107 11780 : DLListItem *next = INITPTR;
108 :
109 11780 : if (*list_handle != INITPTR) {
110 10946 : current = (*list_handle)->head_;
111 10946 : next = INITPTR;
112 33509 : while (current != INITPTR) {
113 11617 : next = current->next_;
114 11617 : free (current);
115 11617 : current = next;
116 : }
117 10946 : free (*list_handle);
118 10946 : *list_handle = INITPTR;
119 : }
120 11780 : }
121 :
122 : /* ------------------------------------------------------------------------- */
123 : /** Frees the data from each item in the list
124 : * @param list_handle adress of the pointer to the doubly linked list.
125 : */
126 : void dl_list_free_data (DLList ** list_handle)
127 273 : {
128 273 : DLListItem *current = INITPTR;
129 273 : DLListItem *next = INITPTR;
130 :
131 273 : if (*list_handle != INITPTR) {
132 273 : current = (*list_handle)->head_;
133 273 : next = INITPTR;
134 609 : while (current != INITPTR) {
135 63 : next = current->next_;
136 63 : free (current->data_);
137 63 : current = next;
138 : }
139 : }
140 273 : }
141 :
142 : /* ------------------------------------------------------------------------- */
143 : /** Adds a new element to the end of the list.
144 : * @param list_handle link to list to which a new element is added.
145 : * @param data pointer to data that is stored on the list.
146 : * @return 0 in case of success, returns -1 and sets errno in case of failure.
147 : *
148 : * Possible errors:
149 : * - EINVAL list handler is invalid
150 : * - ENOMEM not enough memory to allocate new element of the list.
151 : */
152 : int dl_list_add (DLList * list_handle, void *data)
153 17563 : {
154 17563 : DLListItem *new_element = INITPTR;
155 17563 : int retval = 0;
156 17563 : if (list_handle != INITPTR) {
157 17561 : new_element = (DLListItem *) malloc (sizeof (DLListItem));
158 17561 : if (new_element != NULL) {
159 17561 : new_element->data_ = data;
160 17561 : new_element->next_ = INITPTR;
161 17561 : new_element->prev_ = INITPTR;
162 17561 : new_element->list_ = list_handle;
163 :
164 17561 : if (list_handle->tail_ != INITPTR) {
165 11358 : new_element->prev_ = list_handle->tail_;
166 11358 : list_handle->tail_->next_ = new_element;
167 11358 : list_handle->tail_ = new_element;
168 : } else {
169 6203 : list_handle->head_ = new_element;
170 6203 : list_handle->tail_ = new_element;
171 : }
172 : } else {
173 0 : errno = ENOMEM;
174 0 : retval = -1;
175 0 : new_element = INITPTR;
176 : }
177 : } else {
178 2 : errno = EINVAL;
179 2 : retval = -1;
180 : }
181 17563 : return retval;
182 : }
183 :
184 : /* ------------------------------------------------------------------------- */
185 : /** Adds a new element, at the given position, to the list.
186 : * @param list_handle link to list to which a new element is added.
187 : * @param data pointer to data that is stored on the list.
188 : * @param pos position on which the element will be added. [0;N-1]
189 : * @return 0 in case of success, returns -1 and sets errno in case of failure.
190 : *
191 : * If pos is greater then actual size of the list then the element is
192 : * added at the end of the list.
193 : *
194 : * Possible errors:
195 : * - EINVAL list handler is invalid
196 : * - ENOMEM not enough memory to allocate new element of the list.
197 : */
198 : int dl_list_add_at (DLList * list_handle, void *data, unsigned int pos)
199 19 : {
200 19 : DLListItem *new_element = INITPTR;
201 19 : DLListItem *old = INITPTR;
202 19 : DLListItem *prev = INITPTR;
203 19 : int retval = 0;
204 19 : int i = 0;
205 :
206 19 : if (list_handle != INITPTR) {
207 15 : new_element = (DLListItem *) malloc (sizeof (DLListItem));
208 15 : if (new_element != NULL) {
209 15 : new_element->data_ = data;
210 15 : new_element->next_ = INITPTR;
211 15 : new_element->prev_ = INITPTR;
212 15 : new_element->list_ = list_handle;
213 :
214 : /* find element at specified position */
215 15 : old = list_handle->head_;
216 18 : for (i = 0; i < pos; i++) {
217 9 : if (old == INITPTR)
218 2 : break;
219 7 : if (old->next_ == INITPTR)
220 4 : break;
221 3 : old = old->next_;
222 : }
223 :
224 15 : if (i == pos) { /* inside of a list */
225 :
226 9 : if (old == INITPTR) {
227 3 : DELETE (new_element);
228 3 : dl_list_add (list_handle, data);
229 : } else {
230 6 : prev = old->prev_;
231 6 : old->prev_ = new_element;
232 6 : new_element->next_ = old;
233 :
234 6 : if (prev != INITPTR) {
235 2 : new_element->prev_ = prev;
236 2 : prev->next_ = new_element;
237 : } else {
238 4 : list_handle->head_ =
239 : new_element;
240 : }
241 : }
242 : } else { /* outside of a list */
243 6 : DELETE (new_element);
244 6 : dl_list_add (list_handle, data);
245 : }
246 :
247 : } else {
248 0 : errno = ENOMEM;
249 0 : retval = -1;
250 0 : new_element = INITPTR;
251 : }
252 : } else {
253 4 : errno = EINVAL;
254 4 : retval = -1;
255 : }
256 19 : return retval;
257 : }
258 :
259 : /* ------------------------------------------------------------------------- */
260 : /** Removes element from the list which is specified by iterator pointer.
261 : * NOTE: after removal allocated element is freed,
262 : * and input iterator is set to NULL iterator;
263 : * @param it iterator pointing at the element which is going to be removed
264 : * @return 0 in case of success, returns -1 and sets errno in case of failure.
265 : *
266 : * Possible errors:
267 : * - EINVAL input iterator is invalid
268 : */
269 : int dl_list_remove_it (DLListIterator it)
270 3643 : {
271 3643 : int retval = 0;
272 3643 : DLListIterator prev = DLListNULLIterator;
273 3643 : DLListIterator next = DLListNULLIterator;
274 3643 : if (it != DLListNULLIterator) {
275 3641 : prev = it->prev_;
276 3641 : next = it->next_;
277 :
278 3641 : if (prev != DLListNULLIterator)
279 309 : prev->next_ = next;
280 : else
281 3332 : it->list_->head_ = next;
282 :
283 3641 : if (next != DLListNULLIterator)
284 1007 : next->prev_ = prev;
285 : else
286 2634 : it->list_->tail_ = prev;
287 :
288 3641 : free (it);
289 3641 : it = DLListNULLIterator;
290 : } else {
291 2 : retval = -1;
292 2 : errno = EINVAL;
293 : }
294 3643 : return retval;
295 : }
296 :
297 : /* ------------------------------------------------------------------------- */
298 : /** Finds element on the list using a supplied function as a method of
299 : * comparison.
300 : * Given function is called for each element in the list, in the given range.
301 : * Function should return 0 when the element is found.
302 : * @param begin left border of the search area
303 : * @param end right border of the search area
304 : * @param unary the function to call for each element.
305 : * @param data pointer to user data passed to the function.
306 : * @return iterator pointing to found element, or NULL iterator when nothing
307 : * is found. In case of failure NULL iterator is returned.
308 : *
309 : * Possible errors:
310 : * - EINVAL when one or more parameters are invalid.
311 : */
312 : DLListIterator dl_list_find (DLListConstIterator begin,
313 : DLListConstIterator end, ptr2compare unary,
314 : const void *data)
315 2799 : {
316 2799 : DLListIterator retval = DLListNULLIterator;
317 2799 : DLListConstIterator current = DLListNULLIterator;
318 2799 : if (begin == DLListNULLIterator)
319 153 : errno = EINVAL;
320 2646 : else if (end == DLListNULLIterator)
321 2 : errno = EINVAL;
322 2644 : else if (unary == (ptr2compare) 0xDEADBEEF)
323 8 : errno = EINVAL;
324 2636 : else if (data == INITPTR)
325 0 : errno = EINVAL;
326 : else {
327 2636 : current = begin;
328 :
329 6812 : while (current != end && current != DLListNULLIterator) {
330 2176 : if (unary (current->data_, data) == 0) {
331 636 : retval = (DLListIterator) current;
332 636 : break;
333 : }
334 1540 : current = current->next_;
335 : }
336 :
337 2636 : if (retval == DLListNULLIterator) {
338 2000 : if (unary (end->data_, data) == 0) {
339 1920 : retval = (DLListIterator) end;
340 : }
341 : }
342 : }
343 2799 : return retval;
344 : }
345 :
346 : /* ------------------------------------------------------------------------- */
347 : /** Counts elements on the list which are find by specified method that is
348 : * used to compare.
349 : * @param begin left border of the search area
350 : * @param end right border of the search area
351 : * @param unary the function to call for each element.
352 : * @param data pointer to user data passed to the function.
353 : * @return number of found items.
354 : *
355 : * Possible errors:
356 : * - EINVAL when one or more parameters are invalid.
357 : */
358 : unsigned dl_list_count (DLListConstIterator begin,
359 : DLListConstIterator end, ptr2compare unary,
360 : const void *data)
361 2 : {
362 2 : unsigned retval = 0;
363 2 : DLListConstIterator current = DLListNULLIterator;
364 :
365 2 : if (begin == DLListNULLIterator)
366 0 : errno = EINVAL;
367 2 : else if (end == DLListNULLIterator)
368 0 : errno = EINVAL;
369 2 : else if (unary == (ptr2compare) 0xDEADBEEF)
370 0 : errno = EINVAL;
371 2 : else if (data == INITPTR)
372 0 : errno = EINVAL;
373 : else {
374 2 : current = begin;
375 :
376 14 : while (current != end && current != DLListNULLIterator) {
377 10 : if (unary (current->data_, data) == 0) {
378 6 : retval++;
379 : }
380 10 : current = current->next_;
381 : }
382 :
383 2 : if (current == end) {
384 2 : if (unary (end->data_, data) == 0) {
385 2 : retval++;
386 : }
387 : }
388 : }
389 2 : return retval;
390 : }
391 : /* ------------------------------------------------------------------------- */
392 : /** Tells how many elements are appended to the list.
393 : * @param list_handle link to list which size is returned.
394 : * @return number of elements appended to the list, returns -1 and sets errno
395 : * in case of failure.
396 : *
397 : * Possible errors:
398 : * - EINVAL list handler is invalid
399 : */
400 : int dl_list_size (const DLList * list_handle)
401 12770 : {
402 12770 : int retval = 0;
403 12770 : DLListIterator current = DLListNULLIterator;
404 12770 : if (list_handle != INITPTR) {
405 12724 : current = list_handle->head_;
406 51330 : while (current != DLListNULLIterator) {
407 25882 : retval++;
408 25882 : current = current->next_;
409 : }
410 : } else {
411 46 : retval = -1;
412 46 : errno = EINVAL;
413 : }
414 12770 : return retval;
415 : }
416 :
417 : /* ------------------------------------------------------------------------- */
418 : /** Gives pointer to the first element of the list.
419 : * NOTE: When handler to list is invalid errno is set to EINVAL
420 : * @param list_handle link to list from which element is returned.
421 : * @return iterator pointing at the first element on the list. If list is
422 : * empty NULL iterator is returned.
423 : *
424 : * Possible errors:
425 : * - EINVAL list handler is invalid
426 : */
427 : DLListIterator dl_list_head (const DLList * list_handle)
428 6615365 : {
429 6615365 : DLListItem *retval = INITPTR;
430 6615365 : if (list_handle != INITPTR)
431 6614355 : retval = list_handle->head_;
432 : else
433 1010 : errno = EINVAL;
434 6615365 : return retval;
435 : }
436 :
437 : /* ------------------------------------------------------------------------- */
438 : /** Gives pointer to the last element of the list.
439 : * NOTE: When handler to list is invalid errno is set to EINVAL
440 : * @param list_handle link to list from which element is returned.
441 : * @return iterator pointing at the last element on the list. If list is empty
442 : * NULL iterator is returned.
443 : *
444 : * Possible errors:
445 : * - EINVAL list handler is invalid
446 : */
447 : DLListIterator dl_list_tail (const DLList * list_handle)
448 4456 : {
449 4456 : DLListItem *retval = INITPTR;
450 4456 : if (list_handle != INITPTR)
451 4439 : retval = list_handle->tail_;
452 : else
453 17 : errno = EINVAL;
454 4456 : return retval;
455 : }
456 :
457 : /* ------------------------------------------------------------------------- */
458 : /** Gets user data from iterator.
459 : * @param it iterator pointing to one of the elements of list.
460 : * @return pointer to the user-data, in case of failure NULL is returned.
461 : *
462 : * Possible errors:
463 : * - EINVAL input iterator is invalid
464 : */
465 : void *dl_list_data (DLListConstIterator it)
466 4444858 : {
467 4444858 : void *retval = INITPTR;
468 4444858 : if (it != DLListNULLIterator)
469 4444790 : retval = it->data_;
470 : else
471 68 : errno = EINVAL;
472 4444858 : return retval;
473 : }
474 :
475 : /* ------------------------------------------------------------------------- */
476 : /** Gets iterator pointing to the element at given position.
477 : * @param list_handle link to list.
478 : * @param i position of element in the list ( where i = [0,N] )
479 : * @return iterator pointing to the element at i-th position.
480 : * In case of failure NULL iterator is returned.
481 : *
482 : * Possible errors:
483 : * - EINVAL list handler is invalid
484 : * - EFAULT i param is out of its range
485 : */
486 : DLListIterator dl_list_at (const DLList * list_handle, unsigned int i)
487 2548 : {
488 2548 : DLListIterator retval = DLListNULLIterator;
489 2548 : DLListItem *current = INITPTR;
490 2548 : int k = 0;
491 2548 : if (list_handle != INITPTR) {
492 2548 : if (i < 0 || i >= dl_list_size (list_handle))
493 6 : errno = EFAULT;
494 : else {
495 2542 : k = 0;
496 2542 : current = list_handle->head_;
497 3455 : for (k = 0; k < i; ++k)
498 913 : current = current->next_;
499 2542 : retval = current;
500 : }
501 : } else
502 0 : errno = EINVAL;
503 2548 : return retval;
504 : }
505 :
506 : /* ------------------------------------------------------------------------- */
507 : /** Moves iterator in forward direction.
508 : * @param it iterator of some list
509 : * @return iterator to the next element on the list. In case of failure,
510 : * or when the end of list is reached NULL is returned.
511 : *
512 : * Possible errors:
513 : * - EINVAL input iterator is invalid
514 : */
515 : DLListIterator dl_list_next (DLListConstIterator it)
516 4429666 : {
517 4429666 : DLListIterator retval = DLListNULLIterator;
518 4429666 : if (it != DLListNULLIterator)
519 4429664 : retval = it->next_;
520 : else
521 2 : errno = EINVAL;
522 4429666 : return retval;
523 : }
524 :
525 : /* ------------------------------------------------------------------------- */
526 : /** Moves iterator in backward direction.
527 : * @param it iterator of some list
528 : * @return iterator to the previous element on the list. In case of failure,
529 : * or when the begining of list is reached NULL is returned.
530 : *
531 : * Possible errors:
532 : * - EINVAL input iterator is invalid
533 : */
534 : DLListIterator dl_list_prev (DLListConstIterator it)
535 166 : {
536 166 : DLListIterator retval = DLListNULLIterator;
537 166 : if (it != DLListNULLIterator)
538 164 : retval = it->prev_;
539 : else
540 2 : errno = EINVAL;
541 166 : return retval;
542 : }
543 :
544 : /* ------------------------------------------------------------------------- */
545 : /** Alters one element on the list.
546 : * @param it iterator which points to the element to be altered.
547 : * @param data new data which is going to be passed on the list.
548 : * @return 0 in case of success, -1 in case of failure.
549 : *
550 : * Possible errors:
551 : * - EINVAL input iterator
552 : */
553 : int dl_list_alter_it (DLListIterator it, const void *data)
554 6 : {
555 6 : int retval = 0;
556 6 : if (it != DLListNULLIterator)
557 4 : it->data_ = (void *)data;
558 : else {
559 2 : retval = -1;
560 2 : errno = EINVAL;
561 : }
562 6 : return retval;
563 : }
564 :
565 : /* ------------------------------------------------------------------------- */
566 : /** Executes unary function for each data stored on the list.
567 : * @param begin [in] left delimiter.
568 : * @param end [in] right delimiter.
569 : * @param unary [in] adress of the unary function.
570 : *
571 : * Possible errors:
572 : * - EINVAL when one or more parameters are invalid.
573 : */
574 : int dl_list_foreach (DLListConstIterator begin, DLListConstIterator end,
575 : ptr2unary unary)
576 320 : {
577 320 : int retval = -1;
578 320 : DLListConstIterator current = DLListNULLIterator;
579 : DLListConstIterator current_next;
580 :
581 320 : if (begin == DLListNULLIterator)
582 18 : errno = EINVAL;
583 302 : else if (end == DLListNULLIterator)
584 0 : errno = EINVAL;
585 302 : else if (unary == (ptr2unary) 0xDEADBEEF)
586 0 : errno = EINVAL;
587 : else {
588 302 : current = begin;
589 :
590 2751 : while (current != end->next_ && current != DLListNULLIterator) {
591 2147 : current_next = current->next_;
592 2147 : unary (current->data_);
593 2147 : current = current_next;
594 : }
595 :
596 302 : retval = 0;
597 : }
598 320 : return retval;
599 : }
600 :
601 : /* ------------------------------------------------------------------------- */
602 : /** Executes unary function for each iterator on the list.
603 : * @param begin [in] left delimiter.
604 : * @param end [in] right delimiter.
605 : * @param unary [in] adress of the unary function.
606 : *
607 : * Possible errors:
608 : * - EINVAL when one or more parameters are invalid.
609 : */
610 : int dl_list_foreach_it (DLListConstIterator begin, DLListConstIterator end,
611 : ptr2itunary unary)
612 0 : {
613 0 : int retval = -1;
614 0 : DLListConstIterator current = DLListNULLIterator;
615 0 : DLListConstIterator currentnext = DLListNULLIterator;
616 0 : if (begin == DLListNULLIterator)
617 0 : errno = EINVAL;
618 0 : else if (end == DLListNULLIterator)
619 0 : errno = EINVAL;
620 0 : else if (unary == (ptr2itunary) 0xDEADBEEF)
621 0 : errno = EINVAL;
622 : else {
623 0 : current = begin;
624 :
625 0 : while (current != end->next_ && current != DLListNULLIterator) {
626 0 : currentnext = current->next_;
627 0 : unary ((DLListIterator) current);
628 0 : current = currentnext;
629 : }
630 :
631 0 : retval = 0;
632 : }
633 0 : return retval;
634 : }
635 :
636 : /* ------------------------------------------------------------------------- */
637 : /* ================= OTHER EXPORTED FUNCTIONS ============================== */
638 : /* None */
639 :
640 : /* ------------------------------------------------------------------------- */
641 : /* ================= TESTS FOR LOCAL FUNCTIONS ============================= */
642 : #ifdef MIN_UNIT_TEST
643 : #include "dllist.tests"
644 : #endif /* MIN_UNIT_TEST */
645 : /* ------------------------------------------------------------------------- */
646 : /* End of file */
|
