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