src/libjson/linkhash.c

   1 /*
   2  * $Id$
   3  *
   4  * Copyright Metaparadigm Pte. Ltd. 2004.
   5  * Michael Clark <michael@metaparadigm.com>
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public (LGPL)
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details: http://www.gnu.org/
  16  *
  17  */
  18
  19 #include <stdio.h>
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include <stdarg.h>
  23
  24 #include "libjson/linkhash.h"
  25
  26
  27 void lh_abort(const char *msg, ...)
  28 {
  29         va_list ap;
  30         va_start(ap, msg);
  31         vprintf(msg, ap);
  32         exit(1);
  33 }
  34
  35
  36 unsigned long lh_ptr_hash(void *k)
  37 {
  38         return ((long)k * LH_PRIME) >> 4;
  39 }
  40
  41
  42 int lh_ptr_equal(void *k1, void *k2)
  43 {
  44         return (k1 == k2);
  45 }
  46
  47
  48 unsigned long lh_char_hash(void *k)
  49 {
  50         unsigned int h = 0;
  51         const char* data = k;
  52
  53         while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;
  54
  55         return h;
  56 }
  57
  58
  59 int lh_char_equal(void *k1, void *k2)
  60 {
  61         return (strcmp((char*)k1, (char*)k2) == 0);
  62 }
  63
  64
  65 struct lh_table* lh_table_new(int size, char *name,
  66                               lh_entry_free_fn *free_fn,
  67                               lh_hash_fn *hash_fn,
  68                               lh_equal_fn *equal_fn)
  69 {
  70         int i;
  71         struct lh_table *t;
  72
  73         t = calloc(1, sizeof(struct lh_table));
  74         if(!t) lh_abort("lh_table_new: calloc failed\n");
  75         t->count = 0;
  76         t->size = size;
  77         t->name = name;
  78         t->table = calloc(size, sizeof(struct lh_entry));
  79         if(!t->table) lh_abort("lh_table_new: calloc failed\n");
  80         t->free_fn = free_fn;
  81         t->hash_fn = hash_fn;
  82         t->equal_fn = equal_fn;
  83         for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;
  84         return t;
  85 }
  86
  87
  88 struct lh_table* lh_kchar_table_new(int size, char *name,
  89                                     lh_entry_free_fn *free_fn)
  90 {
  91         return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal);
  92 }
  93
  94
  95 struct lh_table* lh_kptr_table_new(int size, char *name,
  96                                    lh_entry_free_fn *free_fn)
  97 {
  98         return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal);
  99 }
 100
 101
 102 void lh_table_resize(struct lh_table *t, int new_size)
 103 {
 104         struct lh_table *new_t;
 105         struct lh_entry *ent;
 106
 107         new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);
 108         ent = t->head;
 109         while(ent) {
 110                 lh_table_insert(new_t, ent->k, ent->v);
 111                 ent = ent->next;
 112         }
 113         free(t->table);
 114         t->table = new_t->table;
 115         t->size = new_size;
 116         t->head = new_t->head;
 117         t->tail = new_t->tail;
 118         t->resizes++;
 119         free(new_t);
 120 }
 121
 122
 123 void lh_table_free(struct lh_table *t)
 124 {
 125         struct lh_entry *c;
 126         for(c = t->head; c != NULL; c = c->next) {
 127                 if(t->free_fn) {
 128                         t->free_fn(c);
 129                 }
 130         }
 131         free(t->table);
 132         free(t);
 133 }
 134
 135
 136 int lh_table_insert(struct lh_table *t, void *k, void *v)
 137 {
 138         unsigned long h, n;
 139
 140         t->inserts++;
 141         if(t->count > t->size * 0.66) lh_table_resize(t, t->size * 2);
 142
 143         h = t->hash_fn(k);
 144         n = h % t->size;
 145
 146         while( 1 ) {
 147                 if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;
 148                 t->collisions++;
 149                 if(++n == t->size) n = 0;
 150         }
 151
 152         t->table[n].k = k;
 153         t->table[n].v = v;
 154         t->count++;
 155
 156         if(t->head == NULL) {
 157                 t->head = t->tail = &t->table[n];
 158                 t->table[n].next = t->table[n].prev = NULL;
 159         } else {
 160                 t->tail->next = &t->table[n];
 161                 t->table[n].prev = t->tail;
 162                 t->table[n].next = NULL;
 163                 t->tail = &t->table[n];
 164         }
 165
 166         return 0;
 167 }
 168
 169
 170 struct lh_entry* lh_table_lookup_entry(struct lh_table *t, void *k)
 171 {
 172         unsigned long h = t->hash_fn(k);
 173         unsigned long n = h % t->size;
 174
 175         t->lookups++;
 176         while( 1 ) {
 177                 if(t->table[n].k == LH_EMPTY) return NULL;
 178                 if(t->table[n].k != LH_FREED &&
 179                    t->equal_fn(t->table[n].k, k)) return &t->table[n];
 180                 if(++n == t->size) n = 0;
 181         }
 182         return NULL;
 183 }
 184
 185
 186 void* lh_table_lookup(struct lh_table *t, void *k)
 187 {
 188         struct lh_entry *e = lh_table_lookup_entry(t, k);
 189         if(e) return e->v;
 190         return NULL;
 191 }
 192
 193
 194 int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)
 195 {
 196         int n = e - t->table;
 197         if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1;
 198         t->count--;
 199         if(t->free_fn) t->free_fn(e);
 200         t->table[n].v = NULL;
 201         t->table[n].k = LH_FREED;
 202         if(t->tail == &t->table[n] && t->head == &t->table[n]) {
 203                 t->head = t->tail = NULL;
 204         } else if (t->head == &t->table[n]) {
 205                 t->head->next->prev = NULL;
 206                 t->head = t->head->next;
 207         } else if (t->tail == &t->table[n]) {
 208                 t->tail->prev->next = NULL;
 209                 t->tail = t->tail->prev;
 210         } else {
 211                 t->table[n].prev->next = t->table[n].next;
 212                 t->table[n].next->prev = t->table[n].prev;
 213         }
 214         t->table[n].next = t->table[n].prev = NULL;
 215         return 0;
 216 }
 217
 218
 219 int lh_table_delete(struct lh_table *t, void *k)
 220 {
 221         struct lh_entry *e = lh_table_lookup_entry(t, k);
 222         if(!e) return -1;
 223         return lh_table_delete_entry(t, e);
 224 }
 225