src/List.c

   1 /**
   2  * @file List.c
   3  */
   4
   5 #include "cgds/List.h"
   6
   7 ////////////////
   8 // List logic //
   9 ////////////////
  10
  11 void _list_init(List* list, size_t dataSize)
  12 {
  13   list->size = 0;
  14   list->dataSize = dataSize;
  15   list->head = NULL;
  16   list->tail = NULL;
  17 }
  18
  19 List* _list_new(size_t dataSize)
  20 {
  21   List* list = (List*) safe_malloc(sizeof (List));
  22   _list_init(list, dataSize);
  23   return list;
  24 }
  25
  26 List* list_copy(List* list)
  27 {
  28   List* listCopy = _list_new(list->dataSize);
  29   ListCell* listCell = list->head;
  30   while (listCell != NULL)
  31   {
  32     _list_insert_back(listCopy, listCell->data);
  33     listCell = listCell->next;
  34   }
  35   return listCopy;
  36 }
  37
  38 bool list_empty(List* list)
  39 {
  40   return (list->size == 0);
  41 }
  42
  43 UInt list_size(List* list)
  44 {
  45   return list->size;
  46 }
  47
  48 void* _list_get(ListCell* listCell)
  49 {
  50   return listCell->data;
  51 }
  52
  53 void _list_set(List* list, ListCell* listCell, void* data)
  54 {
  55   memcpy(listCell->data, data, list->dataSize);
  56 }
  57
  58 void _list_insert_first_element(List* list, void* data)
  59 {
  60   ListCell* newListCell = (ListCell*) safe_malloc(sizeof (ListCell));
  61   newListCell->data = safe_malloc(list->dataSize);
  62   memcpy(newListCell->data, data, list->dataSize);
  63   newListCell->prev = NULL;
  64   newListCell->next = NULL;
  65   list->head = newListCell;
  66   list->tail = newListCell;
  67   list->size = 1;
  68 }
  69
  70 void _list_insert_before(List* list, ListCell* listCell, void* data)
  71 {
  72   ListCell* newListCell = (ListCell*) safe_malloc(sizeof (ListCell));
  73   newListCell->data = safe_malloc(list->dataSize);
  74   memcpy(newListCell->data, data, list->dataSize);
  75   newListCell->prev = listCell->prev;
  76   newListCell->next = listCell;
  77   if (listCell->prev != NULL)
  78     listCell->prev->next = newListCell;
  79   else
  80     list->head = newListCell;
  81   listCell->prev = newListCell;
  82   list->size++;
  83 }
  84
  85 void _list_insert_after(List* list, ListCell* listCell, void* data)
  86 {
  87   ListCell* newListCell = (ListCell*) safe_malloc(sizeof (ListCell));
  88   newListCell->data = safe_malloc(list->dataSize);
  89   memcpy(newListCell->data, data, list->dataSize);
  90   newListCell->prev = listCell;
  91   newListCell->next = listCell->next;
  92   if (listCell->next != NULL)
  93     listCell->next->prev = newListCell;
  94   else
  95     list->tail = newListCell;
  96   listCell->next = newListCell;
  97   list->size++;
  98 }
  99
 100 void _list_insert_front(List* list, void* data)
 101 {
 102   if (list->head != NULL)
 103     _list_insert_before(list, list->head, data);
 104   else
 105     _list_insert_first_element(list, data);
 106 }
 107
 108 void _list_insert_back(List* list, void* data)
 109 {
 110   if (list->tail != NULL)
 111     _list_insert_after(list, list->tail, data);
 112   else
 113     _list_insert_first_element(list, data);
 114 }
 115
 116 void list_remove(List* list, ListCell* listCell)
 117 {
 118   if (listCell->prev != NULL)
 119     listCell->prev->next = listCell->next;
 120   else
 121     list->head = listCell->next;
 122   if (listCell->next != NULL)
 123     listCell->next->prev = listCell->prev;
 124   else
 125     list->tail = listCell->prev;
 126   safe_free(listCell->data);
 127   safe_free(listCell);
 128   list->size--;
 129 }
 130
 131 void list_remove_front(List* list)
 132 {
 133   list_remove(list, list->head);
 134 }
 135
 136 void list_remove_back(List* list)
 137 {
 138   list_remove(list, list->tail);
 139 }
 140
 141 void list_clear(List* list)
 142 {
 143   ListCell* current = list->head;
 144   while (current != NULL)
 145   {
 146     safe_free(current->data);
 147     ListCell* nextListCell = current->next;
 148     safe_free(current);
 149     current = nextListCell;
 150   }
 151   _list_init(list, list->dataSize);
 152 }
 153
 154 void list_destroy(List* list)
 155 {
 156   list_clear(list);
 157   safe_free(list);
 158 }
 159
 160 ////////////////////
 161 // Iterator logic //
 162 ////////////////////
 163
 164 ListIterator* list_get_iterator(List* list)
 165 {
 166   ListIterator* listI = (ListIterator*) safe_malloc(sizeof (ListIterator));
 167   listI->list = list;
 168   listI->current = NULL;
 169   listI_reset_head(listI);
 170   return listI;
 171 }
 172
 173 void listI_reset_head(ListIterator* listI)
 174 {
 175   listI->current = listI->list->head;
 176 }
 177
 178 void listI_reset_tail(ListIterator* listI)
 179 {
 180   listI->current = listI->list->tail;
 181 }
 182
 183 bool listI_has_data(ListIterator* listI)
 184 {
 185   return (listI->current != NULL);
 186 }
 187
 188 void listI_remove(ListIterator* listI, Direction direction)
 189 {
 190   ListCell* toTrash = listI->current;
 191   switch (direction)
 192   {
 193   case FORWARD:
 194     listI->current = listI->current->next;
 195     break;
 196   case BACKWARD:
 197     listI->current = listI->current->prev;
 198     break;
 199   }
 200   list_remove(listI->list, toTrash);
 201 }
 202
 203 void listI_move_next(ListIterator* listI)
 204 {
 205   if (listI->current != NULL)
 206     listI->current = listI->current->next;
 207 }
 208
 209 void listI_move_prev(ListIterator* listI)
 210 {
 211   if (listI->current != NULL)
 212     listI->current = listI->current->prev;
 213 }
 214
 215 void listI_destroy(ListIterator* listI)
 216 {
 217   safe_free(listI);
 218 }