added conversion to mac native filenames from local filesystem handler
[wxWidgets.git] / src / common / hash.cpp
0 / 695 (  0%)
CommitLineData
1/////////////////////////////////////////////////////////////////////////////
2// Name: 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 and Markus Holzem
9// Licence: wxWindows licence
10/////////////////////////////////////////////////////////////////////////////
11
12// ============================================================================
13// declarations
14// ============================================================================
15
16// ----------------------------------------------------------------------------
17// headers
18// ----------------------------------------------------------------------------
19
20#ifdef __GNUG__
21#pragma implementation "hash.h"
22#endif
23
24// For compilers that support precompilation, includes "wx.h".
25#include "wx/wxprec.h"
26
27#ifdef __BORLANDC__
28#pragma hdrstop
29#endif
30
31#ifndef WX_PRECOMP
32#include "wx/list.h"
33#endif
34
35#include "wx/hash.h"
36
37#include <string.h>
38#include <stdarg.h>
39
40// ----------------------------------------------------------------------------
41// wxWin macros
42// ----------------------------------------------------------------------------
43
44IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
45
46// ============================================================================
47// implementation
48// ============================================================================
49
50// ----------------------------------------------------------------------------
51// wxHashTablleBase for working with "void *" data
52// ----------------------------------------------------------------------------
53
54wxHashTableBase::wxHashTableBase()
55{
56 m_deleteContents = FALSE;
57 m_hashTable = (wxListBase **)NULL;
58 m_hashSize = 0;
59 m_count = 0;
60 m_keyType = wxKEY_NONE;
61}
62
63void wxHashTableBase::Create(wxKeyType keyType, size_t size)
64{
65 Destroy();
66
67 m_hashSize = size;
68 m_keyType = keyType;
69 m_hashTable = new wxListBase *[size];
70 for ( size_t n = 0; n < m_hashSize; n++ )
71 {
72 m_hashTable[n] = (wxListBase *) NULL;
73 }
74}
75
76void wxHashTableBase::Destroy()
77{
78 if ( m_hashTable )
79 {
80 for ( size_t n = 0; n < m_hashSize; n++ )
81 {
82 delete m_hashTable[n];
83 }
84
85 delete [] m_hashTable;
86
87 m_hashTable = (wxListBase **)NULL;
88
89 m_count = 0;
90 }
91}
92
93void wxHashTableBase::DeleteContents(bool flag)
94{
95 m_deleteContents = flag;
96 for ( size_t n = 0; n < m_hashSize; n++ )
97 {
98 if ( m_hashTable[n] )
99 {
100 m_hashTable[n]->DeleteContents(flag);
101 }
102 }
103}
104
105wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
106{
107 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
108
109 wxNodeBase *node;
110 if ( m_hashTable[slot] )
111 {
112 node = m_hashTable[slot]->Find(wxListKey(value));
113 }
114 else
115 {
116 node = (wxNodeBase *)NULL;
117 }
118
119 return node;
120}
121
122// ----------------------------------------------------------------------------
123// wxHashTableLong
124// ----------------------------------------------------------------------------
125
126wxHashTableLong::~wxHashTableLong()
127{
128 Destroy();
129}
130
131void wxHashTableLong::Init(size_t size)
132{
133 m_hashSize = size;
134 m_values = new wxArrayLong *[size];
135 m_keys = new wxArrayLong *[size];
136
137 for ( size_t n = 0; n < m_hashSize; n++ )
138 {
139 m_values[n] =
140 m_keys[n] = (wxArrayLong *)NULL;
141 }
142
143 m_count = 0;
144}
145
146void wxHashTableLong::Create(size_t size)
147{
148 Init(size);
149}
150
151void wxHashTableLong::Destroy()
152{
153 for ( size_t n = 0; n < m_hashSize; n++ )
154 {
155 delete m_values[n];
156 delete m_keys[n];
157 }
158
159 delete [] m_values;
160 delete [] m_keys;
161 m_hashSize = 0;
162 m_count = 0;
163}
164
165void wxHashTableLong::Put(long key, long value)
166{
167 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
168
169 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
170
171 if ( !m_keys[slot] )
172 {
173 m_keys[slot] = new wxArrayLong;
174 m_values[slot] = new wxArrayLong;
175 }
176
177 m_keys[slot]->Add(key);
178 m_values[slot]->Add(value);
179
180 m_count++;
181}
182
183long wxHashTableLong::Get(long key) const
184{
185 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
186
187 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
188
189 wxArrayLong *keys = m_keys[slot];
190 if ( keys )
191 {
192 size_t count = keys->GetCount();
193 for ( size_t n = 0; n < count; n++ )
194 {
195 if ( keys->Item(n) == key )
196 {
197 return m_values[slot]->Item(n);
198 }
199 }
200 }
201
202 return wxNOT_FOUND;
203}
204
205long wxHashTableLong::Delete(long key)
206{
207 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
208
209 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
210
211 wxArrayLong *keys = m_keys[slot];
212 if ( keys )
213 {
214 size_t count = keys->GetCount();
215 for ( size_t n = 0; n < count; n++ )
216 {
217 if ( keys->Item(n) == key )
218 {
219 long val = m_values[slot]->Item(n);
220
221 keys->RemoveAt(n);
222 m_values[slot]->RemoveAt(n);
223
224 m_count--;
225
226 return val;
227 }
228 }
229 }
230
231 return wxNOT_FOUND;
232}
233
234// ----------------------------------------------------------------------------
235// wxStringHashTable: more efficient than storing strings in a list
236// ----------------------------------------------------------------------------
237
238wxStringHashTable::wxStringHashTable(size_t sizeTable)
239{
240 m_keys = new wxArrayLong *[sizeTable];
241 m_values = new wxArrayString *[sizeTable];
242
243 m_hashSize = sizeTable;
244 for ( size_t n = 0; n < m_hashSize; n++ )
245 {
246 m_values[n] = (wxArrayString *)NULL;
247 m_keys[n] = (wxArrayLong *)NULL;
248 }
249}
250
251wxStringHashTable::~wxStringHashTable()
252{
253 Destroy();
254}
255
256void wxStringHashTable::Destroy()
257{
258 for ( size_t n = 0; n < m_hashSize; n++ )
259 {
260 delete m_values[n];
261 delete m_keys[n];
262 }
263
264 delete [] m_values;
265 delete [] m_keys;
266 m_hashSize = 0;
267}
268
269void wxStringHashTable::Put(long key, const wxString& value)
270{
271 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
272
273 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
274
275 if ( !m_keys[slot] )
276 {
277 m_keys[slot] = new wxArrayLong;
278 m_values[slot] = new wxArrayString;
279 }
280
281 m_keys[slot]->Add(key);
282 m_values[slot]->Add(value);
283}
284
285wxString wxStringHashTable::Get(long key, bool *wasFound) const
286{
287 wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
288
289 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
290
291 wxArrayLong *keys = m_keys[slot];
292 if ( keys )
293 {
294 size_t count = keys->GetCount();
295 for ( size_t n = 0; n < count; n++ )
296 {
297 if ( keys->Item(n) == key )
298 {
299 if ( wasFound )
300 *wasFound = TRUE;
301
302 return m_values[slot]->Item(n);
303 }
304 }
305 }
306
307 if ( wasFound )
308 *wasFound = FALSE;
309
310 return _T("");
311}
312
313// ----------------------------------------------------------------------------
314// old not type safe wxHashTable
315// ----------------------------------------------------------------------------
316
317wxHashTable::wxHashTable (int the_key_type, int size)
318{
319 n = 0;
320 hash_table = (wxList**) NULL;
321 Create(the_key_type, size);
322 m_count = 0;
323 m_deleteContents = FALSE;
324/*
325 n = size;
326 current_position = -1;
327 current_node = (wxNode *) NULL;
328
329 key_type = the_key_type;
330 hash_table = new wxList *[size];
331 int i;
332 for (i = 0; i < size; i++)
333 hash_table[i] = (wxList *) NULL;
334*/
335}
336
337wxHashTable::~wxHashTable ()
338{
339 Destroy();
340}
341
342void wxHashTable::Destroy()
343{
344 if (!hash_table) return;
345 int i;
346 for (i = 0; i < n; i++)
347 if (hash_table[i])
348 delete hash_table[i];
349 delete[] hash_table;
350 hash_table = NULL;
351}
352
353bool wxHashTable::Create(int the_key_type, int size)
354{
355 Destroy();
356
357 n = size;
358 current_position = -1;
359 current_node = (wxNode *) NULL;
360
361 key_type = the_key_type;
362 hash_table = new wxList *[size];
363 int i;
364 for (i = 0; i < size; i++)
365 hash_table[i] = (wxList *) NULL;
366 return TRUE;
367}
368
369
370void wxHashTable::DoCopy(const wxHashTable& table)
371{
372 n = table.n;
373 current_position = table.current_position;
374 current_node = NULL; // doesn't matter - Next() will reconstruct it
375 key_type = table.key_type;
376
377 hash_table = new wxList *[n];
378 for (int i = 0; i < n; i++) {
379 if (table.hash_table[i] == NULL)
380 hash_table[i] = NULL;
381 else {
382 hash_table[i] = new wxList(key_type);
383 *(hash_table[i]) = *(table.hash_table[i]);
384 }
385 }
386}
387
388void wxHashTable::Put (long key, long value, wxObject * object)
389{
390 // Should NEVER be
391 long k = (long) key;
392
393 int position = (int) (k % n);
394 if (position < 0) position = -position;
395
396 if (!hash_table[position])
397 {
398 hash_table[position] = new wxList (wxKEY_STRING);
399 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
400 }
401
402 hash_table[position]->Append (value, object);
403 m_count++;
404}
405
406void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
407{
408 // Should NEVER be
409 long k = (long) key;
410
411 int position = (int) (k % n);
412 if (position < 0) position = -position;
413
414 if (!hash_table[position])
415 {
416 hash_table[position] = new wxList (wxKEY_INTEGER);
417 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
418 }
419
420 hash_table[position]->Append (value, object);
421 m_count++;
422}
423
424void wxHashTable::Put (long key, wxObject * object)
425{
426 // Should NEVER be
427 long k = (long) key;
428
429 int position = (int) (k % n);
430 if (position < 0) position = -position;
431
432 if (!hash_table[position])
433 {
434 hash_table[position] = new wxList (wxKEY_INTEGER);
435 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
436 }
437
438 hash_table[position]->Append (k, object);
439 m_count++;
440}
441
442void wxHashTable::Put (const wxChar *key, wxObject * object)
443{
444 int position = (int) (MakeKey (key) % n);
445 if (position < 0) position = -position;
446
447 if (!hash_table[position])
448 {
449 hash_table[position] = new wxList (wxKEY_STRING);
450 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
451 }
452
453 hash_table[position]->Append (key, object);
454 m_count++;
455}
456
457wxObject *wxHashTable::Get (long key, long value) const
458{
459 // Should NEVER be
460 long k = (long) key;
461
462 int position = (int) (k % n);
463 if (position < 0) position = -position;
464
465 if (!hash_table[position])
466 return (wxObject *) NULL;
467 else
468 {
469 wxNode *node = hash_table[position]->Find (value);
470 if (node)
471 return node->Data ();
472 else
473 return (wxObject *) NULL;
474 }
475}
476
477wxObject *wxHashTable::Get (long key, const wxChar *value) const
478{
479 // Should NEVER be
480 long k = (long) key;
481
482 int position = (int) (k % n);
483 if (position < 0) position = -position;
484
485 if (!hash_table[position])
486 return (wxObject *) NULL;
487 else
488 {
489 wxNode *node = hash_table[position]->Find (value);
490 if (node)
491 return node->Data ();
492 else
493 return (wxObject *) NULL;
494 }
495}
496
497wxObject *wxHashTable::Get (long key) const
498{
499 // Should NEVER be
500 long k = (long) key;
501
502 int position = (int) (k % n);
503 if (position < 0) position = -position;
504
505 if (!hash_table[position])
506 return (wxObject *) NULL;
507 else
508 {
509 wxNode *node = hash_table[position]->Find (k);
510 return node ? node->Data () : (wxObject*)NULL;
511 }
512}
513
514wxObject *wxHashTable::Get (const wxChar *key) const
515{
516 int position = (int) (MakeKey (key) % n);
517 if (position < 0) position = -position;
518
519 if (!hash_table[position])
520 return (wxObject *) NULL;
521 else
522 {
523 wxNode *node = hash_table[position]->Find (key);
524 return node ? node->Data () : (wxObject*)NULL;
525 }
526}
527
528wxObject *wxHashTable::Delete (long key)
529{
530 // Should NEVER be
531 long k = (long) key;
532
533 int position = (int) (k % n);
534 if (position < 0) position = -position;
535
536 if (!hash_table[position])
537 return (wxObject *) NULL;
538 else
539 {
540 wxNode *node = hash_table[position]->Find (k);
541 if (node)
542 {
543 wxObject *data = node->Data ();
544 delete node;
545 m_count--;
546 return data;
547 }
548 else
549 return (wxObject *) NULL;
550 }
551}
552
553wxObject *wxHashTable::Delete (const wxChar *key)
554{
555 int position = (int) (MakeKey (key) % n);
556 if (position < 0) position = -position;
557
558 if (!hash_table[position])
559 return (wxObject *) NULL;
560 else
561 {
562 wxNode *node = hash_table[position]->Find (key);
563 if (node)
564 {
565 wxObject *data = node->Data ();
566 delete node;
567 m_count--;
568 return data;
569 }
570 else
571 return (wxObject *) NULL;
572 }
573}
574
575wxObject *wxHashTable::Delete (long key, int value)
576{
577 // Should NEVER be
578 long k = (long) key;
579
580 int position = (int) (k % n);
581 if (position < 0) position = -position;
582
583 if (!hash_table[position])
584 return (wxObject *) NULL;
585 else
586 {
587 wxNode *node = hash_table[position]->Find (value);
588 if (node)
589 {
590 wxObject *data = node->Data ();
591 delete node;
592 m_count--;
593 return data;
594 }
595 else
596 return (wxObject *) NULL;
597 }
598}
599
600wxObject *wxHashTable::Delete (long key, const wxChar *value)
601{
602 int position = (int) (key % n);
603 if (position < 0) position = -position;
604
605 if (!hash_table[position])
606 return (wxObject *) NULL;
607 else
608 {
609 wxNode *node = hash_table[position]->Find (value);
610 if (node)
611 {
612 wxObject *data = node->Data ();
613 delete node;
614 m_count--;
615 return data;
616 }
617 else
618 return (wxObject *) NULL;
619 }
620}
621
622long wxHashTable::MakeKey (const wxChar *string) const
623{
624 long int_key = 0;
625
626 while (*string)
627 int_key += (wxUChar) *string++;
628
629 return int_key;
630}
631
632void wxHashTable::BeginFind ()
633{
634 current_position = -1;
635 current_node = (wxNode *) NULL;
636}
637
638wxNode *wxHashTable::Next ()
639{
640 wxNode *found = (wxNode *) NULL;
641 bool end = FALSE;
642 while (!end && !found)
643 {
644 if (!current_node)
645 {
646 current_position++;
647 if (current_position >= n)
648 {
649 current_position = -1;
650 current_node = (wxNode *) NULL;
651 end = TRUE;
652 }
653 else
654 {
655 if (hash_table[current_position])
656 {
657 current_node = hash_table[current_position]->First ();
658 found = current_node;
659 }
660 }
661 }
662 else
663 {
664 current_node = current_node->Next ();
665 found = current_node;
666 }
667 }
668 return found;
669}
670
671void wxHashTable::DeleteContents (bool flag)
672{
673 int i;
674 m_deleteContents = flag;
675 for (i = 0; i < n; i++)
676 {
677 if (hash_table[i])
678 hash_table[i]->DeleteContents (flag);
679 }
680}
681
682void wxHashTable::Clear ()
683{
684 int i;
685 if (hash_table)
686 {
687 for (i = 0; i < n; i++)
688 {
689 if (hash_table[i])
690 hash_table[i]->Clear ();
691 }
692 }
693 m_count = 0;
694}
695