--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/storage/IDBKeyTree.h	Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,153 @@
+/*
+ * Copyright (C) 2010 Google 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 AND ITS CONTRIBUTORS "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 OR ITS 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.
+ */
+
+#ifndef IDBKeyTree_h
+#define IDBKeyTree_h
+
+#if ENABLE(INDEXED_DATABASE)
+
+#include "IDBKey.h"
+#include <wtf/AVLTree.h>
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+template <typename ValueType>
+class IDBKeyTree : public RefCounted<IDBKeyTree<ValueType> > {
+public:
+    static PassRefPtr<IDBKeyTree> create()
+    {
+        return adoptRef(new IDBKeyTree());
+    }
+    ~IDBKeyTree();
+
+    ValueType* get(IDBKey* key);
+    void put(IDBKey* key, ValueType* value);
+    void remove(IDBKey* key);
+
+private:
+    struct TreeNode {
+        RefPtr<ValueType> value;
+        RefPtr<IDBKey> key;
+
+        TreeNode* less;
+        TreeNode* greater;
+        int balanceFactor;
+    };
+
+    struct AVLTreeAbstractor {
+        typedef TreeNode* handle;
+        typedef size_t size;
+        typedef IDBKey* key;
+
+        handle get_less(handle h) { return h->less; }
+        void set_less(handle h, handle lh) { h->less = lh; }
+        handle get_greater(handle h) { return h->greater; }
+        void set_greater(handle h, handle gh) { h->greater = gh; }
+        int get_balance_factor(handle h) { return h->balanceFactor; }
+        void set_balance_factor(handle h, int bf) { h->balanceFactor = bf; }
+
+        static handle null() { return 0; }
+
+        int compare_key_key(key va, key vb);
+        int compare_key_node(key k, handle h) { return compare_key_key(k, h->key.get()); }
+        int compare_node_node(handle h1, handle h2) { return compare_key_key(h1->key.get(), h2->key.get()); }
+    };
+
+    IDBKeyTree();
+
+    typedef WTF::AVLTree<AVLTreeAbstractor> TreeType;
+    TreeType m_tree;
+};
+
+template <typename ValueType>
+IDBKeyTree<ValueType>::IDBKeyTree()
+{
+}
+
+template <typename ValueType>
+IDBKeyTree<ValueType>::~IDBKeyTree()
+{
+    typename TreeType::Iterator iter;
+    iter.start_iter_least(m_tree);
+    for (; *iter; ++iter)
+        delete *iter;
+    m_tree.purge();
+}
+
+template <typename ValueType>
+int IDBKeyTree<ValueType>::AVLTreeAbstractor::compare_key_key(key va, key vb)
+{
+    if (va->type() != vb->type())
+        return vb->type() - va->type();
+
+    switch (va->type()) {
+    case IDBKey::NullType:
+        return 0;
+    case IDBKey::NumberType:
+        return vb->number() - va->number();
+    case IDBKey::StringType:
+        return codePointCompare(va->string(), vb->string());
+    // FIXME: Handle dates.  Oh, and test this thoroughly.
+    default:
+        ASSERT_NOT_REACHED();
+        return 0;
+    }
+}
+
+template <typename ValueType>
+ValueType* IDBKeyTree<ValueType>::get(IDBKey* key)
+{
+    TreeNode* node = m_tree.search(key);
+    if (!node)
+        return 0;
+    return node->value.get();
+}
+
+template <typename ValueType>
+void IDBKeyTree<ValueType>::put(IDBKey* key, ValueType* value)
+{
+    TreeNode* node = m_tree.search(key);
+    if (!node) {
+        node = new TreeNode();
+        node->key = key;
+        m_tree.insert(node);
+    }
+    node->value = value;
+}
+
+template <typename ValueType>
+void IDBKeyTree<ValueType>::remove(IDBKey* key)
+{
+    TreeNode* node = m_tree.remove(key);
+    if (node)
+        delete node;
+}
+
+}
+
+#endif // ENABLE(INDEXED_DATABASE)
+
+#endif // IDBKeyTree_h