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 void
  61 list_delete_link(d_list_t *list, d_list_it_t *pos)
  62 {
  63     d_list_it_t *prev = pos->prev;
  64     d_list_it_t *next = pos->next;
  65
  66     if (next)
  67         next->prev = prev;
  68     if (prev)
  69         prev->next = next;
  70     if (!next) {
  71         assert(list->bottom == pos);
  72         list->bottom = prev;
  73     }
  74     if (!prev) {
  75         assert(list->top == pos);
  76         list->top = next;
  77     }
  78
  79     --list->len;
  80     check_list(list);
  81     free(pos);
  82 }
  83
  84 void
  85 list_move_before(d_list_t *list, d_list_it_t *move, d_list_it_t *before)
  86 {
  87     d_list_it_t *prev, *next;
  88
  89     /* these won't move it anywhere */
  90     if (move == before || move->next == before) return;
  91
  92     prev = move->prev;
  93     next = move->next;
  94
  95     /* remove it from the list */
  96     if (next) next->prev = prev;
  97     else      list->bottom = prev;
  98     if (prev) prev->next = next;
  99     else      list->top = next;
 100
 101     /* reinsert it */
 102     if (before) {
 103         move->next = before;
 104         move->prev = before->prev;
 105         move->next->prev = move;
 106         if (move->prev) move->prev->next = move;
 107     }
 108     else {
 109         /* after the bottom */
 110         move->prev = list->bottom;
 111         move->next = NULL;
 112         if (move->prev) move->prev->next = move;
 113         list->bottom = move;
 114     }
 115
 116     if (!move->prev) list->top = move;
 117 }
 118
 119 int
 120 list_length(d_list_t *list)
 121 {
 122     return list->len;
 123 }
 124
 125 d_list_it_t*
 126 list_top(d_list_t *list)
 127 {
 128     return list->top;
 129 }
 130
 131 d_list_it_t*
 132 list_bottom(d_list_t *list)
 133 {
 134     return list->bottom;
 135 }
 136
 137 d_list_it_t*
 138 list_nth(d_list_t *list, int n)
 139 {
 140     int i;
 141     d_list_it_t *it;
 142
 143     assert(n >= 0);
 144     assert(n < list->len);
 145
 146     it = list->top;
 147     for (i = 0; i < n; ++i)
 148         it = it->next;
 149     return it;
 150 }