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 <tools/gen.hxx> 28 #include <tools/string.hxx> 29 30 // ADT hash table 31 // 32 // Invariante: 33 // 1. m_lElem < m_lSize 34 // 2. die Elemente in m_Array wurden double-hashed erzeugt 35 // 36 class HashItem; 37 38 class HashTable 39 { 40 sal_uIntPtr m_lSize; 41 sal_uIntPtr m_lElem; 42 HashItem *m_pData; 43 double m_dMaxLoadFactor; 44 double m_dGrowFactor; 45 sal_Bool m_bOwner; 46 47 sal_uIntPtr Hash(ByteString const& Key) const; 48 sal_uIntPtr DHash(ByteString const& Key, sal_uIntPtr lHash) const; 49 sal_uIntPtr Probe(sal_uIntPtr lPos) const; 50 51 HashItem* FindPos(ByteString const& Key) const; 52 void SmartGrow(); 53 double CalcLoadFactor() const; 54 55 // Statistik 56 #ifdef DBG_UTIL 57 private: 58 struct 59 { 60 sal_uIntPtr m_lSingleHash; 61 sal_uIntPtr m_lDoubleHash; 62 sal_uIntPtr m_lProbe; 63 } 64 m_aStatistic; 65 #endif 66 67 protected: 68 friend class HashTableIterator; 69 70 virtual void OnDeleteObject(void* pObject); 71 72 void* GetObjectAt(sal_uIntPtr lPos) const; 73 74 // Default-Werte 75 public: 76 static double m_defMaxLoadFactor; 77 static double m_defDefGrowFactor; 78 79 public: 80 HashTable 81 ( 82 sal_uIntPtr lSize, 83 sal_Bool bOwner, 84 double dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */, 85 double dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */ 86 ); 87 88 virtual ~HashTable(); 89 90 sal_Bool IsFull() const; GetSize() const91 sal_uIntPtr GetSize() const { return m_lSize; } 92 93 void* Find (ByteString const& Key) const; 94 sal_Bool Insert (ByteString const& Key, void* pObject); 95 void* Delete (ByteString const& Key); 96 }; 97 98 // ADT hash table iterator 99 // 100 // Invariante: 0 <= m_lAt < m_aTable.GetCount() 101 // 102 class HashTableIterator 103 { 104 sal_uIntPtr m_lAt; 105 HashTable const& m_aTable; 106 107 void* FindValidObject(sal_Bool bForward); 108 109 protected: 110 void* GetFirst(); // Interation _ohne_ Sortierung 111 void* GetNext(); 112 void* GetLast(); 113 void* GetPrev(); 114 115 public: 116 HashTableIterator(HashTable const&); 117 }; 118 119 // typsichere Makros --------------------------------------------------- 120 121 #define DECLARE_HASHTABLE_INTERN(ClassName,Owner,KeyType,ObjType) \ 122 class ClassName : public HashTable \ 123 { \ 124 public: \ 125 ClassName \ 126 ( \ 127 sal_uIntPtr lSize, \ 128 double dMaxLoadFactor = HashTable::m_defMaxLoadFactor, \ 129 double dGrowFactor = HashTable::m_defDefGrowFactor \ 130 ) \ 131 : HashTable(lSize,Owner,dMaxLoadFactor,dGrowFactor) {} \ 132 \ 133 ObjType Find (KeyType const& Key) const \ 134 { return (ObjType) HashTable::Find(ByteString(Key)); } \ 135 \ 136 using HashTable::Insert; \ 137 sal_Bool Insert (KeyType const& Key, ObjType Object) \ 138 { return HashTable::Insert(ByteString(Key), (void*) Object); } \ 139 \ 140 ObjType Delete (KeyType const&Key) \ 141 { return (ObjType) HashTable::Delete (ByteString(Key)); } \ 142 }; 143 144 // HashTable OHNE Owner-Verhalten 145 #define DECLARE_HASHTABLE(ClassName,KeyType,ObjType) \ 146 DECLARE_HASHTABLE_INTERN(ClassName,sal_False,KeyType,ObjType) 147 148 // HashTable MIT Owner-Verhalten 149 #define DECLARE_HASHTABLE_OWNER(ClassName,KeyType,ObjType) \ 150 DECLARE_HASHTABLE_INTERN(ClassName##2,sal_True,KeyType,ObjType) \ 151 class ClassName : public ClassName##2 \ 152 { \ 153 protected: \ 154 virtual void OnDeleteObject(void* pObject); \ 155 public: \ 156 ClassName \ 157 ( \ 158 sal_uIntPtr lSize, \ 159 double dMaxLoadFactor = HashTable::m_defMaxLoadFactor, \ 160 double dGrowFactor = HashTable::m_defDefGrowFactor \ 161 ) \ 162 : ClassName##2(lSize,dMaxLoadFactor,dGrowFactor) {} \ 163 ~ClassName(); \ 164 }; 165 166 #define IMPLEMENT_HASHTABLE_OWNER(ClassName,KeyType,ObjType) \ 167 void ClassName::OnDeleteObject(void* pObject) \ 168 { delete (ObjType) pObject; } \ 169 \ 170 ClassName::~ClassName() \ 171 { \ 172 for (sal_uIntPtr i=0; i<GetSize(); i++) \ 173 { \ 174 void *pObject = GetObjectAt(i); \ 175 if (pObject != NULL) \ 176 OnDeleteObject(pObject); \ 177 } \ 178 } 179 180 // Iterator-Makros -------------------------------------------------- 181 182 #define DECLARE_HASHTABLE_ITERATOR(ClassName,ObjType) \ 183 class ClassName : public HashTableIterator \ 184 { \ 185 public: \ 186 ClassName(HashTable const& aTable) \ 187 : HashTableIterator(aTable) {} \ 188 \ 189 ObjType GetFirst() \ 190 { return (ObjType)HashTableIterator::GetFirst(); } \ 191 ObjType GetNext() \ 192 { return (ObjType)HashTableIterator::GetNext(); } \ 193 ObjType GetLast() \ 194 { return (ObjType)HashTableIterator::GetLast(); } \ 195 ObjType GetPrev() \ 196 { return (ObjType)HashTableIterator::GetPrev(); } \ 197 }; 198 199 200 #endif // _HASHTBL_HXX 201