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