## Mercurial > hg > memcached

### annotate assoc.c @ 3:0b6ac95a09bb default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

Fix unix sockets support under FreeBSD.

author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|

date | Wed, 03 Oct 2007 05:34:42 +0400 |

parents | 30782bb1fc04 |

children |

rev | line source |
---|---|

0 | 1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */ |

2 /* | |

3 * Hash table | |

4 * | |

5 * The hash function used here is by Bob Jenkins, 1996: | |

6 * <http://burtleburtle.net/bob/hash/doobs.html> | |

7 * "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. | |

8 * You may use this code any way you wish, private, educational, | |

9 * or commercial. It's free." | |

10 * | |

11 * The rest of the file is licensed under the BSD license. See LICENSE. | |

12 * | |

13 * $Id: assoc.c 551 2007-05-07 21:24:31Z plindner $ | |

14 */ | |

15 | |

16 #include "memcached.h" | |

17 #include <sys/stat.h> | |

18 #include <sys/socket.h> | |

19 #include <sys/signal.h> | |

20 #include <sys/resource.h> | |

21 #include <fcntl.h> | |

22 #include <netinet/in.h> | |

23 #include <errno.h> | |

24 #include <stdlib.h> | |

25 #include <stdio.h> | |

26 #include <string.h> | |

27 #include <assert.h> | |

28 | |

29 /* | |

30 * Since the hash function does bit manipulation, it needs to know | |

31 * whether it's big or little-endian. ENDIAN_LITTLE and ENDIAN_BIG | |

32 * are set in the configure script. | |

33 */ | |

34 #if ENDIAN_BIG == 1 | |

35 # define HASH_LITTLE_ENDIAN 0 | |

36 # define HASH_BIG_ENDIAN 1 | |

37 #else | |

38 # if ENDIAN_LITTLE == 1 | |

39 # define HASH_LITTLE_ENDIAN 1 | |

40 # define HASH_BIG_ENDIAN 0 | |

41 # else | |

42 # define HASH_LITTLE_ENDIAN 0 | |

43 # define HASH_BIG_ENDIAN 0 | |

44 # endif | |

45 #endif | |

46 | |

47 #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k)))) | |

48 | |

49 /* | |

50 ------------------------------------------------------------------------------- | |

51 mix -- mix 3 32-bit values reversibly. | |

52 | |

53 This is reversible, so any information in (a,b,c) before mix() is | |

54 still in (a,b,c) after mix(). | |

55 | |

56 If four pairs of (a,b,c) inputs are run through mix(), or through | |

57 mix() in reverse, there are at least 32 bits of the output that | |

58 are sometimes the same for one pair and different for another pair. | |

59 This was tested for: | |

60 * pairs that differed by one bit, by two bits, in any combination | |

61 of top bits of (a,b,c), or in any combination of bottom bits of | |

62 (a,b,c). | |

63 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | |

64 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | |

65 is commonly produced by subtraction) look like a single 1-bit | |

66 difference. | |

67 * the base values were pseudorandom, all zero but one bit set, or | |

68 all zero plus a counter that starts at zero. | |

69 | |

70 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that | |

71 satisfy this are | |

72 4 6 8 16 19 4 | |

73 9 15 3 18 27 15 | |

74 14 9 3 7 17 3 | |

75 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing | |

76 for "differ" defined as + with a one-bit base and a two-bit delta. I | |

77 used http://burtleburtle.net/bob/hash/avalanche.html to choose | |

78 the operations, constants, and arrangements of the variables. | |

79 | |

80 This does not achieve avalanche. There are input bits of (a,b,c) | |

81 that fail to affect some output bits of (a,b,c), especially of a. The | |

82 most thoroughly mixed value is c, but it doesn't really even achieve | |

83 avalanche in c. | |

84 | |

85 This allows some parallelism. Read-after-writes are good at doubling | |

86 the number of bits affected, so the goal of mixing pulls in the opposite | |

87 direction as the goal of parallelism. I did what I could. Rotates | |

88 seem to cost as much as shifts on every machine I could lay my hands | |

89 on, and rotates are much kinder to the top and bottom bits, so I used | |

90 rotates. | |

91 ------------------------------------------------------------------------------- | |

92 */ | |

93 #define mix(a,b,c) \ | |

94 { \ | |

95 a -= c; a ^= rot(c, 4); c += b; \ | |

96 b -= a; b ^= rot(a, 6); a += c; \ | |

97 c -= b; c ^= rot(b, 8); b += a; \ | |

98 a -= c; a ^= rot(c,16); c += b; \ | |

99 b -= a; b ^= rot(a,19); a += c; \ | |

100 c -= b; c ^= rot(b, 4); b += a; \ | |

101 } | |

102 | |

103 /* | |

104 ------------------------------------------------------------------------------- | |

105 final -- final mixing of 3 32-bit values (a,b,c) into c | |

106 | |

107 Pairs of (a,b,c) values differing in only a few bits will usually | |

108 produce values of c that look totally different. This was tested for | |

109 * pairs that differed by one bit, by two bits, in any combination | |

110 of top bits of (a,b,c), or in any combination of bottom bits of | |

111 (a,b,c). | |

112 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed | |

113 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as | |

114 is commonly produced by subtraction) look like a single 1-bit | |

115 difference. | |

116 * the base values were pseudorandom, all zero but one bit set, or | |

117 all zero plus a counter that starts at zero. | |

118 | |

119 These constants passed: | |

120 14 11 25 16 4 14 24 | |

121 12 14 25 16 4 14 24 | |

122 and these came close: | |

123 4 8 15 26 3 22 24 | |

124 10 8 15 26 3 22 24 | |

125 11 8 15 26 3 22 24 | |

126 ------------------------------------------------------------------------------- | |

127 */ | |

128 #define final(a,b,c) \ | |

129 { \ | |

130 c ^= b; c -= rot(b,14); \ | |

131 a ^= c; a -= rot(c,11); \ | |

132 b ^= a; b -= rot(a,25); \ | |

133 c ^= b; c -= rot(b,16); \ | |

134 a ^= c; a -= rot(c,4); \ | |

135 b ^= a; b -= rot(a,14); \ | |

136 c ^= b; c -= rot(b,24); \ | |

137 } | |

138 | |

139 #if HASH_LITTLE_ENDIAN == 1 | |

140 uint32_t hash( | |

141 const void *key, /* the key to hash */ | |

142 size_t length, /* length of the key */ | |

143 const uint32_t initval) /* initval */ | |

144 { | |

145 uint32_t a,b,c; /* internal state */ | |

146 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ | |

147 | |

148 /* Set up the internal state */ | |

149 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; | |

150 | |

151 u.ptr = key; | |

152 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { | |

153 const uint32_t *k = key; /* read 32-bit chunks */ | |

154 #ifdef VALGRIND | |

155 const uint8_t *k8; | |

156 #endif // ifdef VALGRIND | |

157 | |

158 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ | |

159 while (length > 12) | |

160 { | |

161 a += k[0]; | |

162 b += k[1]; | |

163 c += k[2]; | |

164 mix(a,b,c); | |

165 length -= 12; | |

166 k += 3; | |

167 } | |

168 | |

169 /*----------------------------- handle the last (probably partial) block */ | |

170 /* | |

171 * "k[2]&0xffffff" actually reads beyond the end of the string, but | |

172 * then masks off the part it's not allowed to read. Because the | |

173 * string is aligned, the masked-off tail is in the same word as the | |

174 * rest of the string. Every machine with memory protection I've seen | |

175 * does it on word boundaries, so is OK with this. But VALGRIND will | |

176 * still catch it and complain. The masking trick does make the hash | |

177 * noticably faster for short strings (like English words). | |

178 */ | |

179 #ifndef VALGRIND | |

180 | |

181 switch(length) | |

182 { | |

183 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |

184 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; | |

185 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; | |

186 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; | |

187 case 8 : b+=k[1]; a+=k[0]; break; | |

188 case 7 : b+=k[1]&0xffffff; a+=k[0]; break; | |

189 case 6 : b+=k[1]&0xffff; a+=k[0]; break; | |

190 case 5 : b+=k[1]&0xff; a+=k[0]; break; | |

191 case 4 : a+=k[0]; break; | |

192 case 3 : a+=k[0]&0xffffff; break; | |

193 case 2 : a+=k[0]&0xffff; break; | |

194 case 1 : a+=k[0]&0xff; break; | |

195 case 0 : return c; /* zero length strings require no mixing */ | |

196 } | |

197 | |

198 #else /* make valgrind happy */ | |

199 | |

200 k8 = (const uint8_t *)k; | |

201 switch(length) | |

202 { | |

203 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |

204 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ | |

205 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ | |

206 case 9 : c+=k8[8]; /* fall through */ | |

207 case 8 : b+=k[1]; a+=k[0]; break; | |

208 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ | |

209 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ | |

210 case 5 : b+=k8[4]; /* fall through */ | |

211 case 4 : a+=k[0]; break; | |

212 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ | |

213 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ | |

214 case 1 : a+=k8[0]; break; | |

215 case 0 : return c; /* zero length strings require no mixing */ | |

216 } | |

217 | |

218 #endif /* !valgrind */ | |

219 | |

220 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { | |

221 const uint16_t *k = key; /* read 16-bit chunks */ | |

222 const uint8_t *k8; | |

223 | |

224 /*--------------- all but last block: aligned reads and different mixing */ | |

225 while (length > 12) | |

226 { | |

227 a += k[0] + (((uint32_t)k[1])<<16); | |

228 b += k[2] + (((uint32_t)k[3])<<16); | |

229 c += k[4] + (((uint32_t)k[5])<<16); | |

230 mix(a,b,c); | |

231 length -= 12; | |

232 k += 6; | |

233 } | |

234 | |

235 /*----------------------------- handle the last (probably partial) block */ | |

236 k8 = (const uint8_t *)k; | |

237 switch(length) | |

238 { | |

239 case 12: c+=k[4]+(((uint32_t)k[5])<<16); | |

240 b+=k[2]+(((uint32_t)k[3])<<16); | |

241 a+=k[0]+(((uint32_t)k[1])<<16); | |

242 break; | |

243 case 11: c+=((uint32_t)k8[10])<<16; /* @fallthrough */ | |

244 case 10: c+=k[4]; /* @fallthrough@ */ | |

245 b+=k[2]+(((uint32_t)k[3])<<16); | |

246 a+=k[0]+(((uint32_t)k[1])<<16); | |

247 break; | |

248 case 9 : c+=k8[8]; /* @fallthrough */ | |

249 case 8 : b+=k[2]+(((uint32_t)k[3])<<16); | |

250 a+=k[0]+(((uint32_t)k[1])<<16); | |

251 break; | |

252 case 7 : b+=((uint32_t)k8[6])<<16; /* @fallthrough */ | |

253 case 6 : b+=k[2]; | |

254 a+=k[0]+(((uint32_t)k[1])<<16); | |

255 break; | |

256 case 5 : b+=k8[4]; /* @fallthrough */ | |

257 case 4 : a+=k[0]+(((uint32_t)k[1])<<16); | |

258 break; | |

259 case 3 : a+=((uint32_t)k8[2])<<16; /* @fallthrough */ | |

260 case 2 : a+=k[0]; | |

261 break; | |

262 case 1 : a+=k8[0]; | |

263 break; | |

264 case 0 : return c; /* zero length strings require no mixing */ | |

265 } | |

266 | |

267 } else { /* need to read the key one byte at a time */ | |

268 const uint8_t *k = key; | |

269 | |

270 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ | |

271 while (length > 12) | |

272 { | |

273 a += k[0]; | |

274 a += ((uint32_t)k[1])<<8; | |

275 a += ((uint32_t)k[2])<<16; | |

276 a += ((uint32_t)k[3])<<24; | |

277 b += k[4]; | |

278 b += ((uint32_t)k[5])<<8; | |

279 b += ((uint32_t)k[6])<<16; | |

280 b += ((uint32_t)k[7])<<24; | |

281 c += k[8]; | |

282 c += ((uint32_t)k[9])<<8; | |

283 c += ((uint32_t)k[10])<<16; | |

284 c += ((uint32_t)k[11])<<24; | |

285 mix(a,b,c); | |

286 length -= 12; | |

287 k += 12; | |

288 } | |

289 | |

290 /*-------------------------------- last block: affect all 32 bits of (c) */ | |

291 switch(length) /* all the case statements fall through */ | |

292 { | |

293 case 12: c+=((uint32_t)k[11])<<24; | |

294 case 11: c+=((uint32_t)k[10])<<16; | |

295 case 10: c+=((uint32_t)k[9])<<8; | |

296 case 9 : c+=k[8]; | |

297 case 8 : b+=((uint32_t)k[7])<<24; | |

298 case 7 : b+=((uint32_t)k[6])<<16; | |

299 case 6 : b+=((uint32_t)k[5])<<8; | |

300 case 5 : b+=k[4]; | |

301 case 4 : a+=((uint32_t)k[3])<<24; | |

302 case 3 : a+=((uint32_t)k[2])<<16; | |

303 case 2 : a+=((uint32_t)k[1])<<8; | |

304 case 1 : a+=k[0]; | |

305 break; | |

306 case 0 : return c; /* zero length strings require no mixing */ | |

307 } | |

308 } | |

309 | |

310 final(a,b,c); | |

311 return c; /* zero length strings require no mixing */ | |

312 } | |

313 | |

314 #elif HASH_BIG_ENDIAN == 1 | |

315 /* | |

316 * hashbig(): | |

317 * This is the same as hashword() on big-endian machines. It is different | |

318 * from hashlittle() on all machines. hashbig() takes advantage of | |

319 * big-endian byte ordering. | |

320 */ | |

321 uint32_t hash( const void *key, size_t length, const uint32_t initval) | |

322 { | |

323 uint32_t a,b,c; | |

324 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ | |

325 | |

326 /* Set up the internal state */ | |

327 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; | |

328 | |

329 u.ptr = key; | |

330 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { | |

331 const uint32_t *k = key; /* read 32-bit chunks */ | |

332 #ifdef VALGRIND | |

333 const uint8_t *k8; | |

334 #endif // ifdef VALGRIND | |

335 | |

336 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ | |

337 while (length > 12) | |

338 { | |

339 a += k[0]; | |

340 b += k[1]; | |

341 c += k[2]; | |

342 mix(a,b,c); | |

343 length -= 12; | |

344 k += 3; | |

345 } | |

346 | |

347 /*----------------------------- handle the last (probably partial) block */ | |

348 /* | |

349 * "k[2]<<8" actually reads beyond the end of the string, but | |

350 * then shifts out the part it's not allowed to read. Because the | |

351 * string is aligned, the illegal read is in the same word as the | |

352 * rest of the string. Every machine with memory protection I've seen | |

353 * does it on word boundaries, so is OK with this. But VALGRIND will | |

354 * still catch it and complain. The masking trick does make the hash | |

355 * noticably faster for short strings (like English words). | |

356 */ | |

357 #ifndef VALGRIND | |

358 | |

359 switch(length) | |

360 { | |

361 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |

362 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; | |

363 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; | |

364 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; | |

365 case 8 : b+=k[1]; a+=k[0]; break; | |

366 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; | |

367 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; | |

368 case 5 : b+=k[1]&0xff000000; a+=k[0]; break; | |

369 case 4 : a+=k[0]; break; | |

370 case 3 : a+=k[0]&0xffffff00; break; | |

371 case 2 : a+=k[0]&0xffff0000; break; | |

372 case 1 : a+=k[0]&0xff000000; break; | |

373 case 0 : return c; /* zero length strings require no mixing */ | |

374 } | |

375 | |

376 #else /* make valgrind happy */ | |

377 | |

378 k8 = (const uint8_t *)k; | |

379 switch(length) /* all the case statements fall through */ | |

380 { | |

381 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; | |

382 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ | |

383 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ | |

384 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ | |

385 case 8 : b+=k[1]; a+=k[0]; break; | |

386 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ | |

387 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ | |

388 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ | |

389 case 4 : a+=k[0]; break; | |

390 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ | |

391 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ | |

392 case 1 : a+=((uint32_t)k8[0])<<24; break; | |

393 case 0 : return c; | |

394 } | |

395 | |

396 #endif /* !VALGRIND */ | |

397 | |

398 } else { /* need to read the key one byte at a time */ | |

399 const uint8_t *k = key; | |

400 | |

401 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ | |

402 while (length > 12) | |

403 { | |

404 a += ((uint32_t)k[0])<<24; | |

405 a += ((uint32_t)k[1])<<16; | |

406 a += ((uint32_t)k[2])<<8; | |

407 a += ((uint32_t)k[3]); | |

408 b += ((uint32_t)k[4])<<24; | |

409 b += ((uint32_t)k[5])<<16; | |

410 b += ((uint32_t)k[6])<<8; | |

411 b += ((uint32_t)k[7]); | |

412 c += ((uint32_t)k[8])<<24; | |

413 c += ((uint32_t)k[9])<<16; | |

414 c += ((uint32_t)k[10])<<8; | |

415 c += ((uint32_t)k[11]); | |

416 mix(a,b,c); | |

417 length -= 12; | |

418 k += 12; | |

419 } | |

420 | |

421 /*-------------------------------- last block: affect all 32 bits of (c) */ | |

422 switch(length) /* all the case statements fall through */ | |

423 { | |

424 case 12: c+=k[11]; | |

425 case 11: c+=((uint32_t)k[10])<<8; | |

426 case 10: c+=((uint32_t)k[9])<<16; | |

427 case 9 : c+=((uint32_t)k[8])<<24; | |

428 case 8 : b+=k[7]; | |

429 case 7 : b+=((uint32_t)k[6])<<8; | |

430 case 6 : b+=((uint32_t)k[5])<<16; | |

431 case 5 : b+=((uint32_t)k[4])<<24; | |

432 case 4 : a+=k[3]; | |

433 case 3 : a+=((uint32_t)k[2])<<8; | |

434 case 2 : a+=((uint32_t)k[1])<<16; | |

435 case 1 : a+=((uint32_t)k[0])<<24; | |

436 break; | |

437 case 0 : return c; | |

438 } | |

439 } | |

440 | |

441 final(a,b,c); | |

442 return c; | |

443 } | |

444 #else // HASH_XXX_ENDIAN == 1 | |

445 #error Must define HASH_BIG_ENDIAN or HASH_LITTLE_ENDIAN | |

446 #endif // hash_XXX_ENDIAN == 1 | |

447 | |

448 typedef unsigned long int ub4; /* unsigned 4-byte quantities */ | |

449 typedef unsigned char ub1; /* unsigned 1-byte quantities */ | |

450 | |

451 /* how many powers of 2's worth of buckets we use */ | |

452 static int hashpower = 16; | |

453 | |

454 #define hashsize(n) ((ub4)1<<(n)) | |

455 #define hashmask(n) (hashsize(n)-1) | |

456 | |

457 /* Main hash table. This is where we look except during expansion. */ | |

458 static item** primary_hashtable = 0; | |

459 | |

460 /* | |

461 * Previous hash table. During expansion, we look here for keys that haven't | |

462 * been moved over to the primary yet. | |

463 */ | |

464 static item** old_hashtable = 0; | |

465 | |

466 /* Number of items in the hash table. */ | |

467 static int hash_items = 0; | |

468 | |

469 /* Flag: Are we in the middle of expanding now? */ | |

470 static int expanding = 0; | |

471 | |

472 /* | |

473 * During expansion we migrate values with bucket granularity; this is how | |

474 * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1. | |

475 */ | |

476 static int expand_bucket = 0; | |

477 | |

478 void assoc_init(void) { | |

479 unsigned int hash_size = hashsize(hashpower) * sizeof(void*); | |

480 primary_hashtable = malloc(hash_size); | |

481 if (! primary_hashtable) { | |

482 fprintf(stderr, "Failed to init hashtable.\n"); | |

483 exit(EXIT_FAILURE); | |

484 } | |

485 memset(primary_hashtable, 0, hash_size); | |

486 } | |

487 | |

488 item *assoc_find(const char *key, const size_t nkey) { | |

489 uint32_t hv = hash(key, nkey, 0); | |

490 item *it; | |

491 int oldbucket; | |

492 | |

493 if (expanding && | |

494 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) | |

495 { | |

496 it = old_hashtable[oldbucket]; | |

497 } else { | |

498 it = primary_hashtable[hv & hashmask(hashpower)]; | |

499 } | |

500 | |

501 while (it) { | |

502 if ((nkey == it->nkey) && | |

503 (memcmp(key, ITEM_key(it), nkey) == 0)) { | |

504 return it; | |

505 } | |

506 it = it->h_next; | |

507 } | |

508 return 0; | |

509 } | |

510 | |

511 /* returns the address of the item pointer before the key. if *item == 0, | |

512 the item wasn't found */ | |

513 | |

514 static item** _hashitem_before (const char *key, const size_t nkey) { | |

515 uint32_t hv = hash(key, nkey, 0); | |

516 item **pos; | |

517 int oldbucket; | |

518 | |

519 if (expanding && | |

520 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) | |

521 { | |

522 pos = &old_hashtable[oldbucket]; | |

523 } else { | |

524 pos = &primary_hashtable[hv & hashmask(hashpower)]; | |

525 } | |

526 | |

527 while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) { | |

528 pos = &(*pos)->h_next; | |

529 } | |

530 return pos; | |

531 } | |

532 | |

533 /* grows the hashtable to the next power of 2. */ | |

534 static void assoc_expand(void) { | |

535 old_hashtable = primary_hashtable; | |

536 | |

537 primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *)); | |

538 if (primary_hashtable) { | |

539 if (settings.verbose > 1) | |

540 fprintf(stderr, "Hash table expansion starting\n"); | |

541 hashpower++; | |

542 expanding = 1; | |

543 expand_bucket = 0; | |

544 do_assoc_move_next_bucket(); | |

545 } else { | |

546 primary_hashtable = old_hashtable; | |

547 /* Bad news, but we can keep running. */ | |

548 } | |

549 } | |

550 | |

551 /* migrates the next bucket to the primary hashtable if we're expanding. */ | |

552 void do_assoc_move_next_bucket(void) { | |

553 item *it, *next; | |

554 int bucket; | |

555 | |

556 if (expanding) { | |

557 for (it = old_hashtable[expand_bucket]; NULL != it; it = next) { | |

558 next = it->h_next; | |

559 | |

560 bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower); | |

561 it->h_next = primary_hashtable[bucket]; | |

562 primary_hashtable[bucket] = it; | |

563 } | |

564 | |

565 old_hashtable[expand_bucket] = NULL; | |

566 | |

567 expand_bucket++; | |

568 if (expand_bucket == hashsize(hashpower - 1)) { | |

569 expanding = 0; | |

570 free(old_hashtable); | |

571 if (settings.verbose > 1) | |

572 fprintf(stderr, "Hash table expansion done\n"); | |

573 } | |

574 } | |

575 } | |

576 | |

577 /* Note: this isn't an assoc_update. The key must not already exist to call this */ | |

578 int assoc_insert(item *it) { | |

579 uint32_t hv; | |

580 int oldbucket; | |

581 | |

582 assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */ | |

583 | |

584 hv = hash(ITEM_key(it), it->nkey, 0); | |

585 if (expanding && | |

586 (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) | |

587 { | |

588 it->h_next = old_hashtable[oldbucket]; | |

589 old_hashtable[oldbucket] = it; | |

590 } else { | |

591 it->h_next = primary_hashtable[hv & hashmask(hashpower)]; | |

592 primary_hashtable[hv & hashmask(hashpower)] = it; | |

593 } | |

594 | |

595 hash_items++; | |

596 if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) { | |

597 assoc_expand(); | |

598 } | |

599 | |

600 return 1; | |

601 } | |

602 | |

603 void assoc_delete(const char *key, const size_t nkey) { | |

604 item **before = _hashitem_before(key, nkey); | |

605 | |

606 if (*before) { | |

607 item *nxt = (*before)->h_next; | |

608 (*before)->h_next = 0; /* probably pointless, but whatever. */ | |

609 *before = nxt; | |

610 hash_items--; | |

611 return; | |

612 } | |

613 /* Note: we never actually get here. the callers don't delete things | |

614 they can't find. */ | |

615 assert(*before != 0); | |

616 } |