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