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

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