Merged in changes from Phobos SVN.

[software/druntime.git] / src / compiler / dmd / aaA.d

diff --git a/src/compiler/dmd/aaA.d b/src/compiler/dmd/aaA.d
index 3c61b9add708be0d56e6cf7d5425bfade6743ff0..6d7ecf93ec65fb1f5f2ff57b79b19aeb0a6d3190 100644 (file)
--- a/src/compiler/dmd/aaA.d
+++ b/src/compiler/dmd/aaA.d
@@ -592,11 +592,58 @@ body
         }
 
         *paa.a = newb;
+        _aaBalance(paa);
     }
     return (*paa).a;
 }
 
+/********************************************
+ * Balance an array.
+ */
 
+void _aaBalance(AA* paa)
+{
+    //printf("_aaBalance()\n");
+    if (paa.a)
+    {
+        aaA*[16] tmp;
+        aaA*[] array = tmp;
+        auto aa = paa.a;
+        foreach (j, e; aa.b)
+        {
+            /* Temporarily store contents of bucket in array[]
+             */
+            size_t k = 0;
+            void addToArray(aaA* e)
+            {
+                while (e)
+                {   addToArray(e.left);
+                    if (k == array.length)
+                        array.length = array.length * 2;
+                    array[k++] = e;
+                    e = e.right;
+                }
+            }
+            addToArray(e);
+            /* The contents of the bucket are now sorted into array[].
+             * Rebuild the tree.
+             */
+            void buildTree(aaA** p, size_t x1, size_t x2)
+            {
+                if (x1 >= x2)
+                    *p = null;
+                else
+                {   auto mid = (x1 + x2) >> 1;
+                    *p = array[mid];
+                    buildTree(&(*p).left, x1, mid);
+                    buildTree(&(*p).right, mid + 1, x2);
+                }
+            }
+            auto p = &aa.b[j];
+            buildTree(p, 0, k);
+        }
+    }
+}
 /********************************************
  * Produce array of N byte keys from aa.
  */