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

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