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 // MARKER(update_precomp.py): autogen include statement, do not remove 25 #include "precompiled_soltools.hxx" 26 27 #include "hashtbl.hxx" 28 #include <string.h> 29 30 // ------------------------------------------------------------- 31 // class HashItem 32 // 33 class HashItem 34 { 35 enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED }; 36 37 void* m_pObject; 38 ETag m_Tag; 39 char* m_Key; 40 41 public: 42 HashItem() { m_Tag = TAG_EMPTY; m_Key = NULL; m_pObject = NULL; } 43 ~HashItem() { delete [] m_Key; } 44 45 bool IsDeleted() const 46 { return m_Tag == TAG_DELETED; } 47 48 bool IsEmpty() const 49 { return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; } 50 51 bool IsFree() const 52 { return m_Tag == TAG_EMPTY; } 53 54 bool IsUsed() const 55 { return m_Tag == TAG_USED; } 56 57 void Delete() 58 { m_Tag = TAG_DELETED; delete [] m_Key; m_Key = new char[ 1 ]; m_Key[ 0 ] = 0; m_pObject = NULL; } 59 60 const char *GetKey() const 61 { return m_Key; } 62 63 void* GetObject() const 64 { return m_pObject; } 65 66 void SetObject(const char * Key, void *pObject) 67 { m_Tag = TAG_USED; delete [] m_Key; m_Key = new char[ strlen( Key ) + 1 ]; strcpy( m_Key, Key ); m_pObject = pObject; } 68 }; 69 70 #define MIN(a,b) (a)<(b)?(a):(b) 71 #define MAX(a,b) (a)>(b)?(a):(b) 72 73 // ------------------------------------------------------------- 74 // class HashTable 75 // 76 77 /*static*/ double HashTable::m_defMaxLoadFactor = 0.5; 78 /*static*/ double HashTable::m_defDefGrowFactor = 2.0; 79 80 HashTable::HashTable(unsigned long lSize, bool bOwner, double dMaxLoadFactor, double dGrowFactor) 81 { 82 m_lSize = lSize; 83 m_bOwner = bOwner; 84 m_lElem = 0; 85 m_dMaxLoadFactor = MAX(0.5,MIN(1.0,dMaxLoadFactor)); // 0.5 ... 1.0 86 m_dGrowFactor = MAX(2.0,MIN(5.0,dGrowFactor)); // 1.3 ... 5.0 87 m_pData = new HashItem [lSize]; 88 } 89 90 HashTable::~HashTable() 91 { 92 // Wenn die HashTable der Owner der Objecte ist, 93 // m�ssen die Destruktoren separat gerufen werden. 94 // Dies geschieht �ber die virtuelle Methode OnDeleteObject() 95 // 96 // Problem: Virtuelle Funktionen sind im Destructor nicht virtuell!! 97 // Der Code mu� deshalb ins Macro 98 99 /* 100 if (m_bOwner) 101 { 102 for (ULONG i=0; i<GetSize(); i++) 103 { 104 void *pObject = GetObjectAt(i); 105 106 if (pObject != NULL) 107 OnDeleteObject(pObject()); 108 } 109 } 110 */ 111 112 // Speicher f�r HashItems freigeben 113 delete [] m_pData; 114 } 115 116 void* HashTable::GetObjectAt(unsigned long lPos) const 117 // Gibt Objekt zur�ck, wenn es eines gibt, sonst NULL; 118 { 119 HashItem *pItem = &m_pData[lPos]; 120 121 return pItem->IsUsed() ? pItem->GetObject() : NULL; 122 } 123 124 void HashTable::OnDeleteObject(void*) 125 { 126 } 127 128 unsigned long HashTable::Hash(const char *Key) const 129 { 130 // Hashfunktion von P.J. Weinberger 131 // aus dem "Drachenbuch" von Aho/Sethi/Ullman 132 unsigned long i,n; 133 unsigned long h = 0; 134 unsigned long g = 0; 135 136 for (i=0,n=strlen( Key ); i<n; i++) 137 { 138 h = (h<<4) + (unsigned long)(unsigned short)Key[i]; 139 g = h & 0xf0000000; 140 141 if (g != 0) 142 { 143 h = h ^ (g >> 24); 144 h = h ^ g; 145 } 146 } 147 148 return h % m_lSize; 149 } 150 151 unsigned long HashTable::DHash(const char* Key, unsigned long lOldHash) const 152 { 153 unsigned long lHash = lOldHash; 154 unsigned long i,n; 155 156 for (i=0,n=strlen( Key ); i<n; i++) 157 { 158 lHash *= 256L; 159 lHash += (unsigned long)(unsigned short)Key[i]; 160 lHash %= m_lSize; 161 } 162 return lHash; 163 } 164 165 unsigned long HashTable::Probe(unsigned long lPos) const 166 // gibt den Folgewert von lPos zur�ck 167 { 168 lPos++; if (lPos==m_lSize) lPos=0; 169 return lPos; 170 } 171 172 bool HashTable::IsFull() const 173 { 174 return m_lElem>=m_lSize; 175 } 176 177 bool HashTable::Insert(const char * Key, void* pObject) 178 // pre: Key ist nicht im Dictionary enthalten, sonst return FALSE 179 // Dictionary ist nicht voll, sonst return FALSE 180 // post: pObject ist unter Key im Dictionary; m_nElem wurde erh�ht 181 { 182 SmartGrow(); 183 184 if (IsFull()) 185 { 186 return false; 187 } 188 189 if (FindPos(Key) != NULL ) 190 return false; 191 192 unsigned long lPos = Hash(Key); 193 HashItem *pItem = &m_pData[lPos]; 194 195 // first hashing 196 // 197 if (pItem->IsEmpty()) 198 { 199 pItem->SetObject(Key, pObject); 200 m_lElem++; 201 202 return true; 203 } 204 205 // double hashing 206 // 207 lPos = DHash(Key,lPos); 208 pItem = &m_pData[lPos]; 209 210 if (pItem->IsEmpty()) 211 { 212 pItem->SetObject(Key, pObject); 213 m_lElem++; 214 215 return true; 216 } 217 218 // linear probing 219 // 220 do 221 { 222 lPos = Probe(lPos); 223 pItem = &m_pData[lPos]; 224 } 225 while(!pItem->IsEmpty()); 226 227 pItem->SetObject(Key, pObject); 228 m_lElem++; 229 return true; 230 } 231 232 HashItem* HashTable::FindPos(const char * Key) const 233 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden) 234 // oder NULL (nicht gefunden) zur�ck 235 // 236 // pre: - 237 // post: - 238 { 239 // first hashing 240 // 241 unsigned long lPos = Hash(Key); 242 HashItem *pItem = &m_pData[lPos]; 243 244 if (pItem->IsUsed() 245 && !(strcmp( pItem->GetKey(), Key ))) 246 { 247 return pItem; 248 } 249 250 // double hashing 251 // 252 if (pItem->IsDeleted() || pItem->IsUsed()) 253 { 254 lPos = DHash(Key,lPos); 255 pItem = &m_pData[lPos]; 256 257 if (pItem->IsUsed() 258 && (!strcmp( pItem->GetKey(), Key))) 259 { 260 return pItem; 261 } 262 263 // linear probing 264 // 265 if (pItem->IsDeleted() || pItem->IsUsed()) 266 { 267 unsigned long n = 0; 268 bool bFound = false; 269 bool bEnd = false; 270 271 do 272 { 273 n++; 274 lPos = Probe(lPos); 275 pItem = &m_pData[lPos]; 276 277 bFound = pItem->IsUsed() 278 && !( strcmp( pItem->GetKey(), Key )); 279 280 bEnd = !(n<m_lSize || pItem->IsFree()); 281 } 282 while(!bFound && !bEnd); 283 284 return bFound ? pItem : NULL; 285 } 286 } 287 288 // nicht gefunden 289 // 290 return NULL; 291 } 292 293 void* HashTable::Find(const char *Key) const 294 // Gibt Verweis des Objektes zur�ck, das unter Key abgespeichert ist, 295 // oder NULL wenn nicht vorhanden. 296 // 297 // pre: - 298 // post: - 299 { 300 HashItem *pItem = FindPos(Key); 301 302 if (pItem != NULL 303 && ( !strcmp( pItem->GetKey(), Key ))) 304 return pItem->GetObject(); 305 else 306 return NULL; 307 } 308 309 void* HashTable::Delete( const char * Key) 310 // L�scht Objekt, das unter Key abgespeichert ist und gibt Verweis 311 // darauf zur�ck. 312 // Gibt NULL zur�ck, wenn Key nicht vorhanden ist. 313 // 314 // pre: - 315 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert 316 // Wenn die HashTable der Owner ist, wurde das Object gel�scht 317 { 318 HashItem *pItem = FindPos(Key); 319 320 if (pItem != NULL 321 && ( !strcmp( pItem->GetKey(), Key ))) 322 { 323 void* pObject = pItem->GetObject(); 324 325 if (m_bOwner) 326 OnDeleteObject(pObject); 327 328 pItem->Delete(); 329 m_lElem--; 330 return pObject; 331 } 332 else 333 { 334 return NULL; 335 } 336 } 337 338 double HashTable::CalcLoadFactor() const 339 // prozentuale Belegung der Hashtabelle berechnen 340 { 341 return double(m_lElem) / double(m_lSize); 342 } 343 344 void HashTable::SmartGrow() 345 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode 346 // nicht gerufen werden 347 { 348 double dLoadFactor = CalcLoadFactor(); 349 350 if (dLoadFactor <= m_dMaxLoadFactor) 351 return; // nothing to grow 352 353 unsigned long lOldSize = m_lSize; // alte Daten sichern 354 HashItem* pOldData = m_pData; 355 356 m_lSize = (unsigned long) (m_dGrowFactor * m_lSize); // neue Gr��e 357 m_pData = new HashItem[m_lSize]; // neue Daten holen 358 359 // kein Speicher: 360 // Zustand "Tabelle voll" wird in Insert abgefangen 361 // 362 if (m_pData == NULL) 363 { 364 m_lSize = lOldSize; 365 m_pData = pOldData; 366 return; 367 } 368 369 m_lElem = 0; // noch keine neuen Daten 370 371 // Umkopieren der Daten 372 // 373 for (unsigned long i=0; i<lOldSize; i++) 374 { 375 HashItem *pItem = &pOldData[i]; 376 377 if (pItem->IsUsed()) 378 Insert(pItem->GetKey(),pItem->GetObject()); 379 } 380 381 delete [] pOldData; 382 } 383 384 // Iterator --------------------------------------------------------- 385 // 386 387 HashTableIterator::HashTableIterator(HashTable const& aTable) 388 : m_aTable(aTable) 389 { 390 m_lAt = 0; 391 } 392 393 void* HashTableIterator::GetFirst() 394 { 395 m_lAt = 0; 396 return FindValidObject(true /* forward */); 397 } 398 399 void* HashTableIterator::GetLast() 400 { 401 m_lAt = m_aTable.GetSize() -1; 402 return FindValidObject(false /* backward */); 403 } 404 405 void* HashTableIterator::GetNext() 406 { 407 if (m_lAt+1 >= m_aTable.GetSize()) 408 return NULL; 409 410 m_lAt++; 411 return FindValidObject(true /* forward */); 412 } 413 414 void* HashTableIterator::GetPrev() 415 { 416 if (m_lAt <= 0) 417 return NULL; 418 419 m_lAt--; 420 return FindValidObject(false /* backward */); 421 } 422 423 void* HashTableIterator::FindValidObject(bool bForward) 424 // Sucht nach einem vorhandenen Objekt ab der aktuellen 425 // Position. 426 // 427 // pre: ab inkl. m_lAt soll die Suche beginnen 428 // post: if not found then 429 // if bForward == TRUE then 430 // m_lAt == m_aTable.GetSize() -1 431 // else 432 // m_lAt == 0 433 // else 434 // m_lAt ist die gefundene Position 435 { 436 void *pObject = m_aTable.GetObjectAt(m_lAt); 437 438 if (pObject != NULL) 439 return pObject; 440 441 while (pObject == NULL 442 && (bForward ? ((m_lAt+1) < m_aTable.GetSize()) 443 : m_lAt > 0)) 444 { 445 if (bForward) 446 m_lAt++; 447 else 448 m_lAt--; 449 450 pObject = m_aTable.GetObjectAt(m_lAt); 451 } 452 453 return pObject; 454 } 455