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 
#include "jlog_config.h" 

34 
#include "jlog_hash.h" 

35 


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

37 


38 
#define JLogHASH_INITIAL_SIZE (1<<7) 

39 


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

41 
{ \ 

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

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

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

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

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

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

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

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

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

51 
} 

52 


53 
static inline 

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

55 
{ 

56 
register u_int32_t a,b,c,len; 

57 


58 
/* Set up the internal state */ 

59 
len = length; 

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

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

62 


63 
/* handle most of the key */ 

64 
while (len >= 12) 

65 
{ 

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

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

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

69 
mix(a,b,c); 

70 
k += 12; len = 12; 

71 
} 

72 


73 
/* handle the last 11 bytes */ 

74 
c += length; 

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

76 
{ 

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

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

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

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

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

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

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

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

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

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

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

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

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

90 
} 

91 
mix(a,b,c); 

92 
/* report the result */ 

93 
return c; 

94 
} 

95 


96 
u_int32_t jlog_hash__hash(const char *k, u_int32_t length, u_int32_t initval) { 

97 
return __hash(k,length,initval); 

98 
} 

99 


100 
void jlog_hash_init(jlog_hash_table *h) { 

101 
memset(h, 0, sizeof(jlog_hash_table)); 

102 
h>initval = lrand48(); 

103 
h>table_size = JLogHASH_INITIAL_SIZE; 

104 
h>buckets = calloc(h>table_size, sizeof(jlog_hash_bucket *)); 

105 
} 

106 


107 
jlog_hash_bucket *jlog_hash__new_bucket(const char *k, int klen, void *data) { 

108 
jlog_hash_bucket *b; 

109 
b = calloc(1, sizeof(jlog_hash_bucket)); 

110 
b>k = k; 

111 
b>klen = klen; 

112 
b>data = data; 

113 
return b; 

114 
} 

115 
void jlog_hash__rebucket(jlog_hash_table *h, int newsize) { 

116 
int i, newoff; 

117 
jlog_hash_bucket **newbuckets, *b, *n; 

118 


119 
if (h>dont_rebucket) return; 

120 


121 
i = newsize; 

122 
while(i) { 

123 
if(i & 1) break; 

124 
i >>= 1; 

125 
} 

126 
if(i & ~1) { 

127 
return; 

128 
} 

129 
newbuckets = calloc(newsize, sizeof(jlog_hash_bucket *)); 

130 
h>num_used_buckets = 0; 

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

132 
b = h>buckets[i]; 

133 
while(b) { 

134 
n = b>next; 

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

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

137 
b>next = newbuckets[newoff]; 

138 
newbuckets[newoff] = b; 

139 
b = n; 

140 
} 

141 
} 

142 
free(h>buckets); 

143 
h>table_size = newsize; 

144 
h>buckets = newbuckets; 

145 
} 

146 
int jlog_hash_replace(jlog_hash_table *h, const char *k, int klen, void *data, 

147 
JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) { 

148 
int off; 

149 
int replaced = 0; 

150 
jlog_hash_bucket __b, *tr, *b = &__b; 

151 


152 
if(h>table_size == 0) jlog_hash_init(h); 

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

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

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

156 
while(b>next) { 

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

158 
tr = b>next; 

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

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

161 
b>next = tr>next; 

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

163 
free(tr); 

164 
replaced = 1; 

165 
break; 

166 
} else { 

167 
b = b>next; 

168 
} 

169 
} 

170 
b = jlog_hash__new_bucket(k, klen, data); 

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

172 
h>buckets[off] = b; 

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

174 


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

176 
jlog_hash__rebucket(h, h>table_size << 1); 

177 
} 

178 
return 1; 

179 
} 

180 
int jlog_hash_store(jlog_hash_table *h, const char *k, int klen, void *data) { 

181 
int off; 

182 
jlog_hash_bucket *b; 

183 


184 
if(h>table_size == 0) jlog_hash_init(h); 

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

186 
b = h>buckets[off]; 

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

188 
while(b) { 

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

190 
b = b>next; 

191 
} 

192 
b = jlog_hash__new_bucket(k, klen, data); 

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

194 
h>buckets[off] = b; 

195 
h>size++; 

196 


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

198 
jlog_hash__rebucket(h, h>table_size << 1); 

199 
} 

200 
return 1; 

201 
} 

202 
int jlog_hash_retrieve(jlog_hash_table *h, const char *k, int klen, void **data) { 

203 
int off; 

204 
jlog_hash_bucket *b; 

205 


206 
if(h>table_size == 0) jlog_hash_init(h); 

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

208 
b = h>buckets[off]; 

209 
while(b) { 

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

211 
b = b>next; 

212 
} 

213 
if(b) { 

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

215 
return 1; 

216 
} 

217 
return 0; 

218 
} 

219 
int jlog_hash_delete(jlog_hash_table *h, const char *k, int klen, 

220 
JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) { 

221 
int off; 

222 
void *data; 

223 
jlog_hash_bucket *b, *prev = NULL; 

224 


225 
if(h>table_size == 0) jlog_hash_init(h); 

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

227 
b = h>buckets[off]; 

228 
while(b) { 

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

230 
prev = b; 

231 
b = b>next; 

232 
} 

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

234 
data = b>data; 

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

236 
else prev>next = b>next; 

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

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

239 
free(b); 

240 
h>size; 

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

242 
if(h>table_size > JLogHASH_INITIAL_SIZE && 

243 
h>size < h>table_size >> 2) 

244 
jlog_hash__rebucket(h, h>table_size >> 1); 

245 
return 1; 

246 
} 

247 


248 
void jlog_hash_delete_all(jlog_hash_table *h, JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) { 

249 
int i; 

250 
jlog_hash_bucket *b, *tofree; 

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

252 
b = h>buckets[i]; 

253 
while(b) { 

254 
tofree = b; 

255 
b = b>next; 

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

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

258 
free(tofree); 

259 
} 

260 
h>buckets[i] = NULL; 

261 
} 

262 
h>num_used_buckets = 0; 

263 
h>size = 0; 

264 
jlog_hash__rebucket(h, JLogHASH_INITIAL_SIZE); 

265 
} 

266 


267 
void jlog_hash_destroy(jlog_hash_table *h, JLogHashFreeFunc keyfree, JLogHashFreeFunc datafree) { 

268 
jlog_hash_delete_all(h, keyfree, datafree); 

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

270 
} 

271 


272 
int jlog_hash_next(jlog_hash_table *h, jlog_hash_iter *iter, 

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

274 
jlog_hash_bucket *b; 

275 
next_row: 

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

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

278 
if(iter>p2 == NULL) { 

279 
iter>p1++; 

280 
goto next_row; 

281 
} 

282 
b = (jlog_hash_bucket *)(iter>p2); 

283 
*k = b>k; *klen = b>klen; 

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

285 
b = b>next; 

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

287 
iter>p2 = b; 

288 
return 1; 

289 
} 

290 


291 
int jlog_hash_firstkey(jlog_hash_table *h, const char **k, int *klen) { 

292 
int i; 

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

294 
if(h>buckets[i]) { 

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

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

297 
return 1; 

298 
} 

299 
} 

300 
return 0; 

301 
} 

302 
int jlog_hash_nextkey(jlog_hash_table *h, const char **k, int *klen, const char *lk, int lklen) { 

303 
int off; 

304 
jlog_hash_bucket *b; 

305 


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

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

308 
b = h>buckets[off]; 

309 
while(b) { 

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

311 
b = b>next; 

312 
} 

313 
if(b) { 

314 
if(b>next) { 

315 
*k = b>next>k; 

316 
*klen = b>next>klen; 

317 
return 1; 

318 
} else { 

319 
off++; 

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

321 
if(h>buckets[off]) { 

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

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

324 
return 1; 

325 
} 

326 
} 

327 
} 

328 
} 

329 
return 0; 

330 
} 

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