Commit | Line | Data |
---|---|---|
36923392 WD |
1 | /* |
2 | * Routines to provide a memory-efficient hashtable. | |
3 | * | |
4 | * Copyright (C) 2007 Wayne Davison | |
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 | { | |
26 | struct hashtable *tbl; | |
27 | int node_size = key64 ? sizeof (struct ht_int64_node ) | |
28 | : sizeof (struct ht_int32_node); | |
29 | ||
30 | /* Pick a power of 2 that can hold the requested size. */ | |
31 | if (size & (size-1) || size < 16) { | |
32 | int req = size; | |
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; | |
44 | ||
45 | return tbl; | |
46 | } | |
47 | ||
48 | void hashtable_destroy(struct hashtable *tbl) | |
49 | { | |
50 | free(tbl->nodes); | |
51 | free(tbl); | |
52 | } | |
53 | ||
54 | /* This returns the node for the indicated key, either newly created or | |
55 | * already existing. Returns NULL if not allocating and not found. */ | |
56 | void *hashtable_find(struct hashtable *tbl, int64 key, int allocate_if_missing) | |
57 | { | |
58 | int key64 = (tbl->node_size > sizeof (struct ht_int32_node)); | |
59 | struct ht_int32_node *node; | |
60 | uint32 ndx; | |
61 | ||
62 | if (allocate_if_missing && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) { | |
63 | void *old_nodes = tbl->nodes; | |
64 | int size = tbl->size * 2; | |
65 | int i; | |
66 | ||
67 | if (!(tbl->nodes = new_array0(char, size * tbl->node_size))) | |
68 | out_of_memory("hashtable_node"); | |
69 | tbl->size = size; | |
70 | tbl->entries = 0; | |
71 | ||
72 | for (i = size / 2; i-- > 0; ) { | |
73 | struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i); | |
74 | int64 move_key = HT_KEY(move_node, key64); | |
75 | if (move_key == 0) | |
76 | continue; | |
77 | node = hashtable_find(tbl, move_key, 1); | |
78 | node->data = move_node->data; | |
79 | } | |
80 | ||
81 | free(old_nodes); | |
82 | } | |
83 | ||
84 | if (!key64) { | |
85 | /* Based on Jenkins One-at-a-time hash. */ | |
86 | uchar buf[4], *keyp = buf; | |
87 | int i; | |
88 | ||
89 | SIVAL(buf, 0, key); | |
90 | for (ndx = 0, i = 0; i < 4; i++) { | |
91 | ndx += keyp[i]; | |
92 | ndx += (ndx << 10); | |
93 | ndx ^= (ndx >> 6); | |
94 | } | |
95 | ndx += (ndx << 3); | |
96 | ndx ^= (ndx >> 11); | |
97 | ndx += (ndx << 15); | |
98 | } else { | |
99 | /* Based on Jenkins hashword() from lookup3.c. */ | |
100 | uint32 a, b, c; | |
101 | ||
102 | /* Set up the internal state */ | |
103 | a = b = c = 0xdeadbeef + (8 << 2); | |
104 | ||
105 | #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k)))) | |
106 | b += (uint32)(key >> 32); | |
107 | a += (uint32)key; | |
108 | c ^= b; c -= rot(b, 14); | |
109 | a ^= c; a -= rot(c, 11); | |
110 | b ^= a; b -= rot(a, 25); | |
111 | c ^= b; c -= rot(b, 16); | |
112 | a ^= c; a -= rot(c, 4); | |
113 | b ^= a; b -= rot(a, 14); | |
114 | c ^= b; c -= rot(b, 24); | |
115 | #undef rot | |
116 | ndx = c; | |
117 | } | |
118 | ||
119 | /* If it already exists, return the node. If we're not | |
120 | * allocating, return NULL if the key is not found. */ | |
121 | while (1) { | |
122 | int64 nkey; | |
123 | ||
124 | ndx &= tbl->size - 1; | |
125 | node = HT_NODE(tbl, tbl->nodes, ndx); | |
126 | nkey = HT_KEY(node, key64); | |
127 | ||
128 | if (nkey == key) | |
129 | return node; | |
130 | if (nkey == 0) { | |
131 | if (!allocate_if_missing) | |
132 | return NULL; | |
133 | break; | |
134 | } | |
135 | ndx++; | |
136 | } | |
137 | ||
138 | /* Take over this empty spot and then return the node. */ | |
139 | if (key64) | |
140 | ((struct ht_int64_node*)node)->key = key; | |
141 | else | |
142 | node->key = key; | |
143 | tbl->entries++; | |
144 | return node; | |
145 | } |