[Scummvm-cvs-logs] SF.net SVN: scummvm: [21473] scummvm/trunk/gui

fingolfin at users.sourceforge.net fingolfin at users.sourceforge.net
Tue Mar 28 02:06:07 CEST 2006


Revision: 21473
Author:   fingolfin
Date:     2006-03-28 02:05:25 -0800 (Tue, 28 Mar 2006)
ViewCVS:  http://svn.sourceforge.net/scummvm/?rev=21473&view=rev

Log Message:
-----------
- Renamed class AssocArray to HashMap to match our existing class Map (note also
  that many STL implementations have a class hash_map next to class map, too)
- Changed some static File class member vars to be normal static variables, in
  yet another attempt to reduce header dependencies (in this case on hashmap.h)

Modified Paths:
--------------
    scummvm/trunk/common/file.cpp
    scummvm/trunk/common/file.h
    scummvm/trunk/common/module.mk
    scummvm/trunk/gui/eval.h

Added Paths:
-----------
    scummvm/trunk/common/hashmap.cpp
    scummvm/trunk/common/hashmap.h

Removed Paths:
-------------
    scummvm/trunk/common/assocarray.cpp
    scummvm/trunk/common/assocarray.h
Deleted: scummvm/trunk/common/assocarray.cpp
===================================================================
--- scummvm/trunk/common/assocarray.cpp	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/common/assocarray.cpp	2006-03-28 10:05:25 UTC (rev 21473)
@@ -1,127 +0,0 @@
-/* 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

Deleted: scummvm/trunk/common/assocarray.h
===================================================================
--- scummvm/trunk/common/assocarray.h	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/common/assocarray.h	2006-03-28 10:05:25 UTC (rev 21473)
@@ -1,368 +0,0 @@
-/* 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/stdafx.h"
-#include "common/str.h"
-#include "common/util.h"
-
-#ifndef COMMON_ASSOCARRAY_H
-#define COMMON_ASSOCARRAY_H
-
-namespace Common {
-
-typedef Common::String String;
-
-// If aa is an AssocArray<Key,Val>, then space is allocated each
-// time aa[key] is referenced, for a new key. To "see" the value
-// of aa[key] but without allocating new memory, use aa.queryVal(key)
-// instead.
-// 
-// An AssocArray<Key,Val> Maps type Key to type Val. For each 
-// Key, we need a int hashit(Key,int) that hashes Key and returns 
-// an integer from 0 to hashsize-1, and a int data_eq(Key,Key) 
-// that returns true if the 2 arguments it is passed are to
-// be considered equal. Also, we assume that "=" works
-// on Val's for assignment.
-
-uint hashit(int x, uint hashsize);
-bool data_eq(int x, int y);
-uint hashit(double x, uint hashsize);
-bool data_eq(double x, double y);
-uint hashit(const char *str, uint hashsize);
-bool data_eq(const char *str1, const char *str2);
-uint hashit(const String &str, uint hashsize);
-bool data_eq(const String &str1, const String &str2);
-
-
-// The table sizes ideally are primes. We use a helper function to find
-// suitable table sizes.
-uint nextTableSize(uint x);
-
-
-// Enable the following #define if you want to check how many collisions the
-// code produces (many collisions indicate either a bad hash function, or a
-// hash table that is too small).
-//#define DEBUG_HASH_COLLISIONS
-
-template <class Key, class Val>
-class AssocArray {
-private:
-	// data structure used by AssocArray internally to keep
-	// track of what's mapped to what.
-	struct aa_ref_t {
-		Key key;
-		Val dat;
-		aa_ref_t(const Key& k) : key(k) {}
-	};
-	
-	aa_ref_t **_arr;	// hashtable of size arrsize.
-	uint _arrsize, _nele;
-	
-#ifdef DEBUG_HASH_COLLISIONS
-	mutable int _collisions, _lookups;
-#endif
-
-	int lookup(const Key &key) const;
-	void expand_array(void);
-
-public:
-
-	AssocArray();
-	~AssocArray();
-
-	bool contains(const Key &key) const;
-
-	Val &operator [](const Key &key);
-	const Val &operator [](const Key &key) const;
-	const Val &queryVal(const Key &key) const;
-
-	void clear(bool shrinkArray = 0);
-
-	// The following two methods are used to return a list of
-	// all the keys / all the values (or rather, duplicates of them).
-	// Currently they aren't used, and I think a better appraoch
-	// is to add iterators, which allow the same in a more C++-style
-	// fashion, do not require making duplicates, and finally
-	// even allow in-place modifications of
-	Key *new_all_keys(void) const;
-	Val *new_all_values(void) const;
-	//const_iterator	begin() const
-	//const_iterator	end() const
-	
-	// TODO: There is no "remove" method yet.
-	//void remove(const Key &key);
-
-
-	bool empty() const {
-		return (_nele == 0);
-	}
-};
-
-//-------------------------------------------------------
-// AssocArray functions
-
-template <class Key, class Val>
-int AssocArray<Key, Val>::lookup(const Key &key) const {
-	uint ctr = hashit(key, _arrsize);
-
-	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->key, key)) {
-		ctr++;
-#ifdef DEBUG_HASH_COLLISIONS
-		_collisions++;
-#endif
-
-		if (ctr == _arrsize)
-			ctr = 0;
-	}
-	
-#ifdef DEBUG_HASH_COLLISIONS
-	_lookups++;
-	fprintf(stderr, "collisions %d, lookups %d, ratio %f in AssocArray %p; size %d num elements %d\n",
-		_collisions, _lookups, ((double) _collisions / (double)_lookups),
-		(const void *)this, _arrsize, _nele);
-#endif
-
-	return ctr;
-}
-
-template <class Key, class Val>
-bool AssocArray<Key, Val>::contains(const Key &key) const {
-	uint ctr = lookup(key);
-	return (_arr[ctr] != NULL);
-}
-
-template <class Key, class Val>
-Key *AssocArray<Key, Val>::new_all_keys(void) const {
-	Key *all_keys;
-	uint ctr, dex;
-
-	if (_nele == 0)
-		return NULL;
-
-	all_keys = new Key[_nele];
-
-	assert(all_keys != NULL);
-
-	dex = 0;
-	for (ctr = 0; ctr < _arrsize; ctr++) {
-		if (_arr[ctr] == NULL)
-			continue;
-		all_keys[dex++] = _arr[ctr]->key;
-
-		assert(dex <= _nele);
-	}
-
-	assert(dex == _nele);
-
-	return all_keys;
-}
-
-template <class Key, class Val>
-Val *AssocArray<Key, Val>::new_all_values(void) const {
-	Val *all_values;
-	uint ctr, dex;
-
-	if (_nele == 0)
-		return NULL;
-
-	all_values = new Val[_nele];
-
-	assert(all_values != NULL);
-
-	dex = 0;
-	for (ctr = 0; ctr < _arrsize; ctr++) {
-		if (_arr[ctr] == NULL)
-			continue;
-
-		all_values[dex++] = _arr[ctr]->dat;
-
-		assert(dex <= _nele);
-	}
-
-	assert(dex == _nele);
-
-	return all_values;
-}
-
-template <class Key, class Val>
-AssocArray<Key, Val>::AssocArray() {
-	uint ctr;
-
-	_arrsize = nextTableSize(0);
-	_arr = new aa_ref_t *[_arrsize];
-	assert(_arr != NULL);
-	for (ctr = 0; ctr < _arrsize; ctr++)
-		_arr[ctr] = NULL;
-
-	_nele = 0;
-	
-#ifdef DEBUG_HASH_COLLISIONS
-	_collisions = 0;
-	_lookups = 0;
-#endif
-}
-
-template <class Key, class Val>
-AssocArray<Key, Val>::~AssocArray() {
-	uint ctr;
-
-	for (ctr = 0; ctr < _arrsize; ctr++)
-		if (_arr[ctr] != NULL)
-			delete _arr[ctr];
-
-	delete[] _arr;
-}
-
-template <class Key, class Val>
-void AssocArray<Key, Val>::clear(bool shrinkArray) {
-	for (uint ctr = 0; ctr < _arrsize; ctr++) {
-		if (_arr[ctr] != NULL) {
-			delete _arr[ctr];
-			_arr[ctr] = NULL;
-		}
-	}
-
-	if (shrinkArray && _arrsize > nextTableSize(0)) {
-		delete[] _arr;
-
-		_arrsize = nextTableSize(0);
-		_arr = new aa_ref_t *[_arrsize];
-		assert(_arr != NULL);
-		for (uint ctr = 0; ctr < _arrsize; ctr++)
-			_arr[ctr] = NULL;
-	}
-
-	_nele = 0;
-}
-
-template <class Key, class Val>
-void AssocArray<Key, Val>::expand_array(void) {
-	aa_ref_t **old_arr;
-	uint old_arrsize, old_nele, ctr, dex;
-
-	old_nele = _nele;
-	old_arr = _arr;
-	old_arrsize = _arrsize;
-
-	// allocate a new array 
-	_arrsize = nextTableSize(old_arrsize);
-	_arr = new aa_ref_t *[_arrsize];
-
-	assert(_arr != NULL);
-
-	for (ctr = 0; ctr < _arrsize; ctr++)
-		_arr[ctr] = NULL;
-
-	_nele = 0;
-
-	// rehash all the old elements
-	for (ctr = 0; ctr < old_arrsize; ctr++) {
-		if (old_arr[ctr] == NULL)
-			continue;
-
-//      (*this)[old_arr[ctr]->key] = old_arr[ctr]->dat;
-		dex = hashit(old_arr[ctr]->key, _arrsize);
-
-		while (_arr[dex] != NULL) {
-			if (++dex == _arrsize)
-				dex = 0;
-		}
-
-		_arr[dex] = old_arr[ctr];
-		_nele++;
-	}
-
-	assert(_nele == old_nele);
-
-	delete[] old_arr;
-
-	return;
-}
-
-template <class Key, class Val>
-Val &AssocArray<Key, Val>::operator [](const Key &key) {
-	uint ctr = lookup(key);
-
-	if (_arr[ctr] == NULL) {
-		_arr[ctr] = new aa_ref_t(key);
-		_nele++;
-
-		// Only fill array to fifty percent
-		if (_nele > _arrsize / 2) {
-			expand_array();
-			ctr = lookup(key);
-		}
-	}
-
-	return _arr[ctr]->dat;
-}
-
-template <class Key, class Val>
-const Val &AssocArray<Key, Val>::operator [](const Key &key) const {
-	return queryVal(key);
-}
-
-template <class Key, class Val>
-const Val &AssocArray<Key, Val>::queryVal(const Key &key) const {
-	uint ctr = lookup(key);
-	assert(_arr[ctr] != NULL);
-	return _arr[ctr]->dat;
-}
-
-}	// End of namespace Common
-
-#endif

Modified: scummvm/trunk/common/file.cpp
===================================================================
--- scummvm/trunk/common/file.cpp	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/common/file.cpp	2006-03-28 10:05:25 UTC (rev 21473)
@@ -21,6 +21,7 @@
  */
 
 #include "common/file.h"
+#include "common/hashmap.h"
 #include "common/util.h"
 #include "backends/fs/fs.h"
 
@@ -30,10 +31,15 @@
 
 namespace Common {
 
-StringList File::_defaultDirectories;
-File::FilesMap File::_filesMap;
+typedef HashMap<String, String> FilesMap;
 
+// The following two objects could be turned into static members of class
+// File. However, then we would be forced to #include hashmap in file.h
+// which seems to be a high price just for a simple beautification...
+static StringList _defaultDirectories;
+static FilesMap _filesMap;
 
+
 static FILE *fopenNoCase(const char *filename, const char *directory, const char *mode) {
 	FILE *file;
 	char buf[512];

Modified: scummvm/trunk/common/file.h
===================================================================
--- scummvm/trunk/common/file.h	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/common/file.h	2006-03-28 10:05:25 UTC (rev 21473)
@@ -27,7 +27,6 @@
 #include "common/scummsys.h"
 #include "common/str.h"
 #include "common/stream.h"
-#include "common/assocarray.h"
 
 namespace Common {
 
@@ -45,11 +44,6 @@
 	/** The name of this file, for debugging. */
 	String _name;
 
-	typedef AssocArray<String, String> FilesMap;
-
-	static StringList _defaultDirectories;
-	static FilesMap _filesMap;
-
 public:
 	enum AccessMode {
 		kFileReadMode = 1,

Copied: scummvm/trunk/common/hashmap.cpp (from rev 21470, scummvm/trunk/common/assocarray.cpp)
===================================================================
--- scummvm/trunk/common/hashmap.cpp	                        (rev 0)
+++ scummvm/trunk/common/hashmap.cpp	2006-03-28 10:05:25 UTC (rev 21473)
@@ -0,0 +1,120 @@
+/* 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$
+ *
+ */
+
+// The hash map (associative array) implementation in this file is
+// based on code by Andrew Y. Ng, 1996:
+
+/* 
+ * 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. 
+ */
+
+#include "common/hashmap.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

Copied: scummvm/trunk/common/hashmap.h (from rev 21472, scummvm/trunk/common/assocarray.h)
===================================================================
--- scummvm/trunk/common/hashmap.h	                        (rev 0)
+++ scummvm/trunk/common/hashmap.h	2006-03-28 10:05:25 UTC (rev 21473)
@@ -0,0 +1,361 @@
+/* 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$
+ *
+ */
+
+// The hash map (associative array) implementation in this file is
+// based on code by Andrew Y. Ng, 1996:
+
+/* 
+ * 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. 
+ */
+
+#include "common/stdafx.h"
+#include "common/str.h"
+#include "common/util.h"
+
+#ifndef COMMON_HASHMAP_H
+#define COMMON_HASHMAP_H
+
+namespace Common {
+
+typedef Common::String String;
+
+// If aa is an HashMap<Key,Val>, then space is allocated each
+// time aa[key] is referenced, for a new key. To "see" the value
+// of aa[key] but without allocating new memory, use aa.queryVal(key)
+// instead.
+// 
+// A HashMap<Key,Val> maps objects of type Key to objects of type Val.
+// For each used Key type, we need an "uint hashit(Key,uint)" function
+// that computes a hash for the given Key object and returns it as an
+// an integer from 0 to hashsize-1, and also a "bool data_eq(Key,Key) "
+// function that returns true if if its two arguments are to be considered
+// equal. Also, we assume that "=" works on Val objects for assignment.
+
+uint hashit(int x, uint hashsize);
+bool data_eq(int x, int y);
+uint hashit(double x, uint hashsize);
+bool data_eq(double x, double y);
+uint hashit(const char *str, uint hashsize);
+bool data_eq(const char *str1, const char *str2);
+uint hashit(const String &str, uint hashsize);
+bool data_eq(const String &str1, const String &str2);
+
+
+// The table sizes ideally are primes. We use a helper function to find
+// suitable table sizes.
+uint nextTableSize(uint x);
+
+
+// Enable the following #define if you want to check how many collisions the
+// code produces (many collisions indicate either a bad hash function, or a
+// hash table that is too small).
+//#define DEBUG_HASH_COLLISIONS
+
+template <class Key, class Val>
+class HashMap {
+private:
+	// data structure used by HashMap internally to keep
+	// track of what's mapped to what.
+	struct aa_ref_t {
+		Key key;
+		Val dat;
+		aa_ref_t(const Key& k) : key(k) {}
+	};
+	
+	aa_ref_t **_arr;	// hashtable of size arrsize.
+	uint _arrsize, _nele;
+	
+#ifdef DEBUG_HASH_COLLISIONS
+	mutable int _collisions, _lookups;
+#endif
+
+	int lookup(const Key &key) const;
+	void expand_array(void);
+
+public:
+
+	HashMap();
+	~HashMap();
+
+	bool contains(const Key &key) const;
+
+	Val &operator [](const Key &key);
+	const Val &operator [](const Key &key) const;
+	const Val &queryVal(const Key &key) const;
+
+	void clear(bool shrinkArray = 0);
+
+	// The following two methods are used to return a list of
+	// all the keys / all the values (or rather, duplicates of them).
+	// Currently they aren't used, and I think a better appraoch
+	// is to add iterators, which allow the same in a more C++-style
+	// fashion, do not require making duplicates, and finally
+	// even allow in-place modifications of
+	Key *new_all_keys(void) const;
+	Val *new_all_values(void) const;
+	//const_iterator	begin() const
+	//const_iterator	end() const
+	
+	// TODO: There is no "remove" method yet.
+	//void remove(const Key &key);
+
+
+	bool empty() const {
+		return (_nele == 0);
+	}
+};
+
+//-------------------------------------------------------
+// HashMap functions
+
+template <class Key, class Val>
+int HashMap<Key, Val>::lookup(const Key &key) const {
+	uint ctr = hashit(key, _arrsize);
+
+	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->key, key)) {
+		ctr++;
+#ifdef DEBUG_HASH_COLLISIONS
+		_collisions++;
+#endif
+
+		if (ctr == _arrsize)
+			ctr = 0;
+	}
+	
+#ifdef DEBUG_HASH_COLLISIONS
+	_lookups++;
+	fprintf(stderr, "collisions %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d\n",
+		_collisions, _lookups, ((double) _collisions / (double)_lookups),
+		(const void *)this, _arrsize, _nele);
+#endif
+
+	return ctr;
+}
+
+template <class Key, class Val>
+bool HashMap<Key, Val>::contains(const Key &key) const {
+	uint ctr = lookup(key);
+	return (_arr[ctr] != NULL);
+}
+
+template <class Key, class Val>
+Key *HashMap<Key, Val>::new_all_keys(void) const {
+	Key *all_keys;
+	uint ctr, dex;
+
+	if (_nele == 0)
+		return NULL;
+
+	all_keys = new Key[_nele];
+
+	assert(all_keys != NULL);
+
+	dex = 0;
+	for (ctr = 0; ctr < _arrsize; ctr++) {
+		if (_arr[ctr] == NULL)
+			continue;
+		all_keys[dex++] = _arr[ctr]->key;
+
+		assert(dex <= _nele);
+	}
+
+	assert(dex == _nele);
+
+	return all_keys;
+}
+
+template <class Key, class Val>
+Val *HashMap<Key, Val>::new_all_values(void) const {
+	Val *all_values;
+	uint ctr, dex;
+
+	if (_nele == 0)
+		return NULL;
+
+	all_values = new Val[_nele];
+
+	assert(all_values != NULL);
+
+	dex = 0;
+	for (ctr = 0; ctr < _arrsize; ctr++) {
+		if (_arr[ctr] == NULL)
+			continue;
+
+		all_values[dex++] = _arr[ctr]->dat;
+
+		assert(dex <= _nele);
+	}
+
+	assert(dex == _nele);
+
+	return all_values;
+}
+
+template <class Key, class Val>
+HashMap<Key, Val>::HashMap() {
+	uint ctr;
+
+	_arrsize = nextTableSize(0);
+	_arr = new aa_ref_t *[_arrsize];
+	assert(_arr != NULL);
+	for (ctr = 0; ctr < _arrsize; ctr++)
+		_arr[ctr] = NULL;
+
+	_nele = 0;
+	
+#ifdef DEBUG_HASH_COLLISIONS
+	_collisions = 0;
+	_lookups = 0;
+#endif
+}
+
+template <class Key, class Val>
+HashMap<Key, Val>::~HashMap() {
+	uint ctr;
+
+	for (ctr = 0; ctr < _arrsize; ctr++)
+		if (_arr[ctr] != NULL)
+			delete _arr[ctr];
+
+	delete[] _arr;
+}
+
+template <class Key, class Val>
+void HashMap<Key, Val>::clear(bool shrinkArray) {
+	for (uint ctr = 0; ctr < _arrsize; ctr++) {
+		if (_arr[ctr] != NULL) {
+			delete _arr[ctr];
+			_arr[ctr] = NULL;
+		}
+	}
+
+	if (shrinkArray && _arrsize > nextTableSize(0)) {
+		delete[] _arr;
+
+		_arrsize = nextTableSize(0);
+		_arr = new aa_ref_t *[_arrsize];
+		assert(_arr != NULL);
+		for (uint ctr = 0; ctr < _arrsize; ctr++)
+			_arr[ctr] = NULL;
+	}
+
+	_nele = 0;
+}
+
+template <class Key, class Val>
+void HashMap<Key, Val>::expand_array(void) {
+	aa_ref_t **old_arr;
+	uint old_arrsize, old_nele, ctr, dex;
+
+	old_nele = _nele;
+	old_arr = _arr;
+	old_arrsize = _arrsize;
+
+	// allocate a new array 
+	_arrsize = nextTableSize(old_arrsize);
+	_arr = new aa_ref_t *[_arrsize];
+
+	assert(_arr != NULL);
+
+	for (ctr = 0; ctr < _arrsize; ctr++)
+		_arr[ctr] = NULL;
+
+	_nele = 0;
+
+	// rehash all the old elements
+	for (ctr = 0; ctr < old_arrsize; ctr++) {
+		if (old_arr[ctr] == NULL)
+			continue;
+
+//      (*this)[old_arr[ctr]->key] = old_arr[ctr]->dat;
+		dex = hashit(old_arr[ctr]->key, _arrsize);
+
+		while (_arr[dex] != NULL) {
+			if (++dex == _arrsize)
+				dex = 0;
+		}
+
+		_arr[dex] = old_arr[ctr];
+		_nele++;
+	}
+
+	assert(_nele == old_nele);
+
+	delete[] old_arr;
+
+	return;
+}
+
+template <class Key, class Val>
+Val &HashMap<Key, Val>::operator [](const Key &key) {
+	uint ctr = lookup(key);
+
+	if (_arr[ctr] == NULL) {
+		_arr[ctr] = new aa_ref_t(key);
+		_nele++;
+
+		// Only fill array to fifty percent
+		if (_nele > _arrsize / 2) {
+			expand_array();
+			ctr = lookup(key);
+		}
+	}
+
+	return _arr[ctr]->dat;
+}
+
+template <class Key, class Val>
+const Val &HashMap<Key, Val>::operator [](const Key &key) const {
+	return queryVal(key);
+}
+
+template <class Key, class Val>
+const Val &HashMap<Key, Val>::queryVal(const Key &key) const {
+	uint ctr = lookup(key);
+	assert(_arr[ctr] != NULL);
+	return _arr[ctr]->dat;
+}
+
+}	// End of namespace Common
+
+#endif

Modified: scummvm/trunk/common/module.mk
===================================================================
--- scummvm/trunk/common/module.mk	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/common/module.mk	2006-03-28 10:05:25 UTC (rev 21473)
@@ -1,10 +1,10 @@
 MODULE := common
 
 MODULE_OBJS := \
-	assocarray.o \
 	config-file.o \
 	config-manager.o \
 	file.o \
+	hashmap.o \
 	md5.o \
 	mutex.o \
 	str.o \

Modified: scummvm/trunk/gui/eval.h
===================================================================
--- scummvm/trunk/gui/eval.h	2006-03-28 09:42:54 UTC (rev 21472)
+++ scummvm/trunk/gui/eval.h	2006-03-28 10:05:25 UTC (rev 21473)
@@ -25,12 +25,12 @@
 
 #include "common/stdafx.h"
 #include "common/str.h"
-#include "common/assocarray.h"
+#include "common/hashmap.h"
 
 namespace GUI {
 
 using Common::String;
-using Common::AssocArray;
+using Common::HashMap;
 
 #define EVAL_UNDEF_VAR -13375
 
@@ -67,8 +67,8 @@
 
 	void reset();
 
-	typedef AssocArray<String, int> VariablesMap;
-	typedef AssocArray<String, String> AliasesMap;
+	typedef HashMap<String, int> VariablesMap;
+	typedef HashMap<String, String> AliasesMap;
 
 private:
 	void getToken();


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.





More information about the Scummvm-git-logs mailing list