update from Vegh Janos

[wxWidgets.git] / src / common / hashmap.cpp

diff --git a/src/common/hashmap.cpp b/src/common/hashmap.cpp
index fe3628c3295804fb3f61847df5d10cba55941f4a..098d789ac776ba88a65af76ba12e995d73cacfad 100644 (file)
--- a/src/common/hashmap.cpp
+++ b/src/common/hashmap.cpp
@@ -2,14 +2,14 @@
 // Name:        hashmap.cpp
 // Purpose:     wxHashMap implementation
 // Author:      Mattia Barbon
 // Name:        hashmap.cpp
 // Purpose:     wxHashMap implementation
 // Author:      Mattia Barbon

-// Modified by: 
+// Modified by:

 // Created:     29/01/2002
 // RCS-ID:      $Id$
 // Copyright:   (c) Mattia Barbon
 // Licence:     wxWindows licence
 /////////////////////////////////////////////////////////////////////////////
 
 // Created:     29/01/2002
 // RCS-ID:      $Id$
 // Copyright:   (c) Mattia Barbon
 // Licence:     wxWindows licence
 /////////////////////////////////////////////////////////////////////////////
 

-#ifdef __GNUG__
+#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)

 #pragma implementation "hashmap.h"
 #endif
 
 #pragma implementation "hashmap.h"
 #endif
 


@@ -22,8 +22,6 @@
 
 #include "wx/hashmap.h"
 
 
 #include "wx/hashmap.h"
 

-#include <assert.h>
-

 /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */
 /* from requirements by Colin Plumb. */
 /* (http://burtleburtle.net/bob/hash/doobs.html) */
 /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */
 /* from requirements by Colin Plumb. */
 /* (http://burtleburtle.net/bob/hash/doobs.html) */


@@ -40,7 +38,7 @@ unsigned long wxStringHash::wxCharStringHash( const wxChar* k )
     }
     hash += (hash << 3);
     hash ^= (hash >> 11);
     }
     hash += (hash << 3);
     hash ^= (hash >> 11);

-    
+

     return hash + (hash << 15);
 }
 
     return hash + (hash << 15);
 }
 


@@ -57,26 +55,26 @@ unsigned long wxStringHash::charStringHash( const char* k )
     }
     hash += (hash << 3);
     hash ^= (hash >> 11);
     }
     hash += (hash << 3);
     hash ^= (hash >> 11);

-    
+

     return hash + (hash << 15);
 }
 #endif
 
 /* from SGI STL */
     return hash + (hash << 15);
 }
 #endif
 
 /* from SGI STL */

-const unsigned long _wxHashTableBase2::s_primes[prime_count] =
+const unsigned long _wxHashTableBase2::ms_primes[prime_count] =

 {
     7ul,          13ul,         29ul,
     53ul,         97ul,         193ul,       389ul,       769ul,
     1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
     49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
     1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
 {
     7ul,          13ul,         29ul,
     53ul,         97ul,         193ul,       389ul,       769ul,
     1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
     49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
     1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,

-    50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul, 
+    50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,

     1610612741ul, 3221225473ul, 4294967291ul
 };
 
 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
 {
     1610612741ul, 3221225473ul, 4294967291ul
 };
 
 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
 {

-    const unsigned long* ptr = &s_primes[0];
+    const unsigned long* ptr = &ms_primes[0];

     for( size_t i = 0; i < prime_count; ++i, ++ptr )
     {
         if( n < *ptr )
     for( size_t i = 0; i < prime_count; ++i, ++ptr )
     {
         if( n < *ptr )


@@ -84,14 +82,15 @@ unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
     }
 
     /* someone might try to alloc a 2^32-element hash table */
     }
 
     /* someone might try to alloc a 2^32-element hash table */

-    assert(0);
+    wxFAIL_MSG( _T("hash table too big?") );
+

     /* quiet warning */
     return 0;
 }
 
 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
 {
     /* quiet warning */
     return 0;
 }
 
 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
 {

-    const unsigned long* ptr = &s_primes[prime_count - 1];
+    const unsigned long* ptr = &ms_primes[prime_count - 1];

 
     for( size_t i = 0; i < prime_count; ++i, --ptr )
     {
 
     for( size_t i = 0; i < prime_count; ++i, --ptr )
     {


@@ -129,20 +128,47 @@ void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
                                        size_t srcBuckets,
                                        _wxHashTableBase2* dst,
                                        _wxHashTable_NodeBase** dstTable,
                                        size_t srcBuckets,
                                        _wxHashTableBase2* dst,
                                        _wxHashTable_NodeBase** dstTable,

+                                       size_t dstBuckets,

                                        BucketFromNode func, ProcessNode proc )
 {
                                        BucketFromNode func, ProcessNode proc )
 {

-    for( size_t i = 0; i < srcBuckets; ++i )
+    // for compatibility with wxHashTable (to avoid reimplementig it
+    // from scratch), we need to preserve the order of nodes in a
+    // source bucket when copying the table, hence, to avoid
+    // allocating an auxiliary table we use a circular list for each
+    // bucket, and we keep the *tail* of each list in dstTable[i], to
+    // be able to append nodes in O(1) time. Wen we're done copying,
+    // we adjust dstTable[i] to point at the head of the list and we
+    // break the circular list into a linear one.
+    size_t i;
+
+    for( i = 0; i < srcBuckets; ++i )

     {
         _wxHashTable_NodeBase* nextnode;
     {
         _wxHashTable_NodeBase* nextnode;

-    
+

         for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
         {
             size_t bucket = func( dst, node );
 
             nextnode = node->m_nxt;
             _wxHashTable_NodeBase* newnode = proc( node );
         for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
         {
             size_t bucket = func( dst, node );
 
             nextnode = node->m_nxt;
             _wxHashTable_NodeBase* newnode = proc( node );

-            newnode->m_nxt = dstTable[bucket];
-            dstTable[bucket] = newnode;
+            if( dstTable[bucket] )
+            {
+                newnode->m_nxt = dstTable[bucket]->m_nxt; // head of the list
+                dstTable[bucket]->m_nxt = newnode;
+                dstTable[bucket] = newnode;
+            }
+            else
+                dstTable[bucket] = newnode->m_nxt = newnode;
+        }
+    }
+
+    for( i = 0; i < dstBuckets; ++i )
+    {
+        if( dstTable[i] )
+        {
+            _wxHashTable_NodeBase* tmp = dstTable[i];
+            dstTable[i] = dstTable[i]->m_nxt;
+            tmp->m_nxt = NULL;

         }
     }
 }
         }
     }
 }