list.c

   1 #include "list.h"
   2 #include <assert.h>
   3 #include <stdlib.h>
   4
   5 struct d_list {
   6     d_list_it_t *top;
   7     d_list_it_t *bottom;
   8     int len;
   9     int ref;
  10 };
  11
  12 #define check_list(list) \
  13     assert((list->len == 0 && !list->top && !list->bottom) || \
  14            (list->len > 0 && list->top && list->bottom))
  15
  16
  17 d_list_t*
  18 list_new(void)
  19 {
  20     d_list_t *list = malloc(sizeof(d_list_t));
  21     list->top = NULL;
  22     list->bottom = NULL;
  23     list->ref = 1;
  24     list->len = 0;
  25     return list;
  26 }
  27
  28 void
  29 list_ref(d_list_t *list)
  30 {
  31     ++list->ref;
  32 }
  33
  34 void
  35 list_unref(d_list_t *list)
  36 {
  37     if (list && --list->ref == 0) {
  38         while (list->len)
  39             list_delete_link(list, list->top);
  40         free(list);
  41     }
  42 }
  43
  44 d_list_it_t*
  45 list_prepend(d_list_t *list, void *data)
  46 {
  47     d_list_it_t *n = malloc(sizeof(d_list_it_t));
  48     n->data = data;
  49
  50     n->prev = NULL;
  51     n->next = list->top;
  52     if (n->next) n->next->prev = n;
  53
  54     list->top = n;
  55     if (!list->bottom) list->bottom = n;
  56     ++list->len;
  57     return n;
  58 }
  59
  60 d_list_it_t*
  61 list_append(d_list_t *list, void *data)
  62 {
  63     d_list_it_t *n = malloc(sizeof(d_list_it_t));
  64     n->data = data;
  65
  66     n->prev = list->bottom;
  67     n->next = NULL;
  68     if (n->prev) n->prev->next = n;
  69
  70     list->bottom = n;
  71     if (!list->top) list->top = n;
  72     ++list->len;
  73     return n;
  74 }
  75
  76 void
  77 list_delete_link(d_list_t *list, d_list_it_t *pos)
  78 {
  79     d_list_it_t *prev = pos->prev;
  80     d_list_it_t *next = pos->next;
  81
  82     if (next)
  83         next->prev = prev;
  84     if (prev)
  85         prev->next = next;
  86     if (!next) {
  87         assert(list->bottom == pos);
  88         list->bottom = prev;
  89     }
  90     if (!prev) {
  91         assert(list->top == pos);
  92         list->top = next;
  93     }
  94
  95     --list->len;
  96     check_list(list);
  97     free(pos);
  98 }
  99
 100 void
 101 list_move_before(d_list_t *list, d_list_it_t *move, d_list_it_t *before)
 102 {
 103     d_list_it_t *prev, *next;
 104
 105     /* these won't move it anywhere */
 106     if (move == before || move->next == before) return;
 107
 108     prev = move->prev;
 109     next = move->next;
 110
 111     /* remove it from the list */
 112     if (next) next->prev = prev;
 113     else      list->bottom = prev;
 114     if (prev) prev->next = next;
 115     else      list->top = next;
 116
 117     /* reinsert it */
 118     if (before) {
 119         move->next = before;
 120         move->prev = before->prev;
 121         move->next->prev = move;
 122         if (move->prev) move->prev->next = move;
 123     }
 124     else {
 125         /* after the bottom */
 126         move->prev = list->bottom;
 127         move->next = NULL;
 128         if (move->prev) move->prev->next = move;
 129         list->bottom = move;
 130     }
 131
 132     if (!move->prev) list->top = move;
 133 }
 134
 135 void
 136 list_remove(d_list_t *list, void *data)
 137 {
 138     d_list_it_t *it = list_find(list, data);
 139     if (it) list_delete_link(list, it);
 140 }
 141
 142 int
 143 list_length(d_list_t *list)
 144 {
 145     return list->len;
 146 }
 147
 148 d_list_it_t*
 149 list_top(d_list_t *list)
 150 {
 151     return list->top;
 152 }
 153
 154 d_list_it_t*
 155 list_bottom(d_list_t *list)
 156 {
 157     return list->bottom;
 158 }
 159
 160 d_list_it_t*
 161 list_nth(d_list_t *list, int n)
 162 {
 163     int i;
 164     d_list_it_t *it;
 165
 166     assert(n >= 0);
 167     assert(n < list->len);
 168
 169     it = list->top;
 170     for (i = 0; i < n; ++i)
 171         it = it->next;
 172     return it;
 173 }
 174
 175 d_list_it_t*
 176 list_find(d_list_t *list, void *data)
 177 {
 178     d_list_it_t *it;
 179
 180     for (it = list->top; it; it = it->next)
 181         if (it->data == data) return it;
 182     return NULL;
 183 }