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