1 
/* 

2 
* Copyright (c) 20012006 OmniTI, Inc. All rights reserved. 

3 
* 

4 
* Redistribution and use in source and binary forms, with or without 

5 
* modification, are permitted provided that the following conditions 

6 
* are met: 

7 
* 1. Redistributions of source code must retain the above copyright 

8 
* notice, this list of conditions and the following disclaimer. 

9 
* 2. Redistributions in binary form must reproduce the above copyright 

10 
* notice, this list of conditions and the following disclaimer in the 

11 
* documentation and/or other materials provided with the distribution. 

12 
* 3. The name of the author may not be used to endorse or promote products 

13 
* derived from this software without specific prior written permission. 

14 
* 

15 
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 

16 
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 

17 
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 

18 
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 

19 
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 

20 
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 

21 
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 

22 
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 

23 
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 

24 
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

25 
*/ 

26 


27 
#include "sld_config.h" 

28 
#include "echash.h" 

29 


30 
/* This is from http://burtleburtle.net/bob/hash/doobs.html */ 

31 


32 
#define ECHASH_INITIAL_SIZE (1<<7) 

33 


34 
#define mix(a,b,c) \ 

35 
{ \ 

36 
a = b; a = c; a ^= (c>>13); \ 

37 
b = c; b = a; b ^= (a<<8); \ 

38 
c = a; c = b; c ^= (b>>13); \ 

39 
a = b; a = c; a ^= (c>>12); \ 

40 
b = c; b = a; b ^= (a<<16); \ 

41 
c = a; c = b; c ^= (b>>5); \ 

42 
a = b; a = c; a ^= (c>>3); \ 

43 
b = c; b = a; b ^= (a<<10); \ 

44 
c = a; c = b; c ^= (b>>15); \ 

45 
} 

46 


47 
static inline 

48 
unsigned int __hash(const char *k, unsigned int length, unsigned int initval) 

49 
{ 

50 
register unsigned int a,b,c,len; 

51 


52 
/* Set up the internal state */ 

53 
len = length; 

54 
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ 

55 
c = initval; /* the previous hash value */ 

56 


57 
/* handle most of the key */ 

58 
while (len >= 12) 

59 
{ 

60 
a += (k[0] +((unsigned int)k[1]<<8) +((unsigned int)k[2]<<16) +((unsigned int)k[3]<<24)); 

61 
b += (k[4] +((unsigned int)k[5]<<8) +((unsigned int)k[6]<<16) +((unsigned int)k[7]<<24)); 

62 
c += (k[8] +((unsigned int)k[9]<<8) +((unsigned int)k[10]<<16)+((unsigned int)k[11]<<24)); 

63 
mix(a,b,c); 

64 
k += 12; len = 12; 

65 
} 

66 


67 
/* handle the last 11 bytes */ 

68 
c += length; 

69 
switch(len) /* all the case statements fall through */ 

70 
{ 

71 
case 11: c+=((unsigned int)k[10]<<24); 

72 
case 10: c+=((unsigned int)k[9]<<16); 

73 
case 9 : c+=((unsigned int)k[8]<<8); 

74 
/* the first byte of c is reserved for the length */ 

75 
case 8 : b+=((unsigned int)k[7]<<24); 

76 
case 7 : b+=((unsigned int)k[6]<<16); 

77 
case 6 : b+=((unsigned int)k[5]<<8); 

78 
case 5 : b+=k[4]; 

79 
case 4 : a+=((unsigned int)k[3]<<24); 

80 
case 3 : a+=((unsigned int)k[2]<<16); 

81 
case 2 : a+=((unsigned int)k[1]<<8); 

82 
case 1 : a+=k[0]; 

83 
/* case 0: nothing left to add */ 

84 
} 

85 
mix(a,b,c); 

86 
/* report the result */ 

87 
return c; 

88 
} 

89 


90 
unsigned int echash__hash(const char *k, unsigned int length, unsigned int initval) { 

91 
return __hash(k,length,initval); 

92 
} 

93 


94 
void echash_init(ec_hash_table *h) { 

95 
memset(h, 0, sizeof(ec_hash_table)); 

96 
h>initval = lrand48(); 

97 
h>table_size = ECHASH_INITIAL_SIZE; 

98 
h>buckets = calloc(h>table_size, sizeof(ec_hash_bucket *)); 

99 
} 

100 


101 
ec_hash_bucket *echash__new_bucket(const char *k, int klen, void *data) { 

102 
ec_hash_bucket *b; 

103 
b = calloc(1, sizeof(ec_hash_bucket)); 

104 
b>k = k; 

105 
b>klen = klen; 

106 
b>data = data; 

107 
return b; 

108 
} 

109 
void echash__rebucket(ec_hash_table *h, int newsize) { 

110 
int i, newoff; 

111 
ec_hash_bucket **newbuckets, *b, *n; 

112 


113 
i = newsize; 

114 
while(i) { 

115 
if(i & 1) break; 

116 
i >>= 1; 

117 
} 

118 
if(i & ~1) { 

119 
return; 

120 
} 

121 
newbuckets = calloc(newsize, sizeof(ec_hash_bucket *)); 

122 
h>num_used_buckets = 0; 

123 
for(i = 0; i < h>table_size; i++) { 

124 
b = h>buckets[i]; 

125 
while(b) { 

126 
n = b>next; 

127 
newoff = __hash(b>k, b>klen, h>initval) & (newsize1); 

128 
if(newbuckets[newoff] == NULL) h>num_used_buckets++; 

129 
b>next = newbuckets[newoff]; 

130 
newbuckets[newoff] = b; 

131 
b = n; 

132 
} 

133 
} 

134 
free(h>buckets); 

135 
h>table_size = newsize; 

136 
h>buckets = newbuckets; 

137 
} 

138 
int echash_replace(ec_hash_table *h, const char *k, int klen, void *data, 

139 
ECHashFreeFunc keyfree, ECHashFreeFunc datafree) { 

140 
int off; 

141 
ec_hash_bucket __b, *tr, *b = &__b; 

142 


143 
if(h>table_size == 0) echash_init(h); 

144 
off = __hash(k, klen, h>initval) & (h>table_size1); 

145 
__b.next = h>buckets[off]; 

146 
if(!b>next) h>num_used_buckets++; 

147 
while(b>next) { 

148 
if(b>next>klen == klen && !memcmp(b>next>k, k, klen)) { 

149 
tr = b>next; 

150 
if(keyfree) keyfree((void *)tr>k); 

151 
if(datafree && tr>data) datafree((void *)tr>data); 

152 
b>next = tr>next; 

153 
if(tr == h>buckets[off]) h>buckets[off] = NULL; 

154 
free(tr); 

155 
} else { 

156 
b = b>next; 

157 
} 

158 
} 

159 
b = echash__new_bucket(k, klen, data); 

160 
b>next = h>buckets[off]; 

161 
h>buckets[off] = b; 

162 
h>size++; 

163 


164 
if(h>size > h>table_size  (h>table_size >> 3)) { 

165 
echash__rebucket(h, h>table_size << 1); 

166 
} 

167 
return 1; 

168 
} 

169 
int echash_store(ec_hash_table *h, const char *k, int klen, void *data) { 

170 
int off; 

171 
ec_hash_bucket *b; 

172 


173 
if(h>table_size == 0) echash_init(h); 

174 
off = __hash(k, klen, h>initval) & (h>table_size1); 

175 
b = h>buckets[off]; 

176 
if(!b) h>num_used_buckets++; 

177 
while(b) { 

178 
if(b>klen == klen && !memcmp(b>k, k, klen)) return 0; 

179 
b = b>next; 

180 
} 

181 
b = echash__new_bucket(k, klen, data); 

182 
b>next = h>buckets[off]; 

183 
h>buckets[off] = b; 

184 
h>size++; 

185 


186 
if(h>size > h>table_size  (h>table_size >> 3)) { 

187 
echash__rebucket(h, h>table_size << 1); 

188 
} 

189 
return 1; 

190 
} 

191 
int echash_retrieve(ec_hash_table *h, const char *k, int klen, void **data) { 

192 
int off; 

193 
ec_hash_bucket *b; 

194 


195 
if(h>table_size == 0) echash_init(h); 

196 
off = __hash(k, klen, h>initval) & (h>table_size1); 

197 
b = h>buckets[off]; 

198 
while(b) { 

199 
if(b>klen == klen && !memcmp(b>k, k, klen)) break; 

200 
b = b>next; 

201 
} 

202 
if(b) { 

203 
if(data) *data = b>data; 

204 
return 1; 

205 
} 

206 
return 0; 

207 
} 

208 
int echash_delete(ec_hash_table *h, const char *k, int klen, 

209 
ECHashFreeFunc keyfree, ECHashFreeFunc datafree) { 

210 
int off; 

211 
void *data; 

212 
ec_hash_bucket *b, *prev = NULL; 

213 


214 
if(h>table_size == 0) echash_init(h); 

215 
off = __hash(k, klen, h>initval) & (h>table_size1); 

216 
b = h>buckets[off]; 

217 
while(b) { 

218 
if(b>klen == klen && !memcmp(b>k, k, klen)) break; 

219 
prev = b; 

220 
b = b>next; 

221 
} 

222 
if(!b) return 0; /* No match */ 

223 
data = b>data; 

224 
if(!prev) h>buckets[off] = h>buckets[off]>next; 

225 
else prev>next = b>next; 

226 
if(keyfree) keyfree((void *)b>k); 

227 
if(datafree && b>data) datafree(b>data); 

228 
free(b); 

229 
h>size; 

230 
if(h>buckets[off] == NULL) h>num_used_buckets; 

231 
if(h>table_size > ECHASH_INITIAL_SIZE && 

232 
h>size < h>table_size >> 2) 

233 
echash__rebucket(h, h>table_size >> 1); 

234 
return 1; 

235 
} 

236 


237 
void echash_delete_all(ec_hash_table *h, ECHashFreeFunc keyfree, ECHashFreeFunc datafree) { 

238 
int i; 

239 
ec_hash_bucket *b, *tofree; 

240 
for(i=0; i<h>table_size; i++) { 

241 
b = h>buckets[i]; 

242 
while(b) { 

243 
tofree = b; 

244 
b = b>next; 

245 
if(keyfree) keyfree((void *)tofree>k); 

246 
if(datafree && tofree>data) datafree(tofree>data); 

247 
free(tofree); 

248 
} 

249 
h>buckets[i] = NULL; 

250 
} 

251 
h>num_used_buckets = 0; 

252 
h>size = 0; 

253 
echash__rebucket(h, ECHASH_INITIAL_SIZE); 

254 
} 

255 


256 
void echash_destroy(ec_hash_table *h, ECHashFreeFunc keyfree, ECHashFreeFunc datafree) { 

257 
echash_delete_all(h, keyfree, datafree); 

258 
if(h>buckets) free(h>buckets); 

259 
} 

260 


261 
int echash_next(ec_hash_table *h, ec_hash_iter *iter, 

262 
const char **k, int *klen, void **data) { 

263 
ec_hash_bucket *b; 

264 
next_row: 

265 
if(iter>p1 < 0  iter>p1 >= h>table_size) return 0; 

266 
if(iter>p2 == NULL) iter>p2 = (void *)h>buckets[iter>p1]; 

267 
if(iter>p2 == NULL) { 

268 
iter>p1++; 

269 
goto next_row; 

270 
} 

271 
b = (ec_hash_bucket *)(iter>p2); 

272 
*k = b>k; *klen = b>klen; 

273 
if(data) *data = b>data; 

274 
b = b>next; 

275 
if(!b) iter>p1++; 

276 
iter>p2 = b; 

277 
return 1; 

278 
} 

279 


280 
int echash_firstkey(ec_hash_table *h, const char **k, int *klen) { 

281 
int i; 

282 
for(i=0;i<h>table_size;i++) { 

283 
if(h>buckets[i]) { 

284 
*k = h>buckets[i]>k; 

285 
*klen = h>buckets[i]>klen; 

286 
return 1; 

287 
} 

288 
} 

289 
return 0; 

290 
} 

291 
int echash_nextkey(ec_hash_table *h, const char **k, int *klen, char *lk, int lklen) { 

292 
int off; 

293 
ec_hash_bucket *b; 

294 


295 
if(h>table_size == 0) return 0; 

296 
off = __hash(lk, lklen, h>initval) & (h>table_size1); 

297 
b = h>buckets[off]; 

298 
while(b) { 

299 
if(b>klen == lklen && !memcmp(b>k, lk, lklen)) break; 

300 
b = b>next; 

301 
} 

302 
if(b) { 

303 
if(b>next) { 

304 
*k = b>next>k; 

305 
*klen = b>next>klen; 

306 
return 1; 

307 
} else { 

308 
off++; 

309 
for(;off < h>table_size; off++) { 

310 
if(h>buckets[off]) { 

311 
*k = h>buckets[off]>k; 

312 
*klen = h>buckets[off]>klen; 

313 
return 1; 

314 
} 

315 
} 

316 
} 

317 
} 

318 
return 0; 

319 
} 

320 
/* vim: se sw=2 ts=2 et: */ 
