![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hashtable.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync|
Return to hashtable.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync |
1.1 misho 1: /*
2: * Routines to provide a memory-efficient hashtable.
3: *
1.1.1.3 ! misho 4: * Copyright (C) 2007-2015 Wayne Davison
1.1 misho 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: {
1.1.1.2 misho 26: int req = size;
1.1 misho 27: struct hashtable *tbl;
28: int node_size = key64 ? sizeof (struct ht_int64_node)
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) {
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: tbl->key64 = key64 ? 1 : 0;
45:
1.1.1.2 misho 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:
1.1 misho 56: return tbl;
57: }
58:
59: void hashtable_destroy(struct hashtable *tbl)
60: {
1.1.1.2 misho 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: }
1.1 misho 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: {
73: int key64 = tbl->key64;
74: struct ht_int32_node *node;
75: uint32 ndx;
76:
77: if (key64 ? key == 0 : (int32)key == 0) {
78: rprintf(FERROR, "Internal hashtable error: illegal key supplied!\n");
79: exit_cleanup(RERR_MESSAGEIO);
80: }
81:
82: if (allocate_if_missing && tbl->entries > HASH_LOAD_LIMIT(tbl->size)) {
83: void *old_nodes = tbl->nodes;
84: int size = tbl->size * 2;
85: int i;
86:
87: if (!(tbl->nodes = new_array0(char, size * tbl->node_size)))
88: out_of_memory("hashtable_node");
89: tbl->size = size;
90: tbl->entries = 0;
91:
1.1.1.2 misho 92: if (DEBUG_GTE(HASH, 1)) {
93: rprintf(FINFO, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n",
94: who_am_i(), (long)tbl, size, key64 ? 64 : 32);
95: }
96:
1.1 misho 97: for (i = size / 2; i-- > 0; ) {
98: struct ht_int32_node *move_node = HT_NODE(tbl, old_nodes, i);
99: int64 move_key = HT_KEY(move_node, key64);
100: if (move_key == 0)
101: continue;
102: node = hashtable_find(tbl, move_key, 1);
103: node->data = move_node->data;
104: }
105:
106: free(old_nodes);
107: }
108:
109: if (!key64) {
110: /* Based on Jenkins One-at-a-time hash. */
111: uchar buf[4], *keyp = buf;
112: int i;
113:
114: SIVALu(buf, 0, key);
115: for (ndx = 0, i = 0; i < 4; i++) {
116: ndx += keyp[i];
117: ndx += (ndx << 10);
118: ndx ^= (ndx >> 6);
119: }
120: ndx += (ndx << 3);
121: ndx ^= (ndx >> 11);
122: ndx += (ndx << 15);
123: } else {
124: /* Based on Jenkins hashword() from lookup3.c. */
125: uint32 a, b, c;
126:
127: /* Set up the internal state */
128: a = b = c = 0xdeadbeef + (8 << 2);
129:
130: #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
131: #if SIZEOF_INT64 >= 8
132: b += (uint32)(key >> 32);
133: #endif
134: a += (uint32)key;
135: c ^= b; c -= rot(b, 14);
136: a ^= c; a -= rot(c, 11);
137: b ^= a; b -= rot(a, 25);
138: c ^= b; c -= rot(b, 16);
139: a ^= c; a -= rot(c, 4);
140: b ^= a; b -= rot(a, 14);
141: c ^= b; c -= rot(b, 24);
142: #undef rot
143: ndx = c;
144: }
145:
146: /* If it already exists, return the node. If we're not
147: * allocating, return NULL if the key is not found. */
148: while (1) {
149: int64 nkey;
150:
151: ndx &= tbl->size - 1;
152: node = HT_NODE(tbl, tbl->nodes, ndx);
153: nkey = HT_KEY(node, key64);
154:
155: if (nkey == key)
156: return node;
157: if (nkey == 0) {
158: if (!allocate_if_missing)
159: return NULL;
160: break;
161: }
162: ndx++;
163: }
164:
165: /* Take over this empty spot and then return the node. */
166: if (key64)
167: ((struct ht_int64_node*)node)->key = key;
168: else
169: node->key = (int32)key;
170: tbl->entries++;
171: return node;
172: }