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