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