diff options
Diffstat (limited to 'avahi-core/hashmap.c')
| -rw-r--r-- | avahi-core/hashmap.c | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/avahi-core/hashmap.c b/avahi-core/hashmap.c new file mode 100644 index 0000000..0c44d4f --- /dev/null +++ b/avahi-core/hashmap.c @@ -0,0 +1,249 @@ +/* $Id$ */ + +/*** + This file is part of avahi. + + avahi is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as + published by the Free Software Foundation; either version 2.1 of the + License, or (at your option) any later version. + + avahi is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General + Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with avahi; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + USA. +***/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include <stdlib.h> +#include <string.h> + +#include <avahi-common/llist.h> +#include <avahi-common/domain.h> +#include <avahi-common/malloc.h> + +#include "hashmap.h" +#include "util.h" + +#define HASH_MAP_SIZE 123 + +typedef struct Entry Entry; +struct Entry { + AvahiHashmap *hashmap; + void *key; + void *value; + + AVAHI_LLIST_FIELDS(Entry, bucket); + AVAHI_LLIST_FIELDS(Entry, entries); +}; + +struct AvahiHashmap { + AvahiHashFunc hash_func; + AvahiEqualFunc equal_func; + AvahiFreeFunc key_free_func, value_free_func; + + Entry *entries[HASH_MAP_SIZE]; + AVAHI_LLIST_HEAD(Entry, entries_list); +}; + +static Entry* entry_get(AvahiHashmap *m, const void *key) { + unsigned idx; + Entry *e; + + idx = m->hash_func(key) % HASH_MAP_SIZE; + + for (e = m->entries[idx]; e; e = e->bucket_next) + if (m->equal_func(key, e->key)) + return e; + + return NULL; +} + +static void entry_free(AvahiHashmap *m, Entry *e, int stolen) { + unsigned idx; + assert(e); + + idx = m->hash_func(e->key) % HASH_MAP_SIZE; + + AVAHI_LLIST_REMOVE(Entry, bucket, m->entries[idx], e); + AVAHI_LLIST_REMOVE(Entry, entries, m->entries_list, e); + + if (m->key_free_func) + m->key_free_func(e->key); + if (m->value_free_func && !stolen) + m->value_free_func(e->value); + + avahi_free(e); +} + +AvahiHashmap* avahi_hashmap_new(AvahiHashFunc hash_func, AvahiEqualFunc equal_func, AvahiFreeFunc key_free_func, AvahiFreeFunc value_free_func) { + AvahiHashmap *m; + + assert(hash_func); + assert(equal_func); + + if (!(m = avahi_new(AvahiHashmap, 1))) + return NULL; + + m->hash_func = hash_func; + m->equal_func = equal_func; + m->key_free_func = key_free_func; + m->value_free_func = value_free_func; + + memset(m->entries, 0, sizeof(m->entries)); + + AVAHI_LLIST_HEAD_INIT(Entry, m->entries_list); + + return m; +} + +void avahi_hashmap_free(AvahiHashmap *m) { + assert(m); + + while (m->entries_list) + entry_free(m, m->entries_list, 0); + + avahi_free(m); +} + +void* avahi_hashmap_lookup(AvahiHashmap *m, const void *key) { + Entry *e; + + assert(m); + + if (!(e = entry_get(m, key))) + return NULL; + + return e->value; +} + +void* avahi_hashmap_steal(AvahiHashmap *m, const void *key) { + Entry *e; + void *v; + + assert(m); + + if (!(e = entry_get(m, key))) + return NULL; + + v = e->value; + entry_free(m, e, 1); + return v; +} + +int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) { + unsigned idx; + Entry *e; + + assert(m); + + if ((e = entry_get(m, key))) { + if (m->key_free_func) + m->key_free_func(key); + if (m->value_free_func) + m->value_free_func(value); + + return 1; + } + + if (!(e = avahi_new(Entry, 1))) + return -1; + + e->hashmap = m; + e->key = key; + e->value = value; + + AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e); + + idx = m->hash_func(key) % HASH_MAP_SIZE; + AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e); + + return 0; +} + + +int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) { + unsigned idx; + Entry *e; + + assert(m); + + if ((e = entry_get(m, key))) { + if (m->key_free_func) + m->key_free_func(e->key); + if (m->value_free_func) + m->value_free_func(e->value); + + e->key = key; + e->value = value; + + return 1; + } + + if (!(e = avahi_new(Entry, 1))) + return -1; + + e->hashmap = m; + e->key = key; + e->value = value; + + AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e); + + idx = m->hash_func(key) % HASH_MAP_SIZE; + AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e); + + return 0; +} + + +void avahi_hashmap_remove(AvahiHashmap *m, const void *key) { + Entry *e; + + assert(m); + + if (!(e = entry_get(m, key))) + return; + + entry_free(m, e, 0); +} + +unsigned avahi_string_hash(const void *data) { + const char *p = data; + unsigned hash = 0; + + for (; *p; p++) + hash = 31 * hash + *p; + + return hash; +} + +int avahi_string_equal(const void *a, const void *b) { + const char *p = a, *q = b; + + return strcmp(p, q) == 0; +} + +unsigned avahi_domain_hash(const void *data) { + unsigned hash = 0; + const char *s; + + for (;;) { + char c[65]; + + if (!avahi_unescape_label(&s, c, sizeof(c))) + return hash; + + if (!c[0]) + continue; + + hash += avahi_string_hash(avahi_strdown(c)); + } +} |