soldep/bootstrp/hashtbl.cxx

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