/**************************************************************************
 * Source Id :
 *
 * $Id: btree.h,v 1.1 2001/04/03 20:10:25 aleksandras Exp $
 *-------------------------------------------------------------------------
 * Project Notes :
 *
 *  Diamond Base
 *  ============
 *      A solid database implementation, spurred on by the continuing
 *  Metal (Lead) Base saga.
 *
 *  Project Team :
 *        A. Davison
 *        K. Lentin
 *        D. Platt
 *
 *	Project Commenced : 05-02-1993
 *
 *-------------------------------------------------------------------------
 *  Module Notes :
 *
 *  The bTree code. Implements a B+Tree (sort of)
 *
 *
 *  Original Author : Daz & Kev
 *
 **************************************************************************/

#ifndef __DB_BTREE_H__
#define __DB_BTREE_H__

#include <diamond/defs.h>
#include <diamond/rserv.h>
#include <diamond/object.h>

// The header data that the btree stores at the start of its revServer

struct bTreeHead {
	int32 keyLen;
	bucketId rootBucket;
	bTreeHead(void) { rootBucket = -2; }
	void invalidate(void) { rootBucket = -2; }
};

// The query structure for bTree. The constructor is so that the class
// that uses this can compile. All its structures/subclasses must have
// constructors.

struct bTreeQuery {
	pKeyType	key;	// Current key, used if unsafe
	bucket*		bptr;	// Current bucket
	int32		idx;	// The index into bptr, used if !unsafe
	bool		unsafe;	// Has someone made a change to influence this query
	bool		used;	// Query used?
	bTreeQuery() {}		// Keep the compiler happy
};

// The bTree class. It inherits recServer to store its data.
// Each recServer record is a bucket in the bTree.

class bTree : public recServer
{
	bTreeHead head;
	int32 indNum; // Which index to quote when asking for comparisons.
	bTreeQuery query[MAX_QUERY];

	void findInternal(
		const	DIA_object 		&searchObject,
		const	bucketId 	rootBucket,
				bool		&Found,
				bucket		**bptr,
				size_t		&ptrIdx,
		const	int			fixParent = 0
	);
	bucket* fetchBucket(const bucketId idx);
	bucket* createNewBucket(const e_leaf leaf, const bucketId parentId, const bucketId nextBucket, const bucketId prevBucket);
	void writeBucket(const bucket* bptr);
	void loseBucket(const bucketId id);
	void traverse(bucket* b, const bool intonly,ostream &out=cerr);
	void initQueries(void);
	bool internalCheckIntegrity(const bucketId buck,ostream &out=cerr);
	void checkHead(void);

public:
#if 0
	dbError status;
	inline dbError bterror(dbError err) { return (status = err); };
#endif

	const char* verStr(void) const;
	bTree(const char *name, const size_t bucketSize, const size_t keyLen, const size_t newIndNum=0); // create constructor
	bTree(const char *name, const int32 newIndNum=0);  // open constructor
	bTree(void) {} // Blank constructor. Use with care.
	dbError add(DIA_object &newObject, const int32 extPtr);
	dbError del(const DIA_object &delObject);
//	dbError find(DIA_object &findObject, int32 &extPtr); // see qFind
	bool checkIntegrity(ostream &out=cerr);
	bool inBTree(const DIA_object &theObject, size_t& idx);
	void flushCache(void)
		{
			recServer::flushCache();
			head.invalidate();
		}
	inline bool inBTree(const DIA_object &theObject)
		{
			size_t temp;
			return inBTree(theObject, temp);
		}
	dbError qBegin(int32& qNum);
	dbError qEnd(const int32 qNum);
	dbError qFirst(const int32 qNum, DIA_object &theObject, int32 &extPtr); // Act as peek
	dbError qLast(const int32 qNum, DIA_object &theObject, int32 &extPtr); // Act as peek
	dbError qFind(const int32 qNum, const DIA_object& findObject, int32& extPtr);
	dbError qNext(const int32 qNum, DIA_object &theObject, int32 &extPtr);
	dbError qPrev(const int32 qNum, DIA_object &theObject, int32 &extPtr);
	dbError qPeekNext(const int32 qNum, DIA_object &theObject, int32 &extPtr);
	dbError qPeekPrev(const int32 qNum, DIA_object &theObject, int32 &extPtr);

	void dump(const bool intonly = false,ostream &out=cerr);

private:
	dbError insertInternal(bucket*& bptr, DIA_object &newObj, int32 extPtr);
};

#endif

//////////////////////////////////////////////////////////////////////////
// Revision History:
//
// $Log: btree.h,v $
// Revision 1.1  2001/04/03 20:10:25  aleksandras
// big one 3.1 (comments later)
//
// Revision 1.30  1996/03/29  13:57:43  daz
// small fixes to eliminate explicit i/o from library.
//
// Revision 1.29  1996/03/05  21:42:35  dmb
// Preliminary modifications to get Dos/Windows 0.4 portability.
//
// Revision 1.28  1996/02/01  22:41:02  dmb
// long->int32
// ,
//
// Revision 1.28  1996/02/01  22:41:02  dmb
// long->int32
// ,
//
// Revision 1.27  1995/10/04  02:08:08  davison
// Changed references to objects to DIA_objects to prevent namespace clashes.
//
// Revision 1.26  1994/09/30 08:36:59  kevinl
// Added head check for flushed data.
//
// Revision 1.25  1994/05/15  05:01:32  kevinl
// Type fixups.
//
// Revision 1.24  1994/04/29  15:02:51  kevinl
// Added a tab
//
// Revision 1.23  1994/02/25  03:11:01  darrenp
// More changes to make DOS binaries compatible with other systems.
//
// Revision 1.22  1994/02/03  05:50:31  kevinl
// Moved include files to diamond/ and fixed HAVE_MALLOC_H
//
// Revision 1.21  1993/12/23  22:58:48  kevinl
// dbErr uses dbString, autoconf stuff, moved logs, added const and size_t
//
// Revision 1.20  1993/06/23  05:21:22  kevinl
// Mallocs are now in angular brackets
//
// Revision 1.19  1993/05/11  14:44:50  kevinl
// Added version number output
//
// Revision 1.18  1993/05/01  14:27:04  kevinl
// Stripped ;'s off inlines
// Got rid of ints
// Made inBTree two functions
//
// Revision 1.17  1993/04/29  07:00:03  kevinl
// Added lsoeBucket
//
// Revision 1.16  1993/04/24  14:31:27  kevinl
// Comments
// Some small fixups and error code changes.
//
// Revision 1.15  1993/04/19  15:50:03  kevinl
// fixParent is no longer boolean. now int
//
// Revision 1.14  1993/04/15  07:55:24  kevinl
// Traverse & dump now have intonly mode
// inBTree takes optional reference to return spot where found.
//
// Revision 1.13  1993/04/08  07:23:40  kevinl
// insertInternal now takes refernce to bucket* so delete on outside works
//
// Revision 1.12  1993/03/28  13:58:23  kevinl
// Added inBTree
//
// Revision 1.11  1993/03/28  10:35:26  kevinl
// Modifed for dbErr
//
// Revision 1.10  1993/03/28  19:07:10  davison
// Deleted pError member.
//
// Revision 1.9  1993/03/26  06:16:38  darrenp
// standardized error codes.
//
// Revision 1.8  1993/03/24  06:15:58  kevinl
// Added pError and bterror members
//
// Revision 1.7  1993/03/17  14:26:31  kevinl
// Fixed up include files and mutiple include protection.
//
// Revision 1.6  1993/03/15  13:56:27  kevinl
// Put query stuff (back) in and finished all of it.
//
// Revision 1.5  1993/03/08  00:30:15  kevinl
// Added (and ifdef'd out) beginnings of query code
// Added integrity checks.
//
// Revision 1.4  1993/02/18  05:40:16  kevinl
// Added query transaction methods
//
// Revision 1.3  1993/02/17  12:14:02  darrenp
// Fixed definition of findInternal
//
// Revision 1.2  1993/02/13  00:54:07  kevinl
// new members added for insertInternal, createNewBucket, writeBucket
// added dbError enum for error codes
//
//////////////////////////////////////////////////////////////////////////
