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