From 0508ba2a6b5806ce54ba290d9c651d09433e15a9 Mon Sep 17 00:00:00 2001 From: Mattia Barbon Date: Tue, 29 Jan 2002 21:26:57 +0000 Subject: [PATCH] New wxHashMap class. git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@13910 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- include/wx/hashmap.h | 519 ++++++++++++++++++++++++++++++++++++ samples/console/console.cpp | 149 +++++++++++ src/common/hashmap.cpp | 154 +++++++++++ 3 files changed, 822 insertions(+) create mode 100644 include/wx/hashmap.h create mode 100644 src/common/hashmap.cpp diff --git a/include/wx/hashmap.h b/include/wx/hashmap.h new file mode 100644 index 0000000000..5bc36a2874 --- /dev/null +++ b/include/wx/hashmap.h @@ -0,0 +1,519 @@ +///////////////////////////////////////////////////////////////////////////// +// Name: hashmap.cpp +// Purpose: wxHashMap class +// Author: Mattia Barbon +// Modified by: +// Created: 29/01/2002 +// RCS-ID: $Id$ +// Copyright: (c) Mattia Barbon +// Licence: wxWindows licence +///////////////////////////////////////////////////////////////////////////// + +#ifndef _WX_HASHMAP_H_ +#define _WX_HASHMAP_H_ + +#ifdef __GNUG__ +#pragma interface "hashmap.h" +#endif + +#include + +// private +struct _wxHashTable_NodeBase +{ + _wxHashTable_NodeBase() : m_nxt(0) {} + + _wxHashTable_NodeBase* m_nxt; +}; + +// private +class _wxHashTableBase2 +{ +public: + typedef void (*NodeDtor)(_wxHashTable_NodeBase*); + typedef unsigned long (*BucketFromNode)(_wxHashTableBase2*,_wxHashTable_NodeBase*); + typedef _wxHashTable_NodeBase* (*ProcessNode)(_wxHashTable_NodeBase*); +protected: + static _wxHashTable_NodeBase* DummyProcessNode(_wxHashTable_NodeBase* node); + static void DeleteNodes( size_t buckets, _wxHashTable_NodeBase** table, + NodeDtor dtor ); + static _wxHashTable_NodeBase* GetFirstNode( size_t buckets, + _wxHashTable_NodeBase** table ) + { + for( size_t i = 0; i < buckets; ++i ) + if( table[i] ) + return table[i]; + return 0; + } + + /* static const unsigned prime_count = 31; */ + enum { prime_count = 31 }; + static const unsigned long s_primes[prime_count]; + + /* returns the first prime in s_primes greater than n */ + static unsigned long GetNextPrime( unsigned long n ); + + /* returns the first prime in s_primes smaller than n */ + /* ( or s_primes[0] if n is very small ) */ + static unsigned long GetPreviousPrime( unsigned long n ); + + static void CopyHashTable( _wxHashTable_NodeBase** srcTable, + size_t srcBuckets, _wxHashTableBase2* dst, + _wxHashTable_NodeBase** dstTable, + BucketFromNode func, ProcessNode proc ); + + /* maybe just use calloc */ + static void** AllocTable( size_t size ) + { + void** table = new void*[size]; + + memset( table, 0, size * sizeof(void*) ); + + return table; + } +}; + +#define _WX_DECLARE_HASHTABLE( VALUE_T, KEY_T, HASH_T, KEY_EX_T, KEY_EQ_T, CLASSNAME, CLASSEXP, SHOULD_GROW, SHOULD_SHRINK ) \ +CLASSEXP CLASSNAME:protected _wxHashTableBase2 \ +{ \ +public: \ + typedef KEY_T key_type; \ + typedef VALUE_T value_type; \ + typedef HASH_T hasher; \ + typedef KEY_EQ_T key_equal; \ + \ + typedef size_t size_type; \ + typedef ptrdiff_t difference_type; \ + typedef value_type* pointer; \ + typedef const value_type* const_pointer; \ + typedef value_type& reference; \ + typedef const value_type& const_reference; \ + /* should these be protected? */ \ + typedef const KEY_T const_key_type; \ + typedef const VALUE_T const_mapped_type; \ +protected: \ + struct Node; \ + typedef KEY_EX_T key_extractor; \ + typedef CLASSNAME Self; \ + \ + Node** m_table; \ + size_t m_tableBuckets; \ + size_t m_items; \ + hasher m_hasher; \ + key_equal m_equals; \ + key_extractor m_getKey; \ + \ + struct Node:public _wxHashTable_NodeBase \ + { \ + public: \ + Node( const value_type& value ) \ + : m_value( value ) {} \ + Node* m_next() { return (Node*)this->m_nxt; } \ + \ + value_type m_value; \ + }; \ + \ + struct Iterator; \ + friend struct CLASSNAME::Iterator; \ + \ + static void DeleteNode( _wxHashTable_NodeBase* node ) \ + { \ + delete (Node*)node; \ + } \ + \ + /* */ \ + /* forward iterator */ \ + /* */ \ + struct Iterator \ + { \ + Node* m_node; \ + Self* m_ht; \ + \ + Iterator() : m_node(0), m_ht(0) {} \ + Iterator( Node* node, const Self* ht ) \ + : m_node(node), m_ht((Self*)ht) {} \ + bool operator ==( const Iterator& it ) const \ + { return m_node == it.m_node; } \ + bool operator !=( const Iterator& it ) const \ + { return m_node != it.m_node; } \ + protected: \ + Node* GetNextNode() \ + { \ + size_type bucket = GetBucketForNode(m_ht,m_node); \ + for( size_type i = bucket + 1; i < m_ht->m_tableBuckets; ++i ) \ + { \ + if( m_ht->m_table[i] ) \ + return m_ht->m_table[i]; \ + } \ + return 0; \ + } \ + \ + void PlusPlus() \ + { \ + Node* next = m_node->m_next(); \ + m_node = next ? next : GetNextNode(); \ + } \ + }; \ + \ +public: \ + struct iterator:public Iterator \ + { \ + iterator() : Iterator() {} \ + iterator( Node* node, Self* ht ) : Iterator( node, ht ) {} \ + iterator& operator++() { PlusPlus(); return *this; } \ + iterator operator++(int) { iterator it=*this;PlusPlus();return it; } \ + reference operator *() const { return m_node->m_value; } \ + pointer operator ->() const { return &(m_node->m_value); } \ + }; \ + \ + struct const_iterator:public Iterator \ + { \ + const_iterator() : Iterator() {} \ + const_iterator( Node* node, const Self* ht ) \ + : Iterator( node, (Self*)ht ) {} \ + const_iterator& operator++() { PlusPlus();return *this; } \ + const_iterator operator++(int) { const_iterator it=*this;PlusPlus();return it; } \ + const_reference operator *() const { return m_node->m_value; } \ + const_pointer operator ->() const { return &(m_node->m_value); } \ + }; \ + \ + CLASSNAME( size_type size = 10, const hasher& hfun = hasher(), \ + const key_equal& k_eq = key_equal(), \ + const key_extractor& k_ex = key_extractor() ) \ + : m_tableBuckets( GetNextPrime( size ) ), \ + m_items( 0 ), \ + m_hasher( hfun ), \ + m_equals( k_eq ), \ + m_getKey( k_ex ) \ + { \ + m_table = (Node**)AllocTable( m_tableBuckets ); \ + } \ + \ + CLASSNAME( const Self& ht ) \ + : m_table( 0 ), \ + m_tableBuckets( 0 ), \ + m_items( ht.m_items ), \ + m_hasher( ht.m_hasher ), \ + m_equals( ht.m_equals ), \ + m_getKey( ht.m_getKey ) \ + { \ + HashCopy( ht ); \ + } \ + \ + const Self& operator=( const Self& ht ) \ + { \ + clear(); \ + m_hasher = ht.m_hasher; \ + m_equals = ht.m_equals; \ + m_getKey = ht.m_getKey; \ + m_items = ht.m_items; \ + HashCopy( ht ); \ + return *this; \ + } \ + \ + ~CLASSNAME() \ + { \ + clear(); \ + \ + delete[] m_table; \ + } \ + \ + hasher hash_funct() { return m_hasher; } \ + key_equal key_eq() { return m_equals; } \ + \ + /* removes all elements from the hash table, but does not */ \ + /* shrink it ( perhaps it should ) */ \ + void clear() { DeleteNodes( m_tableBuckets, (_wxHashTable_NodeBase**)m_table, DeleteNode ); } \ + \ + size_type size() const { return m_items; } \ + size_type max_size() const { return size_type(-1); } \ + bool empty() const { return size() == 0; } \ + \ + const_iterator end() const { return const_iterator( 0, this ); } \ + iterator end() { return iterator( 0, this ); } \ + const_iterator begin() const \ + { return const_iterator( (Node*)GetFirstNode( m_tableBuckets, (_wxHashTable_NodeBase**)m_table ), this ); }; \ + iterator begin() \ + { return iterator( (Node*)GetFirstNode( m_tableBuckets, (_wxHashTable_NodeBase**)m_table ), this ); }; \ + \ + size_type erase( const const_key_type& key ) \ + { \ + Node** node = GetNodePtr( key ); \ + \ + if( !node ) \ + return 0; \ + \ + --m_items; \ + Node* temp = (*node)->m_next(); \ + delete *node; \ + (*node) = temp; \ + if( SHOULD_SHRINK( m_tableBuckets, m_items ) ) \ + ResizeTable( GetPreviousPrime( m_tableBuckets ) - 1 ); \ + return 1; \ + } \ + \ +protected: \ + static size_type GetBucketForNode( Self* ht, Node* node ) \ + { \ + return ht->m_hasher( ht->m_getKey( node->m_value ) ) \ + % ht->m_tableBuckets; \ + } \ + static Node* CopyNode( Node* node ) { return new Node( *node ); } \ + \ + Node* GetOrCreateNode( const value_type& value ) \ + { \ + const const_key_type& key = m_getKey( value ); \ + size_t bucket = m_hasher( key ) % m_tableBuckets; \ + Node* node = m_table[bucket]; \ + \ + while( node ) \ + { \ + if( m_equals( m_getKey( node->m_value ), key ) ) \ + return node; \ + node = node->m_next(); \ + } \ + \ + node = new Node( value ); \ + node->m_nxt = m_table[bucket]; \ + m_table[bucket] = node; \ + \ + /* must be after the node is inserted */ \ + ++m_items; \ + if( SHOULD_GROW( m_tableBuckets, m_items ) ) \ + ResizeTable( m_tableBuckets ); \ + \ + return node; \ + } \ + \ + /* returns NULL if not found */ \ + Node** GetNodePtr( const const_key_type& key ) const \ + { \ + unsigned long hash = m_hasher( key ); \ + Node** node = &m_table[hash % m_tableBuckets]; \ + \ + while( *node ) \ + { \ + if( m_equals( m_getKey( (*node)->m_value ), key ) ) \ + return node; \ + node = (Node**)&(*node)->m_nxt; \ + } \ + \ + return 0; \ + } \ + \ + /* returns NULL if not found */ \ + /* expressing it in terms of GetNodePtr is 5-8% slower :-( */ \ + Node* GetNode( const const_key_type& key ) const \ + { \ + unsigned long hash = m_hasher( key ); \ + Node* node = m_table[hash % m_tableBuckets]; \ + \ + while( node ) \ + { \ + if( m_equals( m_getKey( node->m_value ), key ) ) \ + return node; \ + node = node->m_next(); \ + } \ + \ + return 0; \ + } \ + \ + void ResizeTable( size_t newSize ) \ + { \ + newSize = GetNextPrime( newSize ); \ + Node** srcTable = m_table; \ + size_t srcBuckets = m_tableBuckets; \ + m_table = (Node**)AllocTable( newSize ); \ + m_tableBuckets = newSize; \ + \ + CopyHashTable( (_wxHashTable_NodeBase**)srcTable, srcBuckets, \ + this, (_wxHashTable_NodeBase**)m_table, \ + (BucketFromNode)&GetBucketForNode,\ + (ProcessNode)&DummyProcessNode ); \ + delete[] srcTable; \ + } \ + \ + /* this must be called _after_ m_table has been cleaned */ \ + void HashCopy( const Self& ht ) \ + { \ + ResizeTable( ht.size() ); \ + CopyHashTable( (_wxHashTable_NodeBase**)ht.m_table, ht.m_tableBuckets,\ + (_wxHashTableBase2*)this, \ + (_wxHashTable_NodeBase**)m_table, \ + (BucketFromNode)&GetBucketForNode, \ + (ProcessNode)&CopyNode ); \ + } \ +}; + +#define _WX_DECLARE_PAIR( KEY_T, VALUE_T, CLASSNAME, CLASSEXP ) \ +CLASSEXP CLASSNAME \ +{ \ +public: \ + typedef KEY_T t1; \ + typedef VALUE_T t2; \ + typedef const KEY_T const_t1; \ + typedef const VALUE_T const_t2; \ + \ + CLASSNAME( const const_t1& f, const const_t2& s ):first(t1(f)),second(t2(s)) {} \ + CLASSNAME( const const_t1& f ):first(t1(f)),second(t2()) {} \ + \ + t1 first; \ + t2 second; \ +}; + +#define _WX_DECLARE_HASH_MAP_KEY_EX( KEY_T, PAIR_T, CLASSNAME, CLASSEXP ) \ +CLASSEXP CLASSNAME \ +{ \ +public: \ + CLASSNAME() {}; \ + KEY_T operator()( PAIR_T pair ) const { return pair.first; } \ +}; + +// grow/shrink predicates +inline bool never_grow( size_t, size_t ) { return FALSE; } +inline bool never_shrink( size_t, size_t ) { return FALSE; } +inline bool grow_lf70( size_t buckets, size_t items ) +{ + return float(items)/float(buckets) >= 0.85; +} + +// integer types +class wxIntegerHash +{ +public: + wxIntegerHash() {}; + unsigned long operator()( long x ) const { return (unsigned long)x; } + unsigned long operator()( unsigned long x ) const { return x; } + unsigned long operator()( int x ) const { return (unsigned long)x; } + unsigned long operator()( unsigned int x ) const { return x; } +}; + +class wxIntegerEqual +{ +public: + wxIntegerEqual() {}; + bool operator()( long a, long b ) const { return a == b; } + bool operator()( unsigned long a, unsigned long b ) const + { return a == b; } + bool operator()( int a, int b ) const { return a == b; } + bool operator()( unsigned int a, unsigned int b ) const + { return a == b; } +}; + +// pointers +class wxPointerHash +{ +public: + wxPointerHash() {}; + unsigned long operator()( const void* k ) const + { return (unsigned long)k; } +}; + +class wxPointerEqual +{ +public: + wxPointerEqual() {}; + bool operator()( const void* a, const void* b ) const + { return a == b; } +}; + +// wxString, char*, wxChar* +class wxStringHash +{ +public: + wxStringHash() {}; + unsigned long operator()( const wxString& x ) const + { return wxCharStringHash( x.c_str() ); } + unsigned long operator()( const wxChar* x ) const + { return wxCharStringHash( x ); } + static unsigned long wxCharStringHash( const wxChar* ); +#if wxUSE_UNICODE + unsigned long operator()( const char* x ) const + { return charStringHash( x ); } + static unsigned long charStringHash( const char* ); +#endif +}; + +class wxStringEqual +{ +public: + wxStringEqual() {}; + bool operator()( const wxString& a, const wxString& b ) const + { return a == b; } + bool operator()( const wxChar* a, const wxChar* b ) const + { return wxStrcmp( a, b ) == 0; } +#if wxUSE_UNICODE + bool operator()( const char* a, const char* b ) const + { return strcmp( a, b ) == 0; } +#endif +}; + +#define _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, CLASSEXP ) \ +_WX_DECLARE_PAIR( KEY_T, VALUE_T, CLASSNAME##_wxImplementation_Pair, CLASSEXP ) \ +_WX_DECLARE_HASH_MAP_KEY_EX( KEY_T, CLASSNAME##_wxImplementation_Pair, CLASSNAME##_wxImplementation_KeyEx, CLASSEXP ) \ +_WX_DECLARE_HASHTABLE( CLASSNAME##_wxImplementation_Pair, KEY_T, HASH_T, CLASSNAME##_wxImplementation_KeyEx, KEY_EQ_T, CLASSNAME##_wxImplementation_HashTable, CLASSEXP, grow_lf70, never_shrink ) \ +CLASSEXP CLASSNAME:public CLASSNAME##_wxImplementation_HashTable \ +{ \ +public: \ + typedef VALUE_T mapped_type; \ + \ + CLASSNAME( size_type hint = 100, hasher hf = hasher(), key_equal eq = key_equal() ) \ + : CLASSNAME##_wxImplementation_HashTable( hint, hf, eq, CLASSNAME##_wxImplementation_KeyEx() ) {} \ + \ + mapped_type& operator[]( const const_key_type& key ) \ + { \ + return GetOrCreateNode( CLASSNAME##_wxImplementation_Pair( key ) )->m_value.second; \ + } \ + \ + const_iterator find( const const_key_type& key ) const \ + { \ + return const_iterator( GetNode( key ), this ); \ + } \ + \ + iterator find( const const_key_type& key ) \ + { \ + return iterator( GetNode( key ), this ); \ + } \ + \ + void insert( const value_type& v ) { (*this)[v.first] = v.second; } \ + \ + size_type erase( const key_type& k ) \ + { return CLASSNAME##_wxImplementation_HashTable::erase( k ); } \ + void erase( const iterator& it ) { erase( it->first ); } \ + void erase( const const_iterator& it ) { erase( it->first ); } \ + \ + /* count() == 0 | 1 */ \ + size_type count( const const_key_type& key ) \ + { return GetNode( key ) ? 1 : 0; } \ +}; + +// these macros are to be used in the user code +#define WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME) \ + _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, class ) + +#define WX_DECLARE_STRING_HASH_MAP( VALUE_T, CLASSNAME ) \ + _WX_DECLARE_HASH_MAP( wxString, VALUE_T, wxStringHash, wxStringEqual, \ + CLASSNAME, class ); + +#define WX_DECLARE_VOIDPTR_HASH_MAP( VALUE_T, CLASSNAME ) \ + _WX_DECLARE_HASH_MAP( void*, VALUE_T, wxPointerHash, wxPointerEqual, \ + CLASSNAME, class ); + +// and these do exactly the same thing but should be used inside the +// library +#define WX_DECLARE_EXPORTED_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME) \ + _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, class WXDLLEXPORT ) + +#define WX_DECLARE_EXPORTED_STRING_HASH_MAP( VALUE_T, CLASSNAME ) \ + _WX_DECLARE_HASH_MAP( wxString, VALUE_T, wxStringHash, wxStringEqual, \ + CLASSNAME, class WXDLLEXPORT ); + +#define WX_DECLARE_EXPORTED_VOIDPTR_HASH_MAP( VALUE_T, CLASSNAME ) \ + _WX_DECLARE_HASH_MAP( void*, VALUE_T, wxPointerHash, wxPointerEqual, \ + CLASSNAME, class WXDLLEXPORT ); + +#endif + +// Local variables: +// mode: c++ +// End: diff --git a/samples/console/console.cpp b/samples/console/console.cpp index 052ab5a0ee..a5f7349231 100644 --- a/samples/console/console.cpp +++ b/samples/console/console.cpp @@ -64,6 +64,7 @@ #define TEST_FILETIME #define TEST_FTP #define TEST_HASH + #define TEST_HASHMAP #define TEST_INFO_FUNCTIONS #define TEST_LIST #define TEST_LOCALE @@ -88,6 +89,7 @@ #undef TEST_ALL static const bool TEST_ALL = TRUE; #else + #define TEST_HASHMAP #define TEST_FILENAME static const bool TEST_ALL = FALSE; @@ -1094,6 +1096,149 @@ static void TestHash() #endif // TEST_HASH +// ---------------------------------------------------------------------------- +// wxHashMap +// ---------------------------------------------------------------------------- + +#ifdef TEST_HASHMAP + +#include "wx/hashmap.h" + +// test compilation of basic map types +WX_DECLARE_HASH_MAP( int*, int*, wxPointerHash, wxPointerEqual, myPtrHashMap ); +WX_DECLARE_HASH_MAP( long, long, wxIntegerHash, wxIntegerEqual, myLongHashMap ); +WX_DECLARE_HASH_MAP( unsigned long, unsigned, wxIntegerHash, wxIntegerEqual, + myUnsignedHashMap ); +WX_DECLARE_HASH_MAP( unsigned int, unsigned, wxIntegerHash, wxIntegerEqual, + myTestHashMap1 ); +WX_DECLARE_HASH_MAP( int, unsigned, wxIntegerHash, wxIntegerEqual, + myTestHashMap2 ); +WX_DECLARE_HASH_MAP( short, unsigned, wxIntegerHash, wxIntegerEqual, + myTestHashMap3 ); +WX_DECLARE_HASH_MAP( unsigned short, unsigned, wxIntegerHash, wxIntegerEqual, + myTestHashMap4 ); +WX_DECLARE_HASH_MAP( wxString, wxString, wxStringHash, wxStringEqual, + myStringHashMap ); + +typedef myStringHashMap::iterator Itor; + +static void TestHashMap() +{ + puts("*** Testing wxHashMap ***\n"); + myStringHashMap sh(0); // as small as possible + wxString buf; + size_t i; + const size_t count = 10000; + + // init with some data + for( i = 0; i < count; ++i ) + { + buf.Printf(wxT("%d"), i ); + sh[buf] = wxT("A") + buf + wxT("C"); + } + + // test that insertion worked + if( sh.size() != count ) + { + printf("*** ERROR: %u ELEMENTS, SHOULD BE %u ***\n", sh.size(), count); + } + + for( i = 0; i < count; ++i ) + { + buf.Printf(wxT("%d"), i ); + if( sh[buf] != wxT("A") + buf + wxT("C") ) + { + printf("*** ERROR INSERTION BROKEN! STOPPING NOW! ***\n"); + return; + } + } + + // check that iterators work + Itor it; + for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i ) + { + if( i == count ) + { + printf("*** ERROR ITERATORS DO NOT TERMINATE! STOPPING NOW! ***\n"); + return; + } + + if( it->second != sh[it->first] ) + { + printf("*** ERROR ITERATORS BROKEN! STOPPING NOW! ***\n"); + return; + } + } + + if( sh.size() != i ) + { + printf("*** ERROR: %u ELEMENTS ITERATED, SHOULD BE %u ***\n", i, count); + } + + // test copy ctor, assignment operator + myStringHashMap h1( sh ), h2( 0 ); + h2 = sh; + + for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i ) + { + if( h1[it->first] != it->second ) + { + printf("*** ERROR: COPY CTOR BROKEN %s ***\n", it->first.c_str()); + } + + if( h2[it->first] != it->second ) + { + printf("*** ERROR: OPERATOR= BROKEN %s ***\n", it->first.c_str()); + } + } + + // other tests + for( i = 0; i < count; ++i ) + { + buf.Printf(wxT("%d"), i ); + size_t sz = sh.size(); + + // test find() and erase(it) + if( i < 100 ) + { + it = sh.find( buf ); + if( it != sh.end() ) + { + sh.erase( it ); + + if( sh.find( buf ) != sh.end() ) + { + printf("*** ERROR: FOUND DELETED ELEMENT %u ***\n", i); + } + } + else + printf("*** ERROR: CANT FIND ELEMENT %u ***\n", i); + } + else + // test erase(key) + { + size_t c = sh.erase( buf ); + if( c != 1 ) + printf("*** ERROR: SHOULD RETURN 1 ***\n"); + + if( sh.find( buf ) != sh.end() ) + { + printf("*** ERROR: FOUND DELETED ELEMENT %u ***\n", i); + } + } + + // count should decrease + if( sh.size() != sz - 1 ) + { + printf("*** ERROR: COUNT DID NOT DECREASE ***\n"); + } + } + + printf("*** Finished testing wxHashMap ***\n"); +} + +#endif TEST_HASHMAP + // ---------------------------------------------------------------------------- // wxList // ---------------------------------------------------------------------------- @@ -5396,6 +5541,10 @@ int main(int argc, char **argv) TestHash(); #endif // TEST_HASH +#ifdef TEST_HASHMAP + TestHashMap(); +#endif // TEST_HASHMAP + #ifdef TEST_MIME wxLog::AddTraceMask(_T("mime")); if ( 1 ) diff --git a/src/common/hashmap.cpp b/src/common/hashmap.cpp new file mode 100644 index 0000000000..fe3628c329 --- /dev/null +++ b/src/common/hashmap.cpp @@ -0,0 +1,154 @@ +///////////////////////////////////////////////////////////////////////////// +// Name: hashmap.cpp +// Purpose: wxHashMap implementation +// Author: Mattia Barbon +// Modified by: +// Created: 29/01/2002 +// RCS-ID: $Id$ +// Copyright: (c) Mattia Barbon +// Licence: wxWindows licence +///////////////////////////////////////////////////////////////////////////// + +#ifdef __GNUG__ +#pragma implementation "hashmap.h" +#endif + +// For compilers that support precompilation, includes "wx.h". +#include "wx/wxprec.h" + +#ifdef __BORLANDC__ +#pragma hdrstop +#endif + +#include "wx/hashmap.h" + +#include + +/* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */ +/* from requirements by Colin Plumb. */ +/* (http://burtleburtle.net/bob/hash/doobs.html) */ +/* adapted from Perl sources ( hv.h ) */ +unsigned long wxStringHash::wxCharStringHash( const wxChar* k ) +{ + unsigned long hash = 0; + + while( *k ) + { + hash += *k++; + hash += (hash << 10); + hash ^= (hash >> 6); + } + hash += (hash << 3); + hash ^= (hash >> 11); + + return hash + (hash << 15); +} + +#if wxUSE_UNICODE +unsigned long wxStringHash::charStringHash( const char* k ) +{ + unsigned long hash = 0; + + while( *k ) + { + hash += *k++; + hash += (hash << 10); + hash ^= (hash >> 6); + } + hash += (hash << 3); + hash ^= (hash >> 11); + + return hash + (hash << 15); +} +#endif + +/* from SGI STL */ +const unsigned long _wxHashTableBase2::s_primes[prime_count] = +{ + 7ul, 13ul, 29ul, + 53ul, 97ul, 193ul, 389ul, 769ul, + 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, + 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, + 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, + 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, + 1610612741ul, 3221225473ul, 4294967291ul +}; + +unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n ) +{ + const unsigned long* ptr = &s_primes[0]; + for( size_t i = 0; i < prime_count; ++i, ++ptr ) + { + if( n < *ptr ) + return *ptr; + } + + /* someone might try to alloc a 2^32-element hash table */ + assert(0); + /* quiet warning */ + return 0; +} + +unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n ) +{ + const unsigned long* ptr = &s_primes[prime_count - 1]; + + for( size_t i = 0; i < prime_count; ++i, --ptr ) + { + if( n > *ptr ) + return *ptr; + } + + /* quiet warning */ + return 1; +} + +void _wxHashTableBase2::DeleteNodes( size_t buckets, + _wxHashTable_NodeBase** table, + NodeDtor dtor ) +{ + size_t i; + + for( i = 0; i < buckets; ++i ) + { + _wxHashTable_NodeBase* node = table[i]; + _wxHashTable_NodeBase* tmp; + + while( node ) + { + tmp = node->m_nxt; + dtor( node ); + node = tmp; + } + } + + memset( table, 0, buckets * sizeof(void*) ); +} + +void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable, + size_t srcBuckets, + _wxHashTableBase2* dst, + _wxHashTable_NodeBase** dstTable, + BucketFromNode func, ProcessNode proc ) +{ + for( size_t i = 0; i < srcBuckets; ++i ) + { + _wxHashTable_NodeBase* nextnode; + + for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode ) + { + size_t bucket = func( dst, node ); + + nextnode = node->m_nxt; + _wxHashTable_NodeBase* newnode = proc( node ); + newnode->m_nxt = dstTable[bucket]; + dstTable[bucket] = newnode; + } + } +} + +_wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node) +{ + return node; +} + -- 2.45.2