cmxbtree.cpp

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

            if( pGreaterThan )
            {
                //if( pSearchDataLeaf->pDataCont[1]->pData )
                if( pSearchDataLeaf->pDataCont[1] )
                    *pGreaterThan =  pSearchDataLeaf->pDataCont[1]->pData;
                else
                {
                    if( pSearchDataLeaf->pNext )
                    {
                        pSearchDataLeaf2 = pSearchDataLeaf->pNext;
                        *pGreaterThan =  pSearchDataLeaf2->pDataCont[0]->pData;
                    }
                    else *pGreaterThan = NULL;
                }
            }
        }
        else
        {
            if( pLessThan ) 
                *pLessThan = pSearchDataLeaf->pDataCont[i-1]->pData;

            if( pGreaterThan )
            {
                if( i+1 < BTREE_DEGREE && pSearchDataLeaf->pDataCont[i+1])
                    *pGreaterThan =  pSearchDataLeaf->pDataCont[i+1]->pData;
                else
                {
                    if( pSearchDataLeaf->pNext )
                    {
                        pSearchDataLeaf2 = pSearchDataLeaf->pNext;
                        *pGreaterThan =  pSearchDataLeaf2->pDataCont[0]->pData;
                    }
                    else *pGreaterThan = NULL;
                }
            }
        }
    }

    pRet =  pSearchResult->pData;
    if( pSK )
        pSK->m_pSearchResult = pSearchResult->pNext;
    return pRet;
}

template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetNextKey( SEARCH_KEY *pSK )
{
    if( pSK == NULL )  return NULL;

    if( pSK->m_GetKey.m_pProv == NULL ) return NULL;

    if( pSK->m_GetKey.m_DataCont == NULL) 
    {
        if( (pSK->m_GetKey.m_nDataElemIndex < BTREE_DEGREE) && 
            (pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex] != NULL )
            )
        {
            pSK->m_GetKey.m_DataCont = 
                pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
            return  pSK->m_GetKey.m_DataCont->pData;
        }
        else
        {
            pSK->m_GetKey.m_nDataElemIndex --;
            pSK->m_GetKey.m_DataCont = 
                pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
            return GetNextKey( &(pSK->m_GetKey) );
            
        }
    }
    else
        return GetNextKey( &(pSK->m_GetKey) );
}

template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetPrevKey( SEARCH_KEY *pSK )
{
    if( pSK == NULL )  return NULL;

    if( pSK->m_GetKey.m_pProv == NULL ) return NULL;

    if( pSK->m_GetKey.m_DataCont == NULL) 
    {
        if( pSK->m_GetKey.m_nDataElemIndex > 0) 
        {
            pSK->m_GetKey.m_nDataElemIndex --;
            pSK->m_GetKey.m_DataCont = 
                pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
            return  pSK->m_GetKey.m_DataCont->pData;
        }
        else
        {
            pSK->m_GetKey.m_DataCont = 
                pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
            return GetPrevKey( &(pSK->m_GetKey) );
            
        }
    }
    else
        return GetPrevKey( &(pSK->m_GetKey) );
}


template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::SearchNextKey( SEARCH_KEY *pSK )
{
    if( pSK == NULL )  return NULL;

    RECTYPE* pRet;
    if( !pSK->m_pSearchResult ) return NULL;

    pRet = pSK->m_pSearchResult->pData;
    pSK->m_pSearchResult = pSK->m_pSearchResult->pNext;
    return pRet;
}

template <class RECTYPE>
int CMXBTree<RECTYPE>::DeleteKey( SEARCH_KEY *pSK, RECTYPE * pRec )
{
    
    if( pRec == NULL || pSK == NULL ) return 1;

    if( pSK->m_pSearchResultOrig == NULL ) return 1;

    if( pSK->m_pSearchDataLeaf == NULL ) return 1;

    DATA_CONTAINER *p = pSK->m_pSearchResultOrig, *q ;

    while( p && p->pData != pRec )
        p = p->pNext;

    if( p == NULL )  return 1;

    if( p->pProv == NULL && p->pNext == NULL) //只有一个元素
    {
        RECTYPE key = *pRec;
        return DeleteKey( key );
        return 1;
    }
    else
    if( p->pProv == NULL )
    {
/*
        int i;
        for( i = 0; i < BTREE_DEGREE; i++ )
        {
            if( p == pSK->m_pSearchDataLeaf->pDataCont[i] )
                break;
        }
        
        if( i == BTREE_DEGREE ) return 1;
 */      
        if( p != pSK->m_pSearchResultOrig ) return 1;
        
        p = p->pNext;

        *(pSK->m_pSearchResultOrig->pData) = *(p->pData);

        if( p == pSK->m_pSearchResult )
            pSK->m_pSearchResult = pSK->m_pSearchResultOrig;
    }

    q = p->pProv;
    q->pNext = p->pNext;
    q = p->pNext;
    if( q ) q->pProv = p->pProv;
    DeleteRecType( p->pData );
    DeleteDataContainer( p );
    return 0;
}


template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetFirstKey( GET_KEY * pGK )
{
    if( pGK == NULL ) return NULL;
    
    memset( pGK, 0, sizeof(GET_KEY) );

    if( MakeDataList() < 0 ) return NULL;
    pGK->m_nDataElemIndex = 0;
    pGK->m_pProv = m_pDataLeafList;
    if( ! pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex] ) return NULL;
    pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
    RECTYPE* pRet = pGK->m_DataCont->pData;
    pGK->m_DataCont = pGK->m_DataCont->pNext;
    return pRet;
}


template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetLastKey( GET_KEY * pGK )
{
    if( pGK == NULL ) return NULL;
    
    memset( pGK, 0, sizeof(GET_KEY) );

    if( MakeDataList() < 0 ) return NULL;
    pGK->m_pProv = m_pDataLeafListTail;
    
    int i;
    for( i = BTREE_DEGREE - 1; i >= 0; i -- )
    {
        if( pGK->m_pProv->pDataCont[i] ) 
           break;
    }
    
    if( i < 0 ) return NULL;

    pGK->m_nDataElemIndex = i;
    
    pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
    RECTYPE* pRet = pGK->m_DataCont->pData;
    pGK->m_DataCont = pGK->m_DataCont->pNext;
    return pRet;
}


template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetNextKey( GET_KEY * pGK, bool bGetDup )
{
    if( m_bMadeList == false ) return NULL;
    if( pGK == NULL ) return NULL;

    if( !pGK->m_pProv ) return NULL;
    if( pGK->m_DataCont && bGetDup )
    {
        RECTYPE* pRet = pGK->m_DataCont->pData;
        pGK->m_DataCont = pGK->m_DataCont->pNext;
        return pRet;
    }

    if( (pGK->m_nDataElemIndex+1 < BTREE_DEGREE) && pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex+1] ) //本数据叶还有元素可返回
    {
        pGK->m_nDataElemIndex++;
        pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];

        RECTYPE* pRet = pGK->m_DataCont->pData;
        pGK->m_DataCont = pGK->m_DataCont->pNext;
        return pRet;
    }
    else
    {
        pGK->m_pProv = pGK->m_pProv->pNext;
        if( pGK->m_pProv )
        {
            pGK->m_nDataElemIndex = 0;
            if( pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex] )
            {
                pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
                
                RECTYPE* pRet = pGK->m_DataCont->pData;
                pGK->m_DataCont = pGK->m_DataCont->pNext;

                return pRet;
            }
            else
                return NULL;
        }
        else
            return NULL;
    }
}


template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetPrevKey( GET_KEY * pGK, bool bGetDup )
{
    if( m_bMadeList == false ) return NULL;
    if( pGK == NULL ) return NULL;

    if( !pGK->m_pProv ) return NULL;
    if( pGK->m_DataCont && bGetDup )
    {
        RECTYPE* pRet = pGK->m_DataCont->pData;
        pGK->m_DataCont = pGK->m_DataCont->pNext;
        return pRet;
    }

    if( pGK->m_nDataElemIndex - 1 >= 0 ) //本数据叶还有元素可返回
    {
        pGK->m_nDataElemIndex --;
        pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];

        RECTYPE* pRet = pGK->m_DataCont->pData;
        pGK->m_DataCont = pGK->m_DataCont->pNext;
        return pRet;
    }
    else
    {
        pGK->m_pProv = pGK->m_pProv->pProv;
        if( pGK->m_pProv )
        {

            int i;
            for( i = BTREE_DEGREE - 1; i >= 0; i -- )
            {
                if( pGK->m_pProv->pDataCont[i] ) 
                    break;
            }

            if( i < 0 ) return NULL;

            pGK->m_nDataElemIndex = i;

            pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
            
            RECTYPE* pRet = pGK->m_DataCont->pData;
            pGK->m_DataCont = pGK->m_DataCont->pNext;
            return pRet;
        }
        else
            return NULL;
    }
}


template <class RECTYPE>
int CMXBTree<RECTYPE>::SubMakeDataList( BTREE_INDEX_LEAF *pSearchIndexLeaf )
{
    if ( !pSearchIndexLeaf ) return -1; //无效的索引叶指针？BTREE 错误

    if( pSearchIndexLeaf->cPointerType == DATA_LEAF_POINTER ) //下面就是数据叶
    {
        if( pSearchIndexLeaf->pLeafLeft ) //最左的指针有效
        {
            if( m_pDataLeafList == NULL) 
            {   //队列还没有开始建立
                m_pDataLeafList = (BTREE_DATA_LEAF *) pSearchIndexLeaf->pLeafLeft;
                m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->pLeafLeft;
                m_pProv->pProv = NULL;
                m_pProv->pNext = NULL;
            }
            else
            {   //队列已经建立了
                m_pProv->pNext = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
                m_pProv->pNext->pProv = m_pProv;
                m_pProv = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
                m_pProv->pNext = NULL;
            }
        }

        //一个一个地对索引叶下面的数据叶建立链表
        int i;
        for( i = 0; i < BTREE_DEGREE; i ++ )
        {
            if( pSearchIndexLeaf->IndexKeys[i].pKey )
            {
                if( m_pDataLeafList == NULL) 
                {
                    m_pDataLeafList = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                    m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                    m_pProv->pNext = NULL;
                    m_pProv->pProv = NULL;
                }
                else
                {
                    m_pProv->pNext = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                    m_pProv->pNext->pProv = m_pProv;
                    m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                    m_pProv->pNext = NULL;
                }
            }
            else break;
        }
    }
    else
    if( pSearchIndexLeaf->cPointerType == INDEX_LEAF_POINTER ) //下面还是索引叶
    {
        //对最左的儿子第归
         if( SubMakeDataList((BTREE_INDEX_LEAF *)pSearchIndexLeaf->pLeafLeft) < -1 )
             return -1;
         //对其他儿子第归
        int i;
        for( i = 0; i < BTREE_DEGREE; i ++ )
        {
            if( pSearchIndexLeaf->IndexKeys[i].pKey )
            {
                 if( SubMakeDataList((BTREE_INDEX_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight) < -1 )
                     return -1;
            }
            else break;
        }
    }
    else return -1;

    return 0;
}


//把整棵树铲除
//也是用第归
template <class RECTYPE>
int CMXBTree<RECTYPE>::SubDestroyTree( BTREE_INDEX_LEAF *pSearchIndexLeaf )
{
    if ( !pSearchIndexLeaf ) return -1;
    int i,j;
    if( pSearchIndexLeaf->cPointerType == DATA_LEAF_POINTER ) //下面已经是数据叶
    {
        if( pSearchIndexLeaf->pLeafLeft ) //最左的指针有效
        {
            BTREE_DATA_LEAF *pTmp = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
            for( i = 0; i < BTREE_DEGREE; i++ )
            {
                if( pTmp->pDataCont[i] )
                    DeleteDataContainerTrain( pTmp->pDataCont[i] );
                else break;
            }
            DeleteDataLeaf( pTmp );
        }
        
        for( i = 0; i < BTREE_DEGREE; i ++ )
        {
            if( pSearchIndexLeaf->IndexKeys[i].pKey )
            {
                BTREE_DATA_LEAF *pTmp = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                for( j = 0; j < BTREE_DEGREE; j++ )
                {
                    if( pTmp->pDataCont[j] )
                        DeleteDataContainerTrain( pTmp->pDataCont[j] );
                    else break;
                }
                DeleteDataLeaf( pTmp );
            }
            else break;
        }
        DeleteIndexLeaf( pSearchIndexLeaf );
    }
    else
    if( pSearchIndexLeaf->cPointerType == INDEX_LEAF_POINTER )
    {
         if( SubDestroyTree((BTREE_INDEX_LEAF *)pSearchIndexLeaf->pLeafLeft) < -1 )
             return -1;
        int i;
        for( i = 0; i < BTREE_DEGREE; i ++ )
        {
            if( pSearchIndexLeaf->IndexKeys[i].pKey )
            {
                 if( SubDestroyTree((BTREE_INDEX_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight) < -1 )
                     return -1;
            }
            else break;
        }
        DeleteIndexLeaf( pSearchIndexLeaf );
    }
    else return -1;

    return 0;
}


#endif