src/common/tree.c

   1 /*
   2 This is used for quick userlist insertion and lookup. It's not really
   3 a tree, but it could be :)
   4 */
   5
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <stdlib.h>
   9
  10 #include "tree.h"
  11
  12 #define ARRAY_GROW 32
  13
  14 struct _tree
  15 {
  16         int elements;
  17         int array_size;
  18         void **array;
  19         tree_cmp_func *cmp;
  20         void *data;
  21 };
  22
  23 tree *
  24 tree_new (tree_cmp_func *cmp, void *data)
  25 {
  26         tree *t = calloc (1, sizeof (tree));
  27         t->cmp = cmp;
  28         t->data = data;
  29         return t;
  30 }
  31
  32 void
  33 tree_destroy (tree *t)
  34 {
  35         if (t)
  36         {
  37                 if (t->array)
  38                         free (t->array);
  39                 free (t);
  40         }
  41 }
  42
  43 static int
  44 tree_find_insertion_pos (tree *t, void *key, int *done)
  45 {
  46         int c, u, l, idx;
  47
  48         if (t->elements < 1)
  49         {
  50                 *done = 1;
  51                 t->array[0] = key;
  52                 t->elements++;
  53                 return 0;
  54         }
  55
  56         if (t->elements < 2)
  57         {
  58                 *done = 1;
  59                 c = t->cmp (key, t->array[0], t->data);
  60                 if (c == 0)
  61                         return -1;
  62                 t->elements++;
  63                 if (c > 0)
  64                 {
  65                         t->array[1] = key;
  66                         return 1;
  67                 }
  68                 t->array[1] = t->array[0];
  69                 t->array[0] = key;
  70                 return 0;
  71         }
  72
  73         *done = 0;
  74
  75         c = t->cmp (key, t->array[0], t->data);
  76         if (c < 0)
  77                 return 0;       /* prepend */
  78
  79         c = t->cmp (key, t->array[t->elements - 1], t->data);
  80         if (c > 0)
  81                 return t->elements;     /* append */
  82
  83         l = 0;
  84         u = t->elements - 1;
  85         while (1)
  86         {
  87                 idx = (l + u) / 2;
  88                 c = t->cmp (key, t->array[idx], t->data);
  89
  90                 if (0 > c)
  91                         u = idx;
  92                 else if (0 < c && 0 > t->cmp (key, t->array[idx+1], t->data))
  93                         return idx + 1;
  94                 else if (c == 0)
  95                         return -1;
  96                 else
  97                         l = idx + 1;
  98         }
  99 }
 100
 101 static void
 102 tree_insert_at_pos (tree *t, void *key, int pos)
 103 {
 104         int post_bytes;
 105
 106         /* append is easy */
 107         if (pos != t->elements)
 108         {
 109                 post_bytes = (t->elements - pos) * sizeof (void *);
 110                 memmove (&t->array[pos + 1], &t->array[pos], post_bytes);
 111         }
 112
 113         t->array[pos] = key;
 114         t->elements++;
 115 }
 116
 117 static void *
 118 mybsearch (const void *key, void **array, size_t nmemb,
 119                           int (*compar) (const void *, const void *, void *data), void *data, int *pos)
 120 {
 121         int l, u, idx;
 122         int comparison;
 123
 124         l = 0;
 125         u = nmemb;
 126         while (l < u)
 127         {
 128                 idx = (l + u) / 2;
 129                 comparison = (*compar) (key, array[idx], data);
 130                 if (comparison < 0)
 131                         u = idx;
 132                 else if (comparison > 0)
 133                         l = idx + 1;
 134                 else
 135                 {
 136                         *pos = idx;
 137                         return array[idx];
 138                 }
 139         }
 140
 141         return NULL;
 142 }
 143
 144 void *
 145 tree_find (tree *t, void *key, tree_cmp_func *cmp, void *data, int *pos)
 146 {
 147         if (!t || !t->array)
 148                 return NULL;
 149
 150         return mybsearch (key, &t->array[0], t->elements, cmp, data, pos);
 151 }
 152
 153 void
 154 tree_remove_at_pos (tree *t, int pos)
 155 {
 156         int post_bytes;
 157
 158         t->elements--;
 159         if (pos != t->elements)
 160         {
 161                 post_bytes = (t->elements - pos) * sizeof (void *);
 162                 memmove (&t->array[pos], &t->array[pos + 1], post_bytes);
 163         }
 164 }
 165
 166 int
 167 tree_remove (tree *t, void *key, int *pos)
 168 {
 169         void *data;
 170
 171         data = tree_find (t, key, t->cmp, t->data, pos);
 172         if (!data)
 173                 return 0;
 174
 175         tree_remove_at_pos (t, *pos);
 176         return 1;
 177 }
 178
 179 void
 180 tree_foreach (tree *t, tree_traverse_func *func, void *data)
 181 {
 182         int j;
 183
 184         if (!t || !t->array)
 185                 return;
 186
 187         for (j = 0; j < t->elements; j++)
 188         {
 189                 if (!func (t->array[j], data))
 190                         break;
 191         }
 192 }
 193
 194 static void
 195 tree_grow (tree *t)
 196 {
 197         if (t->array_size < t->elements + 1)
 198         {
 199                 int new_size = t->array_size + ARRAY_GROW;
 200
 201                 t->array = realloc (t->array, sizeof (void *) * new_size);
 202                 t->array_size = new_size;
 203         }
 204
 205 }
 206
 207 int
 208 tree_insert (tree *t, void *key)
 209 {
 210         int pos, done;
 211
 212         if (!t)
 213                 return -1;
 214
 215         tree_grow (t);
 216         pos = tree_find_insertion_pos (t, key, &done);
 217         if (!done && pos != -1)
 218                 tree_insert_at_pos (t, key, pos);
 219
 220         return pos;
 221 }
 222
 223 void
 224 tree_append (tree *t, void *key)
 225 {
 226         tree_grow (t);
 227         tree_insert_at_pos (t, key, t->elements);
 228 }
 229
 230 int tree_size (tree *t)
 231 {
 232         return t->elements;
 233 }
 234