From f4339ff6c438149d7fad05db053444109a4c5611 Mon Sep 17 00:00:00 2001 From: Max Horn Date: Tue, 28 Mar 2006 10:05:25 +0000 Subject: - 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) svn-id: r21473 --- common/assocarray.cpp | 127 ----------------- common/assocarray.h | 368 -------------------------------------------------- common/file.cpp | 10 +- common/file.h | 6 - common/hashmap.cpp | 120 ++++++++++++++++ common/hashmap.h | 361 +++++++++++++++++++++++++++++++++++++++++++++++++ common/module.mk | 2 +- gui/eval.h | 8 +- 8 files changed, 494 insertions(+), 508 deletions(-) delete mode 100644 common/assocarray.cpp delete mode 100644 common/assocarray.h create mode 100644 common/hashmap.cpp create mode 100644 common/hashmap.h diff --git a/common/assocarray.cpp b/common/assocarray.cpp deleted file mode 100644 index c0031b6ecb..0000000000 --- a/common/assocarray.cpp +++ /dev/null @@ -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 diff --git a/common/assocarray.h b/common/assocarray.h deleted file mode 100644 index 8505f48c19..0000000000 --- a/common/assocarray.h +++ /dev/null @@ -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, 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 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 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 -int AssocArray::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 -bool AssocArray::contains(const Key &key) const { - uint ctr = lookup(key); - return (_arr[ctr] != NULL); -} - -template -Key *AssocArray::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 -Val *AssocArray::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 -AssocArray::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 -AssocArray::~AssocArray() { - uint ctr; - - for (ctr = 0; ctr < _arrsize; ctr++) - if (_arr[ctr] != NULL) - delete _arr[ctr]; - - delete[] _arr; -} - -template -void AssocArray::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 -void AssocArray::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 -Val &AssocArray::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 -const Val &AssocArray::operator [](const Key &key) const { - return queryVal(key); -} - -template -const Val &AssocArray::queryVal(const Key &key) const { - uint ctr = lookup(key); - assert(_arr[ctr] != NULL); - return _arr[ctr]->dat; -} - -} // End of namespace Common - -#endif diff --git a/common/file.cpp b/common/file.cpp index c9917f698a..b1ef8f4bec 100644 --- a/common/file.cpp +++ b/common/file.cpp @@ -21,6 +21,7 @@ */ #include "common/file.h" +#include "common/hashmap.h" #include "common/util.h" #include "backends/fs/fs.h" @@ -30,8 +31,13 @@ namespace Common { -StringList File::_defaultDirectories; -File::FilesMap File::_filesMap; +typedef HashMap 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) { diff --git a/common/file.h b/common/file.h index d113e7f531..939cd3cdc5 100644 --- a/common/file.h +++ b/common/file.h @@ -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 @@ protected: /** The name of this file, for debugging. */ String _name; - typedef AssocArray FilesMap; - - static StringList _defaultDirectories; - static FilesMap _filesMap; - public: enum AccessMode { kFileReadMode = 1, diff --git a/common/hashmap.cpp b/common/hashmap.cpp new file mode 100644 index 0000000000..9051398999 --- /dev/null +++ b/common/hashmap.cpp @@ -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 diff --git a/common/hashmap.h b/common/hashmap.h new file mode 100644 index 0000000000..da222d1bfb --- /dev/null +++ b/common/hashmap.h @@ -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, 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 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 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 +int HashMap::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 +bool HashMap::contains(const Key &key) const { + uint ctr = lookup(key); + return (_arr[ctr] != NULL); +} + +template +Key *HashMap::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 +Val *HashMap::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 +HashMap::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 +HashMap::~HashMap() { + uint ctr; + + for (ctr = 0; ctr < _arrsize; ctr++) + if (_arr[ctr] != NULL) + delete _arr[ctr]; + + delete[] _arr; +} + +template +void HashMap::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 +void HashMap::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 +Val &HashMap::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 +const Val &HashMap::operator [](const Key &key) const { + return queryVal(key); +} + +template +const Val &HashMap::queryVal(const Key &key) const { + uint ctr = lookup(key); + assert(_arr[ctr] != NULL); + return _arr[ctr]->dat; +} + +} // End of namespace Common + +#endif diff --git a/common/module.mk b/common/module.mk index 8630e3c7ab..dc8048db64 100644 --- a/common/module.mk +++ b/common/module.mk @@ -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 \ diff --git a/gui/eval.h b/gui/eval.h index 799a6f74e8..1b2df123d4 100644 --- a/gui/eval.h +++ b/gui/eval.h @@ -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 @@ public: void reset(); - typedef AssocArray VariablesMap; - typedef AssocArray AliasesMap; + typedef HashMap VariablesMap; + typedef HashMap AliasesMap; private: void getToken(); -- cgit v1.2.3