list.c

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