]> git.saurik.com Git - wxWidgets.git/blob - src/common/hash.cpp
No longer use semi-static IDs for wxPropertyGrid embedded controls and tool bar tools.
[wxWidgets.git] / src / common / hash.cpp
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/hash.cpp
3 // Purpose: wxHashTable implementation
4 // Author: Julian Smart
5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
6 // Created: 01/02/97
7 // RCS-ID: $Id$
8 // Copyright: (c) Julian Smart
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 // ============================================================================
13 // declarations
14 // ============================================================================
15
16 // ----------------------------------------------------------------------------
17 // headers
18 // ----------------------------------------------------------------------------
19
20 // For compilers that support precompilation, includes "wx.h".
21 #include "wx/wxprec.h"
22
23 #ifdef __BORLANDC__
24 #pragma hdrstop
25 #endif
26
27 #ifndef WX_PRECOMP
28 #include "wx/hash.h"
29 #include "wx/object.h"
30 #endif
31
32 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
33 wxHashTableBase* table )
34 : m_value( value ), m_hashPtr( table )
35 {
36 m_key.integer = key;
37 }
38
39 wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value,
40 wxHashTableBase* table )
41 : m_value( value ), m_hashPtr( table )
42 {
43 m_key.string = new wxString(key);
44 }
45
46 wxHashTableBase_Node::~wxHashTableBase_Node()
47 {
48 if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
49 }
50
51 //
52
53 wxHashTableBase::wxHashTableBase()
54 : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
55 m_deleteContents( false )
56 {
57 }
58
59 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
60 {
61 m_keyType = keyType;
62 m_size = size;
63 m_table = new wxHashTableBase_Node*[ m_size ];
64
65 for( size_t i = 0; i < m_size; ++i )
66 m_table[i] = NULL;
67 }
68
69 void wxHashTableBase::Clear()
70 {
71 for( size_t i = 0; i < m_size; ++i )
72 {
73 Node* end = m_table[i];
74
75 if( end == NULL )
76 continue;
77
78 Node *curr, *next = end->GetNext();
79
80 do
81 {
82 curr = next;
83 next = curr->GetNext();
84
85 DoDestroyNode( curr );
86
87 delete curr;
88 }
89 while( curr != end );
90
91 m_table[i] = NULL;
92 }
93
94 m_count = 0;
95 }
96
97 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
98 {
99 size_t bucket = ( m_keyType == wxKEY_INTEGER ?
100 node->m_key.integer :
101 MakeKey( *node->m_key.string ) ) % m_size;
102
103 if( node->GetNext() == node )
104 {
105 // single-node chain (common case)
106 m_table[bucket] = NULL;
107 }
108 else
109 {
110 Node *start = m_table[bucket], *curr;
111 Node* prev = start;
112
113 for( curr = prev->GetNext(); curr != node;
114 prev = curr, curr = curr->GetNext() ) ;
115
116 DoUnlinkNode( bucket, node, prev );
117 }
118
119 DoDestroyNode( node );
120 }
121
122 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
123 {
124 // if it is called from DoRemoveNode, node has already been
125 // removed, from other places it does not matter
126 node->m_hashPtr = NULL;
127
128 if( m_keyType == wxKEY_STRING )
129 delete node->m_key.string;
130 if( m_deleteContents )
131 DoDeleteContents( node );
132 }
133
134 void wxHashTableBase::Destroy()
135 {
136 Clear();
137
138 wxDELETEA(m_table);
139 m_size = 0;
140 }
141
142 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
143 {
144 if( m_table[bucket] == NULL )
145 {
146 m_table[bucket] = node->m_next = node;
147 }
148 else
149 {
150 Node *prev = m_table[bucket];
151 Node *next = prev->m_next;
152
153 prev->m_next = node;
154 node->m_next = next;
155 m_table[bucket] = node;
156 }
157
158 ++m_count;
159 }
160
161 void wxHashTableBase::DoPut( long key, long hash, void* data )
162 {
163 wxASSERT( m_keyType == wxKEY_INTEGER );
164
165 size_t bucket = size_t(hash) % m_size;
166 Node* node = new wxHashTableBase_Node( key, data, this );
167
168 DoInsertNode( bucket, node );
169 }
170
171 void wxHashTableBase::DoPut( const wxString& key, long hash, void* data )
172 {
173 wxASSERT( m_keyType == wxKEY_STRING );
174
175 size_t bucket = size_t(hash) % m_size;
176 Node* node = new wxHashTableBase_Node( key, data, this );
177
178 DoInsertNode( bucket, node );
179 }
180
181 void* wxHashTableBase::DoGet( long key, long hash ) const
182 {
183 wxASSERT( m_keyType == wxKEY_INTEGER );
184
185 size_t bucket = size_t(hash) % m_size;
186
187 if( m_table[bucket] == NULL )
188 return NULL;
189
190 Node *first = m_table[bucket]->GetNext(),
191 *curr = first;
192
193 do
194 {
195 if( curr->m_key.integer == key )
196 return curr->m_value;
197
198 curr = curr->GetNext();
199 }
200 while( curr != first );
201
202 return NULL;
203 }
204
205 void* wxHashTableBase::DoGet( const wxString& key, long hash ) const
206 {
207 wxASSERT( m_keyType == wxKEY_STRING );
208
209 size_t bucket = size_t(hash) % m_size;
210
211 if( m_table[bucket] == NULL )
212 return NULL;
213
214 Node *first = m_table[bucket]->GetNext(),
215 *curr = first;
216
217 do
218 {
219 if( *curr->m_key.string == key )
220 return curr->m_value;
221
222 curr = curr->GetNext();
223 }
224 while( curr != first );
225
226 return NULL;
227 }
228
229 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
230 wxHashTableBase_Node* prev )
231 {
232 if( node == m_table[bucket] )
233 m_table[bucket] = prev;
234
235 if( prev == node && prev == node->GetNext() )
236 m_table[bucket] = NULL;
237 else
238 prev->m_next = node->m_next;
239
240 DoDestroyNode( node );
241 --m_count;
242 }
243
244 void* wxHashTableBase::DoDelete( long key, long hash )
245 {
246 wxASSERT( m_keyType == wxKEY_INTEGER );
247
248 size_t bucket = size_t(hash) % m_size;
249
250 if( m_table[bucket] == NULL )
251 return NULL;
252
253 Node *first = m_table[bucket]->GetNext(),
254 *curr = first,
255 *prev = m_table[bucket];
256
257 do
258 {
259 if( curr->m_key.integer == key )
260 {
261 void* retval = curr->m_value;
262 curr->m_value = NULL;
263
264 DoUnlinkNode( bucket, curr, prev );
265 delete curr;
266
267 return retval;
268 }
269
270 prev = curr;
271 curr = curr->GetNext();
272 }
273 while( curr != first );
274
275 return NULL;
276 }
277
278 void* wxHashTableBase::DoDelete( const wxString& key, long hash )
279 {
280 wxASSERT( m_keyType == wxKEY_STRING );
281
282 size_t bucket = size_t(hash) % m_size;
283
284 if( m_table[bucket] == NULL )
285 return NULL;
286
287 Node *first = m_table[bucket]->GetNext(),
288 *curr = first,
289 *prev = m_table[bucket];
290
291 do
292 {
293 if( *curr->m_key.string == key )
294 {
295 void* retval = curr->m_value;
296 curr->m_value = NULL;
297
298 DoUnlinkNode( bucket, curr, prev );
299 delete curr;
300
301 return retval;
302 }
303
304 prev = curr;
305 curr = curr->GetNext();
306 }
307 while( curr != first );
308
309 return NULL;
310 }
311
312 long wxHashTableBase::MakeKey( const wxString& str )
313 {
314 long int_key = 0;
315
316 const wxStringCharType *p = str.wx_str();
317 while( *p )
318 int_key += *p++;
319
320 return int_key;
321 }
322
323 // ----------------------------------------------------------------------------
324 // wxHashTable
325 // ----------------------------------------------------------------------------
326
327 wxHashTable::wxHashTable( const wxHashTable& table )
328 : wxHashTableBase()
329 {
330 DoCopy( table );
331 }
332
333 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
334 {
335 Destroy();
336 DoCopy( table );
337
338 return *this;
339 }
340
341 void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
342 {
343 Create( m_keyType, m_size );
344
345 wxFAIL;
346 }
347
348 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
349 {
350 delete ((wxHashTable_Node*)node)->GetData();
351 }
352
353 void wxHashTable::GetNextNode( size_t bucketStart )
354 {
355 for( size_t i = bucketStart; i < m_size; ++i )
356 {
357 if( m_table[i] != NULL )
358 {
359 m_curr = ((Node*)m_table[i])->GetNext();
360 m_currBucket = i;
361 return;
362 }
363 }
364
365 m_curr = NULL;
366 m_currBucket = 0;
367 }
368
369 wxHashTable::Node* wxHashTable::Next()
370 {
371 if( m_curr == NULL )
372 GetNextNode( 0 );
373 else
374 {
375 m_curr = m_curr->GetNext();
376
377 if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
378 GetNextNode( m_currBucket + 1 );
379 }
380
381 return m_curr;
382 }
383