home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / wxos2233.zip / wxOS2-2_3_3.zip / wxWindows-2.3.3 / src / common / hashmap.cpp < prev    next >
C/C++ Source or Header  |  2002-02-03  |  4KB  |  154 lines
  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: hashmap.cpp,v 1.3 2002/02/01 14:58:55 VZ Exp $
  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. /* 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.                                        BucketFromNode func, ProcessNode proc )
  132. {
  133.     for( size_t i = 0; i < srcBuckets; ++i )
  134.     {
  135.         _wxHashTable_NodeBase* nextnode;
  136.  
  137.         for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
  138.         {
  139.             size_t bucket = func( dst, node );
  140.  
  141.             nextnode = node->m_nxt;
  142.             _wxHashTable_NodeBase* newnode = proc( node );
  143.             newnode->m_nxt = dstTable[bucket];
  144.             dstTable[bucket] = newnode;
  145.         }
  146.     }
  147. }
  148.  
  149. _wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
  150. {
  151.     return node;
  152. }
  153.  
  154.