1/* $Id$ */
2
3/***
4  This file is part of avahi.
5
6  avahi is free software; you can redistribute it and/or modify it
7  under the terms of the GNU Lesser General Public License as
8  published by the Free Software Foundation; either version 2.1 of the
9  License, or (at your option) any later version.
10
11  avahi is distributed in the hope that it will be useful, but WITHOUT
12  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
14  Public License for more details.
15
16  You should have received a copy of the GNU Lesser General Public
17  License along with avahi; if not, write to the Free Software
18  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
19  USA.
20***/
21
22#ifdef HAVE_CONFIG_H
23#include <config.h>
24#endif
25
26#include <stdlib.h>
27#include <string.h>
28
29#include <avahi-common/llist.h>
30#include <avahi-common/domain.h>
31#include <avahi-common/malloc.h>
32
33#include "hashmap.h"
34#include "util.h"
35
36#define HASH_MAP_SIZE 123
37
38typedef struct Entry Entry;
39struct Entry {
40    AvahiHashmap *hashmap;
41    void *key;
42    void *value;
43
44    AVAHI_LLIST_FIELDS(Entry, bucket);
45    AVAHI_LLIST_FIELDS(Entry, entries);
46};
47
48struct AvahiHashmap {
49    AvahiHashFunc hash_func;
50    AvahiEqualFunc equal_func;
51    AvahiFreeFunc key_free_func, value_free_func;
52
53    Entry *entries[HASH_MAP_SIZE];
54    AVAHI_LLIST_HEAD(Entry, entries_list);
55};
56
57static Entry* entry_get(AvahiHashmap *m, const void *key) {
58    unsigned idx;
59    Entry *e;
60
61    idx = m->hash_func(key) % HASH_MAP_SIZE;
62
63    for (e = m->entries[idx]; e; e = e->bucket_next)
64        if (m->equal_func(key, e->key))
65            return e;
66
67    return NULL;
68}
69
70static void entry_free(AvahiHashmap *m, Entry *e, int stolen) {
71    unsigned idx;
72    assert(m);
73    assert(e);
74
75    idx = m->hash_func(e->key) % HASH_MAP_SIZE;
76
77    AVAHI_LLIST_REMOVE(Entry, bucket, m->entries[idx], e);
78    AVAHI_LLIST_REMOVE(Entry, entries, m->entries_list, e);
79
80    if (m->key_free_func)
81        m->key_free_func(e->key);
82    if (m->value_free_func && !stolen)
83        m->value_free_func(e->value);
84
85    avahi_free(e);
86}
87
88AvahiHashmap* avahi_hashmap_new(AvahiHashFunc hash_func, AvahiEqualFunc equal_func, AvahiFreeFunc key_free_func, AvahiFreeFunc value_free_func) {
89    AvahiHashmap *m;
90
91    assert(hash_func);
92    assert(equal_func);
93
94    if (!(m = avahi_new0(AvahiHashmap, 1)))
95        return NULL;
96
97    m->hash_func = hash_func;
98    m->equal_func = equal_func;
99    m->key_free_func = key_free_func;
100    m->value_free_func = value_free_func;
101
102    AVAHI_LLIST_HEAD_INIT(Entry, m->entries_list);
103
104    return m;
105}
106
107void avahi_hashmap_free(AvahiHashmap *m) {
108    assert(m);
109
110    while (m->entries_list)
111        entry_free(m, m->entries_list, 0);
112
113    avahi_free(m);
114}
115
116void* avahi_hashmap_lookup(AvahiHashmap *m, const void *key) {
117    Entry *e;
118
119    assert(m);
120
121    if (!(e = entry_get(m, key)))
122        return NULL;
123
124    return e->value;
125}
126
127int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) {
128    unsigned idx;
129    Entry *e;
130
131    assert(m);
132
133    if ((e = entry_get(m, key))) {
134        if (m->key_free_func)
135            m->key_free_func(key);
136        if (m->value_free_func)
137            m->value_free_func(value);
138
139        return 1;
140    }
141
142    if (!(e = avahi_new(Entry, 1)))
143        return -1;
144
145    e->hashmap = m;
146    e->key = key;
147    e->value = value;
148
149    AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
150
151    idx = m->hash_func(key) % HASH_MAP_SIZE;
152    AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
153
154    return 0;
155}
156
157
158int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) {
159    unsigned idx;
160    Entry *e;
161
162    assert(m);
163
164    if ((e = entry_get(m, key))) {
165        if (m->key_free_func)
166            m->key_free_func(e->key);
167        if (m->value_free_func)
168            m->value_free_func(e->value);
169
170        e->key = key;
171        e->value = value;
172
173        return 1;
174    }
175
176    if (!(e = avahi_new(Entry, 1)))
177        return -1;
178
179    e->hashmap = m;
180    e->key = key;
181    e->value = value;
182
183    AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
184
185    idx = m->hash_func(key) % HASH_MAP_SIZE;
186    AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
187
188    return 0;
189}
190
191void avahi_hashmap_remove(AvahiHashmap *m, const void *key) {
192    Entry *e;
193
194    assert(m);
195
196    if (!(e = entry_get(m, key)))
197        return;
198
199    entry_free(m, e, 0);
200}
201
202void avahi_hashmap_foreach(AvahiHashmap *m, AvahiHashmapForeachCallback callback, void *userdata) {
203    Entry *e, *next;
204    assert(m);
205    assert(callback);
206
207    for (e = m->entries_list; e; e = next) {
208        next = e->entries_next;
209
210        callback(e->key, e->value, userdata);
211    }
212}
213
214unsigned avahi_string_hash(const void *data) {
215    const char *p = data;
216    unsigned hash = 0;
217
218    assert(p);
219
220    for (; *p; p++)
221        hash = 31 * hash + *p;
222
223    return hash;
224}
225
226int avahi_string_equal(const void *a, const void *b) {
227    const char *p = a, *q = b;
228
229    assert(p);
230    assert(q);
231
232    return strcmp(p, q) == 0;
233}
234
235unsigned avahi_int_hash(const void *data) {
236    const int *i = data;
237
238    assert(i);
239
240    return (unsigned) *i;
241}
242
243int avahi_int_equal(const void *a, const void *b) {
244    const int *_a = a, *_b = b;
245
246    assert(_a);
247    assert(_b);
248
249    return *_a == *_b;
250}
251