linkhash.c

   1 /*
   2  * $Id: linkhash.c,v 1.4 2006/01/26 02:16:28 mclark Exp $
   3  *
   4  * Copyright (c) 2004, 2005 Metaparadigm Pte. Ltd.
   5  * Michael Clark <michael@metaparadigm.com>
   6  * Copyright (c) 2009 Hewlett-Packard Development Company, L.P.
   7  *
   8  * This library is free software; you can redistribute it and/or modify
   9  * it under the terms of the MIT license. See COPYING for details.
  10  *
  11  */
  12
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <stdlib.h>
  16 #include <stdarg.h>
  17 #include <stddef.h>
  18 #include <limits.h>
  19
  20 #include "linkhash.h"
  21
  22 void lh_abort(const char *msg, ...)
  23 {
  24         va_list ap;
  25         va_start(ap, msg);
  26         vprintf(msg, ap);
  27         va_end(ap);
  28         exit(1);
  29 }
  30
  31 unsigned long lh_ptr_hash(const void *k)
  32 {
  33         /* CAW: refactored to be 64bit nice */
  34         return (unsigned long)((((ptrdiff_t)k * LH_PRIME) >> 4) & ULONG_MAX);
  35 }
  36
  37 int lh_ptr_equal(const void *k1, const void *k2)
  38 {
  39         return (k1 == k2);
  40 }
  41
  42 unsigned long lh_char_hash(const void *k)
  43 {
  44         unsigned int h = 0;
  45         const char* data = (const char*)k;
  46
  47         while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;
  48
  49         return h;
  50 }
  51
  52 int lh_char_equal(const void *k1, const void *k2)
  53 {
  54         return (strcmp((const char*)k1, (const char*)k2) == 0);
  55 }
  56
  57 struct lh_table* lh_table_new(int size, const char *name,
  58                               lh_entry_free_fn *free_fn,
  59                               lh_hash_fn *hash_fn,
  60                               lh_equal_fn *equal_fn)
  61 {
  62         int i;
  63         struct lh_table *t;
  64
  65         t = (struct lh_table*)calloc(1, sizeof(struct lh_table));
  66         if(!t) lh_abort("lh_table_new: calloc failed\n");
  67         t->count = 0;
  68         t->size = size;
  69         t->name = name;
  70         t->table = (struct lh_entry*)calloc(size, sizeof(struct lh_entry));
  71         if(!t->table) lh_abort("lh_table_new: calloc failed\n");
  72         t->free_fn = free_fn;
  73         t->hash_fn = hash_fn;
  74         t->equal_fn = equal_fn;
  75         for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;
  76         return t;
  77 }
  78
  79 struct lh_table* lh_kchar_table_new(int size, const char *name,
  80                                     lh_entry_free_fn *free_fn)
  81 {
  82         return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal);
  83 }
  84
  85 struct lh_table* lh_kptr_table_new(int size, const char *name,
  86                                    lh_entry_free_fn *free_fn)
  87 {
  88         return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal);
  89 }
  90
  91 void lh_table_resize(struct lh_table *t, int new_size)
  92 {
  93         struct lh_table *new_t;
  94         struct lh_entry *ent;
  95
  96         new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);
  97         ent = t->head;
  98         while(ent) {
  99                 lh_table_insert(new_t, ent->k, ent->v);
 100                 ent = ent->next;
 101         }
 102         free(t->table);
 103         t->table = new_t->table;
 104         t->size = new_size;
 105         t->head = new_t->head;
 106         t->tail = new_t->tail;
 107         t->resizes++;
 108         free(new_t);
 109 }
 110
 111 void lh_table_free(struct lh_table *t)
 112 {
 113         struct lh_entry *c;
 114         for(c = t->head; c != NULL; c = c->next) {
 115                 if(t->free_fn) {
 116                         t->free_fn(c);
 117                 }
 118         }
 119         free(t->table);
 120         free(t);
 121 }
 122
 123
 124 int lh_table_insert(struct lh_table *t, void *k, const void *v)
 125 {
 126         unsigned long h, n;
 127
 128         t->inserts++;
 129         if(t->count >= t->size * LH_LOAD_FACTOR) lh_table_resize(t, t->size * 2);
 130
 131         h = t->hash_fn(k);
 132         n = h % t->size;
 133
 134         while( 1 ) {
 135                 if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;
 136                 t->collisions++;
 137                 if(++n == t->size) n = 0;
 138         }
 139
 140         t->table[n].k = k;
 141         t->table[n].v = v;
 142         t->count++;
 143
 144         if(t->head == NULL) {
 145                 t->head = t->tail = &t->table[n];
 146                 t->table[n].next = t->table[n].prev = NULL;
 147         } else {
 148                 t->tail->next = &t->table[n];
 149                 t->table[n].prev = t->tail;
 150                 t->table[n].next = NULL;
 151                 t->tail = &t->table[n];
 152         }
 153
 154         return 0;
 155 }
 156
 157
 158 struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k)
 159 {
 160         unsigned long h = t->hash_fn(k);
 161         unsigned long n = h % t->size;
 162         int count = 0;
 163
 164         t->lookups++;
 165         while( count < t->size ) {
 166                 if(t->table[n].k == LH_EMPTY) return NULL;
 167                 if(t->table[n].k != LH_FREED &&
 168                    t->equal_fn(t->table[n].k, k)) return &t->table[n];
 169                 if(++n == t->size) n = 0;
 170                 count++;
 171         }
 172         return NULL;
 173 }
 174
 175
 176 const void* lh_table_lookup(struct lh_table *t, const void *k)
 177 {
 178         void *result;
 179         lh_table_lookup_ex(t, k, &result);
 180         return result;
 181 }
 182
 183 json_bool lh_table_lookup_ex(struct lh_table* t, const void* k, void **v)
 184 {
 185         struct lh_entry *e = lh_table_lookup_entry(t, k);
 186         if (e != NULL) {
 187                 if (v != NULL) *v = (void *)e->v;
 188                 return TRUE; /* key found */
 189         }
 190         if (v != NULL) *v = NULL;
 191         return FALSE; /* key not found */
 192 }
 193
 194 int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)
 195 {
 196         ptrdiff_t n = (ptrdiff_t)(e - t->table); /* CAW: fixed to be 64bit nice, still need the crazy negative case... */
 197
 198         /* CAW: this is bad, really bad, maybe stack goes other direction on this machine... */
 199         if(n < 0) { return -2; }
 200
 201         if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1;
 202         t->count--;
 203         if(t->free_fn) t->free_fn(e);
 204         t->table[n].v = NULL;
 205         t->table[n].k = LH_FREED;
 206         if(t->tail == &t->table[n] && t->head == &t->table[n]) {
 207                 t->head = t->tail = NULL;
 208         } else if (t->head == &t->table[n]) {
 209                 t->head->next->prev = NULL;
 210                 t->head = t->head->next;
 211         } else if (t->tail == &t->table[n]) {
 212                 t->tail->prev->next = NULL;
 213                 t->tail = t->tail->prev;
 214         } else {
 215                 t->table[n].prev->next = t->table[n].next;
 216                 t->table[n].next->prev = t->table[n].prev;
 217         }
 218         t->table[n].next = t->table[n].prev = NULL;
 219         return 0;
 220 }
 221
 222
 223 int lh_table_delete(struct lh_table *t, const void *k)
 224 {
 225         struct lh_entry *e = lh_table_lookup_entry(t, k);
 226         if(!e) return -1;
 227         return lh_table_delete_entry(t, e);
 228 }
 229