code.delx.au - pulseaudio/blob - src/idxset.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #include "idxset.h"
   7
   8 struct idxset_entry {
   9     void *data;
  10     uint32_t index;
  11     unsigned hash_value;
  12
  13     struct idxset_entry *hash_prev, *hash_next;
  14     struct idxset_entry* iterate_prev, *iterate_next;
  15 };
  16
  17 struct idxset {
  18     unsigned (*hash_func) (void *p);
  19     int (*compare_func)(void *a, void *b);
  20
  21     unsigned hash_table_size, n_entries;
  22     struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
  23     uint32_t index, start_index, array_size;
  24 };
  25
  26 static unsigned trivial_hash_func(void *p) {
  27     return (unsigned) p;
  28 }
  29
  30 static int trivial_compare_func(void *a, void *b) {
  31     return a != b;
  32 }
  33
  34 struct idxset* idxset_new(unsigned (*hash_func) (void *p), int (*compare_func) (void*a, void*b)) {
  35     struct idxset *s;
  36
  37     s = malloc(sizeof(struct idxset));
  38     assert(s);
  39     s->hash_func = hash_func ? hash_func : trivial_hash_func;
  40     s->compare_func = compare_func ? compare_func : trivial_compare_func;
  41     s->hash_table_size = 1023;
  42     s->hash_table = malloc(sizeof(struct idxset_entry*)*s->hash_table_size);
  43     assert(s->hash_table);
  44     memset(s->hash_table, 0, sizeof(struct idxset_entry*)*s->hash_table_size);
  45     s->array = NULL;
  46     s->array_size = 0;
  47     s->index = 0;
  48     s->start_index = 0;
  49     s->n_entries = 0;
  50
  51     s->iterate_list_head = s->iterate_list_tail = NULL;
  52
  53     return s;
  54 }
  55
  56 void idxset_free(struct idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
  57     assert(s);
  58
  59     if (free_func) {
  60         while (s->iterate_list_head) {
  61             struct idxset_entry *e = s->iterate_list_head;
  62             s->iterate_list_head = s->iterate_list_head->iterate_next;
  63
  64             if (free_func)
  65                 free_func(e->data, userdata);
  66             free(e);
  67         }
  68     }
  69
  70     free(s->hash_table);
  71     free(s->array);
  72     free(s);
  73 }
  74
  75 static struct idxset_entry* hash_scan(struct idxset *s, struct idxset_entry* e, void *p) {
  76     assert(p);
  77
  78     assert(s->compare_func);
  79     for (; e; e = e->hash_next)
  80         if (s->compare_func(e->data, p) == 0)
  81             return e;
  82
  83     return NULL;
  84 }
  85
  86 static void extend_array(struct idxset *s, uint32_t index) {
  87     uint32_t i, j, l;
  88     struct idxset_entry** n;
  89     assert(index >= s->start_index);
  90
  91     if (index < s->start_index + s->array_size)
  92         return;
  93
  94     for (i = 0; i < s->array_size; i++)
  95         if (s->array[i])
  96             break;
  97
  98     l = index - s->start_index - i + 100;
  99     n = malloc(sizeof(struct hash_table_entry*)*l);
 100     assert(n);
 101     memset(n, 0, sizeof(struct hash_table_entry*)*l);
 102
 103     for (j = 0; j < s->array_size-i; j++)
 104         n[j] = s->array[i+j];
 105
 106     free(s->array);
 107
 108     s->array = n;
 109     s->array_size = l;
 110     s->start_index += i;
 111 }
 112
 113 static struct idxset_entry** array_index(struct idxset*s, uint32_t index) {
 114     if (index >= s->start_index + s->array_size)
 115         return NULL;
 116
 117     if (index < s->start_index)
 118         return NULL;
 119
 120     return s->array + (index - s->start_index);
 121 }
 122
 123 int idxset_put(struct idxset*s, void *p, uint32_t *index) {
 124     unsigned h;
 125     struct idxset_entry *e, **a;
 126     assert(s && p);
 127
 128     assert(s->hash_func);
 129     h = s->hash_func(p) % s->hash_table_size;
 130
 131     assert(s->hash_table);
 132     if ((e = hash_scan(s, s->hash_table[h], p))) {
 133         if (index)
 134             *index = e->index;
 135
 136         return -1;
 137     }
 138
 139     e = malloc(sizeof(struct idxset_entry));
 140     assert(e);
 141
 142     e->data = p;
 143     e->index = s->index++;
 144     e->hash_value = h;
 145
 146     /* Insert into hash table */
 147     e->hash_next = s->hash_table[h];
 148     e->hash_prev = NULL;
 149     if (s->hash_table[h])
 150         s->hash_table[h]->hash_prev = e;
 151     s->hash_table[h] = e;
 152
 153     /* Insert into array */
 154     extend_array(s, e->index);
 155     a = array_index(s, e->index);
 156     assert(a && !*a);
 157     *a = e;
 158
 159     /* Insert into linked list */
 160     e->iterate_next = NULL;
 161     e->iterate_prev = s->iterate_list_tail;
 162     if (s->iterate_list_tail) {
 163         assert(s->iterate_list_head);
 164         s->iterate_list_tail->iterate_next = e;
 165     } else {
 166         assert(!s->iterate_list_head);
 167         s->iterate_list_head = e;
 168     }
 169     s->iterate_list_tail = e;
 170
 171     s->n_entries++;
 172     assert(s->n_entries >= 1);
 173
 174     if (index)
 175         *index = e->index;
 176
 177     return 0;
 178 }
 179
 180 void* idxset_get_by_index(struct idxset*s, uint32_t index) {
 181     struct idxset_entry **a;
 182     assert(s);
 183
 184     if (!(a = array_index(s, index)))
 185         return NULL;
 186
 187     if (!*a)
 188         return NULL;
 189
 190     return (*a)->data;
 191 }
 192
 193 void* idxset_get_by_data(struct idxset*s, void *p, uint32_t *index) {
 194     unsigned h;
 195     struct idxset_entry *e;
 196     assert(s && p);
 197
 198     assert(s->hash_func);
 199     h = s->hash_func(p) % s->hash_table_size;
 200
 201     assert(s->hash_table);
 202     if (!(e = hash_scan(s, s->hash_table[h], p)))
 203         return NULL;
 204
 205     if (index)
 206         *index = e->index;
 207
 208     return e->data;
 209 }
 210
 211 static void remove_entry(struct idxset *s, struct idxset_entry *e) {
 212     struct idxset_entry **a;
 213     assert(s && e);
 214
 215     /* Remove from array */
 216     a = array_index(s, e->index);
 217     assert(a && *a && *a == e);
 218     *a = NULL;
 219
 220     /* Remove from linked list */
 221     if (e->iterate_next)
 222         e->iterate_next->iterate_prev = e->iterate_prev;
 223     else
 224         s->iterate_list_tail = e->iterate_prev;
 225
 226     if (e->iterate_prev)
 227         e->iterate_prev->iterate_next = e->iterate_next;
 228     else
 229         s->iterate_list_head = e->iterate_next;
 230
 231     /* Remove from hash table */
 232     if (e->hash_next)
 233         e->hash_next->hash_prev = e->hash_prev;
 234
 235     if (e->hash_prev)
 236         e->hash_prev->hash_next = e->hash_next;
 237     else
 238         s->hash_table[e->hash_value] = e->hash_next;
 239
 240     free(e);
 241
 242     assert(s->n_entries >= 1);
 243     s->n_entries--;
 244 }
 245
 246 void* idxset_remove_by_index(struct idxset*s, uint32_t index) {
 247     struct idxset_entry **a;
 248     void *data;
 249
 250     assert(s);
 251
 252     if (!(a = array_index(s, index)))
 253         return NULL;
 254
 255     data = (*a)->data;
 256     remove_entry(s, *a);
 257
 258     return data;
 259 }
 260
 261 void* idxset_remove_by_data(struct idxset*s, void *data, uint32_t *index) {
 262     struct idxset_entry *e;
 263     unsigned h;
 264
 265     assert(s->hash_func);
 266     h = s->hash_func(data) % s->hash_table_size;
 267
 268     assert(s->hash_table);
 269     if (!(e = hash_scan(s, s->hash_table[h], data)))
 270         return NULL;
 271
 272     data = e->data;
 273     if (index)
 274         *index = e->index;
 275
 276     remove_entry(s, e);
 277
 278     return data;
 279 }
 280
 281 void* idxset_rrobin(struct idxset *s, uint32_t *index) {
 282     struct idxset_entry **a, *e = NULL;
 283     assert(s && index);
 284
 285     if ((a = array_index(s, *index)) && *a)
 286         e = (*a)->iterate_next;
 287
 288     if (!e)
 289         e = s->iterate_list_head;
 290
 291     if (!e)
 292         return NULL;
 293
 294     *index = e->index;
 295     return e->data;
 296 }
 297
 298 void* idxset_first(struct idxset *s, uint32_t *index) {
 299     assert(s);
 300
 301     if (!s->iterate_list_head)
 302         return NULL;
 303
 304     if (index)
 305         *index = s->iterate_list_head->index;
 306     return s->iterate_list_head->data;
 307 }
 308
 309 void *idxset_next(struct idxset *s, uint32_t *index) {
 310     struct idxset_entry **a, *e = NULL;
 311     assert(s && index);
 312
 313     if ((a = array_index(s, *index)) && *a)
 314         e = (*a)->iterate_next;
 315
 316     if (e) {
 317         *index = e->index;
 318         return e->data;
 319     } else {
 320         *index = IDXSET_INVALID;
 321         return NULL;
 322     }
 323 }
 324
 325
 326 int idxset_foreach(struct idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) {
 327     struct idxset_entry *e;
 328     assert(s && func);
 329
 330     e = s->iterate_list_head;
 331     while (e) {
 332         int del = 0, r;
 333         struct idxset_entry *n = e->iterate_next;
 334
 335         r = func(e->data, e->index, &del, userdata);
 336
 337         if (del)
 338             remove_entry(s, e);
 339
 340         if (r < 0)
 341             return r;
 342
 343         e = n;
 344     }
 345
 346     return 0;
 347 }
 348
 349 unsigned idxset_ncontents(struct idxset*s) {
 350     assert(s);
 351     return s->n_entries;
 352 }
 353
 354 int idxset_isempty(struct idxset *s) {
 355     assert(s);
 356     return s->n_entries == 0;
 357 }
 358