text: /*         ______   ___    ___
   *        /\  _  \ /\_ \  /\_ \
   *        \ \ \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 <stdlib.h>
  #include <string.h>
  
  #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;
  
        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;
  }
  