1 /////////////////////////////////////////////////////////////////////////////
3 // Purpose: wxHashMap implementation
4 // Author: Mattia Barbon
8 // Copyright: (c) Mattia Barbon
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
13 #pragma implementation "hashmap.h"
16 // For compilers that support precompilation, includes "wx.h".
17 #include "wx/wxprec.h"
23 #include "wx/hashmap.h"
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 ) */
29 unsigned long wxStringHash::wxCharStringHash( const wxChar
* k
)
31 unsigned long hash
= 0;
42 return hash
+ (hash
<< 15);
46 unsigned long wxStringHash::charStringHash( const char* k
)
48 unsigned long hash
= 0;
59 return hash
+ (hash
<< 15);
64 const unsigned long _wxHashTableBase2::ms_primes
[prime_count
] =
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
75 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n
)
77 const unsigned long* ptr
= &ms_primes
[0];
78 for( size_t i
= 0; i
< prime_count
; ++i
, ++ptr
)
84 /* someone might try to alloc a 2^32-element hash table */
85 wxFAIL_MSG( _T("hash table too big?") );
91 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n
)
93 const unsigned long* ptr
= &ms_primes
[prime_count
- 1];
95 for( size_t i
= 0; i
< prime_count
; ++i
, --ptr
)
105 void _wxHashTableBase2::DeleteNodes( size_t buckets
,
106 _wxHashTable_NodeBase
** table
,
111 for( i
= 0; i
< buckets
; ++i
)
113 _wxHashTable_NodeBase
* node
= table
[i
];
114 _wxHashTable_NodeBase
* tmp
;
124 memset( table
, 0, buckets
* sizeof(void*) );
127 void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase
** srcTable
,
129 _wxHashTableBase2
* dst
,
130 _wxHashTable_NodeBase
** dstTable
,
131 BucketFromNode func
, ProcessNode proc
)
133 for( size_t i
= 0; i
< srcBuckets
; ++i
)
135 _wxHashTable_NodeBase
* nextnode
;
137 for( _wxHashTable_NodeBase
* node
= srcTable
[i
]; node
; node
= nextnode
)
139 size_t bucket
= func( dst
, node
);
141 nextnode
= node
->m_nxt
;
142 _wxHashTable_NodeBase
* newnode
= proc( node
);
143 newnode
->m_nxt
= dstTable
[bucket
];
144 dstTable
[bucket
] = newnode
;
149 _wxHashTable_NodeBase
* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase
* node
)