/*
 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Distributed under the terms of the MIT License.
 */


#include "AttributeIndex.h"

#include <new>

#include <TypeConstants.h>

#include <util/AVLTree.h>
#include <util/SinglyLinkedList.h>

#include <file_systems/QueryParserUtils.h>

#include "AttributeIndexer.h"
#include "DebugSupport.h"
#include "IndexImpl.h"
#include "Node.h"
#include "Volume.h"


struct AttributeIndexTreeKey {
        const void*     data;
        size_t          length;

        AttributeIndexTreeKey()
        {
        }

        AttributeIndexTreeKey(const void* data, size_t length)
                :
                data(data),
                length(length)
        {
        }
};


struct AttributeIndexTreeValue : AVLTreeNode {
        Node*                                   node;
        IndexedAttributeOwner*  owner;
        void*                                   attributeCookie;
        size_t                                  length;
        uint8                                   data[0];

        static AttributeIndexTreeValue* Create(IndexedAttributeOwner* owner,
                void* attributeCookie, size_t length)
        {
                AttributeIndexTreeValue* self = (AttributeIndexTreeValue*)malloc(
                        sizeof(AttributeIndexTreeValue) + length);
                if (self == NULL)
                        return NULL;

                self->owner = owner;
                self->attributeCookie = attributeCookie;
                self->length = length;
                return self;
        }

        void Delete()
        {
                free(this);
        }
};


struct AttributeIndex::TreeDefinition {
        typedef TreeKey         Key;
        typedef TreeValue       Value;

        TreeDefinition(uint32 type)
                :
                fType(type)
        {
        }

        AVLTreeNode* GetAVLTreeNode(Value* value) const
        {
                return value;
        }

        Value* GetValue(AVLTreeNode* node) const
        {
                return static_cast<Value*>(node);
        }

        int Compare(const Key& a, const Value* b) const
        {
                int cmp = QueryParser::compareKeys(fType, a.data, a.length, b->data,
                        b->length);
                if (cmp != 0)
                        return cmp;

                // The attribute value is the same. Since the tree value is the tree
                // node itself, we must not return 0, though. We consider a node-less
                // key always less than an actual tree node with the same attribute
                // value.
                return -1;
        }

        int Compare(const Value* a, const Value* b) const
        {
                if (a == b)
                        return 0;

                int cmp = QueryParser::compareKeys(fType, a->data, a->length, b->data,
                        b->length);
                if (cmp != 0)
                        return cmp;

                return a < b ? -1 : 1;
        }

private:
        uint32  fType;
};


// #pragma mark - NodeTree


struct AttributeIndex::NodeTree : public AVLTree<TreeDefinition> {
        typedef TreeValue       Node;

        NodeTree(const TreeDefinition& definition)
                :
                AVLTree<TreeDefinition>(definition)
        {
        }
};


// #pragma mark - IteratorList


class AttributeIndex::IteratorList : public SinglyLinkedList<Iterator> {};


// #pragma mark - Iterator


struct AttributeIndex::IteratorPolicy {
        typedef AttributeIndex                          Index;
        typedef TreeKey                                         Value;
        typedef AttributeIndex::NodeTree        NodeTree;
        typedef TreeValue                                       TreeNode;
        typedef IteratorPolicy                          TreePolicy;

        static NodeTree* GetNodeTree(Index* index)
        {
                return index->fNodes;
        }

        static void GetTreeNodeValue(TreeNode* node, void* buffer,
                size_t* _keyLength)
        {
                if (node->length > 0)
                        memcpy(buffer, node->data, node->length);
                *_keyLength = node->length;
        }

        static Node* GetNode(TreeNode* treeNode)
        {
                return treeNode->node;
        }

        static TreeNode* GetFirstTreeNode(Index* index)
        {
                return index->fNodes->GetIterator().Next();
        }

        static TreeNode* FindClosestTreeNode(Index* index, const Value& value)
        {
                return index->fNodes->FindClosest(value, false);
        }
};


class AttributeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>,
        public SinglyLinkedListLinkImpl<Iterator> {
public:
        virtual void                            NodeChanged(Node* node, uint32 statFields,
                                                                        const OldNodeAttributes& oldAttributes);
};


// #pragma mark - AttributeIndexer


AttributeIndexer::AttributeIndexer(AttributeIndex* index)
        :
        fIndex(index),
        fIndexName(index->Name()),
        fIndexType(index->Type()),
        fCookie(NULL)
{
}


AttributeIndexer::~AttributeIndexer()
{
}


status_t
AttributeIndexer::CreateCookie(IndexedAttributeOwner* owner,
        void* attributeCookie, uint32 attributeType, size_t attributeSize,
        void*& _data, size_t& _toRead)
{
        // check the attribute type and size
        if (attributeType != fIndexType)
                return B_ERROR;

        if (fIndex->HasFixedKeyLength()) {
                if (attributeSize != fIndex->KeyLength())
                        return B_ERROR;
        } else if (attributeSize > kMaxIndexKeyLength)
                attributeSize = kMaxIndexKeyLength;

        // create the tree value
        fCookie = AttributeIndexTreeValue::Create(owner, attributeCookie,
                attributeSize);
        if (fCookie == NULL)
                return B_NO_MEMORY;

        _data = fCookie->data;
        _toRead = attributeSize;

        return B_OK;
}


void
AttributeIndexer::DeleteCookie()
{
        fCookie->Delete();
        fCookie = NULL;
}


// #pragma mark - AttributeIndex


AttributeIndex::AttributeIndex()
        :
        Index(),
        fNodes(NULL),
        fIteratorsToUpdate(NULL),
        fIndexer(NULL)
{
}


AttributeIndex::~AttributeIndex()
{
        if (IsListening())
                fVolume->RemoveNodeListener(this);

        ASSERT(fIteratorsToUpdate->IsEmpty());

        delete fIteratorsToUpdate;
        delete fNodes;
        delete fIndexer;
}


status_t
AttributeIndex::Init(Volume* volume, const char* name,  uint32 type,
        size_t keyLength)
{
        status_t error = Index::Init(volume, name, type, keyLength > 0, keyLength);
        if (error != B_OK)
                return error;

        // TODO: Letting each attribute index be a listener is gets more expensive
        // the more attribute indices we have. Since most attribute indices are
        // rather sparse, it might be a good idea to rather let Volume iterate
        // through the actual attributes of an added node and look up and call the
        // index for each one explicitly. When removing the node, the volume would
        // iterate through the attributes again and determine based on the index
        // cookie whether an index has to be notified.
        fVolume->AddNodeListener(this, NULL);

        fNodes = new(std::nothrow) NodeTree(TreeDefinition(type));
        fIteratorsToUpdate = new(std::nothrow) IteratorList;
        fIndexer = new(std::nothrow) AttributeIndexer(this);

        if (fNodes == NULL || fIteratorsToUpdate == NULL || fIndexer == NULL)
                return B_NO_MEMORY;

        return B_OK;
}


int32
AttributeIndex::CountEntries() const
{
        return fNodes->Count();
}


void
AttributeIndex::NodeAdded(Node* node)
{
        if (node->IndexAttribute(fIndexer) != B_OK)
                return;

        TreeValue* treeValue = fIndexer->Cookie();
        treeValue->node = node;

        fNodes->Insert(treeValue);
}


void
AttributeIndex::NodeRemoved(Node* node)
{
        TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
        if (treeValue == NULL)
                return;

        treeValue->owner->UnsetIndexCookie(treeValue->attributeCookie);
        fNodes->Remove(treeValue);
}


void
AttributeIndex::NodeChanged(Node* node, uint32 statFields,
        const OldNodeAttributes& oldAttributes)
{
        IteratorList iterators;
        iterators.TakeFrom(fIteratorsToUpdate);

        TreeValue* oldTreeValue
                = (TreeValue*)oldAttributes.IndexCookieForAttribute(Name());
        TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
        if (treeValue == NULL && oldTreeValue == NULL)
                return;

        // move the iterators that point to the node to the previous node
        if (oldTreeValue != NULL) {
                for (IteratorList::ConstIterator it = iterators.GetIterator();
                                Iterator* iterator = it.Next();) {
                        iterator->NodeChangeBegin(node);
                }

                // remove the node
                fNodes->Remove(oldTreeValue);
        }

        // re-insert the node
        if (treeValue != NULL)
                fNodes->Insert(treeValue);

        // Move the iterators to the next node again. If the node hasn't changed
        // its place, they will point to it again, otherwise to the node originally
        // succeeding it.
        if (oldTreeValue != NULL) {
                for (IteratorList::ConstIterator it = iterators.GetIterator();
                                Iterator* iterator = it.Next();) {
                        iterator->NodeChangeEnd(node);
                }
        }

        // update live queries
        fVolume->UpdateLiveQueries(node, Name(), Type(),
                oldTreeValue != NULL ? oldTreeValue->data : NULL,
                oldTreeValue != NULL ? oldTreeValue->length : 0,
                treeValue != NULL ? treeValue->data : NULL,
                treeValue != NULL ? treeValue->length : 0);

        if (oldTreeValue != NULL)
                oldTreeValue->Delete();
}


AbstractIndexIterator*
AttributeIndex::InternalGetIterator()
{
        Iterator* iterator = new(std::nothrow) Iterator;
        if (iterator != NULL) {
                if (!iterator->SetTo(this, TreeKey(), true)) {
                        delete iterator;
                        iterator = NULL;
                }
        }
        return iterator;
}


AbstractIndexIterator*
AttributeIndex::InternalFind(const void* key, size_t length)
{
        if (HasFixedKeyLength() && length != KeyLength())
                return NULL;

        Iterator* iterator = new(std::nothrow) Iterator;
        if (iterator != NULL) {
                if (!iterator->SetTo(this, TreeKey(key, length))) {
                        delete iterator;
                        iterator = NULL;
                }
        }
        return iterator;
}


void
AttributeIndex::_AddIteratorToUpdate(Iterator* iterator)
{
        fIteratorsToUpdate->Add(iterator);
}


// #pragma mark - Iterator


void
AttributeIndex::Iterator::NodeChanged(Node* node, uint32 statFields,
        const OldNodeAttributes& oldAttributes)
{
        fIndex->_AddIteratorToUpdate(this);
}