Commit | Line | Data |
---|---|---|
36923392 WD |
1 | /* |
2 | * Routines to provide a memory-efficient hashtable. | |
3 | * | |
d3d07a5e | 4 | * Copyright (C) 2007-2008 Wayne Davison |
36923392 WD |
5 | * |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 3 of the License, or | |
9 | * (at your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License along | |
17 | * with this program; if not, visit the http://fsf.org website. | |
18 | */ | |
19 | ||
20 | #include "rsync.h" | |
21 | ||
22 | #define HASH_LOAD_LIMIT(size) ((size)*3/4) | |
23 | ||
24 | struct hashtable *hashtable_create(int size, int key64) | |
25 | { | |
b3347e2a | 26 | int req = size; |
36923392 | 27 | struct hashtable *tbl; |
d6e6333a | 28 | int node_size = key64 ? sizeof (struct ht_int64_node) |
36923392 WD |
29 | : sizeof (struct ht_int32_node); |
30 | ||
31 | /* Pick a power of 2 that can hold the requested size. */ | |
32 | if (size & (size-1) || size < 16) { | |
36923392 WD |
33 | size = 16; |
34 | while (size < req) | |
35 | size *= 2; | |
36 | } | |
37 | ||
38 | if (!(tbl = new(struct hashtable)) | |
39 | || !(tbl->nodes = new_array0(char, size * node_size))) | |
40 | out_of_memory("hashtable_create"); | |
41 | tbl->size = size; | |
42 | tbl->entries = 0; | |
43 | tbl->node_size = node_size; | |
0c096e29 | 44 | tbl->key64 = (short)key64; |
36923392 | 45 | |
b3347e2a WD |
46 | if (DEBUG_GTE(HASH, 1)) { |
47 | char buf[32]; | |
48 | if (req != size) | |
49 | snprintf(buf, sizeof buf, "req: %d, ", req); | |
50 | else | |
51 | *buf = '\0'; | |
52 | rprintf(FINFO, "[%s] created hashtable %lx (%ssize: %d, keys: %d-bit)\n", | |
53 | who_am_i(), (long)tbl, buf, size, key64 ? 64 : 32); | |
54 | } | |
55 | ||
36923392 WD |
56 | return tbl; |
57 | } | |
58 | ||
59 | void hashtable_destroy(struct hashtable *tbl) | |
60 | { | |
b3347e2a WD |
61 | if (DEBUG_GTE(HASH, 1)) { |
62 | rprintf(FINFO, "[%s] destroyed hashtable %lx (size: %d, keys: %d-bit)\n", | |
63 | who_am_i(), (long)tbl, tbl->size, tbl->key64 ? 64 : 32); | |
64 | } | |
36923392 WD |
65 | free(tbl->nodes); |
66 | free(tbl); | |
67 | } | |
68 | ||
69 | /* This returns the node for the indicated key, either newly created or | |
70 | * already existing. Returns NULL if not allocating and not found. */ | |
71 | void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing) | |
72 | { | |
d6e6333a | 73 | int key64 = tbl->key64; |
36923392 WD |
74 | struct ht_int32_node *node; |
75 | uint32 ndx; | |
76 | ||
77 | if (allocate_if_missing && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) { | |
78 | void *old_nodes = tbl->nodes; | |
79 | int size = tbl->size * 2; | |
80 | int i; | |
81 | ||
82 | if (!(tbl->nodes = new_array0(char, size * tbl->node_size))) | |
83 | out_of_memory("hashtable_node"); | |
84 | tbl->size = size; | |
85 | tbl->entries = 0; | |
86 | ||
b3347e2a WD |
87 | if (DEBUG_GTE(HASH, 1)) { |
88 | rprintf(FINFO, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n", | |
89 | who_am_i(), (long)tbl, size, key64 ? 64 : 32); | |
90 | } | |
91 | ||
36923392 WD |
92 | for (i = size / 2; i-- > 0; ) { |
93 | struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i); | |
94 | int64 move_key = HT_KEY(move_node, key64); | |
95 | if (move_key == 0) | |
96 | continue; | |
97 | node = hashtable_find(tbl, move_key, 1); | |
98 | node->data = move_node->data; | |
99 | } | |
100 | ||
101 | free(old_nodes); | |
102 | } | |
103 | ||
104 | if (!key64) { | |
105 | /* Based on Jenkins One-at-a-time hash. */ | |
106 | uchar buf[4], *keyp = buf; | |
107 | int i; | |
108 | ||
109 | SIVAL(buf, 0, key); | |
110 | for (ndx = 0, i = 0; i < 4; i++) { | |
111 | ndx += keyp[i]; | |
112 | ndx += (ndx << 10); | |
113 | ndx ^= (ndx >> 6); | |
114 | } | |
115 | ndx += (ndx << 3); | |
116 | ndx ^= (ndx >> 11); | |
117 | ndx += (ndx << 15); | |
118 | } else { | |
119 | /* Based on Jenkins hashword() from lookup3.c. */ | |
120 | uint32 a, b, c; | |
121 | ||
122 | /* Set up the internal state */ | |
123 | a = b = c = 0xdeadbeef + (8 << 2); | |
124 | ||
125 | #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k)))) | |
4ecf3e06 | 126 | #if SIZEOF_INT64 >= 8 |
36923392 | 127 | b += (uint32)(key >> 32); |
4ecf3e06 | 128 | #endif |
36923392 WD |
129 | a += (uint32)key; |
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 | #undef rot | |
138 | ndx = c; | |
139 | } | |
140 | ||
141 | /* If it already exists, return the node. If we're not | |
142 | * allocating, return NULL if the key is not found. */ | |
143 | while (1) { | |
144 | int64 nkey; | |
145 | ||
146 | ndx &= tbl->size - 1; | |
147 | node = HT_NODE(tbl, tbl->nodes, ndx); | |
148 | nkey = HT_KEY(node, key64); | |
149 | ||
150 | if (nkey == key) | |
151 | return node; | |
152 | if (nkey == 0) { | |
153 | if (!allocate_if_missing) | |
154 | return NULL; | |
155 | break; | |
156 | } | |
157 | ndx++; | |
158 | } | |
159 | ||
160 | /* Take over this empty spot and then return the node. */ | |
161 | if (key64) | |
162 | ((struct ht_int64_node*)node)->key = key; | |
163 | else | |
aad635f7 | 164 | node->key = (int32)key; |
36923392 WD |
165 | tbl->entries++; |
166 | return node; | |
167 | } |