git.meshlink.io Git - catta/blob - avahi-core/hashmap.c

   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
  38 typedef struct Entry Entry;
  39 struct 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
  48 struct 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
  57 static 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
  70 static 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
  88 AvahiHashmap* 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
 107 void 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
 116 void* 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
 127 void* avahi_hashmap_steal(AvahiHashmap *m, const void *key) {
 128     Entry *e;
 129     void *v;
 130
 131     assert(m);
 132
 133     if (!(e = entry_get(m, key)))
 134         return NULL;
 135
 136     v = e->value;
 137     entry_free(m, e, 1);
 138     return v;
 139 }
 140
 141 int avahi_hashmap_insert(AvahiHashmap *m, void *key, void *value) {
 142     unsigned idx;
 143     Entry *e;
 144
 145     assert(m);
 146
 147     if ((e = entry_get(m, key))) {
 148         if (m->key_free_func)
 149             m->key_free_func(key);
 150         if (m->value_free_func)
 151             m->value_free_func(value);
 152
 153         return 1;
 154     }
 155
 156     if (!(e = avahi_new(Entry, 1)))
 157         return -1;
 158
 159     e->hashmap = m;
 160     e->key = key;
 161     e->value = value;
 162
 163     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
 164
 165     idx = m->hash_func(key) % HASH_MAP_SIZE;
 166     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
 167
 168     return 0;
 169 }
 170
 171
 172 int avahi_hashmap_replace(AvahiHashmap *m, void *key, void *value) {
 173     unsigned idx;
 174     Entry *e;
 175
 176     assert(m);
 177
 178     if ((e = entry_get(m, key))) {
 179         if (m->key_free_func)
 180             m->key_free_func(e->key);
 181         if (m->value_free_func)
 182             m->value_free_func(e->value);
 183
 184         e->key = key;
 185         e->value = value;
 186
 187         return 1;
 188     }
 189
 190     if (!(e = avahi_new(Entry, 1)))
 191         return -1;
 192
 193     e->hashmap = m;
 194     e->key = key;
 195     e->value = value;
 196
 197     AVAHI_LLIST_PREPEND(Entry, entries, m->entries_list, e);
 198
 199     idx = m->hash_func(key) % HASH_MAP_SIZE;
 200     AVAHI_LLIST_PREPEND(Entry, bucket, m->entries[idx], e);
 201
 202     return 0;
 203 }
 204
 205 void avahi_hashmap_remove(AvahiHashmap *m, const void *key) {
 206     Entry *e;
 207
 208     assert(m);
 209
 210     if (!(e = entry_get(m, key)))
 211         return;
 212
 213     entry_free(m, e, 0);
 214 }
 215
 216 void avahi_hashmap_foreach(AvahiHashmap *m, AvahiHashmapForeachCallback callback, void *userdata) {
 217     Entry *e, *next;
 218     assert(m);
 219     assert(callback);
 220
 221     for (e = m->entries_list; e; e = next) {
 222         next = e->entries_next;
 223
 224         callback(e->key, e->value, userdata);
 225     }
 226 }
 227
 228 unsigned avahi_string_hash(const void *data) {
 229     const char *p = data;
 230     unsigned hash = 0;
 231
 232     assert(p);
 233
 234     for (; *p; p++)
 235         hash = 31 * hash + *p;
 236
 237     return hash;
 238 }
 239
 240 int avahi_string_equal(const void *a, const void *b) {
 241     const char *p = a, *q = b;
 242
 243     assert(p);
 244     assert(q);
 245
 246     return strcmp(p, q) == 0;
 247 }
 248
 249 unsigned avahi_int_hash(const void *data) {
 250     const int *i = data;
 251
 252     assert(i);
 253
 254     return (unsigned) *i;
 255 }
 256
 257 int avahi_int_equal(const void *a, const void *b) {
 258     const int *_a = a, *_b = b;
 259
 260     assert(_a);
 261     assert(_b);
 262
 263     return *_a == *_b;
 264 }