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 
} 

170 


171 


172 
const void* lh_table_lookup(struct lh_table *t, const void *k) 

173 
{ 

174 
struct lh_entry *e = lh_table_lookup_entry(t, k); 

175 
if(e) return e>v; 

176 
return NULL; 

177 
} 

178 


179 


180 
int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e) 

181 
{ 

182 
ptrdiff_t n = (ptrdiff_t)(e  t>table); /* CAW: fixed to be 64bit nice, still need the crazy negative case... */ 

183 


184 
/* CAW: this is bad, really bad, maybe stack goes other direction on this machine... */ 

185 
if(n < 0) { return 2; } 

186 


187 
if(t>table[n].k == LH_EMPTY  t>table[n].k == LH_FREED) return 1; 

188 
t>count; 

189 
if(t>free_fn) t>free_fn(e); 

190 
t>table[n].v = NULL; 

191 
t>table[n].k = LH_FREED; 

192 
if(t>tail == &t>table[n] && t>head == &t>table[n]) { 

193 
t>head = t>tail = NULL; 

194 
} else if (t>head == &t>table[n]) { 

195 
t>head>next>prev = NULL; 

196 
t>head = t>head>next; 

197 
} else if (t>tail == &t>table[n]) { 

198 
t>tail>prev>next = NULL; 

199 
t>tail = t>tail>prev; 

200 
} else { 

201 
t>table[n].prev>next = t>table[n].next; 

202 
t>table[n].next>prev = t>table[n].prev; 

203 
} 

204 
t>table[n].next = t>table[n].prev = NULL; 

205 
return 0; 

206 
} 

207 


208 


209 
int lh_table_delete(struct lh_table *t, const void *k) 

210 
{ 

211 
struct lh_entry *e = lh_table_lookup_entry(t, k); 

212 
if(!e) return 1; 

213 
return lh_table_delete_entry(t, e); 

214 
} 

215 

