]> git.saurik.com Git - wxWidgets.git/blame - src/common/hashmap.cpp
added possibility to throw different objects and crash directly from the main frame...
[wxWidgets.git] / src / common / hashmap.cpp
CommitLineData
0508ba2a
MB
1/////////////////////////////////////////////////////////////////////////////
2// Name: hashmap.cpp
3// Purpose: wxHashMap implementation
4// Author: Mattia Barbon
376e1129 5// Modified by:
0508ba2a
MB
6// Created: 29/01/2002
7// RCS-ID: $Id$
8// Copyright: (c) Mattia Barbon
65571936 9// Licence: wxWindows licence
0508ba2a
MB
10/////////////////////////////////////////////////////////////////////////////
11
14f355c2 12#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
0508ba2a
MB
13#pragma implementation "hashmap.h"
14#endif
15
16// For compilers that support precompilation, includes "wx.h".
17#include "wx/wxprec.h"
18
19#ifdef __BORLANDC__
20#pragma hdrstop
21#endif
22
23#include "wx/hashmap.h"
24
0508ba2a
MB
25/* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */
26/* from requirements by Colin Plumb. */
27/* (http://burtleburtle.net/bob/hash/doobs.html) */
28/* adapted from Perl sources ( hv.h ) */
29unsigned long wxStringHash::wxCharStringHash( const wxChar* k )
30{
31 unsigned long hash = 0;
32
33 while( *k )
34 {
35 hash += *k++;
36 hash += (hash << 10);
37 hash ^= (hash >> 6);
38 }
39 hash += (hash << 3);
40 hash ^= (hash >> 11);
e05c8fa7 41
0508ba2a
MB
42 return hash + (hash << 15);
43}
44
45#if wxUSE_UNICODE
46unsigned long wxStringHash::charStringHash( const char* k )
47{
48 unsigned long hash = 0;
49
50 while( *k )
51 {
52 hash += *k++;
53 hash += (hash << 10);
54 hash ^= (hash >> 6);
55 }
56 hash += (hash << 3);
57 hash ^= (hash >> 11);
e05c8fa7 58
0508ba2a
MB
59 return hash + (hash << 15);
60}
61#endif
62
bdcade0a
MB
63#if !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)
64
0508ba2a 65/* from SGI STL */
376e1129 66const unsigned long _wxHashTableBase2::ms_primes[prime_count] =
0508ba2a
MB
67{
68 7ul, 13ul, 29ul,
69 53ul, 97ul, 193ul, 389ul, 769ul,
70 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
71 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
72 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
e05c8fa7 73 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
0508ba2a
MB
74 1610612741ul, 3221225473ul, 4294967291ul
75};
76
77unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
78{
376e1129 79 const unsigned long* ptr = &ms_primes[0];
0508ba2a
MB
80 for( size_t i = 0; i < prime_count; ++i, ++ptr )
81 {
82 if( n < *ptr )
83 return *ptr;
84 }
85
86 /* someone might try to alloc a 2^32-element hash table */
376e1129
VZ
87 wxFAIL_MSG( _T("hash table too big?") );
88
0508ba2a
MB
89 /* quiet warning */
90 return 0;
91}
92
93unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
94{
376e1129 95 const unsigned long* ptr = &ms_primes[prime_count - 1];
0508ba2a
MB
96
97 for( size_t i = 0; i < prime_count; ++i, --ptr )
98 {
99 if( n > *ptr )
100 return *ptr;
101 }
102
103 /* quiet warning */
104 return 1;
105}
106
107void _wxHashTableBase2::DeleteNodes( size_t buckets,
108 _wxHashTable_NodeBase** table,
109 NodeDtor dtor )
110{
111 size_t i;
112
113 for( i = 0; i < buckets; ++i )
114 {
115 _wxHashTable_NodeBase* node = table[i];
116 _wxHashTable_NodeBase* tmp;
117
118 while( node )
119 {
120 tmp = node->m_nxt;
121 dtor( node );
122 node = tmp;
123 }
124 }
125
126 memset( table, 0, buckets * sizeof(void*) );
127}
128
129void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
130 size_t srcBuckets,
131 _wxHashTableBase2* dst,
132 _wxHashTable_NodeBase** dstTable,
133 BucketFromNode func, ProcessNode proc )
134{
1a6d9c76 135 for( size_t i = 0; i < srcBuckets; ++i )
0508ba2a
MB
136 {
137 _wxHashTable_NodeBase* nextnode;
e05c8fa7 138
0508ba2a
MB
139 for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
140 {
141 size_t bucket = func( dst, node );
142
143 nextnode = node->m_nxt;
144 _wxHashTable_NodeBase* newnode = proc( node );
1a6d9c76
MB
145 newnode->m_nxt = dstTable[bucket];
146 dstTable[bucket] = newnode;
0508ba2a
MB
147 }
148 }
149}
150
151_wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
152{
153 return node;
154}
155
bdcade0a 156#endif // !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)