1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 // The hash map (associative array) implementation in this file is
24 // based on the PyDict implementation of CPython. The erase() method
25 // is based on example code in the Wikipedia article on Hash tables.
26
27 #include "common/hashmap.h"
28
29 namespace Common {
30
31 // Hash function for strings, taken from CPython.
hashit(const char * p)32 uint hashit(const char *p) {
33 uint hash = *p << 7;
34 byte c;
35 int size = 0;
36 while ((c = *p++)) {
37 hash = (1000003 * hash) ^ c;
38 size++;
39 }
40 return hash ^ size;
41 }
42
43 // Like hashit, but converts every char to lowercase before hashing.
hashit_lower(const char * p)44 uint hashit_lower(const char *p) {
45 uint hash = tolower(*p) << 7;
46 byte c;
47 int size = 0;
48 while ((c = *p++)) {
49 hash = (1000003 * hash) ^ tolower(c);
50 size++;
51 }
52 return hash ^ size;
53 }
54
55
unknownKeyError(::Common::String key)56 template<> void unknownKeyError(::Common::String key) {
57 error("Unknown key \"%s\"", key.c_str());
58 }
59
unknownKeyError(signed char key)60 template<> void unknownKeyError(signed char key) {
61 error("Unknown key \"%hhi\"", key);
62 }
63
unknownKeyError(unsigned char key)64 template<> void unknownKeyError(unsigned char key) {
65 error("Unknown key \"%hhu\"", key);
66 }
67
unknownKeyError(short signed key)68 template<> void unknownKeyError(short signed key) {
69 error("Unknown key \"%hi\"", key);
70 }
71
unknownKeyError(short unsigned key)72 template<> void unknownKeyError(short unsigned key) {
73 error("Unknown key \"%hu\"", key);
74 }
75
unknownKeyError(long signed key)76 template<> void unknownKeyError(long signed key) {
77 error("Unknown key \"%li\"", key);
78 }
79
unknownKeyError(long unsigned key)80 template<> void unknownKeyError(long unsigned key) {
81 error("Unknown key \"%lu\"", key);
82 }
83
84 template<>
unknownKeyError(signed int key)85 void unknownKeyError(signed int key) {
86 error("Unknown key \"%i\"", key);
87 }
88
89 template<>
unknownKeyError(unsigned int key)90 void unknownKeyError(unsigned int key) {
91 error("Unknown key \"%u\"", key);
92 }
93
unknownKeyError(long long signed key)94 template<> void unknownKeyError(long long signed key) {
95 error("Unknown key \"%lli\"", key);
96 }
97
unknownKeyError(long long unsigned key)98 template<> void unknownKeyError(long long unsigned key) {
99 error("Unknown key \"%llu\"", key);
100 }
101
unknownKeyError(void * key)102 template<> void unknownKeyError(void *key) {
103 error("Unknown key \"%p\"", key);
104 }
105
unknownKeyError(const char * key)106 template<> void unknownKeyError(const char *key) {
107 error("Unknown key \"%s\"", key);
108 }
109
110 #ifdef DEBUG_HASH_COLLISIONS
111 static double
112 g_collisions = 0,
113 g_dummyHits = 0,
114 g_lookups = 0,
115 g_collPerLook = 0,
116 g_capacity = 0,
117 g_size = 0;
118 static int g_max_capacity = 0, g_max_size = 0;
119 static int g_totalHashmaps = 0;
120 static int g_stats[4] = {0,0,0,0};
121
updateHashCollisionStats(int collisions,int dummyHits,int lookups,int arrsize,int nele)122 void updateHashCollisionStats(int collisions, int dummyHits, int lookups, int arrsize, int nele) {
123 g_collisions += collisions;
124 g_lookups += lookups;
125 g_dummyHits += dummyHits;
126 if (lookups)
127 g_collPerLook += (double)collisions / (double)lookups;
128 g_capacity += arrsize;
129 g_size += nele;
130 g_totalHashmaps++;
131
132 if (3*nele <= 2*8)
133 g_stats[0]++;
134 if (3*nele <= 2*16)
135 g_stats[1]++;
136 if (3*nele <= 2*32)
137 g_stats[2]++;
138 if (3*nele <= 2*64)
139 g_stats[3]++;
140
141 g_max_capacity = MAX(g_max_capacity, arrsize);
142 g_max_size = MAX(g_max_size, nele);
143
144 debug("%d hashmaps: colls %.1f; dummies hit %.1f, lookups %.1f; ratio %.3f%%; size %f (max: %d); capacity %f (max: %d)",
145 g_totalHashmaps,
146 g_collisions / g_totalHashmaps,
147 g_dummyHits / g_totalHashmaps,
148 g_lookups / g_totalHashmaps,
149 100 * g_collPerLook / g_totalHashmaps,
150 g_size / g_totalHashmaps, g_max_size,
151 g_capacity / g_totalHashmaps, g_max_capacity);
152 debug(" %d less than %d; %d less than %d; %d less than %d; %d less than %d",
153 g_stats[0], 2 * 8 / 3,
154 g_stats[1], 2 * 16 / 3,
155 g_stats[2], 2 * 32 / 3,
156 g_stats[3], 2 * 64 / 3);
157
158 // TODO:
159 // * Should record the maximal size of the map during its lifetime, not that at its death
160 // * Should do some statistics: how many maps are less than 2/3*8, 2/3*16, 2/3*32, ...
161 }
162 #endif
163
164 } // End of namespace Common
165