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 #ifdef DEBUG_HASH_COLLISIONS
56 static double
57 g_collisions = 0,
58 g_dummyHits = 0,
59 g_lookups = 0,
60 g_collPerLook = 0,
61 g_capacity = 0,
62 g_size = 0;
63 static int g_max_capacity = 0, g_max_size = 0;
64 static int g_totalHashmaps = 0;
65 static int g_stats[4] = {0,0,0,0};
66
updateHashCollisionStats(int collisions,int dummyHits,int lookups,int arrsize,int nele)67 void updateHashCollisionStats(int collisions, int dummyHits, int lookups, int arrsize, int nele) {
68 g_collisions += collisions;
69 g_lookups += lookups;
70 g_dummyHits += dummyHits;
71 if (lookups)
72 g_collPerLook += (double)collisions / (double)lookups;
73 g_capacity += arrsize;
74 g_size += nele;
75 g_totalHashmaps++;
76
77 if (3*nele <= 2*8)
78 g_stats[0]++;
79 if (3*nele <= 2*16)
80 g_stats[1]++;
81 if (3*nele <= 2*32)
82 g_stats[2]++;
83 if (3*nele <= 2*64)
84 g_stats[3]++;
85
86 g_max_capacity = MAX(g_max_capacity, arrsize);
87 g_max_size = MAX(g_max_size, nele);
88
89 debug("%d hashmaps: colls %.1f; dummies hit %.1f, lookups %.1f; ratio %.3f%%; size %f (max: %d); capacity %f (max: %d)",
90 g_totalHashmaps,
91 g_collisions / g_totalHashmaps,
92 g_dummyHits / g_totalHashmaps,
93 g_lookups / g_totalHashmaps,
94 100 * g_collPerLook / g_totalHashmaps,
95 g_size / g_totalHashmaps, g_max_size,
96 g_capacity / g_totalHashmaps, g_max_capacity);
97 debug(" %d less than %d; %d less than %d; %d less than %d; %d less than %d",
98 g_stats[0], 2*8/3,
99 g_stats[1],2*16/3,
100 g_stats[2],2*32/3,
101 g_stats[3],2*64/3);
102
103 // TODO:
104 // * Should record the maximal size of the map during its lifetime, not that at its death
105 // * Should do some statistics: how many maps are less than 2/3*8, 2/3*16, 2/3*32, ...
106 }
107 #endif
108
109 } // End of namespace Common
110