code.delx.au - pulseaudio/blob - 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 #include "xmalloc.h"
  33
  34 struct idxset_entry {
  35     void *data;
  36     uint32_t index;
  37     unsigned hash_value;
  38
  39     struct idxset_entry *hash_prev, *hash_next;
  40     struct idxset_entry* iterate_prev, *iterate_next;
  41 };
  42
  43 struct pa_idxset {
  44     unsigned (*hash_func) (const void *p);
  45     int (*compare_func)(const void *a, const void *b);
  46
  47     unsigned hash_table_size, n_entries;
  48     struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
  49     uint32_t index, start_index, array_size;
  50 };
  51
  52 unsigned pa_idxset_string_hash_func(const void *p) {
  53     unsigned hash = 0;
  54     const char *c;
  55
  56     for (c = p; *c; c++)
  57         hash = 31 * hash + *c;
  58
  59     return hash;
  60 }
  61
  62 int pa_idxset_string_compare_func(const void *a, const void *b) {
  63     return strcmp(a, b);
  64 }
  65
  66 unsigned pa_idxset_trivial_hash_func(const void *p) {
  67     return (unsigned) p;
  68 }
  69
  70 int pa_idxset_trivial_compare_func(const void *a, const void *b) {
  71     return a != b;
  72 }
  73
  74 struct pa_idxset* pa_idxset_new(unsigned (*hash_func) (const void *p), int (*compare_func) (const void*a, const void*b)) {
  75     struct pa_idxset *s;
  76
  77     s = pa_xmalloc(sizeof(struct pa_idxset));
  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 = pa_xmalloc0(sizeof(struct idxset_entry*)*s->hash_table_size);
  82     s->array = NULL;
  83     s->array_size = 0;
  84     s->index = 0;
  85     s->start_index = 0;
  86     s->n_entries = 0;
  87
  88     s->iterate_list_head = s->iterate_list_tail = NULL;
  89
  90     return s;
  91 }
  92
  93 void pa_idxset_free(struct pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
  94     assert(s);
  95
  96     while (s->iterate_list_head) {
  97         struct idxset_entry *e = s->iterate_list_head;
  98         s->iterate_list_head = s->iterate_list_head->iterate_next;
  99
 100         if (free_func)
 101             free_func(e->data, userdata);
 102         pa_xfree(e);
 103     }
 104
 105     pa_xfree(s->hash_table);
 106     pa_xfree(s->array);
 107     pa_xfree(s);
 108 }
 109
 110 static struct idxset_entry* hash_scan(struct pa_idxset *s, struct idxset_entry* e, const void *p) {
 111     assert(p);
 112
 113     assert(s->compare_func);
 114     for (; e; e = e->hash_next)
 115         if (s->compare_func(e->data, p) == 0)
 116             return e;
 117
 118     return NULL;
 119 }
 120
 121 static void extend_array(struct pa_idxset *s, uint32_t index) {
 122     uint32_t i, j, l;
 123     struct idxset_entry** n;
 124     assert(index >= s->start_index);
 125
 126     if (index < s->start_index + s->array_size)
 127         return;
 128
 129     for (i = 0; i < s->array_size; i++)
 130         if (s->array[i])
 131             break;
 132
 133     l = index - s->start_index - i + 100;
 134     n = pa_xmalloc0(sizeof(struct hash_table_entry*)*l);
 135
 136     for (j = 0; j < s->array_size-i; j++)
 137         n[j] = s->array[i+j];
 138
 139     pa_xfree(s->array);
 140
 141     s->array = n;
 142     s->array_size = l;
 143     s->start_index += i;
 144 }
 145
 146 static struct idxset_entry** array_index(struct pa_idxset*s, uint32_t index) {
 147     if (index >= s->start_index + s->array_size)
 148         return NULL;
 149
 150     if (index < s->start_index)
 151         return NULL;
 152
 153     return s->array + (index - s->start_index);
 154 }
 155
 156 int pa_idxset_put(struct pa_idxset*s, void *p, uint32_t *index) {
 157     unsigned h;
 158     struct idxset_entry *e, **a;
 159     assert(s && p);
 160
 161     assert(s->hash_func);
 162     h = s->hash_func(p) % s->hash_table_size;
 163
 164     assert(s->hash_table);
 165     if ((e = hash_scan(s, s->hash_table[h], p))) {
 166         if (index)
 167             *index = e->index;
 168
 169         return -1;
 170     }
 171
 172     e = pa_xmalloc(sizeof(struct idxset_entry));
 173     e->data = p;
 174     e->index = s->index++;
 175     e->hash_value = h;
 176
 177     /* Insert into hash table */
 178     e->hash_next = s->hash_table[h];
 179     e->hash_prev = NULL;
 180     if (s->hash_table[h])
 181         s->hash_table[h]->hash_prev = e;
 182     s->hash_table[h] = e;
 183
 184     /* Insert into array */
 185     extend_array(s, e->index);
 186     a = array_index(s, e->index);
 187     assert(a && !*a);
 188     *a = e;
 189
 190     /* Insert into linked list */
 191     e->iterate_next = NULL;
 192     e->iterate_prev = s->iterate_list_tail;
 193     if (s->iterate_list_tail) {
 194         assert(s->iterate_list_head);
 195         s->iterate_list_tail->iterate_next = e;
 196     } else {
 197         assert(!s->iterate_list_head);
 198         s->iterate_list_head = e;
 199     }
 200     s->iterate_list_tail = e;
 201
 202     s->n_entries++;
 203     assert(s->n_entries >= 1);
 204
 205     if (index)
 206         *index = e->index;
 207
 208     return 0;
 209 }
 210
 211 void* pa_idxset_get_by_index(struct pa_idxset*s, uint32_t index) {
 212     struct idxset_entry **a;
 213     assert(s);
 214
 215     if (!(a = array_index(s, index)))
 216         return NULL;
 217
 218     if (!*a)
 219         return NULL;
 220
 221     return (*a)->data;
 222 }
 223
 224 void* pa_idxset_get_by_data(struct pa_idxset*s, const void *p, uint32_t *index) {
 225     unsigned h;
 226     struct idxset_entry *e;
 227     assert(s && p);
 228
 229     assert(s->hash_func);
 230     h = s->hash_func(p) % s->hash_table_size;
 231
 232     assert(s->hash_table);
 233     if (!(e = hash_scan(s, s->hash_table[h], p)))
 234         return NULL;
 235
 236     if (index)
 237         *index = e->index;
 238
 239     return e->data;
 240 }
 241
 242 static void remove_entry(struct pa_idxset *s, struct idxset_entry *e) {
 243     struct idxset_entry **a;
 244     assert(s && e);
 245
 246     /* Remove from array */
 247     a = array_index(s, e->index);
 248     assert(a && *a && *a == e);
 249     *a = NULL;
 250
 251     /* Remove from linked list */
 252     if (e->iterate_next)
 253         e->iterate_next->iterate_prev = e->iterate_prev;
 254     else
 255         s->iterate_list_tail = e->iterate_prev;
 256
 257     if (e->iterate_prev)
 258         e->iterate_prev->iterate_next = e->iterate_next;
 259     else
 260         s->iterate_list_head = e->iterate_next;
 261
 262     /* Remove from hash table */
 263     if (e->hash_next)
 264         e->hash_next->hash_prev = e->hash_prev;
 265
 266     if (e->hash_prev)
 267         e->hash_prev->hash_next = e->hash_next;
 268     else
 269         s->hash_table[e->hash_value] = e->hash_next;
 270
 271     pa_xfree(e);
 272
 273     assert(s->n_entries >= 1);
 274     s->n_entries--;
 275 }
 276
 277 void* pa_idxset_remove_by_index(struct pa_idxset*s, uint32_t index) {
 278     struct idxset_entry **a;
 279     void *data;
 280
 281     assert(s);
 282
 283     if (!(a = array_index(s, index)))
 284         return NULL;
 285
 286     data = (*a)->data;
 287     remove_entry(s, *a);
 288
 289     return data;
 290 }
 291
 292 void* pa_idxset_remove_by_data(struct pa_idxset*s, const void *data, uint32_t *index) {
 293     struct idxset_entry *e;
 294     unsigned h;
 295     void *r;
 296
 297     assert(s->hash_func);
 298     h = s->hash_func(data) % s->hash_table_size;
 299
 300     assert(s->hash_table);
 301     if (!(e = hash_scan(s, s->hash_table[h], data)))
 302         return NULL;
 303
 304     r = e->data;
 305     if (index)
 306         *index = e->index;
 307
 308     remove_entry(s, e);
 309
 310     return r;
 311 }
 312
 313 void* pa_idxset_rrobin(struct pa_idxset *s, uint32_t *index) {
 314     struct idxset_entry **a, *e = NULL;
 315     assert(s && index);
 316
 317     if ((a = array_index(s, *index)) && *a)
 318         e = (*a)->iterate_next;
 319
 320     if (!e)
 321         e = s->iterate_list_head;
 322
 323     if (!e)
 324         return NULL;
 325
 326     *index = e->index;
 327     return e->data;
 328 }
 329
 330 void* pa_idxset_first(struct pa_idxset *s, uint32_t *index) {
 331     assert(s);
 332
 333     if (!s->iterate_list_head)
 334         return NULL;
 335
 336     if (index)
 337         *index = s->iterate_list_head->index;
 338     return s->iterate_list_head->data;
 339 }
 340
 341 void *pa_idxset_next(struct pa_idxset *s, uint32_t *index) {
 342     struct idxset_entry **a, *e = NULL;
 343     assert(s && index);
 344
 345     if ((a = array_index(s, *index)) && *a)
 346         e = (*a)->iterate_next;
 347
 348     if (e) {
 349         *index = e->index;
 350         return e->data;
 351     } else {
 352         *index = PA_IDXSET_INVALID;
 353         return NULL;
 354     }
 355 }
 356
 357
 358 int pa_idxset_foreach(struct pa_idxset*s, int (*func)(void *p, uint32_t index, int *del, void*userdata), void *userdata) {
 359     struct idxset_entry *e;
 360     assert(s && func);
 361
 362     e = s->iterate_list_head;
 363     while (e) {
 364         int del = 0, r;
 365         struct idxset_entry *n = e->iterate_next;
 366
 367         r = func(e->data, e->index, &del, userdata);
 368
 369         if (del)
 370             remove_entry(s, e);
 371
 372         if (r < 0)
 373             return r;
 374
 375         e = n;
 376     }
 377
 378     return 0;
 379 }
 380
 381 unsigned pa_idxset_ncontents(struct pa_idxset*s) {
 382     assert(s);
 383     return s->n_entries;
 384 }
 385
 386 int pa_idxset_isempty(struct pa_idxset *s) {
 387     assert(s);
 388     return s->n_entries == 0;
 389 }
 390