/***
This file is part of PulseAudio.
- Copyright 2004-2006 Lennart Poettering
+ Copyright 2004-2008 Lennart Poettering
Copyright 2006 Pierre Ossman <ossman@cendio.se> for Cendio AB
PulseAudio is free software; you can redistribute it and/or modify
#include <string.h>
#include <pulse/xmalloc.h>
-#include <pulsecore/macro.h>
#include <pulsecore/flist.h>
+#include <pulsecore/macro.h>
#include "idxset.h"
+#define NBUCKETS 127
+
struct idxset_entry {
+ uint32_t idx;
void *data;
- uint32_t index;
- unsigned hash_value;
- struct idxset_entry *hash_prev, *hash_next;
- struct idxset_entry* iterate_prev, *iterate_next;
+ struct idxset_entry *data_next, *data_previous;
+ struct idxset_entry *index_next, *index_previous;
+ struct idxset_entry *iterate_next, *iterate_previous;
};
struct pa_idxset {
pa_hash_func_t hash_func;
pa_compare_func_t compare_func;
- unsigned hash_table_size, n_entries;
- struct idxset_entry **hash_table, **array, *iterate_list_head, *iterate_list_tail;
- uint32_t index, start_index, array_size;
+ uint32_t current_index;
+
+ struct idxset_entry *iterate_list_head, *iterate_list_tail;
+ unsigned n_entries;
};
+#define BY_DATA(i) ((struct idxset_entry**) ((uint8_t*) (i) + PA_ALIGN(sizeof(pa_idxset))))
+#define BY_INDEX(i) (BY_DATA(i) + NBUCKETS)
+
PA_STATIC_FLIST_DECLARE(entries, 0, pa_xfree);
unsigned pa_idxset_string_hash_func(const void *p) {
const char *c;
for (c = p; *c; c++)
- hash = 31 * hash + *c;
+ hash = 31 * hash + (unsigned) *c;
return hash;
}
}
int pa_idxset_trivial_compare_func(const void *a, const void *b) {
- return a != b;
+ return a < b ? -1 : (a > b ? 1 : 0);
}
pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func) {
pa_idxset *s;
- s = pa_xnew(pa_idxset, 1);
+ s = pa_xmalloc0(PA_ALIGN(sizeof(pa_idxset)) + NBUCKETS*2*sizeof(struct idxset_entry*));
+
s->hash_func = hash_func ? hash_func : pa_idxset_trivial_hash_func;
s->compare_func = compare_func ? compare_func : pa_idxset_trivial_compare_func;
- s->hash_table_size = 127;
- s->hash_table = pa_xnew0(struct idxset_entry*, s->hash_table_size);
- s->array = NULL;
- s->array_size = 0;
- s->index = 0;
- s->start_index = 0;
- s->n_entries = 0;
+ s->current_index = 0;
+ s->n_entries = 0;
s->iterate_list_head = s->iterate_list_tail = NULL;
return s;
}
-void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata) {
+static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
pa_assert(s);
+ pa_assert(e);
- while (s->iterate_list_head) {
- struct idxset_entry *e = s->iterate_list_head;
- s->iterate_list_head = s->iterate_list_head->iterate_next;
+ /* Remove from iteration linked list */
+ if (e->iterate_next)
+ e->iterate_next->iterate_previous = e->iterate_previous;
+ else
+ s->iterate_list_tail = e->iterate_previous;
- if (free_func)
- free_func(e->data, userdata);
+ if (e->iterate_previous)
+ e->iterate_previous->iterate_next = e->iterate_next;
+ else
+ s->iterate_list_head = e->iterate_next;
- if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
- pa_xfree(e);
+ /* Remove from data hash table */
+ if (e->data_next)
+ e->data_next->data_previous = e->data_previous;
+
+ if (e->data_previous)
+ e->data_previous->data_next = e->data_next;
+ else {
+ unsigned hash = s->hash_func(e->data) % NBUCKETS;
+ BY_DATA(s)[hash] = e->data_next;
}
- pa_xfree(s->hash_table);
- pa_xfree(s->array);
- pa_xfree(s);
-}
+ /* Remove from index hash table */
+ if (e->index_next)
+ e->index_next->index_previous = e->index_previous;
-static struct idxset_entry* hash_scan(pa_idxset *s, struct idxset_entry* e, const void *p) {
- pa_assert(p);
+ if (e->index_previous)
+ e->index_previous->index_next = e->index_next;
+ else
+ BY_INDEX(s)[e->idx % NBUCKETS] = e->index_next;
- pa_assert(s->compare_func);
- for (; e; e = e->hash_next)
- if (s->compare_func(e->data, p) == 0)
- return e;
+ if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
+ pa_xfree(e);
- return NULL;
+ pa_assert(s->n_entries >= 1);
+ s->n_entries--;
}
-static void extend_array(pa_idxset *s, uint32_t idx) {
- uint32_t i, j, l;
- struct idxset_entry** n;
-
+void pa_idxset_free(pa_idxset *s, pa_free_cb_t free_cb) {
pa_assert(s);
- pa_assert(idx >= s->start_index);
-
- if (idx < s->start_index + s->array_size)
- return;
- for (i = 0; i < s->array_size; i++)
- if (s->array[i])
- break;
-
- l = idx - s->start_index - i + 100;
- n = pa_xnew0(struct idxset_entry*, l);
+ pa_idxset_remove_all(s, free_cb);
+ pa_xfree(s);
+}
- for (j = 0; j < s->array_size-i; j++)
- n[j] = s->array[i+j];
+static struct idxset_entry* data_scan(pa_idxset *s, unsigned hash, const void *p) {
+ struct idxset_entry *e;
+ pa_assert(s);
+ pa_assert(hash < NBUCKETS);
+ pa_assert(p);
- pa_xfree(s->array);
+ for (e = BY_DATA(s)[hash]; e; e = e->data_next)
+ if (s->compare_func(e->data, p) == 0)
+ return e;
- s->array = n;
- s->array_size = l;
- s->start_index += i;
+ return NULL;
}
-static struct idxset_entry** array_index(pa_idxset*s, uint32_t idx) {
+static struct idxset_entry* index_scan(pa_idxset *s, unsigned hash, uint32_t idx) {
+ struct idxset_entry *e;
pa_assert(s);
+ pa_assert(hash < NBUCKETS);
- if (idx >= s->start_index + s->array_size)
- return NULL;
-
- if (idx < s->start_index)
- return NULL;
+ for (e = BY_INDEX(s)[hash]; e; e = e->index_next)
+ if (e->idx == idx)
+ return e;
- return s->array + idx - s->start_index;
+ return NULL;
}
int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) {
- unsigned h;
- struct idxset_entry *e, **a;
+ unsigned hash;
+ struct idxset_entry *e;
pa_assert(s);
- pa_assert(p);
- pa_assert(s->hash_func);
- h = s->hash_func(p) % s->hash_table_size;
+ hash = s->hash_func(p) % NBUCKETS;
- pa_assert(s->hash_table);
- if ((e = hash_scan(s, s->hash_table[h], p))) {
+ if ((e = data_scan(s, hash, p))) {
if (idx)
- *idx = e->index;
+ *idx = e->idx;
return -1;
}
if (!(e = pa_flist_pop(PA_STATIC_FLIST_GET(entries))))
e = pa_xnew(struct idxset_entry, 1);
+
e->data = p;
- e->index = s->index++;
- e->hash_value = h;
-
- /* Insert into hash table */
- e->hash_next = s->hash_table[h];
- e->hash_prev = NULL;
- if (s->hash_table[h])
- s->hash_table[h]->hash_prev = e;
- s->hash_table[h] = e;
-
- /* Insert into array */
- extend_array(s, e->index);
- a = array_index(s, e->index);
- pa_assert(a && !*a);
- *a = e;
-
- /* Insert into linked list */
+ e->idx = s->current_index++;
+
+ /* Insert into data hash table */
+ e->data_next = BY_DATA(s)[hash];
+ e->data_previous = NULL;
+ if (BY_DATA(s)[hash])
+ BY_DATA(s)[hash]->data_previous = e;
+ BY_DATA(s)[hash] = e;
+
+ hash = e->idx % NBUCKETS;
+
+ /* Insert into index hash table */
+ e->index_next = BY_INDEX(s)[hash];
+ e->index_previous = NULL;
+ if (BY_INDEX(s)[hash])
+ BY_INDEX(s)[hash]->index_previous = e;
+ BY_INDEX(s)[hash] = e;
+
+ /* Insert into iteration list */
+ e->iterate_previous = s->iterate_list_tail;
e->iterate_next = NULL;
- e->iterate_prev = s->iterate_list_tail;
if (s->iterate_list_tail) {
pa_assert(s->iterate_list_head);
s->iterate_list_tail->iterate_next = e;
pa_assert(s->n_entries >= 1);
if (idx)
- *idx = e->index;
+ *idx = e->idx;
return 0;
}
void* pa_idxset_get_by_index(pa_idxset*s, uint32_t idx) {
- struct idxset_entry **a;
+ unsigned hash;
+ struct idxset_entry *e;
+
pa_assert(s);
- if (!(a = array_index(s, idx)))
- return NULL;
+ hash = idx % NBUCKETS;
- if (!*a)
+ if (!(e = index_scan(s, hash, idx)))
return NULL;
- return (*a)->data;
+ return e->data;
}
void* pa_idxset_get_by_data(pa_idxset*s, const void *p, uint32_t *idx) {
- unsigned h;
+ unsigned hash;
struct idxset_entry *e;
pa_assert(s);
- pa_assert(p);
- pa_assert(s->hash_func);
- h = s->hash_func(p) % s->hash_table_size;
+ hash = s->hash_func(p) % NBUCKETS;
- pa_assert(s->hash_table);
- if (!(e = hash_scan(s, s->hash_table[h], p)))
+ if (!(e = data_scan(s, hash, p)))
return NULL;
if (idx)
- *idx = e->index;
+ *idx = e->idx;
return e->data;
}
-static void remove_entry(pa_idxset *s, struct idxset_entry *e) {
- struct idxset_entry **a;
-
- pa_assert(s);
- pa_assert(e);
-
- /* Remove from array */
- a = array_index(s, e->index);
- pa_assert(a && *a && *a == e);
- *a = NULL;
-
- /* Remove from linked list */
- if (e->iterate_next)
- e->iterate_next->iterate_prev = e->iterate_prev;
- else
- s->iterate_list_tail = e->iterate_prev;
-
- if (e->iterate_prev)
- e->iterate_prev->iterate_next = e->iterate_next;
- else
- s->iterate_list_head = e->iterate_next;
-
- /* Remove from hash table */
- if (e->hash_next)
- e->hash_next->hash_prev = e->hash_prev;
-
- if (e->hash_prev)
- e->hash_prev->hash_next = e->hash_next;
- else
- s->hash_table[e->hash_value] = e->hash_next;
-
- if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0)
- pa_xfree(e);
-
- pa_assert(s->n_entries >= 1);
- s->n_entries--;
-}
-
void* pa_idxset_remove_by_index(pa_idxset*s, uint32_t idx) {
- struct idxset_entry **a;
+ struct idxset_entry *e;
+ unsigned hash;
void *data;
pa_assert(s);
- if (!(a = array_index(s, idx)))
- return NULL;
+ hash = idx % NBUCKETS;
- if (!*a)
+ if (!(e = index_scan(s, hash, idx)))
return NULL;
- data = (*a)->data;
- remove_entry(s, *a);
+ data = e->data;
+ remove_entry(s, e);
return data;
}
void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) {
struct idxset_entry *e;
- unsigned h;
+ unsigned hash;
void *r;
pa_assert(s);
- pa_assert(s->hash_func);
- h = s->hash_func(data) % s->hash_table_size;
+ hash = s->hash_func(data) % NBUCKETS;
- pa_assert(s->hash_table);
- if (!(e = hash_scan(s, s->hash_table[h], data)))
+ if (!(e = data_scan(s, hash, data)))
return NULL;
r = e->data;
+
if (idx)
- *idx = e->index;
+ *idx = e->idx;
remove_entry(s, e);
return r;
}
+void pa_idxset_remove_all(pa_idxset *s, pa_free_cb_t free_cb) {
+ pa_assert(s);
+
+ while (s->iterate_list_head) {
+ void *data = s->iterate_list_head->data;
+
+ remove_entry(s, s->iterate_list_head);
+
+ if (free_cb)
+ free_cb(data);
+ }
+}
+
void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx) {
- struct idxset_entry **a, *e = NULL;
+ unsigned hash;
+ struct idxset_entry *e;
pa_assert(s);
pa_assert(idx);
- if ((a = array_index(s, *idx)) && *a)
- e = (*a)->iterate_next;
+ hash = *idx % NBUCKETS;
- if (!e)
+ e = index_scan(s, hash, *idx);
+
+ if (e && e->iterate_next)
+ e = e->iterate_next;
+ else
e = s->iterate_list_head;
if (!e)
return NULL;
- *idx = e->index;
+ *idx = e->idx;
return e->data;
}
-void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
+void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx) {
+ struct idxset_entry *e;
+
pa_assert(s);
+ pa_assert(state);
- if (!s->iterate_list_head)
- return NULL;
+ if (*state == (void*) -1)
+ goto at_end;
+
+ if ((!*state && !s->iterate_list_head))
+ goto at_end;
+
+ e = *state ? *state : s->iterate_list_head;
+
+ if (e->iterate_next)
+ *state = e->iterate_next;
+ else
+ *state = (void*) -1;
if (idx)
- *idx = s->iterate_list_head->index;
- return s->iterate_list_head->data;
+ *idx = e->idx;
+
+ return e->data;
+
+at_end:
+ *state = (void *) -1;
+
+ if (idx)
+ *idx = PA_IDXSET_INVALID;
+
+ return NULL;
}
-void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
- struct idxset_entry **a, *e = NULL;
+void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx) {
+ void *data;
pa_assert(s);
- pa_assert(idx);
- if ((a = array_index(s, *idx)) && *a)
- e = (*a)->iterate_next;
+ if (!s->iterate_list_head)
+ return NULL;
- if (e) {
- *idx = e->index;
- return e->data;
- } else {
- *idx = PA_IDXSET_INVALID;
+ data = s->iterate_list_head->data;
+
+ if (idx)
+ *idx = s->iterate_list_head->idx;
+
+ remove_entry(s, s->iterate_list_head);
+
+ return data;
+}
+
+void* pa_idxset_first(pa_idxset *s, uint32_t *idx) {
+ pa_assert(s);
+
+ if (!s->iterate_list_head) {
+ if (idx)
+ *idx = PA_IDXSET_INVALID;
return NULL;
}
+
+ if (idx)
+ *idx = s->iterate_list_head->idx;
+
+ return s->iterate_list_head->data;
}
-int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata) {
+void *pa_idxset_next(pa_idxset *s, uint32_t *idx) {
struct idxset_entry *e;
+ unsigned hash;
pa_assert(s);
- pa_assert(func);
+ pa_assert(idx);
- e = s->iterate_list_head;
- while (e) {
- int del = 0, r;
- struct idxset_entry *n = e->iterate_next;
+ if (*idx == PA_IDXSET_INVALID)
+ return NULL;
- r = func(e->data, e->index, &del, userdata);
+ hash = *idx % NBUCKETS;
- if (del)
- remove_entry(s, e);
+ if ((e = index_scan(s, hash, *idx))) {
- if (r < 0)
- return r;
+ e = e->iterate_next;
- e = n;
- }
+ if (e) {
+ *idx = e->idx;
+ return e->data;
+ } else {
+ *idx = PA_IDXSET_INVALID;
+ return NULL;
+ }
- return 0;
+ } else {
+
+ /* If the entry passed doesn't exist anymore we try to find
+ * the next following */
+
+ for ((*idx)++; *idx < s->current_index; (*idx)++) {
+
+ hash = *idx % NBUCKETS;
+
+ if ((e = index_scan(s, hash, *idx))) {
+ *idx = e->idx;
+ return e->data;
+ }
+ }
+
+ *idx = PA_IDXSET_INVALID;
+ return NULL;
+ }
}
unsigned pa_idxset_size(pa_idxset*s) {
return s->n_entries;
}
-int pa_idxset_isempty(pa_idxset *s) {
+bool pa_idxset_isempty(pa_idxset *s) {
pa_assert(s);
return s->n_entries == 0;
}
+pa_idxset *pa_idxset_copy(pa_idxset *s, pa_copy_func_t copy_func) {
+ pa_idxset *copy;
+ struct idxset_entry *i;
+
+ pa_assert(s);
+
+ copy = pa_idxset_new(s->hash_func, s->compare_func);
+
+ for (i = s->iterate_list_head; i; i = i->iterate_next)
+ pa_idxset_put(copy, copy_func ? copy_func(i->data) : i->data, NULL);
+
+ return copy;
+}