1*8b851043SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*8b851043SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*8b851043SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*8b851043SAndrew Rist * distributed with this work for additional information 6*8b851043SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*8b851043SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*8b851043SAndrew Rist * "License"); you may not use this file except in compliance 9*8b851043SAndrew Rist * with the License. You may obtain a copy of the License at 10*8b851043SAndrew Rist * 11*8b851043SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12*8b851043SAndrew Rist * 13*8b851043SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*8b851043SAndrew Rist * software distributed under the License is distributed on an 15*8b851043SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*8b851043SAndrew Rist * KIND, either express or implied. See the License for the 17*8b851043SAndrew Rist * specific language governing permissions and limitations 18*8b851043SAndrew Rist * under the License. 19*8b851043SAndrew Rist * 20*8b851043SAndrew Rist *************************************************************/ 21*8b851043SAndrew Rist 22*8b851043SAndrew Rist 23cdf0e10cSrcweir 24cdf0e10cSrcweir #ifndef _HASHTBL_HXX 25cdf0e10cSrcweir #define _HASHTBL_HXX 26cdf0e10cSrcweir 27cdf0e10cSrcweir #include <tlgen.hxx> 28cdf0e10cSrcweir 29cdf0e10cSrcweir // ADT hash table 30cdf0e10cSrcweir // 31cdf0e10cSrcweir // Invariante: 32cdf0e10cSrcweir // 1. m_lElem < m_lSize 33cdf0e10cSrcweir // 2. die Elemente in m_Array wurden double-hashed erzeugt 34cdf0e10cSrcweir // 35cdf0e10cSrcweir class HashItem; 36cdf0e10cSrcweir 37cdf0e10cSrcweir class HashTable 38cdf0e10cSrcweir { 39cdf0e10cSrcweir ULONG m_lSize; 40cdf0e10cSrcweir ULONG m_lElem; 41cdf0e10cSrcweir HashItem *m_pData; 42cdf0e10cSrcweir double m_dMaxLoadFactor; 43cdf0e10cSrcweir double m_dGrowFactor; 44cdf0e10cSrcweir BOOL m_bOwner; 45cdf0e10cSrcweir 46cdf0e10cSrcweir ULONG Hash(String const& Key) const; 47cdf0e10cSrcweir ULONG DHash(String const& Key, ULONG lHash) const; 48cdf0e10cSrcweir ULONG Probe(ULONG lPos) const; 49cdf0e10cSrcweir 50cdf0e10cSrcweir HashItem* FindPos(String const& Key) const; 51cdf0e10cSrcweir void SmartGrow(); 52cdf0e10cSrcweir double CalcLoadFactor() const; 53cdf0e10cSrcweir 54cdf0e10cSrcweir // Statistik 55cdf0e10cSrcweir #ifdef DBG_UTIL 56cdf0e10cSrcweir private: 57cdf0e10cSrcweir struct 58cdf0e10cSrcweir { 59cdf0e10cSrcweir ULONG m_lSingleHash; 60cdf0e10cSrcweir ULONG m_lDoubleHash; 61cdf0e10cSrcweir ULONG m_lProbe; 62cdf0e10cSrcweir } 63cdf0e10cSrcweir m_aStatistic; 64cdf0e10cSrcweir #endif 65cdf0e10cSrcweir 66cdf0e10cSrcweir protected: 67cdf0e10cSrcweir friend class HashTableIterator; 68cdf0e10cSrcweir 69cdf0e10cSrcweir virtual void OnDeleteObject(void* pObject); 70cdf0e10cSrcweir 71cdf0e10cSrcweir void* GetObjectAt(ULONG lPos) const; 72cdf0e10cSrcweir 73cdf0e10cSrcweir // Default-Werte 74cdf0e10cSrcweir public: 75cdf0e10cSrcweir static double m_defMaxLoadFactor; 76cdf0e10cSrcweir static double m_defDefGrowFactor; 77cdf0e10cSrcweir 78cdf0e10cSrcweir public: 79cdf0e10cSrcweir HashTable 80cdf0e10cSrcweir ( 81cdf0e10cSrcweir ULONG lSize, 82cdf0e10cSrcweir BOOL bOwner, 83cdf0e10cSrcweir double dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */, 84cdf0e10cSrcweir double dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */ 85cdf0e10cSrcweir ); 86cdf0e10cSrcweir 87cdf0e10cSrcweir ~HashTable(); 88cdf0e10cSrcweir 89cdf0e10cSrcweir BOOL IsFull() const; GetSize() const90cdf0e10cSrcweir ULONG GetSize() const { return m_lSize; } 91cdf0e10cSrcweir 92cdf0e10cSrcweir void* Find (String const& Key) const; 93cdf0e10cSrcweir BOOL Insert (String const& Key, void* pObject); 94cdf0e10cSrcweir void* Delete (String const& Key); 95cdf0e10cSrcweir }; 96cdf0e10cSrcweir 97cdf0e10cSrcweir // ADT hash table iterator 98cdf0e10cSrcweir // 99cdf0e10cSrcweir // Invariante: 0 <= m_lAt < m_aTable.GetCount() 100cdf0e10cSrcweir // 101cdf0e10cSrcweir class HashTableIterator 102cdf0e10cSrcweir { 103cdf0e10cSrcweir ULONG m_lAt; 104cdf0e10cSrcweir HashTable const& m_aTable; 105cdf0e10cSrcweir 106cdf0e10cSrcweir void* FindValidObject(BOOL bForward); 107cdf0e10cSrcweir 108cdf0e10cSrcweir protected: 109cdf0e10cSrcweir void* GetFirst(); // Interation _ohne_ Sortierung 110cdf0e10cSrcweir void* GetNext(); 111cdf0e10cSrcweir void* GetLast(); 112cdf0e10cSrcweir void* GetPrev(); 113cdf0e10cSrcweir 114cdf0e10cSrcweir public: 115cdf0e10cSrcweir HashTableIterator(HashTable const&); 116cdf0e10cSrcweir }; 117cdf0e10cSrcweir 118cdf0e10cSrcweir // typsichere Makros --------------------------------------------------- 119cdf0e10cSrcweir 120cdf0e10cSrcweir #define DECLARE_HASHTABLE_INTERN(ClassName,Owner,KeyType,ObjType) \ 121cdf0e10cSrcweir class ClassName : public HashTable \ 122cdf0e10cSrcweir { \ 123cdf0e10cSrcweir public: \ 124cdf0e10cSrcweir ClassName \ 125cdf0e10cSrcweir ( \ 126cdf0e10cSrcweir ULONG lSize, \ 127cdf0e10cSrcweir double dMaxLoadFactor = HashTable::m_defMaxLoadFactor, \ 128cdf0e10cSrcweir double dGrowFactor = HashTable::m_defDefGrowFactor \ 129cdf0e10cSrcweir ) \ 130cdf0e10cSrcweir : HashTable(lSize,Owner,dMaxLoadFactor,dGrowFactor) {} \ 131cdf0e10cSrcweir \ 132cdf0e10cSrcweir ObjType Find (KeyType const& Key) const \ 133cdf0e10cSrcweir { return (ObjType) HashTable::Find(String(Key)); } \ 134cdf0e10cSrcweir \ 135cdf0e10cSrcweir BOOL Insert (KeyType const& Key, ObjType Object) \ 136cdf0e10cSrcweir { return HashTable::Insert(String(Key), (void*) Object); } \ 137cdf0e10cSrcweir \ 138cdf0e10cSrcweir ObjType Delete (KeyType const&Key) \ 139cdf0e10cSrcweir { return (ObjType) HashTable::Delete (String(Key)); } \ 140cdf0e10cSrcweir }; 141cdf0e10cSrcweir 142cdf0e10cSrcweir // HashTable OHNE Owner-Verhalten 143cdf0e10cSrcweir #define DECLARE_HASHTABLE(ClassName,KeyType,ObjType) \ 144cdf0e10cSrcweir DECLARE_HASHTABLE_INTERN(ClassName,FALSE,KeyType,ObjType) 145cdf0e10cSrcweir 146cdf0e10cSrcweir // HashTable MIT Owner-Verhalten 147cdf0e10cSrcweir #define DECLARE_HASHTABLE_OWNER(ClassName,KeyType,ObjType) \ 148cdf0e10cSrcweir DECLARE_HASHTABLE_INTERN(ClassName##2,TRUE,KeyType,ObjType) \ 149cdf0e10cSrcweir class ClassName : public ClassName##2 \ 150cdf0e10cSrcweir { \ 151cdf0e10cSrcweir protected: \ 152cdf0e10cSrcweir virtual void OnDeleteObject(void* pObject); \ 153cdf0e10cSrcweir public: \ 154cdf0e10cSrcweir ClassName \ 155cdf0e10cSrcweir ( \ 156cdf0e10cSrcweir ULONG lSize, \ 157cdf0e10cSrcweir double dMaxLoadFactor = HashTable::m_defMaxLoadFactor, \ 158cdf0e10cSrcweir double dGrowFactor = HashTable::m_defDefGrowFactor \ 159cdf0e10cSrcweir ) \ 160cdf0e10cSrcweir : ClassName##2(lSize,dMaxLoadFactor,dGrowFactor) {} \ 161cdf0e10cSrcweir ~ClassName(); \ 162cdf0e10cSrcweir }; 163cdf0e10cSrcweir 164cdf0e10cSrcweir #define IMPLEMENT_HASHTABLE_OWNER(ClassName,KeyType,ObjType) \ 165cdf0e10cSrcweir void ClassName::OnDeleteObject(void* pObject) \ 166cdf0e10cSrcweir { delete (ObjType) pObject; } \ 167cdf0e10cSrcweir \ 168cdf0e10cSrcweir ClassName::~ClassName() \ 169cdf0e10cSrcweir { \ 170cdf0e10cSrcweir for (ULONG i=0; i<GetSize(); i++) \ 171cdf0e10cSrcweir { \ 172cdf0e10cSrcweir void *pObject = GetObjectAt(i); \ 173cdf0e10cSrcweir if (pObject != NULL) \ 174cdf0e10cSrcweir OnDeleteObject(pObject); \ 175cdf0e10cSrcweir } \ 176cdf0e10cSrcweir } 177cdf0e10cSrcweir 178cdf0e10cSrcweir // Iterator-Makros -------------------------------------------------- 179cdf0e10cSrcweir 180cdf0e10cSrcweir #define DECLARE_HASHTABLE_ITERATOR(ClassName,ObjType) \ 181cdf0e10cSrcweir class ClassName : public HashTableIterator \ 182cdf0e10cSrcweir { \ 183cdf0e10cSrcweir public: \ 184cdf0e10cSrcweir ClassName(HashTable const& aTable) \ 185cdf0e10cSrcweir : HashTableIterator(aTable) {} \ 186cdf0e10cSrcweir \ 187cdf0e10cSrcweir ObjType GetFirst() \ 188cdf0e10cSrcweir { return (ObjType)HashTableIterator::GetFirst(); } \ 189cdf0e10cSrcweir ObjType GetNext() \ 190cdf0e10cSrcweir { return (ObjType)HashTableIterator::GetNext(); } \ 191cdf0e10cSrcweir ObjType GetLast() \ 192cdf0e10cSrcweir { return (ObjType)HashTableIterator::GetLast(); } \ 193cdf0e10cSrcweir ObjType GetPrev() \ 194cdf0e10cSrcweir { return (ObjType)HashTableIterator::GetPrev(); } \ 195cdf0e10cSrcweir }; 196cdf0e10cSrcweir 197cdf0e10cSrcweir 198cdf0e10cSrcweir #endif // _HASHTBL_HXX 199cdf0e10cSrcweir 200