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