polyp/idxset.c

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of polypaudio.
   5
   6   polypaudio is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published
   8   by the Free Software Foundation; either version 2 of the License,
   9   or (at your option) any later version.
  10
  11   polypaudio is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with polypaudio; if not, write to the Free Software
  18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  19   USA.
  20 ***/
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <stdio.h>
  27 #include <assert.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #include "idxset.h"
  32
  33 struct idxset_entry {
  34     void *data;
  35     uint32_t index;
  36     unsigned hash_value;
  37
  38     struct idxset_entry *hash_prev, *hash_next;
  39     struct idxset_entry* iterate_prev, *iterate_next;
  40 };
  41
  42 struct pa_idxset {
  43     unsigned (*hash_func) (const void *p);
  44     int (*compare_func)(const void *a, const void *b);
  45
  46     unsigned hash_table_size, n_entries;
  47     struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
  48     uint32_t index, start_index, array_size;
  49 };
  50
  51 unsigned pa_idxset_string_hash_func(const void *p) {
  52     unsigned hash = 0;
  53     const char *c;
  54
  55     for (c = p; *c; c++)
  56         hash = 31 * hash + *c;
  57
  58     return hash;
  59 }
  60
  61 int pa_idxset_string_compare_func(const void *a, const void *b) {
  62     return strcmp(a, b);
  63 }
  64
  65 unsigned pa_idxset_trivial_hash_func(const void *p) {
  66     return (unsigned) p;
  67 }
  68
  69 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  70     return a != b;
  71 }
  72
  73 struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
  74     struct pa_idxset *s;
  75
  76     s = malloc(sizeof(struct pa_idxset));
  77     assert(s);
  78     s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
  79     s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
  80     s->hash_table_size = 1023;
  81     s->hash_table = malloc(sizeof(struct idxset_entry*)*s->hash_table_size);
  82     assert(s->hash_table);
  83     memset(s->hash_table, 0, sizeof(struct idxset_entry*)*s->hash_table_size);
  84     s->array = NULL;
  85     s->array_size = 0;
  86     s->index = 0;
  87     s->start_index = 0;
  88     s->n_entries = 0;
  89
  90     s->iterate_list_head = s->iterate_list_tail = NULL;
  91
  92     return s;
  93 }
  94
  95 void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
  96     assert(s);
  97
  98     if (free_func) {
  99         while (s->iterate_list_head) {
 100             struct idxset_entry *e = s->iterate_list_head;
 101             s->iterate_list_head = s->iterate_list_head->iterate_next;
 102
 103             if (free_func)
 104                 free_func(e->data, userdata);
 105             free(e);
 106         }
 107     }
 108
 109     free(s->hash_table);
 110     free(s->array);
 111     free(s);
 112 }
 113
 114 static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, void *p) {
 115     assert(p);
 116
 117     assert(s->compare_func);
 118     for (; e; e = e->hash_next)
 119         if (s->compare_func(e->data, p) == 0)
 120             return e;
 121
 122     return NULL;
 123 }
 124
 125 static void extend_array(struct pa_idxset *s, uint32_t index) {
 126     uint32_t i, j, l;
 127     struct idxset_entry** n;
 128     assert(index >= s->start_index);
 129
 130     if (index < s->start_index + s->array_size)
 131         return;
 132
 133     for (i = 0; i < s->array_size; i++)
 134         if (s->array[i])
 135             break;
 136
 137     l = index - s->start_index - i + 100;
 138     n = malloc(sizeof(struct hash_table_entry*)*l);
 139     assert(n);
 140     memset(n, 0, sizeof(struct hash_table_entry*)*l);
 141
 142     for (j = 0; j < s->array_size-i; j++)
 143         n[j] = s->array[i+j];
 144
 145     free(s->array);
 146
 147     s->array = n;
 148     s->array_size = l;
 149     s->start_index += i;
 150 }
 151
 152 static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) {
 153     if (index >= s->start_index + s->array_size)
 154         return NULL;
 155
 156     if (index < s->start_index)
 157         return NULL;
 158
 159     return s->array + (index - s->start_index);
 160 }
 161
 162 int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) {
 163     unsigned h;
 164     struct idxset_entry *e, **a;
 165     assert(s && p);
 166
 167     assert(s->hash_func);
 168     h = s->hash_func(p) % s->hash_table_size;
 169
 170     assert(s->hash_table);
 171     if ((e = hash_scan(s, s->hash_table[h], p))) {
 172         if (index)
 173             *index = e->index;
 174
 175         return -1;
 176     }
 177
 178     e = malloc(sizeof(struct idxset_entry));
 179     assert(e);
 180
 181     e->data = p;
 182     e->index = s->index++;
 183     e->hash_value = h;
 184
 185     /* Insert into hash table */
 186     e->hash_next = s->hash_table[h];
 187     e->hash_prev = NULL;
 188     if (s->hash_table[h])
 189         s->hash_table[h]->hash_prev = e;
 190     s->hash_table[h] = e;
 191
 192     /* Insert into array */
 193     extend_array(s, e->index);
 194     a = array_index(s, e->index);
 195     assert(a && !*a);
 196     *a = e;
 197
 198     /* Insert into linked list */
 199     e->iterate_next = NULL;
 200     e->iterate_prev = s->iterate_list_tail;
 201     if (s->iterate_list_tail) {
 202         assert(s->iterate_list_head);
 203         s->iterate_list_tail->iterate_next = e;
 204     } else {
 205         assert(!s->iterate_list_head);
 206         s->iterate_list_head = e;
 207     }
 208     s->iterate_list_tail = e;
 209
 210     s->n_entries++;
 211     assert(s->n_entries >= 1);
 212
 213     if (index)
 214         *index = e->index;
 215
 216     return 0;
 217 }
 218
 219 void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index) {
 220     struct idxset_entry **a;
 221     assert(s);
 222
 223     if (!(a = array_index(s, index)))
 224         return NULL;
 225
 226     if (!*a)
 227         return NULL;
 228
 229     return (*a)->data;
 230 }
 231
 232 void* pa_idxset_get_by_data(struct pa_idxset*s, void *p, uint32_t *index) {
 233     unsigned h;
 234     struct idxset_entry *e;
 235     assert(s && p);
 236
 237     assert(s->hash_func);
 238     h = s->hash_func(p) % s->hash_table_size;
 239
 240     assert(s->hash_table);
 241     if (!(e = hash_scan(s, s->hash_table[h], p)))
 242         return NULL;
 243
 244     if (index)
 245         *index = e->index;
 246
 247     return e->data;
 248 }
 249
 250 static void remove_entry(struct pa_idxset *s, struct idxset_entry *e) {
 251     struct idxset_entry **a;
 252     assert(s && e);
 253
 254     /* Remove from array */
 255     a = array_index(s, e->index);
 256     assert(a && *a && *a == e);
 257     *a = NULL;
 258
 259     /* Remove from linked list */
 260     if (e->iterate_next)
 261         e->iterate_next->iterate_prev = e->iterate_prev;
 262     else
 263         s->iterate_list_tail = e->iterate_prev;
 264
 265     if (e->iterate_prev)
 266         e->iterate_prev->iterate_next = e->iterate_next;
 267     else
 268         s->iterate_list_head = e->iterate_next;
 269
 270     /* Remove from hash table */
 271     if (e->hash_next)
 272         e->hash_next->hash_prev = e->hash_prev;
 273
 274     if (e->hash_prev)
 275         e->hash_prev->hash_next = e->hash_next;
 276     else
 277         s->hash_table[e->hash_value] = e->hash_next;
 278
 279     free(e);
 280
 281     assert(s->n_entries >= 1);
 282     s->n_entries--;
 283 }
 284
 285 void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index) {
 286     struct idxset_entry **a;
 287     void *data;
 288
 289     assert(s);
 290
 291     if (!(a = array_index(s, index)))
 292         return NULL;
 293
 294     data = (*a)->data;
 295     remove_entry(s, *a);
 296
 297     return data;
 298 }
 299
 300 void* pa_idxset_remove_by_data(struct pa_idxset*s, void *data, uint32_t *index) {
 301     struct idxset_entry *e;
 302     unsigned h;
 303
 304     assert(s->hash_func);
 305     h = s->hash_func(data) % s->hash_table_size;
 306
 307     assert(s->hash_table);
 308     if (!(e = hash_scan(s, s->hash_table[h], data)))
 309         return NULL;
 310
 311     data = e->data;
 312     if (index)
 313         *index = e->index;
 314
 315     remove_entry(s, e);
 316
 317     return data;
 318 }
 319
 320 void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) {
 321     struct idxset_entry **a, *e = NULL;
 322     assert(s && index);
 323
 324     if ((a = array_index(s, *index)) && *a)
 325         e = (*a)->iterate_next;
 326
 327     if (!e)
 328         e = s->iterate_list_head;
 329
 330     if (!e)
 331         return NULL;
 332
 333     *index = e->index;
 334     return e->data;
 335 }
 336
 337 void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) {
 338     assert(s);
 339
 340     if (!s->iterate_list_head)
 341         return NULL;
 342
 343     if (index)
 344         *index = s->iterate_list_head->index;
 345     return s->iterate_list_head->data;
 346 }
 347
 348 void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) {
 349     struct idxset_entry **a, *e = NULL;
 350     assert(s && index);
 351
 352     if ((a = array_index(s, *index)) && *a)
 353         e = (*a)->iterate_next;
 354
 355     if (e) {
 356         *index = e->index;
 357         return e->data;
 358     } else {
 359         *index = PA_IDXSET_INVALID;
 360         return NULL;
 361     }
 362 }
 363
 364
 365 int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) {
 366     struct idxset_entry *e;
 367     assert(s && func);
 368
 369     e = s->iterate_list_head;
 370     while (e) {
 371         int del = 0, r;
 372         struct idxset_entry *n = e->iterate_next;
 373
 374         r = func(e->data, e->index, &del, userdata);
 375
 376         if (del)
 377             remove_entry(s, e);
 378
 379         if (r < 0)
 380             return r;
 381
 382         e = n;
 383     }
 384
 385     return 0;
 386 }
 387
 388 unsigned pa_idxset_ncontents(struct pa_idxset*s) {
 389     assert(s);
 390     return s->n_entries;
 391 }
 392
 393 int pa_idxset_isempty(struct pa_idxset *s) {
 394     assert(s);
 395     return s->n_entries == 0;
 396 }
 397