]> git.saurik.com Git - wxWidgets.git/blame_incremental - src/common/hashmap.cpp
added support for range types to runtime depersister
[wxWidgets.git] / src / common / hashmap.cpp
... / ...
CommitLineData
1/////////////////////////////////////////////////////////////////////////////
2// Name: 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#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
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
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);
41
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);
58
59 return hash + (hash << 15);
60}
61#endif
62
63/* from SGI STL */
64const unsigned long _wxHashTableBase2::ms_primes[prime_count] =
65{
66 7ul, 13ul, 29ul,
67 53ul, 97ul, 193ul, 389ul, 769ul,
68 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
69 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
70 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
71 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
72 1610612741ul, 3221225473ul, 4294967291ul
73};
74
75unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
76{
77 const unsigned long* ptr = &ms_primes[0];
78 for( size_t i = 0; i < prime_count; ++i, ++ptr )
79 {
80 if( n < *ptr )
81 return *ptr;
82 }
83
84 /* someone might try to alloc a 2^32-element hash table */
85 wxFAIL_MSG( _T("hash table too big?") );
86
87 /* quiet warning */
88 return 0;
89}
90
91unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
92{
93 const unsigned long* ptr = &ms_primes[prime_count - 1];
94
95 for( size_t i = 0; i < prime_count; ++i, --ptr )
96 {
97 if( n > *ptr )
98 return *ptr;
99 }
100
101 /* quiet warning */
102 return 1;
103}
104
105void _wxHashTableBase2::DeleteNodes( size_t buckets,
106 _wxHashTable_NodeBase** table,
107 NodeDtor dtor )
108{
109 size_t i;
110
111 for( i = 0; i < buckets; ++i )
112 {
113 _wxHashTable_NodeBase* node = table[i];
114 _wxHashTable_NodeBase* tmp;
115
116 while( node )
117 {
118 tmp = node->m_nxt;
119 dtor( node );
120 node = tmp;
121 }
122 }
123
124 memset( table, 0, buckets * sizeof(void*) );
125}
126
127void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
128 size_t srcBuckets,
129 _wxHashTableBase2* dst,
130 _wxHashTable_NodeBase** dstTable,
131 size_t dstBuckets,
132 BucketFromNode func, ProcessNode proc )
133{
134 // for compatibility with wxHashTable (to avoid reimplementig it
135 // from scratch), we need to preserve the order of nodes in a
136 // source bucket when copying the table, hence, to avoid
137 // allocating an auxiliary table we use a circular list for each
138 // bucket, and we keep the *tail* of each list in dstTable[i], to
139 // be able to append nodes in O(1) time. Wen we're done copying,
140 // we adjust dstTable[i] to point at the head of the list and we
141 // break the circular list into a linear one.
142 size_t i;
143
144 for( i = 0; i < srcBuckets; ++i )
145 {
146 _wxHashTable_NodeBase* nextnode;
147
148 for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
149 {
150 size_t bucket = func( dst, node );
151
152 nextnode = node->m_nxt;
153 _wxHashTable_NodeBase* newnode = proc( node );
154 if( dstTable[bucket] )
155 {
156 newnode->m_nxt = dstTable[bucket]->m_nxt; // head of the list
157 dstTable[bucket]->m_nxt = newnode;
158 dstTable[bucket] = newnode;
159 }
160 else
161 dstTable[bucket] = newnode->m_nxt = newnode;
162 }
163 }
164
165 for( i = 0; i < dstBuckets; ++i )
166 {
167 if( dstTable[i] )
168 {
169 _wxHashTable_NodeBase* tmp = dstTable[i];
170 dstTable[i] = dstTable[i]->m_nxt;
171 tmp->m_nxt = NULL;
172 }
173 }
174}
175
176_wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
177{
178 return node;
179}
180