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

   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/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 }