diff options
| -rw-r--r-- | common/assocarray.cpp | 116 | ||||
| -rw-r--r-- | common/assocarray.h | 381 | ||||
| -rw-r--r-- | common/module.mk | 1 | ||||
| -rw-r--r-- | gui/eval.h | 12 |
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(); |