X-Git-Url: https://git.llucax.com/software/druntime.git/blobdiff_plain/5a07183e26b7ca151959629420a83f59af5339f3..ee7c028ebdd89ffc05410551c6e4812187049279:/src/compiler/dmd/aaA.d

diff --git a/src/compiler/dmd/aaA.d b/src/compiler/dmd/aaA.d
index 3c61b9a..d5f84e7 100644
--- a/src/compiler/dmd/aaA.d
+++ b/src/compiler/dmd/aaA.d
@@ -35,8 +35,8 @@ module rt.aaA;
 
 private
 {
-    import stdc.stdarg;
-    import stdc.string;
+    import core.stdc.stdarg;
+    import core.stdc.string;
 
     enum BlkAttr : uint
     {
@@ -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.
  */