aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorEugene Sandulenko2006-03-23 22:59:38 +0000
committerEugene Sandulenko2006-03-23 22:59:38 +0000
commit5d1b4d8f78352f4bfb0073d0ab53647377c98f96 (patch)
tree13c0be604d399a4ea4d9793d0c7425fe5fe2820d
parentf5966123443f89e1f1a1b6859dc077c679f6e715 (diff)
downloadscummvm-rg350-5d1b4d8f78352f4bfb0073d0ab53647377c98f96.tar.gz
scummvm-rg350-5d1b4d8f78352f4bfb0073d0ab53647377c98f96.tar.bz2
scummvm-rg350-5d1b4d8f78352f4bfb0073d0ab53647377c98f96.zip
Implementation of AssociativeArray. Transferred GUI to it. Now it is much
faster. svn-id: r21419
-rw-r--r--common/assocarray.cpp116
-rw-r--r--common/assocarray.h381
-rw-r--r--common/module.mk1
-rw-r--r--gui/eval.h12
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();