From 36021b117b10530bc94e960a3d3d319ff03fe27a Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Fri, 27 Jun 2008 20:34:14 +0200 Subject: modernize idxset a bit, reduce memory consumption, get rid of pa_idxset_foreach() --- src/pulsecore/idxset.c | 387 +++++++++++++++++++++++++------------------------ src/pulsecore/idxset.h | 31 ++-- src/pulsecore/module.c | 72 ++++----- 3 files changed, 246 insertions(+), 244 deletions(-) (limited to 'src/pulsecore') diff --git a/src/pulsecore/idxset.c b/src/pulsecore/idxset.c index 7c9520a4..fb4497b8 100644 --- a/src/pulsecore/idxset.c +++ b/src/pulsecore/idxset.c @@ -1,7 +1,7 @@ /*** This file is part of PulseAudio. - Copyright 2004-2006 Lennart Poettering + Copyright 2004-2008 Lennart Poettering Copyright 2006 Pierre Ossman for Cendio AB PulseAudio is free software; you can redistribute it and/or modify @@ -29,29 +29,36 @@ #include #include -#include +#include #include +#include #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) { @@ -79,131 +86,140 @@ int pa_idxset_trivial_compare_func(const void *a, const void *b) { 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; + + /* Remove from data hash table */ + if (e->data_next) + e->data_next->data_previous = e->data_previous; - if (pa_flist_push(PA_STATIC_FLIST_GET(entries), e) < 0) - pa_xfree(e); + 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_free2_cb_t free_cb, void *userdata) { pa_assert(s); - pa_assert(idx >= s->start_index); - if (idx < s->start_index + s->array_size) - return; + while (s->iterate_list_head) { + void *data = s->iterate_list_head->data; - for (i = 0; i < s->array_size; i++) - if (s->array[i]) - break; + remove_entry(s, s->iterate_list_head); - l = idx - s->start_index - i + 100; - n = pa_xnew0(struct idxset_entry*, l); + if (free_cb) + free_cb(data, userdata); + } - for (j = 0; j < s->array_size-i; j++) - n[j] = s->array[i+j]; + pa_xfree(s); +} - pa_xfree(s->array); +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); - s->array = n; - s->array_size = l; - s->start_index += i; + for (e = BY_DATA(s)[hash]; e; e = e->data_next) + if (s->compare_func(e->data, p) == 0) + return e; + + 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; @@ -217,117 +233,76 @@ int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx) { 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); @@ -335,76 +310,113 @@ void* pa_idxset_remove_by_data(pa_idxset*s, const void *data, uint32_t *idx) { } 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) + if (!(e = index_scan(s, hash, *idx))) + return NULL; + + 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) 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); - - e = s->iterate_list_head; - while (e) { - int del = 0, r; - struct idxset_entry *n = e->iterate_next; - - r = func(e->data, e->index, &del, userdata); + pa_assert(idx); - if (del) - remove_entry(s, e); + hash = *idx % NBUCKETS; - if (r < 0) - return r; + if (!(e = index_scan(s, hash, *idx))) + return NULL; - e = n; + if (!e->iterate_next) { + *idx = PA_IDXSET_INVALID; + return NULL; } - return 0; + e = e->iterate_next; + + *idx = e->idx; + return e->data; } unsigned pa_idxset_size(pa_idxset*s) { @@ -413,9 +425,8 @@ unsigned pa_idxset_size(pa_idxset*s) { return s->n_entries; } -int pa_idxset_isempty(pa_idxset *s) { +pa_bool_t pa_idxset_isempty(pa_idxset *s) { pa_assert(s); return s->n_entries == 0; } - diff --git a/src/pulsecore/idxset.h b/src/pulsecore/idxset.h index f089ef37..7531ea32 100644 --- a/src/pulsecore/idxset.h +++ b/src/pulsecore/idxset.h @@ -1,10 +1,10 @@ -#ifndef fooidxsethfoo -#define fooidxsethfoo +#ifndef foopulsecoreidxsethfoo +#define foopulsecoreidxsethfoo /*** This file is part of PulseAudio. - Copyright 2004-2006 Lennart Poettering + Copyright 2004-2008 Lennart Poettering Copyright 2006 Pierre Ossman for Cendio AB PulseAudio is free software; you can redistribute it and/or modify @@ -25,9 +25,12 @@ #include +#include + /* A combination of a set and a dynamic array. Entries are indexable - * both through a numeric automatically generated index and the entry's - * data pointer. As usual, memory management is the user's job. */ + * both through an automatically generated numeric index and the + * entry's data pointer. As usual, memory management is the user's + * job. */ /* A special index value denoting the invalid index. */ #define PA_IDXSET_INVALID ((uint32_t) -1) @@ -54,7 +57,7 @@ typedef struct pa_idxset pa_idxset; pa_idxset* pa_idxset_new(pa_hash_func_t hash_func, pa_compare_func_t compare_func); /* Free the idxset. When the idxset is not empty the specified function is called for every entry contained */ -void pa_idxset_free(pa_idxset *s, void (*free_func) (void *p, void *userdata), void *userdata); +void pa_idxset_free(pa_idxset *s, pa_free2_cb_t free_cb, void *userdata); /* Store a new item in the idxset. The index of the item is returned in *idx */ int pa_idxset_put(pa_idxset*s, void *p, uint32_t *idx); @@ -79,6 +82,12 @@ void* pa_idxset_remove_by_data(pa_idxset*s, const void *p, uint32_t *idx); returned before the an entry is returned the second time.*/ void* pa_idxset_rrobin(pa_idxset *s, uint32_t *idx); +/* Iterate through the idxset. At first iteration state should be NULL */ +void *pa_idxset_iterate(pa_idxset *s, void **state, uint32_t *idx); + +/* Return the oldest entry in the idxset and remove it. If idx is not NULL fill in its index in *idx */ +void* pa_idxset_steal_first(pa_idxset *s, uint32_t *idx); + /* Return the oldest entry in the idxset. Fill in its index in *idx. */ void* pa_idxset_first(pa_idxset *s, uint32_t *idx); @@ -88,14 +97,10 @@ void* pa_idxset_first(pa_idxset *s, uint32_t *idx); * iterate through the set.*/ void *pa_idxset_next(pa_idxset *s, uint32_t *idx); -/* Call a function for every item in the set. If the callback function - returns -1, the loop is terminated. If *del is set to non-zero that - specific item is removed. It is not safe to call any other - functions on the idxset while pa_idxset_foreach is executed. */ -int pa_idxset_foreach(pa_idxset*s, int (*func)(void *p, uint32_t idx, int *del, void*userdata), void *userdata); - +/* Return the current number of entries in the idxset */ unsigned pa_idxset_size(pa_idxset*s); -int pa_idxset_isempty(pa_idxset *s); +/* Return TRUE of the idxset is empty */ +pa_bool_t pa_idxset_isempty(pa_idxset *s); #endif diff --git a/src/pulsecore/module.c b/src/pulsecore/module.c index f1eeb762..e003dd7c 100644 --- a/src/pulsecore/module.c +++ b/src/pulsecore/module.c @@ -194,25 +194,19 @@ void pa_module_unload_by_index(pa_core *c, uint32_t idx) { pa_module_free(m); } -static void free_callback(void *p, PA_GCC_UNUSED void *userdata) { - pa_module *m = p; - pa_assert(m); - pa_module_free(m); -} - void pa_module_unload_all(pa_core *c) { - pa_module *m; pa_assert(c); - if (!c->modules) - return; + if (c->modules) { + pa_module *m; - while ((m = pa_idxset_first(c->modules, NULL))) - pa_module_unload(c, m); + while ((m = pa_idxset_steal_first(c->modules, NULL))) + pa_module_free(m); - pa_idxset_free(c->modules, free_callback, NULL); - c->modules = NULL; + pa_idxset_free(c->modules, NULL, NULL); + c->modules = NULL; + } if (c->module_auto_unload_event) { c->mainloop->time_free(c->module_auto_unload_event); @@ -225,55 +219,47 @@ void pa_module_unload_all(pa_core *c) { } } -static int unused_callback(void *p, PA_GCC_UNUSED uint32_t idx, int *del, void *userdata) { - pa_module *m = p; - time_t *now = userdata; - - pa_assert(m); - pa_assert(del); - pa_assert(now); - - if (m->n_used == 0 && m->auto_unload && m->last_used_time+m->core->module_idle_time <= *now) { - pa_module_free(m); - *del = 1; - } - - return 0; -} - void pa_module_unload_unused(pa_core *c) { + void *state = NULL; time_t now; + pa_module *m; + pa_assert(c); if (!c->modules) return; time(&now); - pa_idxset_foreach(c->modules, unused_callback, &now); -} -static int unload_callback(void *p, PA_GCC_UNUSED uint32_t idx, int *del, PA_GCC_UNUSED void *userdata) { - pa_module *m = p; - pa_assert(m); + while ((m = pa_idxset_iterate(c->modules, &state, NULL))) { - if (m->unload_requested) { - pa_module_free(m); - *del = 1; - } + if (m->n_used > 0) + continue; + + if (!m->auto_unload) + continue; - return 0; + if (m->last_used_time + m->core->module_idle_time > now) + continue; + + pa_module_unload(c, m); + } } static void defer_cb(pa_mainloop_api*api, pa_defer_event *e, void *userdata) { - pa_core *core = PA_CORE(userdata); + void *state = NULL; + pa_core *c = PA_CORE(userdata); + pa_module *m; - pa_core_assert_ref(core); + pa_core_assert_ref(c); api->defer_enable(e, 0); - if (!core->modules) + if (!c->modules) return; - pa_idxset_foreach(core->modules, unload_callback, NULL); + while ((m = pa_idxset_iterate(c->modules, &state, NULL))) + if (m->unload_requested) + pa_module_unload(c, m); } void pa_module_unload_request(pa_module *m) { -- cgit