haiku.git

/*
 * Copyright 2007, Ingo Weinhold, ingo_weinhold@gmx.de.
 * All rights reserved. Distributed under the terms of the MIT license.
 */

#include <TypeConstants.h>

#include "AttributeIndexImpl.h"
#include "DebugSupport.h"
#include "Entry.h"
#include "EntryListener.h"
#include "IndexImpl.h"
#include "Misc.h"
#include "Node.h"
#include "NodeListener.h"
#include "ramfs.h"
#include "TwoKeyAVLTree.h"
#include "Volume.h"

#include <util/AutoLock.h>


// compare_integral
template<typename Key>
static inline
int
compare_integral(const Key &a, const Key &b)
{
	if (a < b)
		return -1;
	else if (a > b)
		return 1;
	return 0;
}

// compare_keys
static
int
compare_keys(const uint8 *key1, size_t length1, const uint8 *key2,
			 size_t length2, uint32 type)
{
	switch (type) {
		case B_INT32_TYPE:
			return compare_integral(*(int32*)key1, *(int32*)key2);
		case B_UINT32_TYPE:
			return compare_integral(*(uint32*)key1, *(uint32*)key2);
		case B_INT64_TYPE:
			return compare_integral(*(int64*)key1, *(int64*)key2);
		case B_UINT64_TYPE:
			return compare_integral(*(uint64*)key1, *(uint64*)key2);
		case B_FLOAT_TYPE:
			return compare_integral(*(float*)key1, *(float*)key2);
		case B_DOUBLE_TYPE:
			return compare_integral(*(double*)key1, *(double*)key2);
		case B_STRING_TYPE:
		{
			int result = strncmp((const char*)key1, (const char*)key2,
								 min(length1, length2));
			if (result == 0) {
				result = compare_integral(strnlen((const char*)key1, length1),
										  strnlen((const char*)key2, length2));
			}
			return result;
		}
	}
	return -1;
}

// PrimaryKey
class AttributeIndexImpl::PrimaryKey {
public:
	PrimaryKey(Attribute *attribute, const uint8 *theKey,
			   size_t length)
		: attribute(attribute), length(length)
			{ memcpy(key, theKey, length); }
	PrimaryKey(Attribute *attribute)
		: attribute(attribute) { attribute->GetKey(key, &length); }
	PrimaryKey(const uint8 *theKey, size_t length)
		: attribute(NULL), length(length)
			{ memcpy(key, theKey, length); }

	Attribute	*attribute;
	uint8		key[kMaxIndexKeyLength];
	size_t		length;
};

// GetPrimaryKey
class AttributeIndexImpl::GetPrimaryKey {
public:
	inline PrimaryKey operator()(Attribute *a)
	{
		return PrimaryKey(a);
	}

	inline PrimaryKey operator()(Attribute *a) const
	{
		return PrimaryKey(a);
	}
};

// PrimaryKeyCompare
class AttributeIndexImpl::PrimaryKeyCompare
{
public:
	PrimaryKeyCompare(uint32 type) : fType(type) {}

	inline int operator()(const PrimaryKey &a,
						  const PrimaryKey &b) const
	{
		if (a.attribute != NULL && a.attribute == b.attribute)
			return 0;
		return compare_keys(a.key, a.length, b.key, b.length, fType);
	}

	uint32	fType;
};

// AttributeNodeIterator
template<typename AttributeIterator>
class AttributeNodeIterator {
public:
	inline Node **GetCurrent()
	{
		if (Attribute **attribute = fIterator.GetCurrent()) {
			fNode = (*attribute)->GetNode();
			return &fNode;
		}
		return NULL;
	}

	inline Node **GetNext()
	{
		if (Attribute **attribute = fIterator.GetNext()) {
			fNode = (*attribute)->GetNode();
			return &fNode;
		}
		return NULL;
	}

	AttributeIterator	fIterator;
	Node				*fNode;
};


// AttributeTree
class AttributeIndexImpl::AttributeTree
	: public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
						   GetPrimaryKey> {
public:
	AttributeTree(uint32 type)
		: TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
						GetPrimaryKey>(PrimaryKeyCompare(type),
		  	GetPrimaryKey(), TwoKeyAVLTreeStandardCompare<Attribute*>(),
			TwoKeyAVLTreeStandardGetKey<Attribute*, Attribute*>())
	{
	}
};


// Iterator
class AttributeIndexImpl::Iterator
	: public NodeEntryIterator<
		AttributeNodeIterator<AttributeTree::Iterator> >,
	  public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
	  public NodeListener {
public:
	Iterator();
	virtual ~Iterator();

	virtual Entry *GetCurrent();
	virtual Entry *GetCurrent(uint8 *buffer, size_t *keyLength);

	virtual status_t Suspend();
	virtual status_t Resume();

	bool SetTo(AttributeIndexImpl *index, const uint8 *key, size_t length,
			   bool ignoreValue = false);
	void Unset();

	virtual void EntryRemoved(Entry *entry);
	virtual void NodeRemoved(Node *node);

private:
	typedef NodeEntryIterator<
		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;

private:
	AttributeIndexImpl	*fIndex;
};


// IteratorList
class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};


// AttributeIndexImpl

// constructor
AttributeIndexImpl::AttributeIndexImpl(Volume *volume, const char *name,
									   uint32 type, size_t keyLength)
	: AttributeIndex(volume, name, type, (keyLength > 0), keyLength),
	  fAttributes(new(nothrow) AttributeTree(type)),
	  fIterators(new(nothrow) IteratorList)
{
	if (fInitStatus == B_OK && (!fAttributes || !fIterators))
		fInitStatus = B_NO_MEMORY;
}

// destructor
AttributeIndexImpl::~AttributeIndexImpl()
{
	if (fIterators) {
		// unset the iterators
		for (Iterator *iterator = fIterators->First();
			 iterator;
			 iterator = fIterators->GetNext(iterator)) {
			iterator->SetTo(NULL, NULL, 0);
		}
		delete fIterators;
	}
	// unset all attributes and delete the tree
	if (fAttributes) {
		AttributeTree::Iterator it;
		fAttributes->GetIterator(&it);
		for (Attribute **attribute = it.GetCurrent(); attribute; it.GetNext())
			(*attribute)->SetIndex(NULL, false);
		delete fAttributes;
	}
}

// CountEntries
int32
AttributeIndexImpl::CountEntries() const
{
	return fAttributes->CountItems();
}

// Changed
status_t
AttributeIndexImpl::Changed(Attribute *attribute, const uint8 *oldKey, size_t oldLength)
{
	fVolume->AssertWriteLocked();

	status_t error = B_BAD_VALUE;
	if (attribute && attribute->GetIndex() == this) {
		// update the iterators and remove the attribute from the tree
		error = B_OK;
		if (attribute->IsInIndex()) {
			AttributeTree::Iterator it;
			Attribute **foundAttribute = fAttributes->Find(
				PrimaryKey(attribute, oldKey, oldLength), attribute, &it);
			if (foundAttribute && *foundAttribute == attribute) {
				Node *node = attribute->GetNode();
				// update the iterators
				for (Iterator *iterator = fIterators->First();
					 iterator;
					 iterator = fIterators->GetNext(iterator)) {
					if (iterator->GetCurrentNode() == node)
						iterator->NodeRemoved(node);
				}
				// remove and re-insert the attribute
				it.Remove();
				attribute->SetIndex(this, false);
			}
		}
		// re-insert the attribute
		if (fKeyLength > 0 && attribute->GetSize() != (off_t)fKeyLength) {
			ASSERT(!attribute->IsInIndex());
		} else {
			error = fAttributes->Insert(attribute);
			if (error == B_OK)
				attribute->SetIndex(this, true);
		}
	}
	return error;
}

// Added
status_t
AttributeIndexImpl::Added(Attribute *attribute)
{
	PRINT("AttributeIndex::Add(%p)\n", attribute);
	fVolume->AssertWriteLocked();

	status_t error = (attribute ? B_OK : B_BAD_VALUE);
	if (error == B_OK) {
		size_t size = attribute->GetSize();
		if (fKeyLength > 0 && size != fKeyLength) {
			attribute->SetIndex(this, false);
		} else {
			error = fAttributes->Insert(attribute);
			if (error == B_OK)
				attribute->SetIndex(this, true);
		}
	}
	return error;
}

// Removed
bool
AttributeIndexImpl::Removed(Attribute *attribute)
{
	PRINT("AttributeIndex::Removed(%p)\n", attribute);
	fVolume->AssertWriteLocked();

	if (attribute == NULL || attribute->GetIndex() != this)
		return false;

	bool result = true;
	if (attribute->IsInIndex())
		result = (fAttributes->Remove(attribute, attribute) == B_OK);
	if (result)
		attribute->SetIndex(NULL, false);
	return result;
}

// InternalGetIterator
AbstractIndexEntryIterator *
AttributeIndexImpl::InternalGetIterator()
{
	Iterator *iterator = new(nothrow) Iterator;
	if (iterator) {
		if (!iterator->SetTo(this, NULL, 0, true)) {
			delete iterator;
			iterator = NULL;
		}
	}
	return iterator;
}

// InternalFind
AbstractIndexEntryIterator *
AttributeIndexImpl::InternalFind(const uint8 *key, size_t length)
{
	if (!key || (fKeyLength > 0 && length != fKeyLength))
		return NULL;
	Iterator *iterator = new(nothrow) Iterator;
	if (iterator) {
		if (!iterator->SetTo(this, key, length)) {
			delete iterator;
			iterator = NULL;
		}
	}
	return iterator;
}

// _AddIterator
void
AttributeIndexImpl::_AddIterator(Iterator *iterator)
{
	RecursiveLocker locker(fVolume->GetAttributeIteratorLock());
	fIterators->Insert(iterator);
}

// _RemoveIterator
void
AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
{
	RecursiveLocker locker(fVolume->GetAttributeIteratorLock());
	fIterators->Remove(iterator);
}


// Iterator

// constructor
AttributeIndexImpl::Iterator::Iterator()
	: BaseClass(),
	  fIndex(NULL)
{
}

// destructor
AttributeIndexImpl::Iterator::~Iterator()
{
	SetTo(NULL, NULL, 0);
}

// GetCurrent
Entry *
AttributeIndexImpl::Iterator::GetCurrent()
{
	return BaseClass::GetCurrent();
}

// GetCurrent
Entry *
AttributeIndexImpl::Iterator::GetCurrent(uint8 *buffer, size_t *keyLength)
{
	Entry *entry = GetCurrent();
	if (entry) {
		if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
			if ((*attribute)->GetNode() == entry->GetNode()) {
				(*attribute)->GetKey(buffer, keyLength);
			} else {
				FATAL("Node of current attribute and node of current entry "
					   "differ: %" B_PRIdINO " vs. %" B_PRIdINO "\n",
					   (*attribute)->GetNode()->GetID(),
					   entry->GetNode()->GetID());
				entry = NULL;
			}
		} else {
			FATAL("We have a current entry (`%s', node: %" B_PRIdINO "), but no current "
				   "attribute.\n", entry->GetName(),
				   entry->GetNode()->GetID());
			entry = NULL;
		}
	}
	return entry;
}

// Suspend
status_t
AttributeIndexImpl::Iterator::Suspend()
{
	status_t error = BaseClass::Suspend();
	if (error == B_OK) {
		if (fNode) {
			error = fIndex->GetVolume()->AddNodeListener(this, fNode,
														 NODE_LISTEN_REMOVED);
			if (error == B_OK && fEntry) {
				error = fIndex->GetVolume()->AddEntryListener(this, fEntry,
					ENTRY_LISTEN_REMOVED);
				if (error != B_OK)
					fIndex->GetVolume()->RemoveNodeListener(this, fNode);
			}
			if (error != B_OK)
				BaseClass::Resume();
		}
	}
	return error;
}

// Resume
status_t
AttributeIndexImpl::Iterator::Resume()
{
	status_t error = BaseClass::Resume();
	if (error == B_OK) {
		if (fEntry)
			error = fIndex->GetVolume()->RemoveEntryListener(this, fEntry);
		if (fNode) {
			if (error == B_OK)
				error = fIndex->GetVolume()->RemoveNodeListener(this, fNode);
			else
				fIndex->GetVolume()->RemoveNodeListener(this, fNode);
		}
	}
	return error;
}

// SetTo
bool
AttributeIndexImpl::Iterator::SetTo(AttributeIndexImpl *index,
	const uint8 *key, size_t length, bool ignoreValue)
{
	Resume();
	Unset();
	// set the new values
	fIndex = index;
	if (fIndex)
		fIndex->_AddIterator(this);
	fInitialized = fIndex;
	// get the attribute node's first entry
	if (fIndex) {
		// get the first node
		bool found = true;
		if (ignoreValue)
			fIndex->fAttributes->GetIterator(&fIterator.fIterator);
		else {
			found = fIndex->fAttributes->FindFirst(PrimaryKey(key, length),
												   &(fIterator.fIterator));
		}
		// get the first entry
		if (found) {
			if (Node **nodeP = fIterator.GetCurrent()) {
				fNode = *nodeP;
				fEntry = fNode->GetFirstReferrer();
				if (!fEntry)
					BaseClass::GetNext();
				if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
					uint8 attrKey[kMaxIndexKeyLength];
					size_t attrKeyLength;
					(*attribute)->GetKey(attrKey, &attrKeyLength);
					if (!ignoreValue
						&& compare_keys(attrKey, attrKeyLength, key, length,
										fIndex->GetType()) != 0) {
						Unset();
					}
				}
			}
		}
	}
	return fEntry;
}

// Unset
void
AttributeIndexImpl::Iterator::Unset()
{
	if (fIndex) {
		fIndex->_RemoveIterator(this);
		fIndex = NULL;
	}
	BaseClass::Unset();
}

// EntryRemoved
void
AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
{
	Resume();
	fIsNext = BaseClass::GetNext();
	Suspend();
}

// NodeRemoved
void
AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
{
	Resume();
	fEntry = NULL;
	fIsNext = BaseClass::GetNext();
	Suspend();
}