dict.c

   1 /*
   2  * This file is part of ltrace.
   3  * Copyright (C) 2011,2012 Petr Machata
   4  * Copyright (C) 2003,2004,2008,2009 Juan Cespedes
   5  * Copyright (C) 2006 Ian Wienand
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
  20  * 02110-1301 USA
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <assert.h>
  27
  28 #include "common.h"
  29
  30 /*
  31  * Dictionary based on code by Morten Eriksen <mortene@sim.no>.
  32  */
  33
  34 struct dict_entry {
  35         unsigned int hash;
  36         void *key;
  37         void *value;
  38         struct dict_entry *next;
  39 };
  40
  41 /* #define DICTTABLESIZE 97 */
  42 #define DICTTABLESIZE 997       /* Semi-randomly selected prime number. */
  43 /* #define DICTTABLESIZE 9973 */
  44 /* #define DICTTABLESIZE 99991 */
  45 /* #define DICTTABLESIZE 999983 */
  46
  47 struct dict {
  48         struct dict_entry *buckets[DICTTABLESIZE];
  49         unsigned int (*key2hash) (const void *);
  50         int (*key_cmp) (const void *, const void *);
  51 };
  52
  53 Dict *
  54 dict_init(unsigned int (*key2hash) (const void *),
  55           int (*key_cmp) (const void *, const void *))
  56 {
  57         Dict *d;
  58         int i;
  59
  60         debug(DEBUG_FUNCTION, "dict_init()");
  61
  62         d = malloc(sizeof(Dict));
  63         if (!d) {
  64                 perror("malloc()");
  65                 exit(1);
  66         }
  67         for (i = 0; i < DICTTABLESIZE; i++) {   /* better use memset()? */
  68                 d->buckets[i] = NULL;
  69         }
  70         d->key2hash = key2hash;
  71         d->key_cmp = key_cmp;
  72         return d;
  73 }
  74
  75 void
  76 dict_clear(Dict *d) {
  77         int i;
  78         struct dict_entry *entry, *nextentry;
  79
  80         debug(DEBUG_FUNCTION, "dict_clear()");
  81         assert(d);
  82         for (i = 0; i < DICTTABLESIZE; i++) {
  83                 for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
  84                         nextentry = entry->next;
  85                         free(entry);
  86                 }
  87                 d->buckets[i] = NULL;
  88         }
  89         free(d);
  90 }
  91
  92 int
  93 dict_enter(Dict *d, void *key, void *value) {
  94         struct dict_entry *entry, *newentry;
  95         unsigned int hash;
  96         unsigned int bucketpos;
  97
  98         debug(DEBUG_FUNCTION, "dict_enter()");
  99
 100         hash = d->key2hash(key);
 101         bucketpos = hash % DICTTABLESIZE;
 102
 103         assert(d);
 104         newentry = malloc(sizeof(struct dict_entry));
 105         if (!newentry) {
 106                 perror("malloc");
 107                 exit(1);
 108         }
 109
 110         newentry->hash = hash;
 111         newentry->key = key;
 112         newentry->value = value;
 113         newentry->next = NULL;
 114
 115         entry = d->buckets[bucketpos];
 116         while (entry && entry->next)
 117                 entry = entry->next;
 118
 119         if (entry)
 120                 entry->next = newentry;
 121         else
 122                 d->buckets[bucketpos] = newentry;
 123
 124         debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
 125         return 0;
 126 }
 127
 128 void *
 129 dict_remove(Dict *d, void *key)
 130 {
 131         assert(d != NULL);
 132         debug(DEBUG_FUNCTION, "dict_remove(%p)", key);
 133
 134         unsigned int hash = d->key2hash(key);
 135         unsigned int bucketpos = hash % DICTTABLESIZE;
 136
 137         struct dict_entry **entryp;
 138         for (entryp = &d->buckets[bucketpos]; (*entryp) != NULL;
 139              entryp = &(*entryp)->next) {
 140                 struct dict_entry *entry = *entryp;
 141                 if (hash != entry->hash)
 142                         continue;
 143                 if (d->key_cmp(key, entry->key) == 0) {
 144                         *entryp = entry->next;
 145                         void *value = entry->value;
 146                         free(entry);
 147                         return value;
 148                 }
 149         }
 150         return NULL;
 151 }
 152
 153 void *
 154 dict_find_entry(Dict *d, const void *key)
 155 {
 156         unsigned int hash;
 157         unsigned int bucketpos;
 158         struct dict_entry *entry;
 159
 160         debug(DEBUG_FUNCTION, "dict_find_entry()");
 161
 162         hash = d->key2hash(key);
 163         bucketpos = hash % DICTTABLESIZE;
 164
 165         assert(d);
 166         for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
 167                 if (hash != entry->hash) {
 168                         continue;
 169                 }
 170                 if (!d->key_cmp(key, entry->key)) {
 171                         break;
 172                 }
 173         }
 174         return entry ? entry->value : NULL;
 175 }
 176
 177 void
 178 dict_apply_to_all(Dict *d,
 179                   void (*func) (void *key, void *value, void *data), void *data) {
 180         int i;
 181
 182         debug(DEBUG_FUNCTION, "dict_apply_to_all()");
 183
 184         if (!d) {
 185                 return;
 186         }
 187         for (i = 0; i < DICTTABLESIZE; i++) {
 188                 struct dict_entry *entry = d->buckets[i];
 189                 while (entry) {
 190                         func(entry->key, entry->value, data);
 191                         entry = entry->next;
 192                 }
 193         }
 194 }
 195
 196 /*****************************************************************************/
 197
 198 unsigned int
 199 dict_key2hash_string(const void *key)
 200 {
 201         const char *s = (const char *)key;
 202         unsigned int total = 0, shift = 0;
 203
 204         assert(key);
 205         while (*s) {
 206                 total = total ^ ((*s) << shift);
 207                 shift += 5;
 208                 if (shift > 24)
 209                         shift -= 24;
 210                 s++;
 211         }
 212         return total;
 213 }
 214
 215 int
 216 dict_key_cmp_string(const void *key1, const void *key2)
 217 {
 218         assert(key1);
 219         assert(key2);
 220         return strcmp((const char *)key1, (const char *)key2);
 221 }
 222
 223 unsigned int
 224 dict_key2hash_int(const void *key)
 225 {
 226         return (unsigned long)key;
 227 }
 228
 229 int
 230 dict_key_cmp_int(const void *key1, const void *key2)
 231 {
 232         return key1 - key2;
 233 }
 234
 235 Dict *
 236 dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
 237             void * (*value_clone)(void *, void *), void * data)
 238 {
 239         Dict *d;
 240         int i;
 241
 242         debug(DEBUG_FUNCTION, "dict_clone()");
 243
 244         d = malloc(sizeof(Dict));
 245         if (!d) {
 246                 perror("malloc()");
 247                 exit(1);
 248         }
 249         memcpy(d, old, sizeof(Dict));
 250         for (i = 0; i < DICTTABLESIZE; i++) {   /* better use memset()? */
 251                 struct dict_entry *de_old;
 252                 struct dict_entry **de_new;
 253
 254                 de_old = old->buckets[i];
 255                 de_new = &d->buckets[i];
 256                 while (de_old) {
 257                         void * nkey, * nval;
 258                         *de_new = malloc(sizeof(struct dict_entry));
 259                         if (!*de_new) {
 260                                 perror("malloc()");
 261                                 exit(1);
 262                         }
 263                         memcpy(*de_new, de_old, sizeof(struct dict_entry));
 264
 265                         /* The error detection is rather weak :-/ */
 266                         nkey = key_clone(de_old->key, data);
 267                         if (nkey == NULL && de_old->key != NULL) {
 268                                 perror("key_clone");
 269                         err:
 270                                 /* XXX Will this actually work?  We
 271                                  * simply memcpy the old dictionary
 272                                  * over up there.  */
 273                                 dict_clear(d);
 274                                 free(de_new);
 275                                 return NULL;
 276                         }
 277
 278                         nval = value_clone(de_old->value, data);
 279                         if (nval == NULL && de_old->value != NULL) {
 280                                 perror("value_clone");
 281                                 goto err;
 282                         }
 283
 284                         (*de_new)->key = nkey;
 285                         (*de_new)->value = nval;
 286                         de_new = &(*de_new)->next;
 287                         de_old = de_old->next;
 288                 }
 289         }
 290         return d;
 291 }
 292
 293 struct wrap_clone_cb
 294 {
 295         void * (*key_clone)(void *);
 296         void * (*value_clone)(void *);
 297 };
 298
 299 static void *
 300 value_clone_1(void * arg, void * data)
 301 {
 302         return ((struct wrap_clone_cb *)data)->value_clone(arg);
 303 }
 304
 305 static void *
 306 key_clone_1(void * arg, void * data)
 307 {
 308         return ((struct wrap_clone_cb *)data)->key_clone(arg);
 309 }
 310
 311 Dict *
 312 dict_clone(Dict * old, void * (*key_clone)(void *),
 313            void * (*value_clone)(void *))
 314 {
 315         struct wrap_clone_cb cb = { key_clone, value_clone };
 316         return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
 317 }