/* ______ ___ ___ * /\ _ \ /\_ \ /\_ \ * \ \ \L\ \\//\ \ \//\ \ __ __ _ __ ___ * \ \ __ \ \ \ \ \ \ \ /'__`\ /'_ `\/\`'__\/ __`\ * \ \ \/\ \ \_\ \_ \_\ \_/\ __//\ \L\ \ \ \//\ \L\ \ * \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/ * \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/ * /\____/ * \_/__/ * * Double linked list. * * By Michał Cichoń. * * See readme.txt for copyright information. * * * This is a simple general purpose double linked list. * * This module is NOT thread-safe. */ #include #include #include "allegro5/allegro.h" #include "allegro5/internal/aintern.h" #include "allegro5/internal/aintern_list.h" ALLEGRO_DEBUG_CHANNEL("list") /* Definition of list, holds root and size. */ struct _AL_LIST { /* Root of the list. It is an element, but * not visible one. Using it end and the * beginning can be easily identified. */ _AL_LIST_ITEM* root; size_t size; size_t capacity; size_t item_size; size_t item_size_with_extra; _AL_LIST_ITEM* next_free; void* user_data; _AL_LIST_DTOR dtor; }; /* List item, holds user data and destructor. */ struct _AL_LIST_ITEM { _AL_LIST* list; _AL_LIST_ITEM* next; _AL_LIST_ITEM* prev; void* data; _AL_LIST_ITEM_DTOR dtor; }; /* List of the internal functions. */ static _AL_LIST* list_do_create(size_t capacity, size_t item_extra_size); static bool list_is_static(_AL_LIST* list); static _AL_LIST_ITEM* list_get_free_item(_AL_LIST* list); static _AL_LIST_ITEM* list_create_item(_AL_LIST* list); static void list_destroy_item(_AL_LIST* list, _AL_LIST_ITEM* item); /* * Create an instance of double linked list. * * Parameters: * capacity [in] * Maximum number of elements list can hold. If it is zero, list is * created as fully dynamic linked list with unlimited item count. * For any other positive number static linked list is created, * memory for all elements is allocated once and then used. * * extra_item_size [in] * Number of extra bytes which should be left after each list item. * It is currently not used, so default value is zero. * * Returns: * Pointer to new instance of double linked list. * * Remarks: * There are two kind of double linked list supported: dynamic and static. * For dynamic linked list each item is allocated while adding and freed * while removing. This kind of list does not have capacity limit but * suffer from memory allocation delay. * Static linked list use one memory allocation and are hold as solid * piece of memory. This kind of list have capacity, but adding and * removing elements is very cheap operation. */ static _AL_LIST* list_do_create(size_t capacity, size_t extra_item_size) { size_t i; size_t memory_size; uint8_t* memory_ptr; _AL_LIST* list = NULL; _AL_LIST_ITEM* item = NULL; _AL_LIST_ITEM* prev = NULL; /* Calculate amount of memory needed for the list. * Always at least one element is allocated together with list, * which is intended to be a root. */ memory_size = sizeof(_AL_LIST) + (capacity + 1) * (sizeof(_AL_LIST_ITEM) + extra_item_size); memory_ptr = (uint8_t*)al_malloc(memory_size); if (NULL == memory_ptr) { ALLEGRO_ERROR("Out of memory."); return NULL; } list = (_AL_LIST*)memory_ptr; memory_ptr += sizeof(_AL_LIST); list->size = 0; list->capacity = capacity; list->item_size = sizeof(_AL_LIST_ITEM); list->item_size_with_extra = sizeof(_AL_LIST_ITEM) + extra_item_size; list->next_free = (_AL_LIST_ITEM*)memory_ptr; list->user_data = NULL; list->dtor = NULL; /* Initialize free item list. */ prev = NULL; item = list->next_free; for (i = 0; i <= list->capacity; ++i) { memory_ptr += list->item_size_with_extra; item->list = list; item->next = (_AL_LIST_ITEM*)memory_ptr; prev = item; item = item->next; } /* Set proper free list tail value. */ prev->next = NULL; /* Initialize root. */ list->root = list_get_free_item(list); list->root->dtor = NULL; list->root->next = list->root; list->root->prev = list->root; return list; } /* * Returns true if 'list' point to static double linked list. */ static bool list_is_static(_AL_LIST* list) { return 0 != list->capacity; } /* * Returns free item from internal list. Call to this function * is valid only for static lists. */ static _AL_LIST_ITEM* list_get_free_item(_AL_LIST* list) { _AL_LIST_ITEM* item; //thedmd: disabled, root is always static-like element and this method // is called even for dynamic lists //ASSERT(list_is_static(list)); item = list->next_free; if (NULL != item) list->next_free = item->next; return item; } /* * Create an instance of new double linked list item. */ static _AL_LIST_ITEM* list_create_item(_AL_LIST* list) { _AL_LIST_ITEM* item = NULL; if (list_is_static(list)) { /* Items from internal list already are partially initialized. * So we do not have to setup list pointer. */ item = list_get_free_item(list); } else { item = (_AL_LIST_ITEM*)al_malloc(list->item_size_with_extra); item->list = list; } return item; } /* * Destroys double linked list item. Item destructor is called * when necessary. */ static void list_destroy_item(_AL_LIST* list, _AL_LIST_ITEM* item) { ASSERT(list == item->list); if (NULL != item->dtor) item->dtor(item->data, list->user_data); if (list_is_static(list)) { item->next = list->next_free; list->next_free = item; } else al_free(item); } /* * Create new instance of dynamic double linked list. * * See: * list_do_create */ _AL_LIST* _al_list_create(void) { return list_do_create(0, 0); } /* * Create new instance of list item. Maximum number of list items is * limited by capacity. * * See: * list_do_create */ _AL_LIST* _al_list_create_static(size_t capacity) { if (capacity < 1) { ALLEGRO_ERROR("Cannot create static list without any capacity."); return NULL; } return list_do_create(capacity, 0); } /* * Destroys instance of the list. All elements * that list contain are also destroyed. */ void _al_list_destroy(_AL_LIST* list) { if (NULL == list) return; if (list->dtor) list->dtor(list->user_data); _al_list_clear(list); al_free(list); } /* * Sets a destructor for the list. */ void _al_list_set_dtor(_AL_LIST* list, _AL_LIST_DTOR dtor) { list->dtor = dtor; } /* * Returns destructor of the list. */ _AL_LIST_DTOR _al_list_get_dtor(_AL_LIST* list) { return list->dtor; } /* * Create and push new item at the beginning of the list. * * Returns pointer to new item. */ _AL_LIST_ITEM* _al_list_push_front(_AL_LIST* list, void* data) { return _al_list_insert_after(list, list->root, data); } /* * Pretty the same as _al_list_push_front(), but also allow * to provide custom destructor for the item. */ _AL_LIST_ITEM* _al_list_push_front_ex(_AL_LIST* list, void* data, _AL_LIST_ITEM_DTOR dtor) { return _al_list_insert_after_ex(list, list->root, data, dtor); } /* * Create and push new item at the end of the list. * * Returns pointer to new item. */ _AL_LIST_ITEM* _al_list_push_back(_AL_LIST* list, void* data) { return _al_list_insert_before(list, list->root, data); } /* * Pretty the same as _al_list_push_back(), but also allow * to provide custom destructor for the item. */ _AL_LIST_ITEM* _al_list_push_back_ex(_AL_LIST* list, void* data, _AL_LIST_ITEM_DTOR dtor) { return _al_list_insert_before_ex(list, list->root, data, dtor); } /* * Remove first item in the list. */ void _al_list_pop_front(_AL_LIST* list) { if (list->size > 0) _al_list_erase(list, list->root->next); } /* * Remove last item in the list. */ void _al_list_pop_back(_AL_LIST* list) { if (list->size > 0) _al_list_erase(list, list->root->prev); } /* * Create and insert new item after one specified by 'where'. * * Returns pointer to new item. */ _AL_LIST_ITEM* _al_list_insert_after(_AL_LIST* list, _AL_LIST_ITEM* where, void* data) { return _al_list_insert_after_ex(list, where, data, NULL); } /* * Pretty the same as _al_list_insert_after(), but also allow * to provide custom destructor for the item. */ _AL_LIST_ITEM* _al_list_insert_after_ex(_AL_LIST* list, _AL_LIST_ITEM* where, void* data, _AL_LIST_ITEM_DTOR dtor) { _AL_LIST_ITEM* item; ASSERT(list == where->list); item = list_create_item(list); if (NULL == item) return NULL; item->data = data; item->dtor = dtor; item->prev = where; item->next = where->next; where->next->prev = item; where->next = item; list->size++; return item; } /* * Create and insert new item before one specified by 'where'. * * Returns pointer to new item. */ _AL_LIST_ITEM* _al_list_insert_before(_AL_LIST* list, _AL_LIST_ITEM* where, void* data) { return _al_list_insert_before_ex(list, where, data, NULL); } /* * Pretty the same as _al_list_insert_before(), but also allow * to provide custom destructor for the item. */ _AL_LIST_ITEM* _al_list_insert_before_ex(_AL_LIST* list, _AL_LIST_ITEM* where, void* data, _AL_LIST_ITEM_DTOR dtor) { _AL_LIST_ITEM* item; ASSERT(list == where->list); item = list_create_item(list); if (NULL == item) return NULL; item->data = data; item->dtor = dtor; item->next = where; item->prev = where->prev; where->prev->next = item; where->prev = item; list->size++; return item; } /* * Remove specified item from the list. */ void _al_list_erase(_AL_LIST* list, _AL_LIST_ITEM* item) { if (NULL == item) return; ASSERT(list == item->list); item->prev->next = item->next; item->next->prev = item->prev; list->size--; list_destroy_item(list, item); } /* * Remove all items from the list. */ void _al_list_clear(_AL_LIST* list) { _AL_LIST_ITEM* item; _AL_LIST_ITEM* next; item = _al_list_front(list); while (NULL != item) { next = _al_list_next(list, item); _al_list_erase(list, item); item = next; } } /* * Remove all occurrences of specified value in the list. */ void _al_list_remove(_AL_LIST* list, void* data) { _AL_LIST_ITEM* item = NULL; _AL_LIST_ITEM* next = NULL; item = _al_list_find_first(list, data); while (NULL != item) { next = _al_list_find_after(list, item, data); _al_list_erase(list, item); item = next; } } /* * Returns true if list is empty. */ bool _al_list_is_empty(_AL_LIST* list) { return 0 == list->size; } /* * Returns true if list contain specified value. */ bool _al_list_contains(_AL_LIST* list, void* data) { return NULL != _al_list_find_first(list, data); } /* * Returns first occurrence of specified value in the list. */ _AL_LIST_ITEM* _al_list_find_first(_AL_LIST* list, void* data) { return _al_list_find_after(list, list->root, data); } /* * Returns last occurrence of specified value in the list. */ _AL_LIST_ITEM* _al_list_find_last(_AL_LIST* list, void* data) { return _al_list_find_before(list, list->root, data); } /* * Return occurrence of specified value in the list after 'where' item. */ _AL_LIST_ITEM* _al_list_find_after(_AL_LIST* list, _AL_LIST_ITEM* where, void* data) { _AL_LIST_ITEM* item; ASSERT(list == where->list); for (item = where->next; item != list->root; item = item->next) if (item->data == data) return item; return NULL; } /* * Return occurrence of specified value in the list before 'where' item. */ _AL_LIST_ITEM* _al_list_find_before(_AL_LIST* list, _AL_LIST_ITEM* where, void* data) { _AL_LIST_ITEM* item; ASSERT(list == where->list); for (item = where->prev; item != list->root; item = item->prev) if (item->data == data) return item; return NULL; } /* * Returns current size of the list. */ size_t _al_list_size(_AL_LIST* list) { return list->size; } /* * Returns item located at specified index. */ _AL_LIST_ITEM* _al_list_at(_AL_LIST* list, size_t index) { if (index >= list->size) return NULL; if (index < list->size / 2) { _AL_LIST_ITEM* item = list->root->next; while (index--) item = item->next; return item; } else { _AL_LIST_ITEM* item = list->root->prev; index = list->size - index - 1; while (index--) item = item->prev; return item; } } /* * Returns first item in the list. */ _AL_LIST_ITEM* _al_list_front(_AL_LIST* list) { if (list->size > 0) return list->root->next; else return NULL; } /* * Returns last item in the list. */ _AL_LIST_ITEM* _al_list_back(_AL_LIST* list) { if (list->size > 0) return list->root->prev; else return NULL; } /* * Returns next element in the list. */ _AL_LIST_ITEM* _al_list_next(_AL_LIST* list, _AL_LIST_ITEM* item) { ASSERT(list == item->list); (void)list; if (item->next != item->list->root) return item->next; else return NULL; } /* * Returns previous element in the list. */ _AL_LIST_ITEM* _al_list_previous(_AL_LIST* list, _AL_LIST_ITEM* item) { ASSERT(list == item->list); (void)list; if (item->prev != item->list->root) return item->prev; else return NULL; } /* * Returns next element in the list. If end of the list is reached, * first element is returned instead of NULL. */ _AL_LIST_ITEM* _al_list_next_circular(_AL_LIST* list, _AL_LIST_ITEM* item) { ASSERT(list == item->list); if (item->next != item->list->root) return item->next; else return list->root->next; } /* * Returns previous element in the list. If beginning of the list is reached, * last element is returned instead of NULL. */ _AL_LIST_ITEM* _al_list_previous_circular(_AL_LIST* list, _AL_LIST_ITEM* item) { ASSERT(list == item->list); if (item->prev != item->list->root) return item->prev; else return list->root->prev; } /* * Returns value associated with specified item. */ void* _al_list_item_data(_AL_LIST_ITEM* item) { return item->data; } /* * Sets item destructor. */ void _al_list_item_set_dtor(_AL_LIST_ITEM* item, _AL_LIST_ITEM_DTOR dtor) { item->dtor = dtor; } /* * Returns item destructor. */ _AL_LIST_ITEM_DTOR _al_list_item_get_dtor(_AL_LIST_ITEM* item) { return item->dtor; } /* * Sets user data for list. This pointer is passed to list destructor. */ void _al_list_set_user_data(_AL_LIST* list, void* user_data) { list->user_data = user_data; } /* * Returns user data for list. */ void* _al_list_get_user_data(_AL_LIST* list) { return list->user_data; }