/**************************************************************************
 * Source Id :
 *
 * $Id: bucket.cpp,v 1.3 2001/04/20 10:15:01 georgetasker 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 :
 *
 *  Bucket Module
 *
 *  Original Author : Andy & Kev (with inspiration from Daz)
 *
 **************************************************************************/

// FOR NOW::
// For compilers that support precompilation, includes "wx.h".
#include "wx/wxprec.h"

#ifdef __BORLANDC__
    #pragma hdrstop
#endif

#include <diamond/dbconf.h>

#if HAVE_MALLOC_H && !MALLOC_H_INCLUDED
extern "C" {
#include <malloc.h>
}
#define MALLOC_H_INCLUDED 1
#endif
#include <diamond/bucket.h>
#include <diamond/object.h>
#include <iostream.h>

const char* bucket::verStr(void) const
{
	return "$Id: bucket.cpp,v 1.3 2001/04/20 10:15:01 georgetasker Exp $";
}

// The constructor.

bucket::bucket(const bucketId newId, const size_t newKeyLength, 
	const int32 newSize, const e_leaf newLeaf, const bucketId newParentId, 
	const bucketId newNextBucket, const bucketId newPrevBucket, 
	const int32 newKeyNum
)
{

// Allocate the data for the bucket and grab a pointer to the header data.

	// Size is rounded up to the size of a int32 for allocation purposes
	// only. This is array of int32s to satisfy potential alignment problems
	// with casting this to a headerData*

	data = new int32[((size = newSize)+sizeof(int32)-1) / sizeof(int32)];

	headerData *h = (headerData*)data;

// Store the characteristics of the bucket

	h->leaf = newLeaf;
	h->parentId = newParentId;
	h->nextBucket = newNextBucket;
	h->prevBucket = newPrevBucket;
	h->activeKeys = 0;

	id = newId;

	keyLength = newKeyLength;
	keyNum = newKeyNum;

	// Each tuple contains a key, the length of which is defined by
	// the object and stored by the constructor, and a long link.

	// Round keyLength up to a multiple of 4

	myTupleSize = ((keyLength+3)&(~3)) + sizeof(int32);

// The number of keys is as many tuples as will fit in the bucket, taking
// the header and initial pointer into account.

	numKeys = (size - headerSize() - sizeof(int32)) / tupleSize();
}

bucket::~bucket()
{
	delete data;
}

// A little info for the programmer if s/he desires
void
bucket::info(void) const
{ 
#if defined(DEBUG)
	cout << "HeaderSize = " << dec << headerSize() << endl
		<< "TupleSize = " << tupleSize() << endl
		<< "ActiveKeys = " << header()->activeKeys << endl
		<< "Previous = " << header()->prevBucket << "    Next = " << header()->nextBucket << endl;
#endif
}

// Used during debugging. NB Key is assumed to start with an int32

void
bucket::dump(void) const
{
#if defined(DEBUG)
	cout << "Bucket Dump" << endl;

	cout << "Link: " << getLink(0) << endl;
	for (size_t i = 1; i <= (uint32)header()->activeKeys; i++)
		cout << "Data: " << hex << *((int32 *)getKeyAddr(i)) << endl
		     << "Link: " << dec << getLink(i) << endl;
#endif
}

// Actually return the data in the link itself

bucketId
bucket::getLink(const size_t pos) const
{
	bucketId link;
	copyMem(getLinkAddr(pos), (char*)&link, sizeof(bucketId));
	return link;
}

// Store a new link

void
bucket::setLink(const size_t pos, const bucketId link)
{
	copyMem(&link, getLinkAddr(pos), sizeof(bucketId));
}

// The key in theObject and the link are inserted into the bucket in the
// appropriate spot.

void
bucket::insert(const DIA_object& theObject, const int32 link)
{
	size_t pos = 0;

// This returns the position where theObject should be inserted in the bucket.

	searchForKey(theObject,pos);

// Shift the existing data along one.

	pKeyType tempKey = getKeyAddr(pos+1); // to stop it being called twice
	copyMem(
		tempKey,
		getKeyAddr(pos+2),
		(size_t)((header()->activeKeys-pos)*tupleSize()));

// Now put the key in.

	pKeyType key = theObject.getKey(keyNum);
	copyMem(key, tempKey, (size_t)keyLength);
	delete key;

// Now the Link.
	setLink(pos+1, link);

// Now we have one more...

	header()->activeKeys++;
}

// Delete a key from a bucket

dbError
bucket::del(const size_t pos)
{
	// Can't delete an entry that is not there.
	// Are there pos in the bucket?

	if (pos > (uint32)header()->activeKeys)
		return dbErr(db_range);

	// All after pos roll over and one falls out...
	// NB For Inner nodes, we move starting at a link, not a key. This is
	// so that the less than link at the start of the bucket is maintained
	// accurate. The number to move is therefore 1 tuple less plus the extra
	// link.

	if (header()->leaf)
		copyMem(getKeyAddr(pos+1), getKeyAddr(pos), (size_t)((header()->activeKeys - pos) * tupleSize()));
	else
		if ((uint32)header()->activeKeys > pos)
			copyMem(getLinkAddr(pos+1), getLinkAddr(pos), (size_t)((header()->activeKeys - pos - 1) * tupleSize() + sizeof(int32)));

	// And there was one less entry in the bucket.
	header()->activeKeys--;

	return dbErr(db_ok);
}

// Find a key in the bucket or return where it should go.
// If the key is not found then return the entry before where it would be
// If the key is found, return the spot where it is

// This function has been replaced by the binary chop version below.

#if 0
bool
bucket::searchForKey(const DIA_object& theObject, int32& ptr)
{
	int32 i=1;

	while (i <= header()->activeKeys) // NB pairs are numbered 1 to n
	{
		pKeyType key = getKeyAddr(i);
		if (theObject.isLessThan(key, keyNum) )
		{
			ptr = i-1; // Needs to be inserted before i
			return false;
		}
		else if (theObject.isEqual(key, keyNum) )
		{
			ptr = i;
			return true;
		}
		i++;
	}
	ptr=i-1;
	return false;
}
#endif

bool
bucket::searchForKey(const DIA_object& theObject, size_t& ptr) const
{
	// Don't make these size_t since the binary search in some cases may
	// set them to -1.
	int32 high = header()->activeKeys;
	int32 low = 1; // NB pairs are numbered 1 to n

	while (low <= high)
	{
		int32 mid = (low + high) / 2;
		pKeyType key = getKeyAddr((size_t)mid);
		if (theObject.isEqual(key, keyNum) )
		{
			ptr = (size_t)mid;
			return true;
		}
		if (theObject.isLessThan(key, keyNum) )
			high = mid - 1;
		else
			low = mid + 1;
	}
	// OK, now high is less than low. The key must therefore go after
	// position high

	ptr = (size_t)high;
	return false;
}

// Search a bucket for a particular link and return it's position. This is
// used during delete, when trying to find where, in it's parent, a deleted
// bucket was positioned.

void
bucket::findIndex(size_t& ind, bool& found) const
{
	found = false;
	for (size_t i=0; i <= (uint32)header()->activeKeys; i++)
		if ((uint32)getLink(i) == ind)
		{
			found = true;
			ind = i;
			break;
		}
}

// When a bucket is full, it contents need to be split into two buckets.
// The calling function creates the new bucket and fixes the forward and
// backward links.
// In the case of a leaf bucket, the first key in the new bucket is returned
// in 'out'. In the case of an inner node, the key deleted is returned.

void
bucket::sploosh(bucket* newBucket, pKeyType in, 
	pKeyType out, const DIA_object& theObject, const int32 link)
{
	in = in;

	size_t newKeyPos=0;
	int32 delFromPos=(int32)header()->activeKeys/2+1;
//	pKeyType medianKey = getKeyAddr(header()->activeKeys / 2);

// This loop is a little ugly! It determines where the key must be inserted.

	size_t i;
	for(i=1; (!newKeyPos) && i<=(uint32)header()->activeKeys;i++)
	{
		// is in < current key ?
		if (theObject.isLessThan(getKeyAddr(i), keyNum)) // && (newKeyPos!=0))
			newKeyPos = i;
	}
	if (!newKeyPos)
		newKeyPos = i;

// Now put the excess values into the new bucket.

	copyMem(getKeyAddr((size_t)delFromPos), newBucket->getKeyAddr(1),
			(size_t)((header()->activeKeys-(size_t)delFromPos+1)*tupleSize()));
	newBucket->setActiveKeys(header()->activeKeys-(size_t)delFromPos+1);

	setActiveKeys(delFromPos-1);

// Now add the new key where appropriate...

	if (newKeyPos <= (size_t)delFromPos)
		insert(theObject,link);
	else
		newBucket->insert(theObject,link);

	copyMem(newBucket->getKeyAddr(1), out, (size_t)keyLength);

// If this is an inner node then move everything in the new bucket down one.
// Note that it is not the first tuple that is deleted, but the link number
// 0 and key number 1. This deletes the key that will be sent back in 'out'
// and leaves the correct link in the extra spot.

	if (header()->leaf == INNER)
	{
		copyMem(newBucket->getLinkAddr(1), newBucket->firstTuple(),
				(size_t)((newBucket->header()->activeKeys-1)*tupleSize()+sizeof(int32)));
		newBucket->setActiveKeys(newBucket->header()->activeKeys-1);
	}
}

///////////////////////////////////////////////////////////////////////////
// Revision History:
//
// $Log: bucket.cpp,v $
// Revision 1.3  2001/04/20 10:15:01  georgetasker
// Cygwin compilation fixes, compilation speed enhancements
// Code modified to get rid of some compiler warnings
//
// Revision 1.2  2001/04/19 21:12:54  georgetasker
// cygwin compilation fixes
//
// Revision 1.1  2001/04/04 12:05:49  aleksandras
// forgotten diamond .cpps
//
// Revision 1.44  1996/03/05  22:04:29  dmb
// removed ^M.
//
// Revision 1.43  1996/03/05  21:42:35  dmb
// Preliminary modifications to get Dos/Windows 0.4 portability.
//
// Revision 1.42  1996/01/30  22:20:59  dmb
// Fixed int32 problems.
//
// Revision 1.41  1995/10/04  02:08:33  davison
// Changed references to objects to DIA_objects to prevent namespace clashes.
//
// Revision 1.40  1995/06/27 13:27:16  kevinl
// Fixes to repair the gcc 2.7.0 carnage:
// modified for loop local variable scope semantics
// some new errors invented.
// moved some inline friends out of classes (stoopid - mystring)
// Modified the setUnique generated member
//
// Revision 1.39  1994/12/22  03:47:17  kevinl
// s/bcopy/copyMem/g
//
// Revision 1.38  1994/08/01  00:12:32  darrenp
// Changed TRUE->true FALSE->false
//
// Revision 1.37  1994/07/04  12:15:38  kevinl
// Got rid of __CC conditional compilation
//
// Revision 1.36  1994/05/15  04:55:16  kevinl
// Type fixups
//
// Revision 1.35  1994/02/25  04:29:15  darrenp
// DOS binary compatibility modifications.
//
// Revision 1.34  1994/02/03  05:54:19  kevinl
// Moved include files to diamond/ and fixed HAVE_MALLOC_H
//
// Revision 1.33  1993/12/23  22:58:48  kevinl
// dbErr uses dbString, autoconf stuff, moved logs, added const and size_t
//
// Revision 1.32  1993/11/09  04:04:22  kevinl
// Moved logs
// Removed some old prottypes/includes
// bucket.h
//
// Revision 1.31  1993/10/05  07:29:18  kevinl
// Fixed negative offset problem in bucket::del
//
// Revision 1.30  1993/07/20  13:05:14  kevinl
// No longer complains about unused 'in' in sploosh.
//
// Revision 1.29  1993/07/20  12:59:30  kevinl
// Some unisgned int vs long problems
//
// Revision 1.28  1993/06/23  05:21:22  kevinl
// Mallocs are now in angular brackets
//
// Revision 1.27  1993/06/20  13:43:05  kevinl
// Fixed multiple mallocs
//
// Revision 1.26  1993/05/26  01:01:39  kevinl
// MALLOC_H_MISSING
//
// Revision 1.25  1993/05/11  14:44:50  kevinl
// Added version number output
//
// Revision 1.24  1993/05/06  04:00:19  kevinl
// SASC define for malloc.h
//
// Revision 1.23  1993/05/03  23:33:37  kevinl
// long aligned data
//
// Revision 1.22  1993/05/03  01:33:03  kevinl
// Cosmetic (mainly) changes for CC
//
// Revision 1.21  1993/05/01  14:29:12  kevinl
// Replaced linear searchForKey with a binary search
// Got rid of ints
//
// Revision 1.20  1993/04/30  07:45:45  kevinl
// Some optimizing
//
// Revision 1.19  1993/04/28  11:30:15  kevinl
// Fixed up inlines
//
// Revision 1.18  1993/04/25  09:52:39  kevinl
// Fixed some dberror calls
//
// Revision 1.17  1993/04/24  07:15:27  kevinl
// Comments!
//
// Revision 1.16  1993/04/19  15:49:37  kevinl
// empty() now handles internal vs leaf nodes correctly
//
// Revision 1.15  1993/04/15  07:57:57  kevinl
// Added findIndex, del and empty
// Shortened full()
//
// Revision 1.14  1993/04/08  10:57:27  kevinl
// played with bcopy prototype to placate linux.
//
// Revision 1.13  1993/04/04  23:56:25  kevinl
// Rounded off keyLengths
// searchForKey returns orrect indicies
//
// Revision 1.12  1993/03/29  08:20:09  darrenp
// Added new malloc library support
//
// Revision 1.11  1993/03/18  08:33:58  kevinl
// Fixed up reinitiaised default argument
//
// Revision 1.10  1993/03/17  14:27:42  kevinl
// Added index number to bucket constructor
// Added keyNum entry to all object key accesses
//
// Revision 1.9  1993/03/15  13:58:35  kevinl
// Added setParent
// changed some int's to long
//
// Revision 1.8  1993/03/08  00:30:50  kevinl
// Replaced BORLANDC with __BORLANDC__
//
// Revision 1.7  1993/02/17  12:15:53  kevinl
// Added getLink and setLink to solve alignment problems
// some tidying
//
// Revision 1.6  1993/02/13  00:55:33  kevinl
// replaced some long's with bucketId
//
// Revision 1.5  1993/02/11  03:53:38  kevinl
// a few fixes.
//
// Revision 1.4  1993/02/10  07:56:34  darrenp
// commented now.
//
// Revision 1.3  1993/02/08  14:33:24  davison
// Andy: wrote sploosh
// Kev: minor fixes to sploosh, comments, some output routines for debugging
//
// Revision 1.2  1993/02/08  00:12:28  kevinl
// Kevin adds a constructor...
//
// Revision 1.1  1993/02/06  16:50:36  davison
// Initial revision
//
///////////////////////////////////////////////////////////////////////////
