1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 // MARKER(update_precomp.py): autogen include statement, do not remove 29 #include "precompiled_tools.hxx" 30 31 #include <tlgen.hxx> 32 #include "hashtbl.hxx" 33 34 #include <algorithm> 35 36 // ------------------------------------------------------------- 37 // class HashItem 38 // 39 class HashItem 40 { 41 enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED }; 42 43 void* m_pObject; 44 ETag m_Tag; 45 String m_Key; 46 47 public: 48 HashItem() { m_Tag = TAG_EMPTY; m_pObject = NULL; } 49 50 BOOL IsDeleted() const 51 { return m_Tag == TAG_DELETED; } 52 53 BOOL IsEmpty() const 54 { return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; } 55 56 BOOL IsFree() const 57 { return m_Tag == TAG_EMPTY; } 58 59 BOOL IsUsed() const 60 { return m_Tag == TAG_USED; } 61 62 void Delete() 63 { m_Tag = TAG_DELETED; m_Key = ""; m_pObject = NULL; } 64 65 String const& GetKey() const 66 { return m_Key; } 67 68 void* GetObject() const 69 { return m_pObject; } 70 71 void SetObject(String const Key, void *pObject) 72 { m_Tag = TAG_USED; m_Key = Key; m_pObject = pObject; } 73 }; 74 75 // #define MIN(a,b) (a)<(b)?(a):(b) 76 // #define MAX(a,b) (a)>(b)?(a):(b) 77 78 // ------------------------------------------------------------- 79 // class HashTable 80 // 81 82 /*static*/ double HashTable::m_defMaxLoadFactor = 0.8; 83 /*static*/ double HashTable::m_defDefGrowFactor = 2.0; 84 85 HashTable::HashTable(ULONG lSize, BOOL bOwner, double dMaxLoadFactor, double dGrowFactor) 86 { 87 m_lSize = lSize; 88 m_bOwner = bOwner; 89 m_lElem = 0; 90 m_dMaxLoadFactor = std::max(0.5,std::min(1.0,dMaxLoadFactor)); // 0.5 ... 1.0 91 m_dGrowFactor = std::max(1.3,(5.0,dGrowFactor)); // 1.3 ... 5.0 92 m_pData = new HashItem [lSize]; 93 94 // Statistik 95 #ifdef DBG_UTIL 96 m_aStatistic.m_lSingleHash = 0; 97 m_aStatistic.m_lDoubleHash = 0; 98 m_aStatistic.m_lProbe = 0; 99 #endif 100 } 101 102 HashTable::~HashTable() 103 { 104 // Wenn die HashTable der Owner der Objecte ist, 105 // m�ssen die Destruktoren separat gerufen werden. 106 // Dies geschieht �ber die virtuelle Methode OnDeleteObject() 107 // 108 // Problem: Virtuelle Funktionen sind im Destructor nicht virtuell!! 109 // Der Code mu� deshalb ins Macro 110 111 /* 112 if (m_bOwner) 113 { 114 for (ULONG i=0; i<GetSize(); i++) 115 { 116 void *pObject = GetObjectAt(i); 117 118 if (pObject != NULL) 119 OnDeleteObject(pObject()); 120 } 121 } 122 */ 123 124 // Speicher f�r HashItems freigeben 125 delete [] m_pData; 126 } 127 128 void* HashTable::GetObjectAt(ULONG lPos) const 129 // Gibt Objekt zur�ck, wenn es eines gibt, sonst NULL; 130 { 131 DBG_ASSERT(lPos<m_lSize, "HashTable::GetObjectAt()"); 132 133 HashItem *pItem = &m_pData[lPos]; 134 135 return pItem->IsUsed() ? pItem->GetObject() : NULL; 136 } 137 138 void HashTable::OnDeleteObject(void*) 139 { 140 DBG_ERROR("HashTable::OnDeleteObject(void*) nicht �berladen"); 141 } 142 143 ULONG HashTable::Hash(String const& Key) const 144 { 145 /* 146 ULONG lHash = 0; 147 ULONG i,n; 148 149 for (i=0,n=Key.Len(); i<n; i++) 150 { 151 lHash *= 256L; 152 lHash += (ULONG)(USHORT)Key.GetStr()[i]; 153 lHash %= m_lSize; 154 } 155 return lHash; 156 */ 157 158 // Hashfunktion von P.J. Weinberger 159 // aus dem "Drachenbuch" von Aho/Sethi/Ullman 160 ULONG i,n; 161 ULONG h = 0; 162 ULONG g = 0; 163 164 for (i=0,n=Key.Len(); i<n; i++) 165 { 166 h = (h<<4) + (ULONG)(USHORT)Key.GetStr()[i]; 167 g = h & 0xf0000000; 168 169 if (g != 0) 170 { 171 h = h ^ (g >> 24); 172 h = h ^ g; 173 } 174 } 175 176 return h % m_lSize; 177 } 178 179 ULONG HashTable::DHash(String const& Key, ULONG lOldHash) const 180 { 181 ULONG lHash = lOldHash; 182 ULONG i,n; 183 184 for (i=0,n=Key.Len(); i<n; i++) 185 { 186 lHash *= 256L; 187 lHash += (ULONG)(USHORT)Key.GetStr()[i]; 188 lHash %= m_lSize; 189 } 190 return lHash; 191 192 /* return 193 ( 194 lHash 195 + (char)Key.GetStr()[0] * 256 196 + (char)Key.GetStr()[Key.Len()-1] 197 + 1 198 ) 199 % m_lSize; 200 */ 201 } 202 203 ULONG HashTable::Probe(ULONG lPos) const 204 // gibt den Folgewert von lPos zur�ck 205 { 206 lPos++; if (lPos==m_lSize) lPos=0; 207 return lPos; 208 } 209 210 BOOL HashTable::IsFull() const 211 { 212 return m_lElem>=m_lSize; 213 } 214 215 BOOL HashTable::Insert(String const& Key, void* pObject) 216 // pre: Key ist nicht im Dictionary enthalten, sonst return FALSE 217 // Dictionary ist nicht voll, sonst return FALSE 218 // post: pObject ist unter Key im Dictionary; m_nElem wurde erh�ht 219 { 220 SmartGrow(); 221 222 if (IsFull()) 223 { 224 DBG_ERROR("HashTable::Insert() is full"); 225 return FALSE; 226 } 227 228 if (FindPos(Key) != NULL ) 229 return FALSE; 230 231 ULONG lPos = Hash(Key); 232 HashItem *pItem = &m_pData[lPos]; 233 234 // first hashing 235 // 236 if (pItem->IsEmpty()) 237 { 238 pItem->SetObject(Key, pObject); 239 m_lElem++; 240 241 #ifdef DBG_UTIL 242 m_aStatistic.m_lSingleHash++; 243 #endif 244 245 return TRUE; 246 } 247 248 // double hashing 249 // 250 lPos = DHash(Key,lPos); 251 pItem = &m_pData[lPos]; 252 253 if (pItem->IsEmpty()) 254 { 255 pItem->SetObject(Key, pObject); 256 m_lElem++; 257 258 #ifdef DBG_UTIL 259 m_aStatistic.m_lDoubleHash++; 260 #endif 261 262 return TRUE; 263 } 264 265 // linear probing 266 // 267 do 268 { 269 #ifdef DBG_UTIL 270 m_aStatistic.m_lProbe++; 271 #endif 272 273 lPos = Probe(lPos); 274 pItem = &m_pData[lPos]; 275 } 276 while(!pItem->IsEmpty()); 277 278 pItem->SetObject(Key, pObject); 279 m_lElem++; 280 return TRUE; 281 } 282 283 HashItem* HashTable::FindPos(String const& Key) const 284 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden) 285 // oder NULL (nicht gefunden) zur�ck 286 // 287 // pre: - 288 // post: - 289 { 290 // first hashing 291 // 292 ULONG lPos = Hash(Key); 293 HashItem *pItem = &m_pData[lPos]; 294 295 if (pItem->IsUsed() 296 && pItem->GetKey() == Key) 297 { 298 return pItem; 299 } 300 301 // double hashing 302 // 303 if (pItem->IsDeleted() || pItem->IsUsed()) 304 { 305 lPos = DHash(Key,lPos); 306 pItem = &m_pData[lPos]; 307 308 if (pItem->IsUsed() 309 && pItem->GetKey() == Key) 310 { 311 return pItem; 312 } 313 314 // linear probing 315 // 316 if (pItem->IsDeleted() || pItem->IsUsed()) 317 { 318 ULONG n = 0; 319 BOOL bFound = FALSE; 320 BOOL bEnd = FALSE; 321 322 do 323 { 324 n++; 325 lPos = Probe(lPos); 326 pItem = &m_pData[lPos]; 327 328 bFound = pItem->IsUsed() 329 && pItem->GetKey() == Key; 330 331 bEnd = !(n<m_lSize || pItem->IsFree()); 332 } 333 while(!bFound && !bEnd); 334 335 return bFound ? pItem : NULL; 336 } 337 } 338 339 // nicht gefunden 340 // 341 return NULL; 342 } 343 344 void* HashTable::Find(String const& Key) const 345 // Gibt Verweis des Objektes zur�ck, das unter Key abgespeichert ist, 346 // oder NULL wenn nicht vorhanden. 347 // 348 // pre: - 349 // post: - 350 { 351 HashItem *pItem = FindPos(Key); 352 353 if (pItem != NULL 354 && pItem->GetKey() == Key) 355 return pItem->GetObject(); 356 else 357 return NULL; 358 } 359 360 void* HashTable::Delete(String const& Key) 361 // L�scht Objekt, das unter Key abgespeichert ist und gibt Verweis 362 // darauf zur�ck. 363 // Gibt NULL zur�ck, wenn Key nicht vorhanden ist. 364 // 365 // pre: - 366 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert 367 // Wenn die HashTable der Owner ist, wurde das Object gel�scht 368 { 369 HashItem *pItem = FindPos(Key); 370 371 if (pItem != NULL 372 && pItem->GetKey() == Key) 373 { 374 void* pObject = pItem->GetObject(); 375 376 if (m_bOwner) 377 OnDeleteObject(pObject); 378 379 pItem->Delete(); 380 m_lElem--; 381 return pObject; 382 } 383 else 384 { 385 return NULL; 386 } 387 } 388 389 double HashTable::CalcLoadFactor() const 390 // prozentuale Belegung der Hashtabelle berechnen 391 { 392 return double(m_lElem) / double(m_lSize); 393 } 394 395 void HashTable::SmartGrow() 396 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode 397 // nicht gerufen werden 398 { 399 double dLoadFactor = CalcLoadFactor(); 400 401 if (dLoadFactor <= m_dMaxLoadFactor) 402 return; // nothing to grow 403 404 ULONG lOldSize = m_lSize; // alte Daten sichern 405 HashItem* pOldData = m_pData; 406 407 m_lSize = ULONG (m_dGrowFactor * m_lSize); // neue Gr��e 408 m_pData = new HashItem[m_lSize]; // neue Daten holen 409 410 // kein Speicher: 411 // Zustand "Tabelle voll" wird in Insert abgefangen 412 // 413 if (m_pData == NULL) 414 { 415 m_lSize = lOldSize; 416 m_pData = pOldData; 417 return; 418 } 419 420 m_lElem = 0; // noch keine neuen Daten 421 422 // Umkopieren der Daten 423 // 424 for (ULONG i=0; i<lOldSize; i++) 425 { 426 HashItem *pItem = &pOldData[i]; 427 428 if (pItem->IsUsed()) 429 Insert(pItem->GetKey(),pItem->GetObject()); 430 } 431 432 delete [] pOldData; 433 } 434 435 // Iterator --------------------------------------------------------- 436 // 437 438 HashTableIterator::HashTableIterator(HashTable const& aTable) 439 : m_aTable(aTable) 440 { 441 m_lAt = 0; 442 } 443 444 void* HashTableIterator::GetFirst() 445 { 446 m_lAt = 0; 447 return FindValidObject(TRUE /* forward */); 448 } 449 450 void* HashTableIterator::GetLast() 451 { 452 m_lAt = m_aTable.GetSize() -1; 453 return FindValidObject(FALSE /* backward */); 454 } 455 456 void* HashTableIterator::GetNext() 457 { 458 if (m_lAt+1 >= m_aTable.GetSize()) 459 return NULL; 460 461 m_lAt++; 462 return FindValidObject(TRUE /* forward */); 463 } 464 465 void* HashTableIterator::GetPrev() 466 { 467 if (m_lAt <= 0) 468 return NULL; 469 470 m_lAt--; 471 return FindValidObject(FALSE /* backward */); 472 } 473 474 void* HashTableIterator::FindValidObject(BOOL bForward) 475 // Sucht nach einem vorhandenen Objekt ab der aktuellen 476 // Position. 477 // 478 // pre: ab inkl. m_lAt soll die Suche beginnen 479 // post: if not found then 480 // if bForward == TRUE then 481 // m_lAt == m_aTable.GetSize() -1 482 // else 483 // m_lAt == 0 484 // else 485 // m_lAt ist die gefundene Position 486 { 487 void *pObject = m_aTable.GetObjectAt(m_lAt); 488 489 if (pObject != NULL) 490 return pObject; 491 492 while (pObject == NULL 493 && (bForward ? ((m_lAt+1) < m_aTable.GetSize()) 494 : m_lAt > 0)) 495 { 496 if (bForward) 497 m_lAt++; 498 else 499 m_lAt--; 500 501 pObject = m_aTable.GetObjectAt(m_lAt); 502 } 503 504 #ifdef DBG_UTIL 505 506 if (pObject == NULL) 507 { 508 DBG_ASSERT(bForward ? m_lAt == m_aTable.GetSize() -1 : m_lAt == 0, 509 "HashTableIterator::FindValidObject()"); 510 } 511 512 #endif 513 514 return pObject; 515 } 516