xref: /aoo42x/main/tools/workben/hashtbl.hxx (revision 8b851043)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 #ifndef _HASHTBL_HXX
25 #define _HASHTBL_HXX
26 
27 #include <tlgen.hxx>
28 
29 // ADT hash table
30 //
31 // Invariante:
32 //    1. m_lElem < m_lSize
33 //    2. die Elemente in m_Array wurden double-hashed erzeugt
34 //
35 class HashItem;
36 
37 class HashTable
38 {
39     ULONG     m_lSize;
40     ULONG     m_lElem;
41     HashItem *m_pData;
42     double    m_dMaxLoadFactor;
43     double    m_dGrowFactor;
44     BOOL      m_bOwner;
45 
46     ULONG Hash(String const& Key) const;
47     ULONG DHash(String const& Key, ULONG lHash) const;
48     ULONG Probe(ULONG lPos) const;
49 
50     HashItem* FindPos(String const& Key) const;
51     void      SmartGrow();
52     double    CalcLoadFactor() const;
53 
54 // Statistik
55 #ifdef DBG_UTIL
56 private:
57 	struct
58 	{
59 		ULONG m_lSingleHash;
60 		ULONG m_lDoubleHash;
61 		ULONG m_lProbe;
62 	}
63 		m_aStatistic;
64 #endif
65 
66 protected:
67 	friend class HashTableIterator;
68 
69     virtual void OnDeleteObject(void* pObject);
70 
71     void* GetObjectAt(ULONG lPos) const;
72 
73 // Default-Werte
74 public:
75 	static double m_defMaxLoadFactor;
76 	static double m_defDefGrowFactor;
77 
78 public:
79     HashTable
80 	(
81 		ULONG	lSize,
82 		BOOL	bOwner,
83 		double	dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */,
84 		double	dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */
85 	);
86 
87     ~HashTable();
88 
89     BOOL  IsFull() const;
GetSize() const90     ULONG GetSize() const { return m_lSize; }
91 
92     void* Find   (String const& Key) const;
93     BOOL  Insert (String const& Key, void* pObject);
94     void* Delete (String const& Key);
95 };
96 
97 // ADT hash table iterator
98 //
99 // Invariante: 0 <= m_lAt < m_aTable.GetCount()
100 //
101 class HashTableIterator
102 {
103 	ULONG			 m_lAt;
104 	HashTable const& m_aTable;
105 
106 	void* FindValidObject(BOOL bForward);
107 
108 protected:
109 	void* GetFirst(); // Interation _ohne_ Sortierung
110 	void* GetNext();
111 	void* GetLast();
112 	void* GetPrev();
113 
114 public:
115 	HashTableIterator(HashTable const&);
116 };
117 
118 // typsichere Makros ---------------------------------------------------
119 
120 #define DECLARE_HASHTABLE_INTERN(ClassName,Owner,KeyType,ObjType)       \
121     class ClassName : public HashTable                                  \
122     {                                                                   \
123     public:                                                             \
124         ClassName														\
125 		(																\
126 			ULONG	lSize,												\
127 			double	dMaxLoadFactor = HashTable::m_defMaxLoadFactor,		\
128 			double	dGrowFactor = HashTable::m_defDefGrowFactor			\
129 		)																\
130         : HashTable(lSize,Owner,dMaxLoadFactor,dGrowFactor) {}          \
131                                                                         \
132         ObjType  Find (KeyType const& Key) const                        \
133         { return (ObjType) HashTable::Find(String(Key)); }              \
134                                                                         \
135         BOOL Insert (KeyType const& Key, ObjType Object)                \
136         { return HashTable::Insert(String(Key), (void*) Object); }      \
137                                                                         \
138         ObjType  Delete (KeyType const&Key)                             \
139         { return (ObjType) HashTable::Delete (String(Key)); }           \
140     };
141 
142 // HashTable OHNE Owner-Verhalten
143 #define DECLARE_HASHTABLE(ClassName,KeyType,ObjType)                 \
144     DECLARE_HASHTABLE_INTERN(ClassName,FALSE,KeyType,ObjType)
145 
146 // HashTable MIT Owner-Verhalten
147 #define DECLARE_HASHTABLE_OWNER(ClassName,KeyType,ObjType)           \
148     DECLARE_HASHTABLE_INTERN(ClassName##2,TRUE,KeyType,ObjType)      \
149     class ClassName : public ClassName##2                            \
150     {                                                                \
151     protected:                                                       \
152         virtual void OnDeleteObject(void* pObject);                  \
153     public:                                                          \
154         ClassName													 \
155 		(															 \
156 			ULONG	lSize,											 \
157 			double	dMaxLoadFactor = HashTable::m_defMaxLoadFactor,	 \
158 			double	dGrowFactor = HashTable::m_defDefGrowFactor		 \
159 		)															 \
160         : ClassName##2(lSize,dMaxLoadFactor,dGrowFactor) {}			 \
161         ~ClassName();                                                \
162     };
163 
164 #define IMPLEMENT_HASHTABLE_OWNER(ClassName,KeyType,ObjType)         \
165     void ClassName::OnDeleteObject(void* pObject)                    \
166     { delete (ObjType) pObject; }                                    \
167                                                                      \
168     ClassName::~ClassName()                                          \
169     {                                                                \
170         for (ULONG i=0; i<GetSize(); i++)                            \
171         {                                                            \
172             void *pObject = GetObjectAt(i);                          \
173             if (pObject != NULL)                                     \
174                 OnDeleteObject(pObject);                             \
175         }                                                            \
176     }
177 
178 // Iterator-Makros --------------------------------------------------
179 
180 #define DECLARE_HASHTABLE_ITERATOR(ClassName,ObjType)				\
181 	class ClassName : public HashTableIterator						\
182 	{																\
183 	public:															\
184 		ClassName(HashTable const& aTable)							\
185 		: HashTableIterator(aTable)	{}								\
186 																	\
187 		ObjType GetFirst()		 									\
188 			{ return (ObjType)HashTableIterator::GetFirst(); }		\
189 		ObjType GetNext()		 									\
190 			{ return (ObjType)HashTableIterator::GetNext();  }		\
191 		ObjType GetLast()		 									\
192 			{ return (ObjType)HashTableIterator::GetLast();  }		\
193 		ObjType GetPrev()		 									\
194 			{ return (ObjType)HashTableIterator::GetPrev();  }		\
195 	};
196 
197 
198 #endif // _HASHTBL_HXX
199 
200