--- /dev/null
+++ libmalloc/libmalloc-283.100.6/tests/MallocBenchTest/MALLOC_BENCH/MallocBench/tree.cpp
@@ -0,0 +1,221 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "tree.h"
+#include <limits>
+#include <stdlib.h>
+#include <strings.h>
+
+#include "mbmalloc.h"
+
+namespace {
+
+struct Node {
+    void* operator new(size_t size)
+    {
+        return mbmalloc(size);
+    }
+
+    void operator delete(void* p, size_t size)
+    {
+        mbfree(p, size);
+    }
+
+    Node(Node* left, Node* right, size_t payloadSize, size_t id)
+        : m_refCount(1)
+        , m_left(left)
+        , m_right(right)
+        , m_payload(static_cast<char*>(mbmalloc(payloadSize)))
+        , m_payloadSize(payloadSize)
+        , m_id(id)
+    {
+        if (m_left)
+            m_left->ref();
+        if (m_right)
+            m_right->ref();
+        bzero(m_payload, payloadSize);
+    }
+
+    ~Node()
+    {
+        if (m_left)
+            m_left->deref();
+        if (m_right)
+            m_right->deref();
+        mbfree(m_payload, m_payloadSize);
+    }
+
+    void ref()
+    {
+        ++m_refCount;
+    }
+
+    void deref()
+    {
+        if (m_refCount == 1)
+            delete this;
+        else
+            --m_refCount;
+    }
+    
+    size_t id() { return m_id; }
+    Node* left() { return m_left; }
+    Node* right() { return m_right; }
+
+    void setLeft(Node* left)
+    {
+        left->ref();
+        if (m_left)
+            m_left->deref();
+        
+        m_left = left;
+    }
+
+    void setRight(Node* right)
+    {
+        right->ref();
+        if (m_right)
+            m_right->deref();
+        
+        m_right = right;
+    }
+
+    unsigned m_refCount;
+    Node* m_left;
+    Node* m_right;
+    char* m_payload;
+    size_t m_payloadSize;
+    size_t m_id;
+};
+
+void verify(Node* node, Node* left, Node* right)
+{
+    if (left && left->id() >= node->id())
+        abort();
+
+    if (right && right->id() <= node->id())
+        abort();
+}
+
+Node* createTree(size_t depth, size_t& counter)
+{
+    if (!depth)
+        return 0;
+
+    Node* left = createTree(depth - 1, counter);
+    size_t id = counter++;
+    Node* right = createTree(depth - 1, counter);
+
+    Node* result = new Node(left, right, ((depth * 8) & (64 - 1)) | 1, id);
+
+    verify(result, left, right);
+
+    if (left)
+        left->deref();
+    if (right)
+        right->deref();
+    return result;
+}
+
+Node* createTree(size_t depth)
+{
+    size_t counter = 0;
+    return createTree(depth, counter);
+}
+
+void churnTree(Node* node, size_t stride, size_t& counter)
+{
+    if (!node)
+        return;
+    
+    churnTree(node->left(), stride, counter);
+
+    if (node->left() && !(counter % stride)) {
+        Node* left = new Node(node->left()->left(), node->left()->right(), (counter & (64 - 1)) | 1, node->left()->id());
+        Node* right = new Node(node->right()->left(), node->right()->right(), (counter & (64 - 1)) | 1, node->right()->id());
+        node->setLeft(left);
+        node->setRight(right);
+        left->deref();
+        right->deref();
+    }
+    ++counter;
+
+    churnTree(node->right(), stride, counter);
+
+    verify(node, node->left(), node->right());
+}
+
+void churnTree(Node* tree, size_t stride)
+{
+    size_t counter;
+    churnTree(tree, stride, counter);
+}
+
+} // namespace
+
+void benchmark_tree_allocate(CommandLine& commandLine)
+{
+    size_t times = 24;
+    size_t depth = 16;
+    if (commandLine.isParallel()) {
+        times *= 4;
+        depth = 13;
+    }
+
+    for (size_t time = 0; time < times; ++time) {
+        Node* tree = createTree(depth);
+        tree->deref();
+    }
+}
+
+void benchmark_tree_traverse(CommandLine& commandLine)
+{
+    size_t times = 256;
+    size_t depth = 15;
+    if (commandLine.isParallel()) {
+        times = 512;
+        depth = 13;
+    }
+
+    Node* tree = createTree(depth);
+    for (size_t time = 0; time < times; ++time)
+        churnTree(tree, std::numeric_limits<size_t>::max()); // Reuse this to iterate and validate.
+    tree->deref();
+}
+
+void benchmark_tree_churn(CommandLine& commandLine)
+{
+    size_t times = 130;
+    size_t depth = 15;
+    if (commandLine.isParallel()) {
+        times *= 4;
+        depth = 12;
+    }
+
+    Node* tree = createTree(depth);
+    for (size_t time = 0; time < times; ++time)
+        churnTree(tree, 8);
+    tree->deref();
+}