soltools/ldump/hashtbl.cxx

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