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 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
  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 /* 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 )
  30 {
  31     unsigned long hash = 0;
  32
  33     while( *k )
  34     {
  35         hash += *k++;
  36         hash += (hash << 10);
  37         hash ^= (hash >> 6);
  38     }
  39     hash += (hash << 3);
  40     hash ^= (hash >> 11);
  41
  42     return hash + (hash << 15);
  43 }
  44
  45 #if wxUSE_UNICODE
  46 unsigned long wxStringHash::charStringHash( const char* k )
  47 {
  48     unsigned long hash = 0;
  49
  50     while( *k )
  51     {
  52         hash += *k++;
  53         hash += (hash << 10);
  54         hash ^= (hash >> 6);
  55     }
  56     hash += (hash << 3);
  57     hash ^= (hash >> 11);
  58
  59     return hash + (hash << 15);
  60 }
  61 #endif
  62
  63 /* from SGI STL */
  64 const unsigned long _wxHashTableBase2::ms_primes[prime_count] =
  65 {
  66     7ul,          13ul,         29ul,
  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
  73 };
  74
  75 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
  76 {
  77     const unsigned long* ptr = &ms_primes[0];
  78     for( size_t i = 0; i < prime_count; ++i, ++ptr )
  79     {
  80         if( n < *ptr )
  81             return *ptr;
  82     }
  83
  84     /* someone might try to alloc a 2^32-element hash table */
  85     wxFAIL_MSG( _T("hash table too big?") );
  86
  87     /* quiet warning */
  88     return 0;
  89 }
  90
  91 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
  92 {
  93     const unsigned long* ptr = &ms_primes[prime_count - 1];
  94
  95     for( size_t i = 0; i < prime_count; ++i, --ptr )
  96     {
  97         if( n > *ptr )
  98             return *ptr;
  99     }
 100
 101     /* quiet warning */
 102     return 1;
 103 }
 104
 105 void _wxHashTableBase2::DeleteNodes( size_t buckets,
 106                                      _wxHashTable_NodeBase** table,
 107                                      NodeDtor dtor )
 108 {
 109     size_t i;
 110
 111     for( i = 0; i < buckets; ++i )
 112     {
 113         _wxHashTable_NodeBase* node = table[i];
 114         _wxHashTable_NodeBase* tmp;
 115
 116         while( node )
 117         {
 118             tmp = node->m_nxt;
 119             dtor( node );
 120             node = tmp;
 121         }
 122     }
 123
 124     memset( table, 0, buckets * sizeof(void*) );
 125 }
 126
 127 void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
 128                                        size_t srcBuckets,
 129                                        _wxHashTableBase2* dst,
 130                                        _wxHashTable_NodeBase** dstTable,
 131                                        size_t dstBuckets,
 132                                        BucketFromNode func, ProcessNode proc )
 133 {
 134     // for compatibility with wxHashTable (to avoid reimplementig it
 135     // from scratch), we need to preserve the order of nodes in a
 136     // source bucket when copying the table, hence, to avoid
 137     // allocating an auxiliary table we use a circular list for each
 138     // bucket, and we keep the *tail* of each list in dstTable[i], to
 139     // be able to append nodes in O(1) time. Wen we're done copying,
 140     // we adjust dstTable[i] to point at the head of the list and we
 141     // break the circular list into a linear one.
 142     size_t i;
 143
 144     for( i = 0; i < srcBuckets; ++i )
 145     {
 146         _wxHashTable_NodeBase* nextnode;
 147
 148         for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
 149         {
 150             size_t bucket = func( dst, node );
 151
 152             nextnode = node->m_nxt;
 153             _wxHashTable_NodeBase* newnode = proc( node );
 154             if( dstTable[bucket] )
 155             {
 156                 newnode->m_nxt = dstTable[bucket]->m_nxt; // head of the list
 157                 dstTable[bucket]->m_nxt = newnode;
 158                 dstTable[bucket] = newnode;
 159             }
 160             else
 161                 dstTable[bucket] = newnode->m_nxt = newnode;
 162         }
 163     }
 164
 165     for( i = 0; i < dstBuckets; ++i )
 166     {
 167         if( dstTable[i] )
 168         {
 169             _wxHashTable_NodeBase* tmp = dstTable[i];
 170             dstTable[i] = dstTable[i]->m_nxt;
 171             tmp->m_nxt = NULL;
 172         }
 173     }
 174 }
 175
 176 _wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
 177 {
 178     return node;
 179 }
 180