123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552 |
- /*!
- Temelia - Linked list implementation source file.
- Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).
- @author Dascalu Laurentiu, Macovei Alexandru
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/linked_list.h"
- #include "include/common.h"
- #include "include/list_common.h"
- #include <stdlib.h>
- struct _linked_list_t
- {
- /*! reference to the first node in the list */
- struct _linked_list_iterator_t *begin;
- /*! reference to the last node in the list */
- struct _linked_list_iterator_t *end;
- /*! list's size */
- int size;
- };
- /* Auxiliary recursive function used by the linked_list_print function if value == -1 . */
- static void _linked_list_iterate_aux(linked_list_iterator_t it,
- void key_handler(void *, void *context), void *context);
- static void _linked_list_reverse_aux(linked_list_iterator_t it);
- linked_list_t linked_list_new(void)
- {
- linked_list_t list;
- LIST_NEW(linked_list_t, list);
- return list;
- }
- void linked_list_delete(linked_list_t list)
- {
- linked_list_iterator_t crt, prc;
- LIST_DELETE(list, crt, prc, linked_list_iterator);
- }
- linked_list_t linked_list_clone(linked_list_t list, void *(*clone)(void *key,
- void *context), void *context)
- {
- linked_list_t clone_list;
- linked_list_iterator_t it;
- LIST_CLONE(linked_list, list, it, clone_list, clone, context);
- return clone_list;
- }
- int linked_list_is_empty(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, -1);
- return list->size == 0;
- }
- void *linked_list_get_front(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(list->size, ==, 0, INVALID_INPUT, NULL);
- return linked_list_iterator_get_key(list->begin);
- }
- void *linked_list_get_back(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(list->size, ==, 0, INVALID_INPUT, NULL);
- return linked_list_iterator_get_key(list->end);
- }
- linked_list_iterator_t linked_list_get_begin(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- return list->begin;
- }
- void linked_list_set_begin(linked_list_t list, linked_list_iterator_t begin)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- list->begin = begin;
- }
- linked_list_iterator_t linked_list_get_end(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- return list->end;
- }
- void linked_list_set_end(linked_list_t list, linked_list_iterator_t end)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- list->end = end;
- }
- int linked_list_get_size(linked_list_t list)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER, -1);
- return list->size;
- }
- void linked_list_set_size(linked_list_t list, int size)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- list->size = size;
- }
- int linked_list_check(linked_list_t list, linked_list_iterator_t p)
- {
- linked_list_iterator_t it;
- for (it = list->begin; it != NULL; it = linked_list_iterator_get_next(it))
- if (it == p)
- return 1;
- return 0;
- }
- linked_list_iterator_t linked_list_iterator_get_prev(linked_list_t list,
- linked_list_iterator_t p)
- {
- linked_list_iterator_t it;
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- if (p == list->begin)
- return NULL;
- for (it = list->begin;; it = linked_list_iterator_get_next(it))
- if (linked_list_iterator_get_next(it) == p)
- return it;
- return NULL;
- }
- linked_list_iterator_t linked_list_get_iterator_at(linked_list_t list,
- int position)
- {
- linked_list_iterator_t it;
- int i;
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(position, <, 0, INVALID_INPUT, NULL);
- _ASSERT(position, >=, list->size, INVALID_INPUT, NULL);
- for (i = 0, it = list->begin; i < position && it != NULL; i++, it
- = linked_list_iterator_get_next(it))
- ;
- return it;
- }
- void *linked_list_get_key_at(linked_list_t list, int position)
- {
- linked_list_iterator_t it = linked_list_get_iterator_at(list, position);
- if (it)
- return linked_list_iterator_get_key(it);
- return NULL;
- }
- void linked_list_set_key_at(linked_list_t list, int position, void *new_key)
- {
- linked_list_iterator_t it = linked_list_get_iterator_at(list, position);
- if (it)
- linked_list_iterator_set_key(it, new_key);
- }
- linked_list_iterator_t linked_list_search_key(linked_list_t list, void *key,
- int compare(void *x, void *y, void *context), void *context)
- {
- linked_list_iterator_t it;
- _ASSERT(list, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- for (it = list->begin; it != NULL; it = linked_list_iterator_get_next(it))
- if (!compare(linked_list_iterator_get_key(it), key, context))
- return it;
- return NULL;
- }
- int linked_list_search_iterator(linked_list_t list, linked_list_iterator_t it)
- {
- int i;
- linked_list_iterator_t it_search;
- _ASSERT(list, ==, NULL, NULL_POINTER, -1);
- for (it_search = list->begin, i = 0; it_search; it_search
- = linked_list_iterator_get_next(it_search), i++)
- if (it_search == it)
- return i;
- return -1;
- }
- void linked_list_remove_iterator(linked_list_t list, linked_list_iterator_t it,
- int free)
- {
- linked_list_iterator_t aux;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- _ASSERT(it, ==, NULL, NULL_POINTER,);
- _ASSERT(list->size, ==, 0, EMPTY,);
- if (list->size == 1)
- {
- if (list->begin == it && list->end == it)
- list->begin = list->end = NULL;
- else
- _ASSERT(1, ==, 1, INVALID_INPUT,);
- }
- else
- {
- if (it == list->begin)
- list->begin = linked_list_iterator_get_next(list->begin);
- else if (it == list->end)
- {
- for (aux = list->begin; linked_list_iterator_get_next(aux) != it; aux
- = linked_list_iterator_get_next(aux))
- ;
- linked_list_iterator_set_next(aux, NULL);
- list->end = aux;
- }
- else
- {
- for (aux = list->begin; linked_list_iterator_get_next(aux) != it; aux
- = linked_list_iterator_get_next(aux))
- ;
- if (aux)
- linked_list_iterator_set_next(aux,
- linked_list_iterator_get_next(
- linked_list_iterator_get_next(aux)));
- else
- _ASSERT(1, ==, 1, INVALID_INPUT,);
- }
- }
- list->size--;
- if (free)
- _delete(it);
- }
- linked_list_iterator_t linked_list_remove_key(linked_list_t list, void *key,
- int compare(void *x, void *y, void *context), void *context, int free)
- {
- linked_list_iterator_t it = linked_list_search_key(list, key, compare,
- context);
- if (it)
- {
- linked_list_remove_iterator(list, it, free);
- if (free)
- return NULL;
- return it;
- }
- return NULL;
- }
- void linked_list_insert_after(linked_list_t list, linked_list_iterator_t it,
- void *key)
- {
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- /*
- * Inserting after NULL iterator is equivalent
- * with inserting before list's begin iterator.
- */
- if (it == NULL)
- linked_list_insert_before(list, list->begin, key);
- else
- {
- linked_list_iterator_join(it, linked_list_iterator_new(key, NULL),
- linked_list_iterator_get_next(it));
- if (it == list->end)
- list->end = linked_list_iterator_get_next(list->end);
- list->size++;
- }
- }
- void linked_list_insert_before(linked_list_t list, linked_list_iterator_t it,
- void *key)
- {
- linked_list_iterator_t new_node;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- new_node = linked_list_iterator_new(key, NULL);
- if (list->size == 0)
- {
- if (it == NULL)
- list->begin = list->end = new_node;
- else
- {
- linked_list_iterator_delete(new_node);
- _ASSERT(NULL, ==, NULL, INVALID_INPUT,);
- }
- }
- else if (it == list->begin)
- {
- linked_list_iterator_set_next(new_node, it);
- list->begin = new_node;
- }
- else if (it == NULL)
- {
- linked_list_iterator_set_next(list->end, new_node);
- list->end = new_node;
- }
- else
- {
- linked_list_iterator_join(linked_list_iterator_get_prev(list, it),
- new_node, it);
- if (list->size == 1)
- list->begin = new_node;
- }
- list->size++;
- }
- void linked_list_push_front(linked_list_t list, void *key)
- {
- linked_list_iterator_t new_node;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- new_node = linked_list_iterator_new(key, list->begin);
- if (list->size == 0)
- list->end = list->begin = new_node;
- else
- list->begin = new_node;
- list->size++;
- }
- void linked_list_push_back(linked_list_t list, void *key)
- {
- linked_list_iterator_t new_node;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- new_node = linked_list_iterator_new(key, NULL);
- if (list->size == 0)
- list->end = list->begin = new_node;
- else
- {
- linked_list_iterator_set_next(list->end, new_node);
- list->end = new_node;
- }
- list->size++;
- }
- void linked_list_pop_front(linked_list_t list)
- {
- linked_list_iterator_t aux;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- _ASSERT(list->size, <=, 0, INVALID_INPUT,);
- aux = list->begin;
- list->begin = linked_list_iterator_get_next(list->begin);
- list->size--;
- if (list->size == 0)
- list->end = NULL;
- _delete(aux);
- }
- void linked_list_pop_back(linked_list_t list)
- {
- linked_list_iterator_t it, aux;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- _ASSERT(list->size, <=, 0, INVALID_INPUT,);
- aux = list->end;
- if (list->size == 1)
- list->begin = list->end = NULL;
- else
- {
- for (it = list->begin; linked_list_iterator_get_next(it) != list->end; it
- = linked_list_iterator_get_next(it))
- ;
- list->end = it;
- }
- _delete(aux);
- list->size--;
- }
- void linked_list_iterate(linked_list_t list, void key_handler(void *x,
- void *context), void *context, int order)
- {
- linked_list_iterator_t p;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- if (order == 1)
- for (p = list->begin; p != NULL; p = linked_list_iterator_get_next(p))
- key_handler(linked_list_iterator_get_key(p), context);
- else if (order == -1)
- _linked_list_iterate_aux(list->begin, key_handler, context);
- else
- temelia_errno = INVALID_INPUT;
- }
- void linked_list_sort(linked_list_t list, int compare(void *x, void *y,
- void *context), void *context)
- {
- void *aux;
- linked_list_iterator_t it;
- LIST_SORT(list, it, aux, compare, context, linked_list_iterator);
- }
- linked_list_t linked_list_merge(linked_list_t L1, linked_list_t L2,
- int compare(void *x, void *y, void *context), void *context)
- {
- linked_list_t L3;
- linked_list_iterator_t it1, it2;
- void *key1, *key2;
- _ASSERT(L1, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(L2, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
- L3 = linked_list_new();
- it1 = L1->begin;
- it2 = L2->begin;
- LIST_MERGE(L3, it1, it2, key1, key2, linked_list, compare, context);
- return L3;
- }
- void linked_list_reverse(linked_list_t list)
- {
- void *aux;
- _ASSERT(list, ==, NULL, NULL_POINTER,);
- _linked_list_reverse_aux(list->begin);
- /*
- * Swaps "begin" with "end" for a consistent reverse;
- * also sets "end's" next iterator pointer to NULL
- */
- aux = list->begin;
- list->begin = list->end;
- list->end = aux;
- linked_list_iterator_set_next(list->end, NULL);
- }
- void linked_list_spice(linked_list_t list1, linked_list_t list2,
- linked_list_iterator_t it)
- {
- linked_list_iterator_t next_node;
- _ASSERT(list1, ==, NULL, NULL_POINTER,);
- _ASSERT(list2, ==, NULL, NULL_POINTER,);
- if (it == NULL)
- {
- /*
- * => list2 -> list1
- */
- if (list1->end == NULL || list1->begin == list1->end)
- list1->end = list2->end;
- linked_list_iterator_set_next(list2->end, list1->begin);
- list1->begin = list2->begin;
- }
- else if (list1->size > 0)
- {
- if (it == list1->end)
- {
- linked_list_iterator_set_next(list1->end, list2->begin);
- list1->end = list2->end;
- }
- else
- {
- // Finally, we can use the given iterator :-)
- next_node = linked_list_iterator_get_next(it);
- _ASSERT(next_node, ==, NULL, NULL_POINTER,);
- linked_list_iterator_set_next(it, list2->begin);
- linked_list_iterator_set_next(list2->end, next_node);
- }
- }
- else if (list1->size == 0)
- {
- // Simply copies the two pointers
- list1->begin = list2->begin;
- list1->end = list2->end;
- }
- list1->size += list2->size;
- _delete(list2);
- }
- static void _linked_list_iterate_aux(linked_list_iterator_t it,
- void key_handler(void *key, void *context), void *context)
- {
- _ASSERT(it, ==, NULL, NULL_POINTER,);
- _ASSERT(key_handler, ==, NULL, NULL_POINTER,);
- _linked_list_iterate_aux(linked_list_iterator_get_next(it), key_handler,
- context);
- key_handler(linked_list_iterator_get_key(it), context);
- }
- static void _linked_list_reverse_aux(linked_list_iterator_t it)
- {
- if (it == NULL)
- return;
- _linked_list_reverse_aux(linked_list_iterator_get_next(it));
- linked_list_iterator_set_next(linked_list_iterator_get_next(it), it);
- }
|