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