pd.if.org Git - lice/blob - list.c

   1 #include "util.h"
   2 #include "list.h"
   3
   4 typedef struct list_node_s list_node_t;
   5
   6 struct list_node_s {
   7     void        *element;
   8     list_node_t *next;
   9     list_node_t *prev;
  10 };
  11
  12 struct list_iterator_s {
  13     list_node_t *pointer;
  14 };
  15
  16 list_t *list_create(void) {
  17     list_t *list = memory_allocate(sizeof(list_t));
  18     list->length = 0;
  19     list->head   = NULL;
  20     list->tail   = NULL;
  21
  22     return list;
  23 }
  24
  25 void *list_node_create(void *element) {
  26     list_node_t *node = memory_allocate(sizeof(list_node_t));
  27     node->element     = element;
  28     node->next        = NULL;
  29     node->prev        = NULL;
  30     return node;
  31 }
  32
  33 void list_push(list_t *list, void *element) {
  34     list_node_t *node = list_node_create(element);
  35     if (!list->head)
  36         list->head = node;
  37     else {
  38         list->tail->next = node;
  39         node->prev       = list->tail;
  40     }
  41     list->tail = node;
  42     list->length++;
  43 }
  44
  45 void *list_pop(list_t *list) {
  46     if (!list->head)
  47         return NULL;
  48     void *element = list->tail->element;
  49     list->tail = list->tail->prev;
  50     if (list->tail)
  51         list->tail->next = NULL;
  52     else
  53         list->head = NULL;
  54     list->length--;
  55     return element;
  56 }
  57
  58 void *list_shift(list_t *list) {
  59     if (!list->head)
  60         return NULL;
  61     void *element = list->head->element;
  62     list->head = list->head->next;
  63     if (list->head)
  64         list->head->prev = NULL;
  65     else
  66         list->tail = NULL;
  67     list->length--;
  68     return element;
  69 }
  70
  71 int list_length(list_t *list) {
  72     return list->length;
  73 }
  74
  75 list_iterator_t *list_iterator(list_t *list) {
  76     list_iterator_t *iter = memory_allocate(sizeof(list_iterator_t));
  77     iter->pointer         = list->head;
  78     return iter;
  79 }
  80
  81 void *list_iterator_next(list_iterator_t *iter) {
  82     void *ret;
  83
  84     if (!iter->pointer)
  85         return NULL;
  86
  87     ret           = iter->pointer->element;
  88     iter->pointer = iter->pointer->next;
  89
  90     return ret;
  91 }
  92
  93 bool list_iterator_end(list_iterator_t *iter) {
  94     return !iter->pointer;
  95 }
  96
  97 static void list_shiftify(list_t *list, void *element) {
  98     list_node_t *node = list_node_create(element);
  99     node->next = list->head;
 100     if (list->head)
 101         list->head->prev = node;
 102     list->head = node;
 103     if (!list->tail)
 104         list->tail = node;
 105     list->length++;
 106 }
 107
 108 list_t *list_reverse(list_t *list) {
 109     list_t *ret = list_create();
 110     for (list_iterator_t *it = list_iterator(list); !list_iterator_end(it); )
 111         list_shiftify(ret, list_iterator_next(it));
 112     return ret;
 113 }
 114
 115 void *list_tail(list_t *list) {
 116     if (!list->head)
 117         return NULL;
 118
 119     list_node_t *node = list->head;
 120     while (node->next)
 121         node = node->next;
 122
 123     return node->element;
 124 }
 125
 126 void *list_head(list_t *list) {
 127     return list->head->element;
 128 }
 129
 130 void list_empty(list_t *list) {
 131     list->length = 0;
 132     list->head   = NULL;
 133     list->tail   = NULL;
 134 }
 135
 136 list_t *list_default(void *item) {
 137     list_t *list = list_create();
 138     list_push(list, item);
 139     return list;
 140 }