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
120
121
122
123
124
125
126
127
|
/* ScummVM - Scumm Interpreter
* Copyright (C) 2006 The ScummVM project
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* $URL$
* $Id$
*
*/
// Code is based on:
/*
* Copyright (c) 1998-2003 Massachusetts Institute of Technology.
* This code was developed as part of the Haystack research project
* (http://haystack.lcs.mit.edu/). Permission is hereby granted,
* free of charge, to any person obtaining a copy of this software
* and associated documentation files (the "Software"), to deal in
* the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute,
* sublicense, and/or sell copies of the Software, and to permit
* persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
/*************************************************
assocarray.h - Associative arrays
Andrew Y. Ng, 1996
**************************************************/
#include "common/assocarray.h"
namespace Common {
// int:
uint hashit(int x, uint hashsize) {
return x % hashsize;
}
bool data_eq(int x, int y) {
return x == y;
}
#if 0
// double:
uint hashit(double d, uint hashsize) {
TODO
}
#endif
bool data_eq(double d1, double d2) {
return (d1 == d2);
}
// const char *:
uint hashit(const char *str, uint hashsize) {
const byte *p = (const byte *)str;
uint hash;
char c;
// my31 algo
hash = 0;
while ((c = *p++))
hash = (hash * 31 + c);
return hash % hashsize;
}
bool data_eq(const char *str1, const char *str2) {
return !strcmp(str1, str2);
}
// String:
uint hashit(const Common::String &str, uint hashsize) {
return hashit(str.c_str(), hashsize);
}
bool data_eq(const Common::String &str1, const String &str2) {
return (str1 == str2);
}
// The following table is taken from the GNU ISO C++ Library's hashtable.h file.
static const uint primes[] = {
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
uint nextTableSize(uint x) {
int i = 0;
while (x >= primes[i])
i++;
return primes[i];
}
} // End of namespace Common
|
