1 /* $Id$ */
2
3 /*
4 *
5 * Copyright (C) 1998 David Mazieres (dm@uun.org)
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; either version 2, or (at
10 * your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
20 * USA
21 *
22 */
23
24 #include "amisc.h"
25 #include "ihash.h"
26 #include "msb.h"
27
28 /* Some prime numbers <= powers of 2 */
29 const u_int exp2primes[33] = {
30 0x1, /* place holder */
31 0x2, 0x3, 0x7, 0xd,
32 0x1f, 0x3d, 0x7f, 0xfb,
33 0x1fd, 0x3fd, 0x7f7, 0xffd,
34 0x1fff, 0x3ffd, 0x7fed, 0xfff1,
35 0x1ffff, 0x3fffb, 0x7ffff, 0xffffd,
36 0x1ffff7, 0x3ffffd, 0x7ffff1, 0xfffffd,
37 0x1ffffd9, 0x3fffffb, 0x7ffffd9, 0xfffffc7,
38 0x1ffffffd, 0x3fffffdd, 0x7fffffff, 0xfffffffb,
39 };
40
41 #define hteof(p) ((_ihash_entry *) ((char *) (p) + eos))
42
43 void
_ihash_grow(_ihash_table * htp,const size_t eos)44 _ihash_grow (_ihash_table *htp, const size_t eos)
45 {
46 u_int nbuckets;
47 void **ntab;
48 void *p, *np;
49 size_t i;
50
51 nbuckets = exp2primes[log2c(htp->buckets)+1];
52 if (nbuckets < 3)
53 nbuckets = 3;
54
55 ntab = New void *[nbuckets];
56 bzero (ntab, nbuckets * sizeof (*ntab));
57
58 for (i = 0; i < htp->buckets; i++)
59 for (p = htp->tab[i]; p; p = np) {
60 _ihash_entry *htep = hteof (p);
61 size_t ni = htep->val % nbuckets;
62 np = htep->next;
63
64 htep->next = ntab[ni];
65 htep->pprev = &ntab[ni];
66 if (ntab[ni])
67 hteof(ntab[ni])->pprev = &htep->next;
68 ntab[ni] = p;
69 }
70
71 delete[] htp->tab;
72 htp->tab = ntab;
73 htp->buckets = nbuckets;
74 }
75