From: Mattia Barbon <mbarbon@cpan.org>
Date: Wed, 20 Aug 2003 16:59:17 +0000 (+0000)
Subject:   Keep order of nodes when wxHashMap is resized; this ensures
X-Git-Url: https://git.saurik.com/wxWidgets.git/commitdiff_plain/8ae94823a3bf377614a5a67f750545217b6f6b8d

  Keep order of nodes when wxHashMap is resized; this ensures
that wxHashTable has the same behaviour when wxUSE_STL=1 as
when wxUSE_STL=0.


git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@23052 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775
---

diff --git a/include/wx/hashmap.h b/include/wx/hashmap.h
index fbabe5b8f2..0502f6a27a 100644
--- a/include/wx/hashmap.h
+++ b/include/wx/hashmap.h
@@ -70,6 +70,7 @@ protected:
     static void CopyHashTable( _wxHashTable_NodeBase** srcTable,
                                size_t srcBuckets, _wxHashTableBase2* dst,
                                _wxHashTable_NodeBase** dstTable,
+                               size_t dstBuckets,
                                BucketFromNode func, ProcessNode proc );
 
     static void** AllocTable( size_t sz )
@@ -357,7 +358,7 @@ protected: \
         m_tableBuckets = newSize; \
  \
         CopyHashTable( (_wxHashTable_NodeBase**)srcTable, srcBuckets, \
-                       this, (_wxHashTable_NodeBase**)m_table, \
+                       this, (_wxHashTable_NodeBase**)m_table, newSize, \
                        (BucketFromNode)GetBucketForNode,\
                        (ProcessNode)&DummyProcessNode ); \
         free(srcTable); \
@@ -369,7 +370,7 @@ protected: \
         ResizeTable( ht.size() ); \
         CopyHashTable( (_wxHashTable_NodeBase**)ht.m_table, ht.m_tableBuckets,\
                        (_wxHashTableBase2*)this, \
-                       (_wxHashTable_NodeBase**)m_table, \
+                       (_wxHashTable_NodeBase**)m_table, m_tableBuckets, \
                        (BucketFromNode)GetBucketForNode, \
                        (ProcessNode)CopyNode ); \
     } \
diff --git a/samples/console/console.cpp b/samples/console/console.cpp
index 42df7b135b..417daefcd4 100644
--- a/samples/console/console.cpp
+++ b/samples/console/console.cpp
@@ -1151,7 +1151,7 @@ static void TestHash()
     wxPuts(_T("*** Testing wxHashTable ***\n"));
 
     {
-        wxHashTable hash(wxKEY_INTEGER), hash2(wxKEY_STRING);
+        wxHashTable hash(wxKEY_INTEGER, 10), hash2(wxKEY_STRING);
         wxObject o;
         int i;
 
diff --git a/src/common/hashmap.cpp b/src/common/hashmap.cpp
index f86e192644..098d789ac7 100644
--- a/src/common/hashmap.cpp
+++ b/src/common/hashmap.cpp
@@ -128,9 +128,20 @@ void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
                                        size_t srcBuckets,
                                        _wxHashTableBase2* dst,
                                        _wxHashTable_NodeBase** dstTable,
+                                       size_t dstBuckets,
                                        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;
 
@@ -140,8 +151,24 @@ void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
 
             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;
         }
     }
 }