cmxbtree.h

CMXBTree 的主要作用是在内存中建立一棵B+树

#ifndef _CMXBTREE_H_
#define _CMXBTREE_H_

#include <stdio.h>
#include <memory.h>

#include "smartpointer.h"

//typedef int RECTYPE;

#define BTREE_DEGREE    4

template <class RECTYPE> class CMXBTree: public RefCount
{
public:
//索引叶的指针类别
typedef enum 
{
    NO_TYPE = 0,
    INDEX_LEAF_POINTER,
    DATA_LEAF_POINTER
} BTREE_POINTER_TYPE;
    
//存放数据的容器
typedef struct DATA_CONTAINER_tag
{
    RECTYPE *pData;
    DATA_CONTAINER_tag *pNext; //指向下一个DATA_CONTAINER
    DATA_CONTAINER_tag *pProv; //指向下一个DATA_CONTAINER
} DATA_CONTAINER;

//数据叶
typedef struct BTREE_DATA_LEAF_tag
{
    DATA_CONTAINER *pDataCont[BTREE_DEGREE];
    BTREE_DATA_LEAF_tag *pNext;
    BTREE_DATA_LEAF_tag *pProv;
} BTREE_DATA_LEAF;


//索引叶的 Index Key
typedef struct INDEX_KEY_tag
{
    RECTYPE *pKey;
    void *pKeyRight;
} INDEX_KEY;

typedef struct GET_KEY_tag
{
    BTREE_DATA_LEAF *m_pProv;
    DATA_CONTAINER *m_DataCont;
    int m_nDataElemIndex; 
}GET_KEY;


typedef struct SEARCH_KEY_tag
{
    DATA_CONTAINER *m_pSearchResultOrig;
    BTREE_DATA_LEAF *m_pSearchDataLeaf;
    DATA_CONTAINER *m_pSearchResult;
    GET_KEY m_GetKey;
}SEARCH_KEY;


//索引叶
typedef struct BTREE_INDEX_LEAF_tag
{
    //叶子最左边的指针，可能指向数据叶，或者索引叶
    void *pLeafLeft; 
    INDEX_KEY IndexKeys[BTREE_DEGREE];

    //本叶子的指针类型，POINTER_TYPE
    char cPointerType;
    BTREE_INDEX_LEAF_tag *pParent;
} BTREE_INDEX_LEAF ;


private:
    
    void QuickSortData(DATA_CONTAINER **A, int nLo, int nHi, DATA_CONTAINER *Key);

    BTREE_INDEX_LEAF *NewIndexLeaf( void );
    void DeleteIndexLeaf( BTREE_INDEX_LEAF * pPtr );
    BTREE_DATA_LEAF *NewDataLeaf( void );
    void DeleteDataLeaf( BTREE_DATA_LEAF * pPtr );
    DATA_CONTAINER *NewDataContainer( void );
    void DeleteDataContainer( DATA_CONTAINER *pPtr );
    RECTYPE *NewRecType( void );
    void DeleteRecType( RECTYPE *pPtr );

    int GetFreeElemInDataLeaf( BTREE_DATA_LEAF *pDataLeaf );
    int GetTotalElemInDataLeaf( BTREE_DATA_LEAF *pDataLeaf );
    int GetFreeElemInIndexLeaf( BTREE_INDEX_LEAF *pIndexLeaf );
    int GetTotalElemInIndexLeaf( BTREE_INDEX_LEAF *pIndexLeaf );
    int SeekInsertPoint( BTREE_INDEX_LEAF * pSearchIndexLeaf, RECTYPE & Key, bool *pKeyInIndex = NULL );
    int SeekParent( BTREE_INDEX_LEAF * pParentLeaf, BTREE_INDEX_LEAF * pIndexLeaf);

    int SplitIndexLeaf(BTREE_INDEX_LEAF * pCurIndexLeaf, //要容纳新 Key 的索引叶
                    //void * pLeftLeaf,       //儿子被拆分后，左边的叶子 可能是数据叶或索引叶
                    //void * pRightLeaf,      //儿子被拆分后，右边的叶子 可能是数据叶或索引叶
                    INDEX_KEY NewKey,       //新的 Key
                    int i );                 //插入位置 0 ~ BTREE_DEGREE
    int DeleteDataContainerTrain( DATA_CONTAINER *pHead );
    int RemoveIndexKey( BTREE_INDEX_LEAF *pSearchIndexLeaf, int q );

    int GetDataLeaf( RECTYPE &Key, BTREE_INDEX_LEAF * &pSearchIndexLeaf, BTREE_DATA_LEAF  * &pSearchDataLeaf, bool *pKeyInIndex = NULL );
    DATA_CONTAINER * SeekInDataLeaf( BTREE_DATA_LEAF *pDataLeaf, 
                                    RECTYPE &Key, 
                                    int *nIndex = NULL
                                    );
    
    //DATA_CONTAINER *m_pSearchResult;
    //DATA_CONTAINER *m_pSearchResultOrig;
    //BTREE_DATA_LEAF *m_pSearchDataLeaf;

    BTREE_DATA_LEAF *m_pDataLeafList;
    BTREE_DATA_LEAF *m_pProv;
    BTREE_DATA_LEAF *m_pDataLeafListTail;
    //int m_nDataElemIndex; 

    BTREE_INDEX_LEAF *m_pRoot ; //指向树根的指针

    bool m_bMadeList;
    //建立数据叶链表
    //用第归方案
    int SubMakeDataList( BTREE_INDEX_LEAF *pSearchIndexLeaf );
    
    //用第归方法
    //删除整棵树
    int SubDestroyTree( BTREE_INDEX_LEAF *pSearchIndexLeaf);

    int MakeDataList( void )
    {
        if( ! m_bMadeList )
        {
            m_pDataLeafListTail = m_pDataLeafList = NULL;
            int nRC = SubMakeDataList( this->m_pRoot );
            if( nRC >= 0 ) m_bMadeList = true;
            m_pDataLeafListTail = m_pProv;
            m_pProv = NULL;
            return nRC;
        }
        else
            return 0;
    };

    
protected:
    //将被RefCount调用
    void DestroyMe( void )
    {
        delete this;
    }

public:

    unsigned long m_nNewIndexLeaf ;
    unsigned long  m_nDelIndexLeaf;

    unsigned long  m_nNewDataLeaf;
    unsigned long  m_nDelDataLeaf;

    unsigned long  m_nNewDataCon;
    unsigned long  m_nDelDataCon;

    unsigned long  m_nNewRecType;
    unsigned long  m_nDelRecType;

    //删除某个 Key
    //返回 -1 表示B+Tree 错误
    //-2 表示没有内存
    // 0 表示正常
    int DeleteKey( RECTYPE &Key );

    //插入某个 Key
    //返回 -1 表示B+Tree 错误
    //-2 表示没有内存
    // 0 表示正常
    int InsertKey( RECTYPE &Key );

    //搜索某个 Key
    //返回 NULL 表示搜寻失败
    RECTYPE *SearchKey( RECTYPE & Key, 
        SEARCH_KEY *pSK = NULL,
        RECTYPE **pLessThan = NULL, //此参数返回比Key小的Key
        RECTYPE **pGreaterThan = NULL //此参数返回比Key大的Key
        );
    //返回下一个具有同样值的 Key
    RECTYPE *SearchNextKey( SEARCH_KEY *pSK );
    int DeleteKey( SEARCH_KEY *pSK, RECTYPE * pRec );
    RECTYPE *GetPrevKey( SEARCH_KEY * pGK);
    RECTYPE *GetNextKey( SEARCH_KEY * pGK);



    //按照从小到大的顺序返回 Key
    //NULL 表示结束
    RECTYPE *GetFirstKey( GET_KEY * pGK);
    RECTYPE *GetNextKey( GET_KEY * pGK, bool bGetDup = false);
 
    //按照从大到小的顺序返回 Key
    //NULL 表示结束
    RECTYPE *GetLastKey( GET_KEY * pGK);
    RECTYPE *GetPrevKey( GET_KEY * pGK, bool bGetDup = false);
    
    
    //毁灭这棵树
    int DestroyTree( void )
    {
        
        int nRC = SubDestroyTree( m_pRoot );
        m_pRoot = NULL;
//        m_pSearchResult = NULL;
//        m_pSearchResultOrig = NULL;
//        m_pSearchDataLeaf = NULL;

        m_pDataLeafList = NULL;

        m_nNewIndexLeaf = 0;
        m_nDelIndexLeaf = 0;

        m_nNewDataLeaf = 0;
        m_nDelDataLeaf = 0;

        m_nNewDataCon = 0;
        m_nDelDataCon = 0;

        m_nNewRecType = 0;
        m_nDelRecType = 0;

        m_bMadeList = false;

        return nRC;
    }
    
    //这棵树总共有多少个元素
    size_t GetCount( void )
    {
        return m_nNewRecType - m_nDelRecType;
    }

    //这棵树是否为空
    bool IsEmpty( void )
    {
        if( m_pRoot == NULL ) return true;
        else return false;
    }
    
    CMXBTree( void )
    {
        m_pRoot =  NULL ;
//        m_pSearchResult = NULL;
//        m_pSearchResultOrig = NULL;
//        m_pSearchDataLeaf = NULL;
        m_pDataLeafList = NULL;

        m_nNewIndexLeaf = 0;
        m_nDelIndexLeaf = 0;

        m_nNewDataLeaf = 0;
        m_nDelDataLeaf = 0;

        m_nNewDataCon = 0;
        m_nDelDataCon = 0;

        m_nNewRecType = 0;
        m_nDelRecType = 0;
        
        
        m_bMadeList = false;
    };

    ~CMXBTree( void )
    {
        DestroyTree();
    }
};

#include "cmxbtree.cpp"

#endif