tools/workben/hashtbl.hxx

   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.hxx,v $
  10  * $Revision: 1.3 $
  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 #ifndef _HASHTBL_HXX
  32 #define _HASHTBL_HXX
  33
  34 #include <tlgen.hxx>
  35
  36 // ADT hash table
  37 //
  38 // Invariante:
  39 //    1. m_lElem < m_lSize
  40 //    2. die Elemente in m_Array wurden double-hashed erzeugt
  41 //
  42 class HashItem;
  43
  44 class HashTable
  45 {
  46     ULONG     m_lSize;
  47     ULONG     m_lElem;
  48     HashItem *m_pData;
  49     double    m_dMaxLoadFactor;
  50     double    m_dGrowFactor;
  51     BOOL      m_bOwner;
  52
  53     ULONG Hash(String const& Key) const;
  54     ULONG DHash(String const& Key, ULONG lHash) const;
  55     ULONG Probe(ULONG lPos) const;
  56
  57     HashItem* FindPos(String const& Key) const;
  58     void      SmartGrow();
  59     double    CalcLoadFactor() const;
  60
  61 // Statistik
  62 #ifdef DBG_UTIL
  63 private:
  64     struct
  65     {
  66         ULONG m_lSingleHash;
  67         ULONG m_lDoubleHash;
  68         ULONG m_lProbe;
  69     }
  70         m_aStatistic;
  71 #endif
  72
  73 protected:
  74     friend class HashTableIterator;
  75
  76     virtual void OnDeleteObject(void* pObject);
  77
  78     void* GetObjectAt(ULONG lPos) const;
  79
  80 // Default-Werte
  81 public:
  82     static double m_defMaxLoadFactor;
  83     static double m_defDefGrowFactor;
  84
  85 public:
  86     HashTable
  87     (
  88         ULONG   lSize,
  89         BOOL    bOwner,
  90         double  dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */,
  91         double  dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */
  92     );
  93
  94     ~HashTable();
  95
  96     BOOL  IsFull() const;
  97     ULONG GetSize() const { return m_lSize; }
  98
  99     void* Find   (String const& Key) const;
 100     BOOL  Insert (String const& Key, void* pObject);
 101     void* Delete (String const& Key);
 102 };
 103
 104 // ADT hash table iterator
 105 //
 106 // Invariante: 0 <= m_lAt < m_aTable.GetCount()
 107 //
 108 class HashTableIterator
 109 {
 110     ULONG                        m_lAt;
 111     HashTable const& m_aTable;
 112
 113     void* FindValidObject(BOOL bForward);
 114
 115 protected:
 116     void* GetFirst(); // Interation _ohne_ Sortierung
 117     void* GetNext();
 118     void* GetLast();
 119     void* GetPrev();
 120
 121 public:
 122     HashTableIterator(HashTable const&);
 123 };
 124
 125 // typsichere Makros ---------------------------------------------------
 126
 127 #define DECLARE_HASHTABLE_INTERN(ClassName,Owner,KeyType,ObjType)       \
 128     class ClassName : public HashTable                                  \
 129     {                                                                   \
 130     public:                                                             \
 131         ClassName                                                                                                               \
 132         (                                                                                                                               \
 133             ULONG       lSize,                                                                                          \
 134             double      dMaxLoadFactor = HashTable::m_defMaxLoadFactor,         \
 135             double      dGrowFactor = HashTable::m_defDefGrowFactor                     \
 136         )                                                                                                                               \
 137         : HashTable(lSize,Owner,dMaxLoadFactor,dGrowFactor) {}          \
 138                                                                         \
 139         ObjType  Find (KeyType const& Key) const                        \
 140         { return (ObjType) HashTable::Find(String(Key)); }              \
 141                                                                         \
 142         BOOL Insert (KeyType const& Key, ObjType Object)                \
 143         { return HashTable::Insert(String(Key), (void*) Object); }      \
 144                                                                         \
 145         ObjType  Delete (KeyType const&Key)                             \
 146         { return (ObjType) HashTable::Delete (String(Key)); }           \
 147     };
 148
 149 // HashTable OHNE Owner-Verhalten
 150 #define DECLARE_HASHTABLE(ClassName,KeyType,ObjType)                 \
 151     DECLARE_HASHTABLE_INTERN(ClassName,FALSE,KeyType,ObjType)
 152
 153 // HashTable MIT Owner-Verhalten
 154 #define DECLARE_HASHTABLE_OWNER(ClassName,KeyType,ObjType)           \
 155     DECLARE_HASHTABLE_INTERN(ClassName##2,TRUE,KeyType,ObjType)      \
 156     class ClassName : public ClassName##2                            \
 157     {                                                                \
 158     protected:                                                       \
 159         virtual void OnDeleteObject(void* pObject);                  \
 160     public:                                                          \
 161         ClassName                                                                                                        \
 162         (                                                                                                                        \
 163             ULONG       lSize,                                                                                   \
 164             double      dMaxLoadFactor = HashTable::m_defMaxLoadFactor,  \
 165             double      dGrowFactor = HashTable::m_defDefGrowFactor              \
 166         )                                                                                                                        \
 167         : ClassName##2(lSize,dMaxLoadFactor,dGrowFactor) {}                      \
 168         ~ClassName();                                                \
 169     };
 170
 171 #define IMPLEMENT_HASHTABLE_OWNER(ClassName,KeyType,ObjType)         \
 172     void ClassName::OnDeleteObject(void* pObject)                    \
 173     { delete (ObjType) pObject; }                                    \
 174                                                                      \
 175     ClassName::~ClassName()                                          \
 176     {                                                                \
 177         for (ULONG i=0; i<GetSize(); i++)                            \
 178         {                                                            \
 179             void *pObject = GetObjectAt(i);                          \
 180             if (pObject != NULL)                                     \
 181                 OnDeleteObject(pObject);                             \
 182         }                                                            \
 183     }
 184
 185 // Iterator-Makros --------------------------------------------------
 186
 187 #define DECLARE_HASHTABLE_ITERATOR(ClassName,ObjType)                           \
 188     class ClassName : public HashTableIterator                                          \
 189     {                                                                                                                           \
 190     public:                                                                                                                     \
 191         ClassName(HashTable const& aTable)                                                      \
 192         : HashTableIterator(aTable)     {}                                                              \
 193                                                                     \
 194         ObjType GetFirst()                                                                                      \
 195             { return (ObjType)HashTableIterator::GetFirst(); }          \
 196         ObjType GetNext()                                                                                       \
 197             { return (ObjType)HashTableIterator::GetNext();  }          \
 198         ObjType GetLast()                                                                                       \
 199             { return (ObjType)HashTableIterator::GetLast();  }          \
 200         ObjType GetPrev()                                                                                       \
 201             { return (ObjType)HashTableIterator::GetPrev();  }          \
 202     };
 203
 204
 205 #endif // _HASHTBL_HXX
 206