Implementation of AssociativeArray. Transferred GUI to it. Now it is much

faster.

svn-id: r21419

4 files changed, 502 insertions, 8 deletions

diff --git a/common/assocarray.cpp b/common/assocarray.cpp
new file mode 100644
index 0000000000..eb2ee47f66
--- /dev/null
+++ b/common/assocarray.cpp
@@ -0,0 +1,116 @@
+/* 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:
+int hashit(int x, int hashsize) {
+	return x % hashsize;
+}
+
+int data_eq(int x, int y) {
+	return x == y;
+}
+
+#if 0
+// double:
+int hashit(double d, int hashsize) {
+	int hash, dex;
+	byte *p = (byte *)&d;
+
+	hash = 0;
+
+	for (dex = 0; dex < sizeof(double); dex++)
+		hash = ((hash << 8) + p[dex]) % hashsize;
+
+	return hash;
+}
+#endif
+
+int data_eq(double d1, double d2) {
+	return (d1 == d2);
+}
+
+// const char *:
+int hashit(const char *str, int hashsize) {
+	const byte *p = (const byte *)str;
+	int hash, dex;
+
+	hash = 0;
+
+	for (dex = 0; p[dex] != 0; dex++)
+		hash = ((hash << 8) + p[dex]) % hashsize;
+
+	return hash;
+}
+
+int data_eq(const char *str1, const char *str2) {
+	return !strcmp(str1, str2);
+}
+
+// String:
+int hashit(const Common::String &str, int hashsize) {
+	return hashit(str.c_str(), hashsize);
+}
+
+int data_eq(const Common::String &str1, const String &str2) {
+	return (str1 == str2);
+}
+
+}	// End of namespace Common
diff --git a/common/assocarray.h b/common/assocarray.h
new file mode 100644
index 0000000000..d1032ebf2c
--- /dev/null
+++ b/common/assocarray.h
@@ -0,0 +1,381 @@
+/* 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 {
+
+#define INIT_SIZE 11
+
+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.
+
+int hashit(int x, int hashsize);
+int data_eq(int x, int y);
+int hashit(double x, int hashsize);
+int data_eq(double x, double y);
+int hashit(const char *str, int hashsize);
+int data_eq(const char *str1, const char *str2);
+int hashit(const String &str, int hashsize);
+int data_eq(const String &str1, const String &str2);
+
+// data structure used by AssocArray internally to keep
+// track of what's mapped to what.
+template <class Key, class Val>
+struct aa_ref_t {
+	Key index;
+	Val dat;
+};
+
+template <class Key, class Val>
+class AssocArray {
+private:
+	aa_ref_t <Key, Val> **_arr;	// hashtable of size arrsize.
+	Val _default_value;
+	int _arrsize, _nele;
+
+	inline void expand_array(void);
+	inline Val &subscript_helper(Key &index);	// like [], but never expands array
+
+public:
+	inline int nele_val(void) const { return _nele; }
+	inline Val defaultValue_val(void) const { return _default_value; }
+
+	inline Val &operator [](const Key &index);
+	inline AssocArray(Val default_value = NULL);
+	inline ~AssocArray();
+	inline int contains(const Key &index) const;
+	inline Key *new_all_keys(void) const;
+	inline Val *new_all_values(void) const;
+	inline Val queryVal(const Key &index) const;
+	inline void clear(int shrinkArray = 0);
+};
+
+//-------------------------------------------------------
+// AssocArray functions
+
+template <class Key, class Val>
+inline int AssocArray <Key, Val>::contains(const Key &index) const {
+	int ctr;
+
+	ctr = hashit(index, _arrsize);
+
+	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->index, index)) {
+		ctr++;
+
+		if (ctr == _arrsize)
+			ctr = 0;
+	}
+
+	if (_arr[ctr] == NULL)
+		return 0;
+	else
+		return 1;
+}
+
+template <class Key, class Val>
+inline Key *AssocArray <Key, Val>::new_all_keys(void) const {
+	Key *all_keys;
+	int 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]->index;
+
+		assert(dex <= _nele);
+	}
+
+	assert(dex == _nele);
+
+	return all_keys;
+}
+
+template <class Key, class Val>
+inline Val *AssocArray <Key, Val>::new_all_values(void) const {
+	Val *all_values;
+	int 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>
+inline AssocArray <Key, Val>::AssocArray(Val default_value) : _default_value(default_value) {
+	int ctr;
+
+	_arr = new aa_ref_t <Key, Val> *[INIT_SIZE];
+
+	for (ctr = 0; ctr < INIT_SIZE; ctr++)
+		_arr[ctr] = NULL;
+
+	assert(_arr != NULL);
+
+	_arrsize = INIT_SIZE;
+	_nele = 0;
+
+	return;
+}
+
+template <class Key, class Val>
+inline AssocArray <Key, Val>::~AssocArray() {
+	int ctr;
+
+	for (ctr = 0; ctr < _arrsize; ctr++)
+		if (_arr[ctr] != NULL)
+			delete _arr[ctr];
+
+	delete[] _arr;
+}
+
+template <class Key, class Val>
+inline void AssocArray <Key, Val>::clear(int shrinkArray) {
+	for (int ctr = 0; ctr < _arrsize; ctr++) {
+		if (_arr[ctr] != NULL) {
+			delete _arr[ctr];
+			_arr[ctr] = NULL;
+		}
+	}
+
+	shrinkArray = 0;
+	if (shrinkArray && _arrsize > INIT_SIZE) {
+		delete _arr;
+
+		_arr = new aa_ref_t <Key, Val> *[INIT_SIZE];
+		_arrsize = INIT_SIZE;
+
+		for (int ctr = 0; ctr < _arrsize; ctr++)
+			_arr[ctr] = NULL;
+	}
+
+	_nele = 0;
+}
+
+static int is_odd(int x) {return x&1;}
+static int is_even(int x) {return !is_odd(x);}
+
+template <class Key, class Val>
+inline void AssocArray <Key, Val>::expand_array(void) {
+	aa_ref_t <Key, Val> **old_arr;
+	int old_arrsize, old_nele, ctr, dex;
+
+	old_nele = _nele;
+	old_arr = _arr;
+	old_arrsize = _arrsize;
+
+    // GROWTH_FACTOR 1.531415936535
+	// allocate a new array 
+	_arrsize = 153 * old_arrsize / 100;
+
+	if (is_even(_arrsize))
+		_arrsize++;
+
+	_arr = new aa_ref_t <Key, Val> *[_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]->index] = old_arr[ctr]->dat;
+		dex = hashit(old_arr[ctr]->index, _arrsize);
+
+		while (_arr[dex] != NULL)
+			if (++dex == _arrsize)
+				dex = 0;
+
+		_arr[dex] = old_arr[ctr];
+		_nele++;
+	}
+
+	assert(_nele == old_nele);
+
+	delete[] old_arr;
+
+	return;
+}
+
+// like [], but never expands array.
+// Precond: index is a key that is already in the hash table.
+template <class Key, class Val>
+inline Val &AssocArray <Key, Val>::subscript_helper(Key &index) {
+	int ctr;
+
+	ctr = hashit(index, _arrsize);
+
+	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->index, index)) {
+		ctr++;
+
+		if (ctr == _arrsize)
+			ctr = 0;
+	}
+
+//  if (_arr[ctr] == NULL)
+//      {
+//      _arr[ctr] = new aa_ref_t<Val,Key>;
+//      _arr[ctr]->index = index;
+//      _arr[ctr]->dat = _default_value;
+//      _nele++;
+//      }
+
+	assert(_arr[ctr] != NULL);
+
+	return _arr[ctr]->dat;
+}
+
+template <class Key, class Val>
+inline Val &AssocArray <Key, Val>::operator [](const Key &index) {
+	int ctr;
+
+	ctr = hashit(index, _arrsize);
+
+	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->index, index)) {
+		ctr++;
+
+		if (ctr == _arrsize)
+			ctr = 0;
+	}
+
+	if (_arr[ctr] == NULL) {
+		_arr[ctr] = new aa_ref_t <Key, Val>;
+		_arr[ctr]->index = index;
+		_arr[ctr]->dat = _default_value;
+		_nele++;
+
+		if (_nele > _arrsize / 2) {
+			expand_array();
+
+			return (*this)[index];
+		} else {
+			return _arr[ctr]->dat;
+		}
+	}
+
+	return _arr[ctr]->dat;
+}
+
+template <class Key, class Val>
+inline Val AssocArray <Key, Val>::queryVal(const Key &index) const {
+	int ctr;
+
+	ctr = hashit(index, _arrsize);
+
+	while (_arr[ctr] != NULL && !data_eq(_arr[ctr]->index, index)) {
+		ctr++;
+
+		if (ctr == _arrsize)
+			ctr = 0;
+	}
+
+	if (_arr[ctr] == NULL)
+		return _default_value;
+	else
+		return _arr[ctr]->dat;
+}
+
+}	// End of namespace Common
+
+#endif
diff --git a/common/module.mk b/common/module.mk
index cf1348ba2b..8630e3c7ab 100644
--- a/common/module.mk
+++ b/common/module.mk
@@ -1,6 +1,7 @@
 MODULE := common
 
 MODULE_OBJS := \
+	assocarray.o \
 	config-file.o \
 	config-manager.o \
 	file.o \
diff --git a/gui/eval.h b/gui/eval.h
index 69389c58c9..fc4f12c11d 100644
--- a/gui/eval.h
+++ b/gui/eval.h
@@ -25,12 +25,12 @@
 
 #include "common/stdafx.h"
 #include "common/str.h"
-#include "common/map.h"
+#include "common/assocarray.h"
 
 namespace GUI {
 
 using Common::String;
-using Common::Map;
+using Common::AssocArray;
 
 #define EVAL_UNDEF_VAR -13375
 
@@ -49,10 +49,6 @@ enum evalErrors {
 	eUndefVar
 };
 
-struct IgnoreCaseComparator {
-  int operator()(const String& x, const String& y) const { return strcmp(x.c_str(), y.c_str()); }
-};
-
 class Eval {
 public:
 	Eval();
@@ -71,8 +67,8 @@ public:
 
 	void reset();
 
-	typedef Map<String, int, IgnoreCaseComparator> VariablesMap;
-	typedef Map<String, String, IgnoreCaseComparator> AliasesMap;
+	typedef AssocArray<String, int> VariablesMap;
+	typedef AssocArray<String, String> AliasesMap;
 
 private:
 	void getToken();