1 
/* 

2 
* Copyright (c) 20052007, OmniTI Computer Consulting, Inc. 

3 
* All rights reserved. 

4 
* 

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

6 
* modification, are permitted provided that the following conditions are 

7 
* met: 

8 
* 

9 
* * Redistributions of source code must retain the above copyright 

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

11 
* * Redistributions in binary form must reproduce the above 

12 
* copyright notice, this list of conditions and the following 

13 
* disclaimer in the documentation and/or other materials provided 

14 
* with the distribution. 

15 
* * Neither the name OmniTI Computer Consulting, Inc. nor the names 

16 
* of its contributors may be used to endorse or promote products 

17 
* derived from this software without specific prior written 

18 
* permission. 

19 
* 

20 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 

21 
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 

22 
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 

23 
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 

24 
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 

25 
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 

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

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

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

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

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

31 
*/ 

32 


33 
/* this is just a copy (with search and replace) from jlog_hash */ 

34 


35 
#include "noit_config.h" 

36 
#include "noit_hash.h" 

37 


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

39 


40 
#define NoitHASH_INITIAL_SIZE (1<<7) 

41 


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

43 
{ \ 

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

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

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

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

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

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

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

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

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

53 
} 

54 


55 
static inline 

56 
u_int32_t __hash(const char *k, u_int32_t length, u_int32_t initval) 

57 
{ 

58 
register u_int32_t a,b,c,len; 

59 


60 
/* Set up the internal state */ 

61 
len = length; 

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

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

64 


65 
/* handle most of the key */ 

66 
while (len >= 12) 

67 
{ 

68 
a += (k[0] +((u_int32_t)k[1]<<8) +((u_int32_t)k[2]<<16) +((u_int32_t)k[3]<<24)); 

69 
b += (k[4] +((u_int32_t)k[5]<<8) +((u_int32_t)k[6]<<16) +((u_int32_t)k[7]<<24)); 

70 
c += (k[8] +((u_int32_t)k[9]<<8) +((u_int32_t)k[10]<<16)+((u_int32_t)k[11]<<24)); 

71 
mix(a,b,c); 

72 
k += 12; len = 12; 

73 
} 

74 


75 
/* handle the last 11 bytes */ 

76 
c += length; 

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

78 
{ 

79 
case 11: c+=((u_int32_t)k[10]<<24); 

80 
case 10: c+=((u_int32_t)k[9]<<16); 

81 
case 9 : c+=((u_int32_t)k[8]<<8); 

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

83 
case 8 : b+=((u_int32_t)k[7]<<24); 

84 
case 7 : b+=((u_int32_t)k[6]<<16); 

85 
case 6 : b+=((u_int32_t)k[5]<<8); 

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

87 
case 4 : a+=((u_int32_t)k[3]<<24); 

88 
case 3 : a+=((u_int32_t)k[2]<<16); 

89 
case 2 : a+=((u_int32_t)k[1]<<8); 

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

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

92 
} 

93 
mix(a,b,c); 

94 
/* report the result */ 

95 
return c; 

96 
} 

97 


98 
u_int32_t noit_hash__hash(const char *k, u_int32_t length, u_int32_t initval) { 

99 
return __hash(k,length,initval); 

100 
} 

101 


102 
void noit_hash_init(noit_hash_table *h) { 

103 
memset(h, 0, sizeof(noit_hash_table)); 

104 
h>initval = lrand48(); 

105 
h>table_size = NoitHASH_INITIAL_SIZE; 

106 
h>buckets = calloc(h>table_size, sizeof(noit_hash_bucket *)); 

107 
} 

108 


109 
noit_hash_bucket *noit_hash__new_bucket(const char *k, int klen, void *data) { 

110 
noit_hash_bucket *b; 

111 
b = calloc(1, sizeof(noit_hash_bucket)); 

112 
b>k = k; 

113 
b>klen = klen; 

114 
b>data = data; 

115 
return b; 

116 
} 

117 
void noit_hash__rebucket(noit_hash_table *h, int newsize) { 

118 
int i, newoff; 

119 
noit_hash_bucket **newbuckets, *b, *n; 

120 


121 
if (h>dont_rebucket) return; 

122 


123 
i = newsize; 

124 
while(i) { 

125 
if(i & 1) break; 

126 
i >>= 1; 

127 
} 

128 
if(i & ~1) { 

129 
return; 

130 
} 

131 
newbuckets = calloc(newsize, sizeof(noit_hash_bucket *)); 

132 
h>num_used_buckets = 0; 

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

134 
b = h>buckets[i]; 

135 
while(b) { 

136 
n = b>next; 

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

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

139 
b>next = newbuckets[newoff]; 

140 
newbuckets[newoff] = b; 

141 
b = n; 

142 
} 

143 
} 

144 
free(h>buckets); 

145 
h>table_size = newsize; 

146 
h>buckets = newbuckets; 

147 
} 

148 
int noit_hash_replace(noit_hash_table *h, const char *k, int klen, void *data, 

149 
NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { 

150 
int off; 

151 
int replaced = 0; 

152 
noit_hash_bucket __b, *tr, *b = &__b; 

153 


154 
if(h>table_size == 0) noit_hash_init(h); 

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

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

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

158 
while(b>next) { 

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

160 
tr = b>next; 

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

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

163 
b>next = tr>next; 

164 
if(tr == h>buckets[off]) h>buckets[off] = tr>next; 

165 
free(tr); 

166 
replaced = 1; 

167 
break; 

168 
} else { 

169 
b = b>next; 

170 
} 

171 
} 

172 
b = noit_hash__new_bucket(k, klen, data); 

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

174 
h>buckets[off] = b; 

175 
if(!replaced) h>size++; 

176 


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

178 
noit_hash__rebucket(h, h>table_size << 1); 

179 
} 

180 
return 1; 

181 
} 

182 
int noit_hash_store(noit_hash_table *h, const char *k, int klen, void *data) { 

183 
int off; 

184 
noit_hash_bucket *b; 

185 


186 
if(h>table_size == 0) noit_hash_init(h); 

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

188 
b = h>buckets[off]; 

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

190 
while(b) { 

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

192 
b = b>next; 

193 
} 

194 
b = noit_hash__new_bucket(k, klen, data); 

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

196 
h>buckets[off] = b; 

197 
h>size++; 

198 


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

200 
noit_hash__rebucket(h, h>table_size << 1); 

201 
} 

202 
return 1; 

203 
} 

204 
int noit_hash_retrieve(noit_hash_table *h, const char *k, int klen, void **data) { 

205 
int off; 

206 
noit_hash_bucket *b; 

207 


208 
if(!h) return 0; 

209 
if(h>table_size == 0) noit_hash_init(h); 

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

211 
b = h>buckets[off]; 

212 
while(b) { 

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

214 
b = b>next; 

215 
} 

216 
if(b) { 

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

218 
return 1; 

219 
} 

220 
return 0; 

221 
} 

222 
int noit_hash_delete(noit_hash_table *h, const char *k, int klen, 

223 
NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { 

224 
int off; 

225 
void *data; 

226 
noit_hash_bucket *b, *prev = NULL; 

227 


228 
if(h>table_size == 0) noit_hash_init(h); 

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

230 
b = h>buckets[off]; 

231 
while(b) { 

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

233 
prev = b; 

234 
b = b>next; 

235 
} 

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

237 
data = b>data; 

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

239 
else prev>next = b>next; 

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

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

242 
free(b); 

243 
h>size; 

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

245 
if(h>table_size > NoitHASH_INITIAL_SIZE && 

246 
h>size < h>table_size >> 2) 

247 
noit_hash__rebucket(h, h>table_size >> 1); 

248 
return 1; 

249 
} 

250 


251 
void noit_hash_delete_all(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { 

252 
int i; 

253 
noit_hash_bucket *b, *tofree; 

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

255 
b = h>buckets[i]; 

256 
while(b) { 

257 
tofree = b; 

258 
b = b>next; 

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

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

261 
free(tofree); 

262 
} 

263 
h>buckets[i] = NULL; 

264 
} 

265 
h>num_used_buckets = 0; 

266 
h>size = 0; 

267 
noit_hash__rebucket(h, NoitHASH_INITIAL_SIZE); 

268 
} 

269 


270 
void noit_hash_destroy(noit_hash_table *h, NoitHashFreeFunc keyfree, NoitHashFreeFunc datafree) { 

271 
noit_hash_delete_all(h, keyfree, datafree); 

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

273 
} 

274 


275 
void noit_hash_merge_as_dict(noit_hash_table *dst, noit_hash_table *src) { 

276 
noit_hash_iter iter = NOIT_HASH_ITER_ZERO; 

277 
const char *k; 

278 
int klen; 

279 
void *data; 

280 
if(src == NULL  dst == NULL) return; 

281 
while(noit_hash_next(src, &iter, &k, &klen, &data)) 

282 
noit_hash_store(dst, strdup(k), klen, strdup((char *)data)); 

283 
} 

284 


285 
int noit_hash_next(noit_hash_table *h, noit_hash_iter *iter, 

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

287 
noit_hash_bucket *b; 

288 
next_row: 

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

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

291 
if(iter>p2 == NULL) { 

292 
iter>p1++; 

293 
goto next_row; 

294 
} 

295 
b = (noit_hash_bucket *)(iter>p2); 

296 
*k = b>k; *klen = b>klen; 

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

298 
b = b>next; 

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

300 
iter>p2 = b; 

301 
return 1; 

302 
} 

303 


304 
int noit_hash_firstkey(noit_hash_table *h, const char **k, int *klen) { 

305 
int i; 

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

307 
if(h>buckets[i]) { 

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

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

310 
return 1; 

311 
} 

312 
} 

313 
return 0; 

314 
} 

315 
int noit_hash_nextkey(noit_hash_table *h, const char **k, int *klen, const char *lk, int lklen) { 

316 
int off; 

317 
noit_hash_bucket *b; 

318 


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

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

321 
b = h>buckets[off]; 

322 
while(b) { 

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

324 
b = b>next; 

325 
} 

326 
if(b) { 

327 
if(b>next) { 

328 
*k = b>next>k; 

329 
*klen = b>next>klen; 

330 
return 1; 

331 
} else { 

332 
off++; 

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

334 
if(h>buckets[off]) { 

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

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

337 
return 1; 

338 
} 

339 
} 

340 
} 

341 
} 

342 
return 0; 

343 
} 

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