btrees.cpp

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C++ 代码 · 共 643 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


/*
BTREES:  WinHelp-style B-tree implementation.
*/
#include "btrees.h"
#include <stdlib.h>


//
//  BtreePage   --A b-tree 'node'.  Used only by other
//                b-tree functions.
//

struct BtreePage
{
    uint_16     _numEntries;    // # of BtreeData in this page.
    BtreePage   *_prevPage;     // Prev page in this level.
    BtreePage   *_nextPage;     // Next page in this level.
    uint_16     _thisPage;      // Index # of this page.
    uint_32     _size;          // Size of the page
    uint_32     _maxSize;       // The page size; used for dumping
    BtreeData   *_entries;              // Pointer to BtreeData list.
    BtreePage   *_parent;               // Parent page.
    BtreePage   *_firstChild;           // First child page.

    // Dump this page to an output file.
    int         dump( OutFile *dest );

    // Split a page which has gotten too large into two pages.
    int         split();

    BtreePage( uint_32 max_size, BtreePage *ancestor, BtreePage *descendant=NULL );
    ~BtreePage();
};


//  BtreeData::BtreeData

BtreeData::BtreeData()
        : _bnext( NULL ),
          _bprev( NULL ),
          _child( NULL )
{
    // empty
}


//  BtreeData::insertSelf       --Insert this object into the specified page.

void BtreeData::insertSelf( BtreePage *dest )
{
    BtreeData   *current = dest->_entries;
    BtreeData   *temp = NULL;
    while( current != NULL && current->lessThan( this ) ){
        temp = current;
        current = current->_bnext;
    }
    if( temp == NULL ){
        if( current != NULL ){
            _bnext = current;
            current->_bprev = this;
        }
        dest->_entries = this;
    } else {
        _bnext = temp->_bnext;
        _bprev = temp;
        temp->_bnext = this;
        if( _bnext != NULL ){
            _bnext->_bprev = this;
        }
    }
    dest->_size += size();
    dest->_numEntries += 1;

    return;
}


//  BtreeDate::seekNext         --Find the child of the specified
//                                page where this data belongs.

BtreePage *BtreeData::seekNext( BtreePage *first )
{
    BtreePage   *result = first->_firstChild;
    BtreeData   *current = first->_entries;
    while( current != NULL ){
        if( lessThan( current ) ) break;
        result = current->_child;
        current = current->_bnext;
    }
    return result;
}


//  BtreePage::BtreePage

#define TREEPAGE_HEADER_SIZE    4

BtreePage::BtreePage( uint_32 max_size, BtreePage *ancestor, BtreePage *descendant )
        : _maxSize( max_size ),
          _parent( ancestor ),
          _firstChild( descendant ),
          _numEntries( 0 ),
          _prevPage( NULL ),
          _nextPage( NULL ),
          _entries( NULL )
{
    if( descendant == NULL ){
        // Leaf pages start with a header and indices to the previous
        // and next leaf pages.
        _size = TREEPAGE_HEADER_SIZE+2*sizeof( uint_16 );
    } else {
        // Index pages start with a header and index to the leftmost
        // child.
        _size = TREEPAGE_HEADER_SIZE+sizeof( uint_16 );
    }
}


//  BtreePage::~BtreePage       --Deletes all of its contents as well.

BtreePage::~BtreePage()
{
    BtreeData   *current = _entries;
    BtreeData   *temp;
    while( current != NULL ){
        temp = current;
        current = current->bnext();
        delete temp;
    }
}


//  BtreePage::dump             --Dump the page to an output file.

BtreePage::dump( OutFile *dest )
{
    uint_32     amount_left = _maxSize;
    uint_16     nil_16 = (uint_16) ~0;

    // Spit out the page header.
    dest->writech(0);
    dest->writech(0);
    dest->writebuf( &_numEntries, sizeof( uint_16 ), 1 );
    amount_left -= TREEPAGE_HEADER_SIZE;

    // If this a leaf node, print the indices of the previous
    // and next pages.
    if( _firstChild == NULL ){
        if( _prevPage ){
            dest->writebuf( &(_prevPage->_thisPage), sizeof( uint_16 ), 1 );
        } else {
            dest->writebuf( &nil_16, sizeof( uint_16 ), 1 );
        }
        if( _nextPage ){
            dest->writebuf( &(_nextPage->_thisPage), sizeof( uint_16 ), 1 );
        } else {
            dest->writebuf( &nil_16, sizeof( uint_16 ), 1 );
        }
        amount_left -= 2 * sizeof( uint_16 );
    } else {
        // If this is a tree node, print the index of the first child.
        dest->writebuf( &(_firstChild->_thisPage), sizeof( uint_16 ), 1 );
        amount_left -= sizeof( uint_16 );
    }

    for( BtreeData *i = _entries; i != NULL; i = i->bnext() ){

        // Dump the data.
        i->dump( dest );
        amount_left -= i->size();

        // if this is a tree node, print the index of the child page
        // corresponding to this data.

        if( _firstChild != NULL ){
            dest->writebuf( &(i->child()->_thisPage), sizeof( uint_16 ), 1 );
            amount_left -= sizeof( uint_16 );
        }
    }

    // Pad out the remaining space.
    while( amount_left ){
        dest->writech( 0 );
        amount_left--;
    }
    return 1;
}


//  BtreePage::split    --Break the page in two.  Assumes the parent
//                        page is non-empty.

int BtreePage::split()
{
    int         i=0;
    uint_16     limit = (uint_16) ((_numEntries + 1) / 2);
    uint_32     cur_size = 0;
    uint_16     cur_num = 0;
    BtreeData   *current = _entries;
    BtreePage   *sibling;

    // Search for the point to break the page at.
    while( current != NULL ){
        if( cur_num >= limit ) break;
        cur_size += current->size();
        cur_num++;
        current = current->bnext();
    }
    if( current == NULL ) return 0;

    // Create a new page, and modify the assorted pointers.
    sibling = new BtreePage( _maxSize, _parent, current->child() );
    sibling->_prevPage = this;
    sibling->_nextPage = _nextPage;
    if( _nextPage != NULL ){
        _nextPage->_prevPage = sibling;
    }
    _nextPage = sibling;

    // Give some of our data to the new page by modifying our data list.
    if( _firstChild != NULL ){
        sibling->_entries = current->bnext();
        if( current->bprev() != NULL ){
            current->bprev()->bnext( NULL );
        } else {
            _entries = NULL;
        }
        if( current->bnext() != NULL ){
            current->bnext()->bprev( NULL );
        }
        sibling->_numEntries = (uint_16) (_numEntries-cur_num-1);
        sibling->_size = _size-cur_size-current->size();
    } else {
        sibling->_entries = current;
        if( current->bprev() != NULL ){
            current->bprev()->bnext( NULL );
        } else {
            _entries = NULL;
        }
        current->bprev( NULL );
        sibling->_numEntries = (uint_16) (_numEntries-cur_num);
        sibling->_size = _size-cur_size;
    }

    // Record the fact that we've lost data.
    _numEntries = cur_num;
    _size = cur_size + TREEPAGE_HEADER_SIZE + sizeof(uint_16);
    if( _firstChild == NULL ){
        _size += sizeof( uint_16 );
    }

    if( _parent == NULL ){

        // Die in flames!!!
        HCError( BTREE_ERR );

    } else {

        // Notify the parent page of the split by passing a new data item.
        BtreeData *newdata;
        if( _firstChild == NULL ){

            // If this is a leaf page, we generate a new item.
            newdata = current->myKey();

        } else {

            // If this is a tree page, we pass an existing item.
            newdata = current;
            newdata->bnext( NULL );
            newdata->bprev( NULL );

        }
        newdata->child( sibling );
        newdata->insertSelf( _parent );
        _parent->_size += sizeof( uint_16 );
    }

    // Update the parent field of 'sibling's children.
    if( _firstChild != NULL ){
        sibling->_firstChild->_parent = sibling;
        current = sibling->_entries;
        while( current != NULL ){
            current->child()->_parent = sibling;
            current = current->bnext();
        }
    }

    // And we're done!
    return 1;