1 
/* 

2 
* Copyright (c) 20052008, Message Systems, 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 Message Systems, 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 
jlog_hash_bucket *b, *prev = NULL; 

223 


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

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

226 
b = h>buckets[off]; 

227 
while(b) { 

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

229 
prev = b; 

230 
b = b>next; 

231 
} 

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

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

234 
else prev>next = b>next; 

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

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

237 
free(b); 

238 
h>size; 

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

240 
if(h>table_size > JLogHASH_INITIAL_SIZE && 

241 
h>size < h>table_size >> 2) 

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

243 
return 1; 

244 
} 

245 


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

247 
int i; 

248 
jlog_hash_bucket *b, *tofree; 

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

250 
b = h>buckets[i]; 

251 
while(b) { 

252 
tofree = b; 

253 
b = b>next; 

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

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

256 
free(tofree); 

257 
} 

258 
h>buckets[i] = NULL; 

259 
} 

260 
h>num_used_buckets = 0; 

261 
h>size = 0; 

262 
jlog_hash__rebucket(h, JLogHASH_INITIAL_SIZE); 

263 
} 

264 


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

266 
jlog_hash_delete_all(h, keyfree, datafree); 

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

268 
} 

269 


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

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

272 
jlog_hash_bucket *b; 

273 
next_row: 

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

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

276 
if(iter>p2 == NULL) { 

277 
iter>p1++; 

278 
goto next_row; 

279 
} 

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

281 
*k = b>k; *klen = b>klen; 

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

283 
b = b>next; 

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

285 
iter>p2 = b; 

286 
return 1; 

287 
} 

288 


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

290 
int i; 

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

292 
if(h>buckets[i]) { 

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

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

295 
return 1; 

296 
} 

297 
} 

298 
return 0; 

299 
} 

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

301 
int off; 

302 
jlog_hash_bucket *b; 

303 


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

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

306 
b = h>buckets[off]; 

307 
while(b) { 

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

309 
b = b>next; 

310 
} 

311 
if(b) { 

312 
if(b>next) { 

313 
*k = b>next>k; 

314 
*klen = b>next>klen; 

315 
return 1; 

316 
} else { 

317 
off++; 

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

319 
if(h>buckets[off]) { 

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

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

322 
return 1; 

323 
} 

324 
} 

325 
} 

326 
} 

327 
return 0; 

328 
} 

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