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 0 : {
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 : unsigned long lh_ptr_hash(const void *k)
31 0 : {
32 : /* CAW: refactored to be 64bit nice */
33 0 : 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 0 : {
38 0 : return (k1 == k2);
39 : }
40 :
41 : unsigned long lh_char_hash(const void *k)
42 822 : {
43 822 : unsigned int h = 0;
44 822 : const char* data = (const char*)k;
45 :
46 822 : while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;
47 :
48 822 : return h;
49 : }
50 :
51 : int lh_char_equal(const void *k1, const void *k2)
52 67 : {
53 67 : 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 211 : {
61 : int i;
62 : struct lh_table *t;
63 :
64 211 : t = (struct lh_table*)calloc(1, sizeof(struct lh_table));
65 211 : if(!t) lh_abort("lh_table_new: calloc failed\n");
66 211 : t->count = 0;
67 211 : t->size = size;
68 211 : t->name = name;
69 211 : t->table = (struct lh_entry*)calloc(size, sizeof(struct lh_entry));
70 211 : if(!t->table) lh_abort("lh_table_new: calloc failed\n");
71 211 : t->free_fn = free_fn;
72 211 : t->hash_fn = hash_fn;
73 211 : t->equal_fn = equal_fn;
74 211 : for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;
75 211 : 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 211 : {
81 211 : 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 0 : {
87 0 : 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 0 : {
92 : struct lh_table *new_t;
93 : struct lh_entry *ent;
94 :
95 0 : new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);
96 0 : ent = t->head;
97 0 : while(ent) {
98 0 : lh_table_insert(new_t, ent->k, ent->v);
99 0 : ent = ent->next;
100 : }
101 0 : free(t->table);
102 0 : t->table = new_t->table;
103 0 : t->size = new_size;
104 0 : t->head = new_t->head;
105 0 : t->tail = new_t->tail;
106 0 : t->resizes++;
107 0 : free(new_t);
108 0 : }
109 :
110 : void lh_table_free(struct lh_table *t)
111 211 : {
112 : struct lh_entry *c;
113 622 : for(c = t->head; c != NULL; c = c->next) {
114 411 : if(t->free_fn) {
115 411 : t->free_fn(c);
116 : }
117 : }
118 211 : free(t->table);
119 211 : free(t);
120 211 : }
121 :
122 :
123 : int lh_table_insert(struct lh_table *t, void *k, const void *v)
124 411 : {
125 : unsigned long h, n;
126 :
127 411 : t->inserts++;
128 411 : if(t->count > t->size * 0.66) lh_table_resize(t, t->size * 2);
129 :
130 411 : h = t->hash_fn(k);
131 411 : n = h % t->size;
132 :
133 : while( 1 ) {
134 478 : if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;
135 67 : t->collisions++;
136 67 : if(++n == t->size) n = 0;
137 67 : }
138 :
139 411 : t->table[n].k = k;
140 411 : t->table[n].v = v;
141 411 : t->count++;
142 :
143 411 : if(t->head == NULL) {
144 176 : t->head = t->tail = &t->table[n];
145 176 : t->table[n].next = t->table[n].prev = NULL;
146 : } else {
147 235 : t->tail->next = &t->table[n];
148 235 : t->table[n].prev = t->tail;
149 235 : t->table[n].next = NULL;
150 235 : t->tail = &t->table[n];
151 : }
152 :
153 411 : return 0;
154 : }
155 :
156 :
157 : struct lh_entry* lh_table_lookup_entry(struct lh_table *t, const void *k)
158 411 : {
159 411 : unsigned long h = t->hash_fn(k);
160 411 : unsigned long n = h % t->size;
161 :
162 411 : t->lookups++;
163 : while( 1 ) {
164 478 : if(t->table[n].k == LH_EMPTY) return NULL;
165 67 : if(t->table[n].k != LH_FREED &&
166 0 : t->equal_fn(t->table[n].k, k)) return &t->table[n];
167 67 : if(++n == t->size) n = 0;
168 67 : }
169 : return NULL;
170 : }
171 :
172 :
173 : const void* lh_table_lookup(struct lh_table *t, const void *k)
174 0 : {
175 0 : struct lh_entry *e = lh_table_lookup_entry(t, k);
176 0 : if(e) return e->v;
177 0 : return NULL;
178 : }
179 :
180 :
181 : int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)
182 0 : {
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 : int lh_table_delete(struct lh_table *t, const void *k)
211 411 : {
212 411 : struct lh_entry *e = lh_table_lookup_entry(t, k);
213 411 : if(!e) return -1;
214 0 : return lh_table_delete_entry(t, e);
215 : }
216 :
|
