ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

hashmap.cpp

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 // The hash map (associative array) implementation in this file is
00024 // based on the PyDict implementation of CPython. The erase() method
00025 // is based on example code in the Wikipedia article on Hash tables.
00026 
00027 #include "common/hashmap.h"
00028 
00029 namespace Common {
00030 
00031 // Hash function for strings, taken from CPython.
00032 uint hashit(const char *p) {
00033     uint hash = *p << 7;
00034     byte c;
00035     int size = 0;
00036     while ((c = *p++)) {
00037         hash = (1000003 * hash) ^ c;
00038         size++;
00039     }
00040     return hash ^ size;
00041 }
00042 
00043 // Like hashit, but converts every char to lowercase before hashing.
00044 uint hashit_lower(const char *p) {
00045     uint hash = tolower(*p) << 7;
00046     byte c;
00047     int size = 0;
00048     while ((c = *p++)) {
00049         hash = (1000003 * hash) ^ tolower(c);
00050         size++;
00051     }
00052     return hash ^ size;
00053 }
00054 
00055 #ifdef DEBUG_HASH_COLLISIONS
00056 static double
00057     g_collisions = 0,
00058     g_dummyHits = 0,
00059     g_lookups = 0,
00060     g_collPerLook = 0,
00061     g_capacity = 0,
00062     g_size = 0;
00063 static int g_max_capacity = 0, g_max_size = 0;
00064 static int g_totalHashmaps = 0;
00065 static int g_stats[4] = {0,0,0,0};
00066 
00067 void updateHashCollisionStats(int collisions, int dummyHits, int lookups, int arrsize, int nele) {
00068     g_collisions += collisions;
00069     g_lookups += lookups;
00070     g_dummyHits += dummyHits;
00071     if (lookups)
00072         g_collPerLook += (double)collisions / (double)lookups;
00073     g_capacity += arrsize;
00074     g_size += nele;
00075     g_totalHashmaps++;
00076 
00077     if (3*nele <= 2*8)
00078         g_stats[0]++;
00079     if (3*nele <= 2*16)
00080         g_stats[1]++;
00081     if (3*nele <= 2*32)
00082         g_stats[2]++;
00083     if (3*nele <= 2*64)
00084         g_stats[3]++;
00085 
00086     g_max_capacity = MAX(g_max_capacity, arrsize);
00087     g_max_size = MAX(g_max_size, nele);
00088 
00089     debug("%d hashmaps: colls %.1f; dummies hit %.1f, lookups %.1f; ratio %.3f%%; size %f (max: %d); capacity %f (max: %d)",
00090         g_totalHashmaps,
00091         g_collisions / g_totalHashmaps,
00092         g_dummyHits / g_totalHashmaps,
00093         g_lookups / g_totalHashmaps,
00094         100 * g_collPerLook / g_totalHashmaps,
00095         g_size / g_totalHashmaps, g_max_size,
00096         g_capacity / g_totalHashmaps, g_max_capacity);
00097     debug("  %d less than %d; %d less than %d; %d less than %d; %d less than %d",
00098         g_stats[0], 2 *  8 / 3,
00099         g_stats[1], 2 * 16 / 3,
00100         g_stats[2], 2 * 32 / 3,
00101         g_stats[3], 2 * 64 / 3);
00102 
00103     // TODO:
00104     // * Should record the maximal size of the map during its lifetime, not that at its death
00105     // * Should do some statistics: how many maps are less than 2/3*8, 2/3*16, 2/3*32, ...
00106 }
00107 #endif
00108 
00109 } // End of namespace Common


Generated on Sat Sep 14 2019 05:01:04 for ResidualVM by doxygen 1.7.1
curved edge   curved edge