diff options
Diffstat (limited to 'WebCore/storage/IDBKeyTree.h')
-rw-r--r-- | WebCore/storage/IDBKeyTree.h | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/WebCore/storage/IDBKeyTree.h b/WebCore/storage/IDBKeyTree.h new file mode 100644 index 0000000..0e39e77 --- /dev/null +++ b/WebCore/storage/IDBKeyTree.h @@ -0,0 +1,157 @@ +/* + * 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 + +#include "IDBKey.h" +#include <wtf/AVLTree.h> +#include <wtf/Vector.h> + +#if ENABLE(INDEXED_DATABASE) + +namespace WebCore { + +template <typename ValueType> +class IDBKeyTree : public RefCounted<IDBKeyTree<ValueType> > { +public: + static PassRefPtr<IDBKeyTree> create() + { + return adoptRef(new IDBKeyTree()); + } + ~IDBKeyTree(); + + PassRefPtr<ValueType> get(PassRefPtr<IDBKey> key); + void put(PassRefPtr<IDBKey> key, PassRefPtr<ValueType> value); + void remove(PassRefPtr<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> +PassRefPtr<ValueType> IDBKeyTree<ValueType>::get(PassRefPtr<IDBKey> prpKey) +{ + RefPtr<IDBKey> key = prpKey; + TreeNode* node = m_tree.search(key.get()); + if (!node) + return 0; + return node->value; +} + + +template <typename ValueType> +void IDBKeyTree<ValueType>::put(PassRefPtr<IDBKey> prpKey, PassRefPtr<ValueType> value) +{ + RefPtr<IDBKey> key = prpKey; + TreeNode* node = m_tree.search(key.get()); + if (!node) { + node = new TreeNode(); + node->key = key.release(); + m_tree.insert(node); + } + node->value = value; +} + +template <typename ValueType> +void IDBKeyTree<ValueType>::remove(PassRefPtr<IDBKey> prpKey) +{ + RefPtr<IDBKey> key = prpKey; + TreeNode* node = m_tree.remove(key.get()); + if (node) + delete node; +} + +} + +#endif // ENABLE(INDEXED_DATABASE) + +#endif // IDBKeyTree_h |