src/common/hashmap.cpp

   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 // 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 unsigned long wxStringHash::wxCharStringHash( const wxChar* 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 #if wxUSE_UNICODE
  42 unsigned long wxStringHash::charStringHash( const char* k )
  43 {
  44     unsigned long hash = 0;
  45
  46     while( *k )
  47     {
  48         hash += *k++;
  49         hash += (hash << 10);
  50         hash ^= (hash >> 6);
  51     }
  52     hash += (hash << 3);
  53     hash ^= (hash >> 11);
  54
  55     return hash + (hash << 15);
  56 }
  57 #endif
  58
  59 #if !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)
  60
  61 /* from SGI STL */
  62 const unsigned long _wxHashTableBase2::ms_primes[prime_count] =
  63 {
  64     7ul,          13ul,         29ul,
  65     53ul,         97ul,         193ul,       389ul,       769ul,
  66     1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  67     49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  68     1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  69     50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  70     1610612741ul, 3221225473ul, 4294967291ul
  71 };
  72
  73 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
  74 {
  75     const unsigned long* ptr = &ms_primes[0];
  76     for( size_t i = 0; i < prime_count; ++i, ++ptr )
  77     {
  78         if( n < *ptr )
  79             return *ptr;
  80     }
  81
  82     /* someone might try to alloc a 2^32-element hash table */
  83     wxFAIL_MSG( _T("hash table too big?") );
  84
  85     /* quiet warning */
  86     return 0;
  87 }
  88
  89 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
  90 {
  91     const unsigned long* ptr = &ms_primes[prime_count - 1];
  92
  93     for( size_t i = 0; i < prime_count; ++i, --ptr )
  94     {
  95         if( n > *ptr )
  96             return *ptr;
  97     }
  98
  99     /* quiet warning */
 100     return 1;
 101 }
 102
 103 void _wxHashTableBase2::DeleteNodes( size_t buckets,
 104                                      _wxHashTable_NodeBase** table,
 105                                      NodeDtor dtor )
 106 {
 107     size_t i;
 108
 109     for( i = 0; i < buckets; ++i )
 110     {
 111         _wxHashTable_NodeBase* node = table[i];
 112         _wxHashTable_NodeBase* tmp;
 113
 114         while( node )
 115         {
 116             tmp = node->m_nxt;
 117             dtor( node );
 118             node = tmp;
 119         }
 120     }
 121
 122     memset( table, 0, buckets * sizeof(void*) );
 123 }
 124
 125 void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
 126                                        size_t srcBuckets,
 127                                        _wxHashTableBase2* dst,
 128                                        _wxHashTable_NodeBase** dstTable,
 129                                        BucketFromNode func, ProcessNode proc )
 130 {
 131     for( size_t i = 0; i < srcBuckets; ++i )
 132     {
 133         _wxHashTable_NodeBase* nextnode;
 134
 135         for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
 136         {
 137             size_t bucket = func( dst, node );
 138
 139             nextnode = node->m_nxt;
 140             _wxHashTable_NodeBase* newnode = proc( node );
 141             newnode->m_nxt = dstTable[bucket];
 142             dstTable[bucket] = newnode;
 143         }
 144     }
 145 }
 146
 147 _wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
 148 {
 149     return node;
 150 }
 151
 152 #endif // !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)