src/tlist/tlist.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "../../include/tlist.h"
   4
   5 #ifndef UINT_MAX
   6 #define UINT_MAX 0xffffffffU
   7 #endif
   8
   9 static int mrand(unsigned *seed)
  10 {
  11        return (*seed = (*seed+1) * 1103515245 + 12345 - 1)+1 & 0x7fffffff;
  12 }
  13
  14 typedef struct item* pitem;
  15 struct item {
  16         unsigned prior, cnt;
  17         pitem l, r;
  18 };
  19
  20 static unsigned cnt (pitem it) {
  21         return it ? it->cnt : 0;
  22 }
  23
  24 static void upd_cnt (pitem it) {
  25         if (it)
  26                 it->cnt = cnt(it->l) + cnt(it->r) + 1;
  27 }
  28
  29 static void merge (pitem *t, pitem l, pitem r) {
  30         if (!l || !r)
  31                 *t = l ? l : r;
  32         else if (l->prior > r->prior)
  33                 merge (&l->r, l->r, r),  *t = l;
  34         else
  35                 merge (&r->l, l, r->l),  *t = r;
  36         upd_cnt (*t);
  37 }
  38
  39 static void split (pitem t, pitem *l, pitem *r, unsigned key, unsigned add) {
  40         if (!t) {
  41                 *l = *r = 0;
  42                 return;
  43         }
  44         unsigned cur_key = add + cnt(t->l);
  45         if (key <= cur_key)
  46                 split (t->l, l, &t->l, key, add),  *r = t;
  47         else
  48                 split (t->r, &t->r, r, key, add + 1 + cnt(t->l)),  *l = t;
  49         upd_cnt (t);
  50 }
  51
  52 static pitem getitem(pitem t, unsigned idx, unsigned add) {
  53         if (!t) return t;
  54         unsigned ls = cnt (t->l), cur_key = add + ls;
  55         if (cur_key == idx) return t;
  56         if (cur_key < idx)
  57                 return getitem (t->r, idx, add + 1 + ls);
  58         else
  59                 return getitem (t->l, idx, add);
  60 }
  61
  62 static void insert(pitem *t, pitem n, unsigned idx) {
  63         pitem t1, t2;
  64         split (*t, &t1, &t2, idx, 0);
  65         merge (t, t1, n);
  66         merge (t, *t, t2);
  67 }
  68
  69 static void remove(pitem *t, unsigned idx, unsigned add) {
  70         pitem n;
  71         if (!(*t)) return;
  72         unsigned cur_key = add + cnt ((*t)->l), new_add = cur_key + 1;
  73         unsigned rk, lk = rk = UINT_MAX;
  74         if ((*t)->l) lk = cnt ((*t)->l->l) + add;
  75         if ((*t)->r) rk = cnt ((*t)->r->l) + new_add;
  76         if (cur_key == idx) {
  77                 merge (t, (*t)->l, (*t)->r);
  78         } else if (lk == idx) {
  79                 merge (&n, (*t)->l->l, (*t)->l->r);
  80                 (*t)->l = n;
  81                 upd_cnt (*t);
  82         } else if (rk == idx) {
  83                 merge (&n, (*t)->r->l, (*t)->r->r);
  84                 (*t)->r = n;
  85                 upd_cnt (*t);
  86         } else if (cur_key < idx) {
  87                 remove (&(*t)->r, idx, new_add);
  88                 upd_cnt (*t);
  89         } else {
  90                 remove (&(*t)->l, idx, add);
  91                 upd_cnt (*t);
  92         }
  93 }
  94
  95 static pitem new_item(void* value, unsigned valsz, unsigned *seed) {
  96         pitem n = malloc(sizeof(struct item) + valsz);
  97         if(!n) return n;
  98         memcpy(n+1, value, valsz);
  99         n->prior = mrand(seed);
 100         n->cnt = 1;
 101         n->l = n->r = 0;
 102         return n;
 103 }
 104
 105 struct tlist {
 106         unsigned seed;
 107         unsigned itemsize;
 108         pitem root;
 109 };
 110
 111 struct tlist *tlist_new(unsigned itemsize) {
 112         struct tlist* new = malloc(sizeof (struct tlist));
 113         if(!new) return 0;
 114         new->seed = 385-1;
 115         new->itemsize = itemsize;
 116         new->root = 0;
 117         return new;
 118 }
 119
 120 static void* data(pitem it) {
 121         return it+1;
 122 }
 123
 124 size_t tlist_getsize(struct tlist* t) {
 125         return cnt(t->root);
 126 }
 127
 128 void* tlist_get(struct tlist* t, size_t idx) {
 129         return data(getitem(t->root, idx, 0));
 130 }
 131
 132 int tlist_insert(struct tlist* t, size_t idx, void *value) {
 133         if(idx > cnt (t->root)) return 0;
 134         pitem new = new_item(value, t->itemsize, &t->seed);
 135         if(!new) return 0;
 136         insert(&t->root, new, idx);
 137         return 1;
 138 }
 139
 140 int tlist_append(struct tlist* t, void *value) {
 141         return tlist_insert(t, cnt(t->root), value);
 142 }
 143
 144 static int tlist_delete_impl(struct tlist *t, size_t idx, int deep) {
 145         if(idx >= cnt (t->root)) return 0;
 146         pitem it = getitem(t->root, idx, 0);
 147         if(deep) free(data(it));
 148         remove(&t->root, idx, 0);
 149         free(it);
 150         return 1;
 151 }
 152
 153 int tlist_delete(struct tlist *t, size_t idx) {
 154         return tlist_delete_impl(t, idx, 0);
 155 }
 156
 157 int tlist_delete_deep(struct tlist *t, size_t idx) {
 158         return tlist_delete_impl(t, idx, 1);
 159 }
 160
 161 static void tlist_free_items_impl(struct tlist *t, int deep) {
 162         while(cnt(t->root)) tlist_delete_impl(t, 0, deep);
 163 }
 164
 165 void tlist_free_items(struct tlist *t) {
 166         tlist_free_items_impl(t, 0);
 167 }
 168
 169 void tlist_free_items_deep(struct tlist *t) {
 170         tlist_free_items_impl(t, 1);
 171 }
 172
 173 static void* tlist_free_impl(struct tlist *t, int deep) {
 174         tlist_free_items_impl(t, deep);
 175         free(t);
 176         return 0;
 177 }
 178
 179 void *tlist_free(struct tlist *t) {
 180         return tlist_free_impl(t, 0);
 181 }
 182
 183 void *tlist_free_deep(struct tlist *t) {
 184         return tlist_free_impl(t, 1);
 185 }
 186
 187 #ifdef TLIST_TEST
 188 extern int printf(const char *__restrict, ...);
 189 float tlist_getbalance(struct tlist *t) {
 190         size_t n = tlist_getsize(t);
 191         int r, l;
 192         if (n == 0) return 1.0;
 193         l = cnt (t->root->l);
 194         r = cnt (t->root->r);
 195         printf("l %d, r %d, diff %d\n", l, r, abs(l-r));
 196         return 100.f - ((float)abs(l - r)/(n/100.f));
 197 }
 198 #endif