soldep/bootstrp/hashtbl.cxx

   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     BOOL IsDeleted() const
  47     {   return m_Tag == TAG_DELETED; }
  48
  49     BOOL IsEmpty() const
  50     {   return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; }
  51
  52     BOOL IsFree() const
  53     {   return m_Tag == TAG_EMPTY; }
  54
  55     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(ULONG lSize, 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 (ULONG 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(ULONG 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 ULONG HashTable::Hash(ByteString const& Key) const
 140 {
 141     /*
 142     ULONG lHash = 0;
 143     ULONG i,n;
 144
 145     for (i=0,n=Key.Len(); i<n; i++)
 146     {
 147         lHash *= 256L;
 148         lHash += (ULONG)(USHORT)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     ULONG i,n;
 157     ULONG h = 0;
 158     ULONG g = 0;
 159
 160     for (i=0,n=Key.Len(); i<n; i++)
 161     {
 162         h = (h<<4) + (ULONG)(USHORT)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 ULONG HashTable::DHash(ByteString const& Key, ULONG lOldHash) const
 176 {
 177     ULONG lHash = lOldHash;
 178     ULONG i,n;
 179
 180     for (i=0,n=Key.Len(); i<n; i++)
 181     {
 182         lHash *= 256L;
 183         lHash += (ULONG)(USHORT)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 ULONG HashTable::Probe(ULONG 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 BOOL HashTable::IsFull() const
 207 {
 208     return m_lElem>=m_lSize;
 209 }
 210
 211 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 FALSE;
 222     }
 223
 224     if (FindPos(Key) != NULL )
 225         return FALSE;
 226
 227     ULONG     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 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 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 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     ULONG     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             ULONG n      = 0;
 315             BOOL  bFound = FALSE;
 316             BOOL  bEnd   = 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     ULONG     lOldSize = m_lSize;              // alte Daten sichern
 401     HashItem* pOldData = m_pData;
 402
 403     m_lSize = ULONG (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 (ULONG 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(TRUE /* forward */);
 444 }
 445
 446 void* HashTableIterator::GetLast()
 447 {
 448     m_lAt = m_aTable.GetSize() -1;
 449     return FindValidObject(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(TRUE /* forward */);
 459 }
 460
 461 void* HashTableIterator::GetPrev()
 462 {
 463     if (m_lAt <= 0)
 464         return NULL;
 465
 466     m_lAt--;
 467     return FindValidObject(FALSE /* backward */);
 468 }
 469
 470 void* HashTableIterator::FindValidObject(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 == 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 }