[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