]> git.saurik.com Git - wxWidgets.git/blame_incremental - src/common/hash.cpp
always NUL-terminate log messages, even if they're longer than buffer size
[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
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
313bool wxStringHashTable::Delete(long key) const
314{
315 wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") );
316
317 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
318
319 wxArrayLong *keys = m_keys[slot];
320 if ( keys )
321 {
322 size_t count = keys->GetCount();
323 for ( size_t n = 0; n < count; n++ )
324 {
325 if ( keys->Item(n) == key )
326 {
327 keys->RemoveAt(n);
328 m_values[slot]->RemoveAt(n);
329 return TRUE;
330 }
331 }
332 }
333
334 return FALSE;
335}
336
337// ----------------------------------------------------------------------------
338// old not type safe wxHashTable
339// ----------------------------------------------------------------------------
340
341wxHashTable::wxHashTable (int the_key_type, int size)
342{
343 n = 0;
344 hash_table = (wxList**) NULL;
345 Create(the_key_type, size);
346 m_count = 0;
347 m_deleteContents = FALSE;
348/*
349 n = size;
350 current_position = -1;
351 current_node = (wxNode *) NULL;
352
353 key_type = the_key_type;
354 hash_table = new wxList *[size];
355 int i;
356 for (i = 0; i < size; i++)
357 hash_table[i] = (wxList *) NULL;
358*/
359}
360
361wxHashTable::~wxHashTable ()
362{
363 Destroy();
364}
365
366void wxHashTable::Destroy()
367{
368 if (!hash_table) return;
369 int i;
370 for (i = 0; i < n; i++)
371 if (hash_table[i])
372 delete hash_table[i];
373 delete[] hash_table;
374 hash_table = NULL;
375}
376
377bool wxHashTable::Create(int the_key_type, int size)
378{
379 Destroy();
380
381 n = size;
382 current_position = -1;
383 current_node = (wxNode *) NULL;
384
385 key_type = the_key_type;
386 hash_table = new wxList *[size];
387 int i;
388 for (i = 0; i < size; i++)
389 hash_table[i] = (wxList *) NULL;
390 return TRUE;
391}
392
393
394void wxHashTable::DoCopy(const wxHashTable& table)
395{
396 n = table.n;
397 m_count = table.m_count;
398 current_position = table.current_position;
399 current_node = NULL; // doesn't matter - Next() will reconstruct it
400 key_type = table.key_type;
401
402 hash_table = new wxList *[n];
403 for (int i = 0; i < n; i++) {
404 if (table.hash_table[i] == NULL)
405 hash_table[i] = NULL;
406 else {
407 hash_table[i] = new wxList(key_type);
408 *(hash_table[i]) = *(table.hash_table[i]);
409 }
410 }
411}
412
413void wxHashTable::Put (long key, long value, wxObject * object)
414{
415 // Should NEVER be
416 long k = (long) key;
417
418 int position = (int) (k % n);
419 if (position < 0) position = -position;
420
421 if (!hash_table[position])
422 {
423 hash_table[position] = new wxList (wxKEY_INTEGER);
424 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
425 }
426
427 hash_table[position]->Append (value, object);
428 m_count++;
429}
430
431void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
432{
433 // Should NEVER be
434 long k = (long) key;
435
436 int position = (int) (k % n);
437 if (position < 0) position = -position;
438
439 if (!hash_table[position])
440 {
441 hash_table[position] = new wxList (wxKEY_STRING);
442 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
443 }
444
445 hash_table[position]->Append (value, object);
446 m_count++;
447}
448
449void wxHashTable::Put (long key, wxObject * object)
450{
451 // Should NEVER be
452 long k = (long) key;
453
454 int position = (int) (k % n);
455 if (position < 0) position = -position;
456
457 if (!hash_table[position])
458 {
459 hash_table[position] = new wxList (wxKEY_INTEGER);
460 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
461 }
462
463 hash_table[position]->Append (k, object);
464 m_count++;
465}
466
467void wxHashTable::Put (const wxChar *key, wxObject * object)
468{
469 int position = (int) (MakeKey (key) % n);
470 if (position < 0) position = -position;
471
472 if (!hash_table[position])
473 {
474 hash_table[position] = new wxList (wxKEY_STRING);
475 if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
476 }
477
478 hash_table[position]->Append (key, object);
479 m_count++;
480}
481
482wxObject *wxHashTable::Get (long key, long value) const
483{
484 // Should NEVER be
485 long k = (long) key;
486
487 int position = (int) (k % n);
488 if (position < 0) position = -position;
489
490 if (!hash_table[position])
491 return (wxObject *) NULL;
492 else
493 {
494 wxNode *node = hash_table[position]->Find (value);
495 if (node)
496 return node->GetData ();
497 else
498 return (wxObject *) NULL;
499 }
500}
501
502wxObject *wxHashTable::Get (long key, const wxChar *value) const
503{
504 // Should NEVER be
505 long k = (long) key;
506
507 int position = (int) (k % n);
508 if (position < 0) position = -position;
509
510 if (!hash_table[position])
511 return (wxObject *) NULL;
512 else
513 {
514 wxNode *node = hash_table[position]->Find (value);
515 if (node)
516 return node->GetData ();
517 else
518 return (wxObject *) NULL;
519 }
520}
521
522wxObject *wxHashTable::Get (long key) const
523{
524 // Should NEVER be
525 long k = (long) key;
526
527 int position = (int) (k % n);
528 if (position < 0) position = -position;
529
530 if (!hash_table[position])
531 return (wxObject *) NULL;
532 else
533 {
534 wxNode *node = hash_table[position]->Find (k);
535 return node ? node->GetData () : (wxObject*)NULL;
536 }
537}
538
539wxObject *wxHashTable::Get (const wxChar *key) const
540{
541 int position = (int) (MakeKey (key) % n);
542 if (position < 0) position = -position;
543
544 if (!hash_table[position])
545 return (wxObject *) NULL;
546 else
547 {
548 wxNode *node = hash_table[position]->Find (key);
549 return node ? node->GetData () : (wxObject*)NULL;
550 }
551}
552
553wxObject *wxHashTable::Delete (long key)
554{
555 // Should NEVER be
556 long k = (long) key;
557
558 int position = (int) (k % n);
559 if (position < 0) position = -position;
560
561 if (!hash_table[position])
562 return (wxObject *) NULL;
563 else
564 {
565 wxNode *node = hash_table[position]->Find (k);
566 if (node)
567 {
568 wxObject *data = node->GetData ();
569 delete node;
570 m_count--;
571 return data;
572 }
573 else
574 return (wxObject *) NULL;
575 }
576}
577
578wxObject *wxHashTable::Delete (const wxChar *key)
579{
580 int position = (int) (MakeKey (key) % 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 (key);
588 if (node)
589 {
590 wxObject *data = node->GetData ();
591 delete node;
592 m_count--;
593 return data;
594 }
595 else
596 return (wxObject *) NULL;
597 }
598}
599
600wxObject *wxHashTable::Delete (long key, int value)
601{
602 // Should NEVER be
603 long k = (long) key;
604
605 int position = (int) (k % n);
606 if (position < 0) position = -position;
607
608 if (!hash_table[position])
609 return (wxObject *) NULL;
610 else
611 {
612 wxNode *node = hash_table[position]->Find (value);
613 if (node)
614 {
615 wxObject *data = node->GetData ();
616 delete node;
617 m_count--;
618 return data;
619 }
620 else
621 return (wxObject *) NULL;
622 }
623}
624
625wxObject *wxHashTable::Delete (long key, const wxChar *value)
626{
627 int position = (int) (key % n);
628 if (position < 0) position = -position;
629
630 if (!hash_table[position])
631 return (wxObject *) NULL;
632 else
633 {
634 wxNode *node = hash_table[position]->Find (value);
635 if (node)
636 {
637 wxObject *data = node->GetData ();
638 delete node;
639 m_count--;
640 return data;
641 }
642 else
643 return (wxObject *) NULL;
644 }
645}
646
647long wxHashTable::MakeKey (const wxChar *string) const
648{
649 long int_key = 0;
650
651 while (*string)
652 int_key += (wxUChar) *string++;
653
654 return int_key;
655}
656
657void wxHashTable::BeginFind ()
658{
659 current_position = -1;
660 current_node = (wxNode *) NULL;
661}
662
663wxNode *wxHashTable::Next ()
664{
665 wxNode *found = (wxNode *) NULL;
666 bool end = FALSE;
667 while (!end && !found)
668 {
669 if (!current_node)
670 {
671 current_position++;
672 if (current_position >= n)
673 {
674 current_position = -1;
675 current_node = (wxNode *) NULL;
676 end = TRUE;
677 }
678 else
679 {
680 if (hash_table[current_position])
681 {
682 current_node = hash_table[current_position]->GetFirst ();
683 found = current_node;
684 }
685 }
686 }
687 else
688 {
689 current_node = current_node->GetNext ();
690 found = current_node;
691 }
692 }
693 return found;
694}
695
696void wxHashTable::DeleteContents (bool flag)
697{
698 int i;
699 m_deleteContents = flag;
700 for (i = 0; i < n; i++)
701 {
702 if (hash_table[i])
703 hash_table[i]->DeleteContents (flag);
704 }
705}
706
707void wxHashTable::Clear ()
708{
709 int i;
710 if (hash_table)
711 {
712 for (i = 0; i < n; i++)
713 {
714 if (hash_table[i])
715 hash_table[i]->Clear ();
716 }
717 }
718 m_count = 0;
719}
720