/
Hash.cpp
119 lines (103 loc) · 2.74 KB
/
Hash.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//
// Thread-safe hash template class
//
// Copyright (c) 2004, Algin Technology LLC
// Written by Alan Klietz
// Distributed under GNU General Public License version 2.
//
// Mostly implemented in hash.h
//
// $Id: Hash.cpp,v 1.1 2004/02/02 07:16:23 alank Exp $
//
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <crtdbg.h>
#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <tchar.h>
#include <wchar.h>
#include "more.h"
#define NEED_CSTR_H
#define NEED_HASH_H
#include "windows-support.h"
#ifdef _DEBUG // test
#ifdef __AFX_H__
#define CHASH CHash<CHData<int>, CHData<CString> >
IMPLEMENT_SERIALx(Hash1, CHASH, CObject, 1)
#undef CHASH
#endif
void TestHash()
{
CHash<CHData<int>, CHData<CString> > MyHash;
int i;
MyHash.SetAt(3, _T("test"));
int iKey; CString strVal;
if (MyHash.Lookup(iKey, strVal)) { }
MyHash.RemoveKey(3);
MyHash[5] = _T("boo");
i = MyHash.GetCount();
if (MyHash.IsEmpty()) { }
POSITION pos = MyHash.GetStartPosition();
while (pos != NULL) {
MyHash.GetNextAssoc(pos, iKey, strVal);
//use(key, value)
}
}
#endif // _DEBUG
//
// Table of primes suitable as keys, in ascending order.
// The first line is the largest primes less than some powers of two,
// the second line is the largest prime less than 6000,
// the third line is a selection from Knuth, Vol. 3, Sec. 6.1, Table 1,
// and the next two lines were suggested by Steve Kirsch.
//
static const LONG HashPrimes[] = {
7, 13, 31, 61, 127, 251, 509, 1021, 2017, 4093,
5987,
9551, 15683, 19609, 31397,
65521L, 131071L, 262139L, 524287L, 1048573L, 2097143L, 4194301L,
//8388593L, 16777213L, 33554393L, 67108859L,
//134217689L, 268435399L, 536870909L, 1073741789L,
0
};
//
// We must come up with (i,incr) such that 0 <= 1 < cSize
// and 0 < incr < cSize and both are a function of lHashVal.
// The incr is guaranteed to be relatively prime so all
// locations in the hash table will eventually be tested.
//
EXPORT ULONG CalcHashIncr(LONG lHashVal, register int cSize)
{
register ULONG uSum, uIncr;
ASSERT(lHashVal != 0 && lHashVal != -1);
uSum = (ULONG)lHashVal;
do {
uSum = 3*uSum + 1; // somewhat arbitrary
uIncr = uSum % (ULONG)cSize;
} while (uIncr == 0);
return uIncr;
}
EXPORT LONG NewPrimeSize(int cSize)
{
register int i;
ASSERT(cSize > 0);
for (i=0; ; ++i) {
if (HashPrimes[i] == 0) {
DLL_ENTRY;
#ifdef UNDEFINED
ThrowTSException(AEMSG,
AE_FATAL_ERROR, AE_CATEGORY_FATAL,
_T("Hash table too large: %lu entries"), (ULONG)cSize);
#else
fputs("Hash table too large.\n", stderr);
exit(1);
#endif
}
if (HashPrimes[i] > (LONG)cSize)
return HashPrimes[i];
}
}
/*
vim:tabstop=4:shiftwidth=4:noexpandtab
*/