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 0 : void lh_abort(const char *msg, ...)
22 : {
23 : va_list ap;
24 0 : va_start(ap, msg);
25 0 : vprintf(msg, ap);
26 0 : va_end(ap);
27 0 : exit(1);
28 : }
29 :
30 0 : unsigned long lh_ptr_hash(const void *k)
31 : {
32 : /* CAW: refactored to be 64bit nice */
33 0 : return (unsigned long)((((ptrdiff_t)k * LH_PRIME) >> 4) & ULONG_MAX);
34 : }
35 :
36 0 : int lh_ptr_equal(const void *k1, const void *k2)
37 : {
38 0 : return (k1 == k2);
39 : }
40 :
41 12697 : unsigned long lh_char_hash(const void *k)
42 : {
43 12697 : unsigned int h = 0;
44 12697 : const char* data = (const char*)k;
45 :
46 12697 : while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;
47 :
48 12697 : return h;
49 : }
50 :
51 4108 : int lh_char_equal(const void *k1, const void *k2)
52 : {
53 4108 : return (strcmp((const char*)k1, (const char*)k2) == 0);
54 : }
55 :
56 1441 : 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 1441 : t = (struct lh_table*)calloc(1, sizeof(struct lh_table));
65 1441 : if(!t) lh_abort("lh_table_new: calloc failed\n");
66 1441 : t->count = 0;
67 1441 : t->size = size;
68 1441 : t->name = name;
69 1441 : t->table = (struct lh_entry*)calloc(size, sizeof(struct lh_entry));
70 1441 : if(!t->table) lh_abort("lh_table_new: calloc failed\n");
71 1441 : t->free_fn = free_fn;
72 1441 : t->hash_fn = hash_fn;
73 1441 : t->equal_fn = equal_fn;
74 1441 : for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;
75 1441 : return t;
76 : }
77 :
78 1394 : struct lh_table* lh_kchar_table_new(int size, const char *name,
79 : lh_entry_free_fn *free_fn)
80 : {
81 1394 : return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal);
82 : }
83 :
84 0 : struct lh_table* lh_kptr_table_new(int size, const char *name,
85 : lh_entry_free_fn *free_fn)
86 : {
87 0 : return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal);
88 : }
89 :
90 47 : 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 47 : new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);
96 47 : ent = t->head;
97 611 : while(ent) {
98 517 : lh_table_insert(new_t, ent->k, ent->v);
99 517 : ent = ent->next;
100 : }
101 47 : free(t->table);
102 47 : t->table = new_t->table;
103 47 : t->size = new_size;
104 47 : t->head = new_t->head;
105 47 : t->tail = new_t->tail;
106 47 : t->resizes++;
107 47 : free(new_t);
108 47 : }
109 :
110 1394 : void lh_table_free(struct lh_table *t)
111 : {
112 : struct lh_entry *c;
113 6744 : for(c = t->head; c != NULL; c = c->next) {
114 5350 : if(t->free_fn) {
115 5350 : t->free_fn(c);
116 : }
117 : }
118 1394 : free(t->table);
119 1394 : free(t);
120 1394 : }
121 :
122 :
123 5867 : int lh_table_insert(struct lh_table *t, void *k, const void *v)
124 : {
125 : unsigned long h, n;
126 :
127 5867 : t->inserts++;
128 5867 : if(t->count > t->size * 0.66) lh_table_resize(t, t->size * 2);
129 :
130 5867 : h = t->hash_fn(k);
131 5867 : n = h % t->size;
132 :
133 : while( 1 ) {
134 7947 : if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;
135 2080 : t->collisions++;
136 2080 : if(++n == t->size) n = 0;
137 2080 : }
138 :
139 5867 : t->table[n].k = k;
140 5867 : t->table[n].v = v;
141 5867 : t->count++;
142 :
143 5867 : if(t->head == NULL) {
144 1369 : t->head = t->tail = &t->table[n];
145 1369 : t->table[n].next = t->table[n].prev = NULL;
146 : } else {
147 4498 : t->tail->next = &t->table[n];
148 4498 : t->table[n].prev = t->tail;
149 4498 : t->table[n].next = NULL;
150 4498 : t->tail = &t->table[n];
151 : }
152 :
153 5867 : return 0;
154 : }
155 :
156 :
157 6830 : struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k)
158 : {
159 6830 : unsigned long h = t->hash_fn(k);
160 6830 : unsigned long n = h % t->size;
161 :
162 6830 : t->lookups++;
163 : while( 1 ) {
164 9668 : if(t->table[n].k == LH_EMPTY) return NULL;
165 8216 : if(t->table[n].k != LH_FREED &&
166 5378 : t->equal_fn(t->table[n].k, k)) return &t->table[n];
167 2838 : if(++n == t->size) n = 0;
168 2838 : }
169 : return NULL;
170 : }
171 :
172 :
173 1480 : const void* lh_table_lookup(struct lh_table *t, const void *k)
174 : {
175 1480 : struct lh_entry *e = lh_table_lookup_entry(t, k);
176 1480 : if(e) return e->v;
177 210 : return NULL;
178 : }
179 :
180 :
181 0 : int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)
182 : {
183 0 : 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 0 : if(n < 0) { return -2; }
187 :
188 0 : if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1;
189 0 : t->count--;
190 0 : if(t->free_fn) t->free_fn(e);
191 0 : t->table[n].v = NULL;
192 0 : t->table[n].k = LH_FREED;
193 0 : if(t->tail == &t->table[n] && t->head == &t->table[n]) {
194 0 : t->head = t->tail = NULL;
195 0 : } else if (t->head == &t->table[n]) {
196 0 : t->head->next->prev = NULL;
197 0 : t->head = t->head->next;
198 0 : } else if (t->tail == &t->table[n]) {
199 0 : t->tail->prev->next = NULL;
200 0 : t->tail = t->tail->prev;
201 : } else {
202 0 : t->table[n].prev->next = t->table[n].next;
203 0 : t->table[n].next->prev = t->table[n].prev;
204 : }
205 0 : t->table[n].next = t->table[n].prev = NULL;
206 0 : return 0;
207 : }
208 :
209 :
210 5350 : int lh_table_delete(struct lh_table *t, const void *k)
211 : {
212 5350 : struct lh_entry *e = lh_table_lookup_entry(t, k);
213 5350 : if(!e) return -1;
214 0 : return lh_table_delete_entry(t, e);
215 : }
216 :
|
