src/pulsecore/idxset.c

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