/*!***************************************************************************

  module      : LVCSim_ObjectTree.hpp

  -------------------------------------------------------------------------

  responsible : IvanS

  special area: liveCache Simulator
  description : Tree for storing keys for keyed objects.

  -------------------------------------------------------------------------





    ========== licence begin  GPL
    Copyright (c) 2002-2005 SAP AG

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
    ========== licence end




*****************************************************************************/


#ifndef LVCSIM_OBJECTTREE_HPP
#define LVCSIM_OBJECTTREE_HPP

/*===========================================================================*
 *  INCLUDES                                                                 *
 *===========================================================================*/

#include "LVCSimulator/LVCSim_ObjectHandle.hpp"
#include "LVCSimulator/LVCSim_CheckpointIO.hpp"
#include "SAPDBCommon/SAPDB_MemCopyMove.hpp"

#ifdef _WIN32
#pragma warning( disable : 4786 )
#endif

#include <map>

/*===========================================================================*
 *  CLASSES, STRUCTURES, TYPES, UNIONS ...                                   *
 *===========================================================================*/


class LVCSim_BinaryKey {
public:
    size_t	size;
    char	data[1];

    void *operator new(size_t sz1, size_t sz2)
    {
        return new char[sz1 + sz2 - 1];
    }

    void operator delete(void *p, size_t sz2)
    {
        delete[] (char*) p;
    }

    void *operator new(size_t sz, void *ptr)
    {
        return ptr;
    }

    void operator delete(void *ptr, void *ptr2)
    {
    }

    void operator delete(void *ptr)
    {
        delete[] (char*) ptr;
    }

    static inline size_t contSize(size_t datasz);

    LVCSim_BinaryKey(LVCSim_CheckpointReader &i, size_t _size) : size(_size)
	{
        i.read(&data[0], size);
	}

    LVCSim_BinaryKey(const void *_data, size_t _size) : size(_size)
	{
		SAPDB_MemCopyNoCheck(data, _data, _size);
	}

	LVCSim_BinaryKey(const LVCSim_BinaryKey &x)
	{
        size = x.size;
        SAPDB_MemCopyNoCheck(data, x.data, size);
	}

	~LVCSim_BinaryKey()
	{
	}

	int compare(const LVCSim_BinaryKey &x) const;
	int compare(const void *key, size_t keySize) const;

	void writeToStream(LVCSim_CheckpointWriter &o) const
	{
		o.write(&size, sizeof(size));
		o.write(&data[0], size);
	}
};

inline size_t LVCSim_BinaryKey::contSize(size_t datasz)
{
    return sizeof(LVCSim_BinaryKey) + datasz - 1;
}

class LVCSim_BinaryKeyRef {
public:
    LVCSim_BinaryKeyRef() : m_ref(NULL) {}
    LVCSim_BinaryKeyRef(const LVCSim_BinaryKey *k) : m_ref(k) {}
    LVCSim_BinaryKeyRef(const LVCSim_BinaryKey &k) : m_ref(&k) {}

    const LVCSim_BinaryKey *m_ref;
};

/*! 
  Class: LVCSim_ObjectTree
  
  Description: Object tree for storing object keys.
*/

class LVCSim_ObjectTree  
{
protected:
	class Locker {
	private:
		LVCSim_ObjectTree	*tree;
		LVCSim_SID			sid;
	public:
		Locker(LVCSim_ObjectTree *tree, LVCSim_SID sid);
		~Locker();
	};

	friend class LVCSim_ObjectTreeNode;
	friend class Locker;

	RTESync_Spinlock			lock;
	volatile LVCSim_SID			locksid;
	int							lockcnt;

	typedef LVCSIM_STD map<LVCSim_BinaryKeyRef, class LVCSim_ObjectTreeNode*>	tree_type;
	typedef LVCSIM_STD pair<const LVCSim_BinaryKeyRef, class LVCSim_ObjectTreeNode*>	pair_type;

	tree_type					tree;

public:
	LVCSim_ObjectTree();
	LVCSim_ObjectTree(LVCSim_CheckpointReader &i, LVCSim_OIDAllocator *alloc);
	~LVCSim_ObjectTree();

	/*!
		function:	addKey

		description: adds a new key into the tree, if possible

		arguments:
			key	 [in]	pointer to key data
			size [in]	key size
			node [in]	object handle
			sid	 [in]	sid - sink ID

		returns: true, if there was no conflict, false otherwise
		prototypes: 2
	*/
	bool addKey(const void *key, size_t size, LVCSim_ObjectHandle *node, LVCSim_SID sid);
	bool addKey(const LVCSim_BinaryKey *key, LVCSim_ObjectHandle *node, LVCSim_SID sid);

	/*!
		function:	delKey

		description: removes a key from the tree that points to given object node
		arguments:
			node [in]	object handle to be removed from the tree
			sid	 [in]	sink ID of current TX
	*/
	void delKey(LVCSim_ObjectHandle *node, LVCSim_SID sid);

	/*!
		function:	firstKey

		description: return the handle of first visible object in the tree

		arguments:
			sid	[in]	sink ID

		returns:	pointer to the first object handle in the tree or NULL
	*/
	LVCSim_ObjectHandle *firstKey(LVCSim_SID sid);

	/*!
		function:	lastKey

		description: return the handle of last visible object in the tree

		arguments:
			sid	[in]	sink ID

		returns:	pointer to the last object handle in the tree or NULL

    since: PTS 1119480
	*/
	LVCSim_ObjectHandle *lastKey(LVCSim_SID sid);

	/*!
		function:	findKey

		description: return the first matching key

		arguments:
			key		[in]	key data
			size	[in]	key size
			sid		[in]	sink ID
			partial	[in]	if true, partial match will be returned (>= key)

		returns:	pointer to the first matching visible object or NULL
	*/
	LVCSim_ObjectHandle *findKey(const void *key, size_t size, LVCSim_SID sid, bool partial = true, 
                               OmsIterDirection direction = OMS_ASCENDING);

	/*!
		function:	nextKey

		description: return the next matching key

		arguments:
			node		[in]	pointer to an object in the tree
			sid			[in]	sink ID

		returns:	pointer to the next matching visible object or NULL
	*/
	LVCSim_ObjectHandle *nextKey(const LVCSim_ObjectHandle *node, LVCSim_SID sid);

	/*!
		function:	prevKey    

		description: return the previous matching key

		arguments:
			node		[in]	pointer to an object in the tree
			sid			[in]	sink ID

		returns:	pointer to the next matching visible object or NULL

    since PTS 1119480
	*/
	LVCSim_ObjectHandle *prevKey(const LVCSim_ObjectHandle *node, LVCSim_SID sid);

	/*!
		function:	compareKey

		description: compare node key with supplied key

		arguments:
			node	[in]	pointer to an object in the tree
			key		[in]	pointer to the key
			keySize	[in]	size of the key

		returns:	-1, 0 or 1 when node key is <, == or > as given key
	*/
	int compareKey(const LVCSim_ObjectHandle *node, const void *key, size_t keySize);

	void writeToStream(LVCSim_CheckpointWriter &o) const;
};

/*! endclass: LVCSim_ObjectTree */


#endif
