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