]> git.saurik.com Git - wxWidgets.git/blame_incremental - src/common/hash.cpp
added English and English US for testing
[wxWidgets.git] / src / common / hash.cpp
... / ...
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::Destroy()
147{
148 for ( size_t n = 0; n < m_hashSize; n++ )
149 {
150 delete m_values[n];
151 delete m_keys[n];
152 }
153
154 delete [] m_values;
155 delete [] m_keys;
156 m_hashSize = 0;
157 m_count = 0;
158}
159
160void wxHashTableLong::Put(long key, long value)
161{
162 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
163
164 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
165
166 if ( !m_keys[slot] )
167 {
168 m_keys[slot] = new wxArrayLong;
169 m_values[slot] = new wxArrayLong;
170 }
171
172 m_keys[slot]->Add(key);
173 m_values[slot]->Add(value);
174
175 m_count++;
176}
177
178long wxHashTableLong::Get(long key) const
179{
180 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
181
182 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
183
184 wxArrayLong *keys = m_keys[slot];
185 if ( keys )
186 {
187 size_t count = keys->GetCount();
188 for ( size_t n = 0; n < count; n++ )
189 {
190 if ( keys->Item(n) == key )
191 {
192 return m_values[slot]->Item(n);
193 }
194 }
195 }
196
197 return wxNOT_FOUND;
198}
199
200long wxHashTableLong::Delete(long key)
201{
202 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
203
204 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
205
206 wxArrayLong *keys = m_keys[slot];
207 if ( keys )
208 {
209 size_t count = keys->GetCount();
210 for ( size_t n = 0; n < count; n++ )
211 {
212 if ( keys->Item(n) == key )
213 {
214 long val = m_values[slot]->Item(n);
215
216 keys->RemoveAt(n);
217 m_values[slot]->RemoveAt(n);
218
219 m_count--;
220
221 return val;
222 }
223 }
224 }
225
226 return wxNOT_FOUND;
227}
228
229// ----------------------------------------------------------------------------
230// wxStringHashTable: more efficient than storing strings in a list
231// ----------------------------------------------------------------------------
232
233wxStringHashTable::wxStringHashTable(size_t sizeTable)
234{
235 m_keys = new wxArrayLong *[sizeTable];
236 m_values = new wxArrayString *[sizeTable];
237
238 m_hashSize = sizeTable;
239 for ( size_t n = 0; n < m_hashSize; n++ )
240 {
241 m_values[n] = (wxArrayString *)NULL;
242 m_keys[n] = (wxArrayLong *)NULL;
243 }
244}
245
246wxStringHashTable::~wxStringHashTable()
247{
248 Destroy();
249}
250
251void wxStringHashTable::Destroy()
252{
253 for ( size_t n = 0; n < m_hashSize; n++ )
254 {
255 delete m_values[n];
256 delete m_keys[n];
257 }
258
259 delete [] m_values;
260 delete [] m_keys;
261 m_hashSize = 0;
262}
263
264void wxStringHashTable::Put(long key, const wxString& value)
265{
266 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
267
268 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
269
270 if ( !m_keys[slot] )
271 {
272 m_keys[slot] = new wxArrayLong;
273 m_values[slot] = new wxArrayString;
274 }
275
276 m_keys[slot]->Add(key);
277 m_values[slot]->Add(value);
278}
279
280wxString wxStringHashTable::Get(long key, bool *wasFound) const
281{
282 wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
283
284 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
285
286 wxArrayLong *keys = m_keys[slot];
287 if ( keys )
288 {
289 size_t count = keys->GetCount();
290 for ( size_t n = 0; n < count; n++ )
291 {
292 if ( keys->Item(n) == key )
293 {
294 if ( wasFound )
295 *wasFound = TRUE;
296
297 return m_values[slot]->Item(n);
298 }
299 }
300 }
301
302 if ( wasFound )
303 *wasFound = FALSE;
304
305 return _T("");
306}
307
308// ----------------------------------------------------------------------------
309// old not type safe wxHashTable
310// ----------------------------------------------------------------------------
311
312wxHashTable::wxHashTable (int the_key_type, int size)
313{
314 n = 0;
315 hash_table = (wxList**) NULL;
316 Create(the_key_type, size);
317 m_count = 0;
318 m_deleteContents = FALSE;
319/*
320 n = size;
321 current_position = -1;
322 current_node = (wxNode *) NULL;
323
324 key_type = the_key_type;
325 hash_table = new wxList *[size];
326 int i;
327 for (i = 0; i < size; i++)
328 hash_table[i] = (wxList *) NULL;
329*/
330}
331
332wxHashTable::~wxHashTable ()
333{
334 Destroy();
335}
336
337void wxHashTable::Destroy()
338{
339 if (!hash_table) return;
340 int i;
341 for (i = 0; i < n; i++)
342 if (hash_table[i])
343 delete hash_table[i];
344 delete[] hash_table;
345 hash_table = NULL;
346}
347
348bool wxHashTable::Create(int the_key_type, int size)
349{
350 Destroy();
351
352 n = size;
353 current_position = -1;
354 current_node = (wxNode *) NULL;
355
356 key_type = the_key_type;
357 hash_table = new wxList *[size];
358 int i;
359 for (i = 0; i < size; i++)
360 hash_table[i] = (wxList *) NULL;
361 return TRUE;
362}
363
364
365void wxHashTable::DoCopy(const wxHashTable& table)
366{
367 n = table.n;
368 current_position = table.current_position;
369 current_node = NULL; // doesn't matter - Next() will reconstruct it
370 key_type = table.key_type;
371
372 hash_table = new wxList *[n];
373 for (int i = 0; i < n; i++) {
374 if (table.hash_table[i] == NULL)
375 hash_table[i] = NULL;
376 else {
377 hash_table[i] = new wxList(key_type);
378 *(hash_table[i]) = *(table.hash_table[i]);
379 }
380 }
381}
382
383void wxHashTable::Put (long key, long value, wxObject * object)
384{
385 // Should NEVER be
386 long k = (long) key;
387
388 int position = (int) (k % n);
389 if (position < 0) position = -position;
390
391 if (!hash_table[position])
392 {
393 hash_table[position] = new wxList (wxKEY_INTEGER);
394 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
395 }
396
397 hash_table[position]->Append (value, object);
398 m_count++;
399}
400
401void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
402{
403 // Should NEVER be
404 long k = (long) key;
405
406 int position = (int) (k % n);
407 if (position < 0) position = -position;
408
409 if (!hash_table[position])
410 {
411 hash_table[position] = new wxList (wxKEY_INTEGER);
412 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
413 }
414
415 hash_table[position]->Append (value, object);
416 m_count++;
417}
418
419void wxHashTable::Put (long key, wxObject * object)
420{
421 // Should NEVER be
422 long k = (long) key;
423
424 int position = (int) (k % n);
425 if (position < 0) position = -position;
426
427 if (!hash_table[position])
428 {
429 hash_table[position] = new wxList (wxKEY_INTEGER);
430 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
431 }
432
433 hash_table[position]->Append (k, object);
434 m_count++;
435}
436
437void wxHashTable::Put (const wxChar *key, wxObject * object)
438{
439 int position = (int) (MakeKey (key) % n);
440 if (position < 0) position = -position;
441
442 if (!hash_table[position])
443 {
444 hash_table[position] = new wxList (wxKEY_STRING);
445 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
446 }
447
448 hash_table[position]->Append (key, object);
449 m_count++;
450}
451
452wxObject *wxHashTable::Get (long key, long value) const
453{
454 // Should NEVER be
455 long k = (long) key;
456
457 int position = (int) (k % n);
458 if (position < 0) position = -position;
459
460 if (!hash_table[position])
461 return (wxObject *) NULL;
462 else
463 {
464 wxNode *node = hash_table[position]->Find (value);
465 if (node)
466 return node->Data ();
467 else
468 return (wxObject *) NULL;
469 }
470}
471
472wxObject *wxHashTable::Get (long key, const wxChar *value) const
473{
474 // Should NEVER be
475 long k = (long) key;
476
477 int position = (int) (k % n);
478 if (position < 0) position = -position;
479
480 if (!hash_table[position])
481 return (wxObject *) NULL;
482 else
483 {
484 wxNode *node = hash_table[position]->Find (value);
485 if (node)
486 return node->Data ();
487 else
488 return (wxObject *) NULL;
489 }
490}
491
492wxObject *wxHashTable::Get (long key) const
493{
494 // Should NEVER be
495 long k = (long) key;
496
497 int position = (int) (k % n);
498 if (position < 0) position = -position;
499
500 if (!hash_table[position])
501 return (wxObject *) NULL;
502 else
503 {
504 wxNode *node = hash_table[position]->Find (k);
505 return node ? node->Data () : (wxObject*)NULL;
506 }
507}
508
509wxObject *wxHashTable::Get (const wxChar *key) const
510{
511 int position = (int) (MakeKey (key) % n);
512 if (position < 0) position = -position;
513
514 if (!hash_table[position])
515 return (wxObject *) NULL;
516 else
517 {
518 wxNode *node = hash_table[position]->Find (key);
519 return node ? node->Data () : (wxObject*)NULL;
520 }
521}
522
523wxObject *wxHashTable::Delete (long key)
524{
525 // Should NEVER be
526 long k = (long) key;
527
528 int position = (int) (k % n);
529 if (position < 0) position = -position;
530
531 if (!hash_table[position])
532 return (wxObject *) NULL;
533 else
534 {
535 wxNode *node = hash_table[position]->Find (k);
536 if (node)
537 {
538 wxObject *data = node->Data ();
539 delete node;
540 m_count--;
541 return data;
542 }
543 else
544 return (wxObject *) NULL;
545 }
546}
547
548wxObject *wxHashTable::Delete (const wxChar *key)
549{
550 int position = (int) (MakeKey (key) % n);
551 if (position < 0) position = -position;
552
553 if (!hash_table[position])
554 return (wxObject *) NULL;
555 else
556 {
557 wxNode *node = hash_table[position]->Find (key);
558 if (node)
559 {
560 wxObject *data = node->Data ();
561 delete node;
562 m_count--;
563 return data;
564 }
565 else
566 return (wxObject *) NULL;
567 }
568}
569
570wxObject *wxHashTable::Delete (long key, int value)
571{
572 // Should NEVER be
573 long k = (long) key;
574
575 int position = (int) (k % n);
576 if (position < 0) position = -position;
577
578 if (!hash_table[position])
579 return (wxObject *) NULL;
580 else
581 {
582 wxNode *node = hash_table[position]->Find (value);
583 if (node)
584 {
585 wxObject *data = node->Data ();
586 delete node;
587 m_count--;
588 return data;
589 }
590 else
591 return (wxObject *) NULL;
592 }
593}
594
595wxObject *wxHashTable::Delete (long key, const wxChar *value)
596{
597 int position = (int) (key % n);
598 if (position < 0) position = -position;
599
600 if (!hash_table[position])
601 return (wxObject *) NULL;
602 else
603 {
604 wxNode *node = hash_table[position]->Find (value);
605 if (node)
606 {
607 wxObject *data = node->Data ();
608 delete node;
609 m_count--;
610 return data;
611 }
612 else
613 return (wxObject *) NULL;
614 }
615}
616
617long wxHashTable::MakeKey (const wxChar *string) const
618{
619 long int_key = 0;
620
621 while (*string)
622 int_key += (wxUChar) *string++;
623
624 return int_key;
625}
626
627void wxHashTable::BeginFind ()
628{
629 current_position = -1;
630 current_node = (wxNode *) NULL;
631}
632
633wxNode *wxHashTable::Next ()
634{
635 wxNode *found = (wxNode *) NULL;
636 bool end = FALSE;
637 while (!end && !found)
638 {
639 if (!current_node)
640 {
641 current_position++;
642 if (current_position >= n)
643 {
644 current_position = -1;
645 current_node = (wxNode *) NULL;
646 end = TRUE;
647 }
648 else
649 {
650 if (hash_table[current_position])
651 {
652 current_node = hash_table[current_position]->First ();
653 found = current_node;
654 }
655 }
656 }
657 else
658 {
659 current_node = current_node->Next ();
660 found = current_node;
661 }
662 }
663 return found;
664}
665
666void wxHashTable::DeleteContents (bool flag)
667{
668 int i;
669 m_deleteContents = flag;
670 for (i = 0; i < n; i++)
671 {
672 if (hash_table[i])
673 hash_table[i]->DeleteContents (flag);
674 }
675}
676
677void wxHashTable::Clear ()
678{
679 int i;
680 for (i = 0; i < n; i++)
681 {
682 if (hash_table[i])
683 hash_table[i]->Clear ();
684 }
685 m_count = 0;
686}
687