bptree.h

用CJ60Lib界面库制作的SQL数据库客户与服务器程序。

#if !defined(AFX_BPTREE_H__4F07FF58_0500_49E0_AE67_1A22A29A5D8A__INCLUDED_)
#define AFX_BPTREE_H__4F07FF58_0500_49E0_AE67_1A22A29A5D8A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "Cache.h"
#include "Table.h"

/////////////////////////////////////////////////////////////
// CStack

template< class TYPE, class ARG_TYPE >
class CStack
{
public:
	CStack() : top( -1 ) {}

// operations
public:
	int Size()
	{
		return m_List.GetCount();
	}

	bool Empty()
	{
		if( top > -1 )
			return false;
		return true;
	}

	void Push( TYPE t )
	{
		top++;
		m_List.AddTail( t );
	}
	
	ARG_TYPE Pop()
	{
		TYPE t;
		if( top == -1 )
			throw Error( ERROR_STACK, 0, _T("") );
		
		top--;
		t = m_List.GetTail();
		m_List.RemoveTail();

		return t;
	}

// attributes
public:
	int top;

private:
	CList< TYPE, ARG_TYPE > m_List;
};

typedef CStack< long, long > Path;

/////////////////////////////////////////////////////////////
// CBPTAttr

class CBPTAttr
{
public:
	bool		bucket;
	int			N;
	long		root;
	CEntryAttr	kattr;
};

/////////////////////////////////////////////////////////////
// CBPTNode

class CBPTNode
{
public:
	CBPTNode( CBlock* bptr, CBPTAttr& battr, bool dirty ) :
		Bptr( bptr ), Dptr( bptr->GetBlock() ), attr( battr ) 
	{
		Bptr->lock() = true;
		dirty && ( Bptr->dirty() = true );
	}
	~CBPTNode()
	{
		Bptr->lock() = false;
	} 

// Operations
public:
	// length of one node( ptr + key )
	long   length()     {  return attr.kattr.length+sizeof(long);   }
	// number of keys
	int&   keys()       {  return *(int*)Dptr;                      }
	// number of ptrs
	int&   ptrs()       {  return *(int*)(Dptr+sizeof(int));        }
	bool&  leaf()       {  return *(bool*)(Dptr+sizeof(int)*2);     }
	// start position of b-plus tree node in the block
	char*  start()      {  return Dptr+sizeof(int)*2+sizeof(bool);  }
	char*  ptr( int i ) {  return start()+length()*i;               }
	char*  key( int i ) {  return ptr(i)+sizeof(long);              }

    long&  pick_ptr( int i ) {  return *(long*)ptr(i);              }
    long&  last_ptr()        {  return pick_ptr( ptrs() - 1 );      }
    CEntry pick_key( int i ) {  return CEntry(key(i),attr.kattr);   }
    CEntry last_key()        {  return pick_key( keys() - 1 );      }

    void   insert_key( int, const CEntry& );                // insert key[Pos|Key]
    void   insert_ptr( int, long );                         // insert ptr[Pos|ptr]
    void   remove_key( int );                               // delete key[Pos]
    void   remove_ptr( int );                               // delete ptr[Pos]
    
    int    find_ptr( long );                                // search ptr position
    int    lower_bound( const CEntry& );                    // search the lower boundary of Key using binary search
    int    upper_bound( const CEntry& );                    // search the upper boundary of Key using binary search
    void   init( bool );                                    // init node[is leaf?]
    void   relink( CBlock*, bool );                         // link new node[Block ptr|being modified?]

private:
    char*		Dptr;                                       // date ptr
    CBlock*		Bptr;                                       // cache block ptr
    CBPTAttr&	attr;
};

/////////////////////////////////////////////////////////////
// PNode

struct PNode                                                // node of bucket
{
    long    PTR;                                            // ptr
    long    NEXT;                                           // next ptr position
};

/////////////////////////////////////////////////////////////
// CPBucket : ptr bucket

class CPBucket
{
public:
	CPBucket( CFileAPI* bkt, long head ) :
		bktAPI( bkt ), head_posi( head ) {}

// Operations
public:
    long    insert( long );                                 // insert ptr, return new head position
    long    remove( long );                                 // delete ptr, return new head position
    void    output( RESULT& );                              // output all ptrs in bucket into RESULT

private:
    CFileAPI*   bktAPI;
    long        head_posi;
};

/////////////////////////////////////////////////////////////
// CBPTree

class CBPTree
{
public:
    CBPTree( const char*, const CEntryAttr&, bool );	 // create a b-plus tree
    CBPTree( const char* );                              // construct a b-plus tree, open the index
    ~CBPTree();

// Operations
public:
	bool search( RESULT&, const CEntry& );
	bool search( RESULT&, const CEntry&, const CEntry& );

	void insert( const CEntry& E, long PTR )             // 插入一个索引
	{   
		CEntry KEY( attr.kattr );
		convert( KEY, E, false );                       // 将纪录实体转化为键[键|实体|提取]
		node_insert( node_seek(KEY), KEY, PTR );   
	}
	void remove( const CEntry& E, long PTR )             // 删除一个索引
	{   
		CEntry KEY( attr.kattr );
		convert( KEY, E, false );
		node_remove( node_seek(KEY), KEY, PTR );
	}

// operations
private:
	long	node_seek( const CEntry& );                  // 查找搜索码所在的叶子结点
	void	node_insert( long, const CEntry&, long );    // 在结点中插入一个搜索码
	void	node_remove( long, const CEntry&, long );    // 从结点中删除一个搜索码
	bool	convert( CEntry&, const CEntry&, bool );      // 实体与键的转化[键|实体|一一对应 OR 提取]

    void    load_attr()                                 // 读入索引属性信息
    {
		bptAPI->ReadAttr( &attr, sizeof( CBPTAttr ) );
	}
    void    save_attr()                                 // 保存索引属性信息
    {
		bptAPI->WriteAttr( &attr, sizeof( CBPTAttr ) );
	}

// attributes
private:
	Path		path;                                   // 父结点路径
	CBPTAttr	attr;                                   // 索引属性
	CFileAPI*	bptAPI;                                 // B+树物理存储接口
	CFileAPI*	bktAPI;                                 // 指针桶物理存储接口
};

#endif // !defined(AFX_BPTREE_H__4F07FF58_0500_49E0_AE67_1A22A29A5D8A__INCLUDED_)