gbtree.cpp

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

/*
 *
 *          Copyright (C) 1994, M. A. Sridhar
 *  
 *
 *     This software is Copyright M. A. Sridhar, 1994. You are free
 *     to copy, modify or distribute this software  as you see fit,
 *     and to use  it  for  any  purpose, provided   this copyright
 *     notice and the following   disclaimer are included  with all
 *     copies.
 *
 *                        DISCLAIMER
 *
 *     The author makes no warranties, either expressed or implied,
 *     with respect  to  this  software, its  quality, performance,
 *     merchantability, or fitness for any particular purpose. This
 *     software is distributed  AS IS.  The  user of this  software
 *     assumes all risks  as to its quality  and performance. In no
 *     event shall the author be liable for any direct, indirect or
 *     consequential damages, even if the  author has been  advised
 *     as to the possibility of such damages.
 *
 */





#ifdef __GNUC__
#pragma implementation
#endif

#include "base/gbtree.h"
#ifdef DEBUG
#include "base/memory.h"
#endif

#define MAX_BTREE_HEIGHT 30 // Can't have trees higher than this



////////////////////////////////////////////////////////////////////////////
//         CL_GenericBTreeNode function definitions                       //
////////////////////////////////////////////////////////////////////////////



CL_GenericBTreeNode::CL_GenericBTreeNode
    (short order, CL_BTreeNodeSpace* space, CL_AbstractComparator& cmp)
:  _order (order), _cmp (cmp), _nodeSpace (space)
{
    _keyCount = 0;
    register short n = 2*order;
    _subtree = new CL_BTreeNodeHandle [n];
    for (short i = 0; i < n; i++)
        _subtree[i] = 0;
    _item = new CL_VoidPtr [n-1];
    _isLeaf = TRUE;
    _subtreeSize = 0;
    
}
 

CL_GenericBTreeNode::~CL_GenericBTreeNode()
{
    delete [] _item;
    delete [] _subtree ;
}
 
 
bool CL_GenericBTreeNode::Search (CL_VoidPtr itm, short& index) const
{
    if (!_item)
        return FALSE;
    long i;
    short result;
    if (_keyCount <= 7) { // Small number of keys, do a linear search
        if (_keyCount == 0) {
            index = -1;
            return FALSE;
        }
        for (i = 0; i < _keyCount; i++) {
            result = _cmp (_item[i], itm);
            if (result >= 0)
                break;
        }
        if (result == 0) {
            index = i;
            return TRUE;
        }
        else  {
            index = i-1;
            return FALSE;
        }
    }

    // Do a binary search
    long lo = 0, hi = _keyCount-1, mid;
    while (lo <= hi) {
        mid = (lo + hi)/2;
        result = _cmp (_item[mid], itm);
        if (result == 0) {
            index = mid;
            return TRUE;
        }
        if (result < 0)
            lo = mid+1;
        else
            hi = mid-1;
    }
    index = (result <= 0) ? (mid) :  mid-1;
    return FALSE;
}

void CL_GenericBTreeNode::ShiftRightAt (short pos, short amount)
{
    short i;
    for (i = _keyCount-1; i >= pos; i--) {
        _item[i+amount] = _item[i];
        _subtree[i+amount+1] = _subtree[i+1];
    }
    _subtree [pos+amount] = _subtree[pos];
    for (i = pos; i < pos+amount; i++) {
        _item[i] = 0;
    }
}


void CL_GenericBTreeNode::ShiftLeftAt (short pos, short amount)
{
    short i;
    for (i = pos; i < _keyCount; i++) {
        _item[i-amount] = _item[i];
        _subtree[i-amount] = _subtree[i];
    }
    // Now move the rightmost subtree
    _subtree [_keyCount-amount] = _subtree[_keyCount];
    for (i = _keyCount-amount+1; i <= _keyCount; i++)
        _subtree[i] = 0;
    for (i = _keyCount-amount; i < _keyCount; i++)
        _item[i] = 0;
    _keyCount -= amount;
}



void CL_GenericBTreeNode::MoveSubNode
    (const CL_GenericBTreeNode& x, short pos, short our_pos,
     short nkeys)
{
    short i, j;
    for (i = our_pos, j = pos; i < our_pos + nkeys; i++, j++) {
        _item[i] = x._item[j];
        _subtree[i] = x._subtree[j];
        x._item[j] = 0;
        x._subtree[j] = 0;
    }
    _subtree[our_pos+nkeys] = x._subtree[pos + nkeys];
}


 
////////////////////////////////////////////////////////////////////////////
//                  CL_BTreeNodeSpace methods                             //
////////////////////////////////////////////////////////////////////////////




 
void CL_BTreeNodeSpace::_Destroy (CL_GenericBTreeNode* node) const
{
    if (node) {
        register short n = node->Size();
        for (short i = 0; i < n; i++)
            DestroyItem (node->Item(i));
        delete node;
    }
}
    






////////////////////////////////////////////////////////////////////////////
//              CL_HeapBTreeNodeSpace methods                             //
////////////////////////////////////////////////////////////////////////////



CL_HeapBTreeNodeSpace::CL_HeapBTreeNodeSpace (short order, const
                                              CL_GenericBTree& tree,
                                              CL_AbstractComparator& cmp)
: CL_BTreeNodeSpace (order, tree, cmp)
{
    _root = CreateNode();
}



CL_HeapBTreeNodeSpace::~CL_HeapBTreeNodeSpace ()
{
    // Traverse the tree and get rid of all the nodes
    _DestroySubtree (_root);
    _root = NULL;
}



void CL_HeapBTreeNodeSpace::_DestroySubtree (CL_BTreeNodeHandle h)
{
    // Do a post-order walk, destroying nodes as we go along
    if (!h)
        return;
    CL_GenericBTreeNode* node = (CL_GenericBTreeNode*) h;
    register short n = node->Size();
    for (register short i = 0; i <= n; i++)
        _DestroySubtree (node->Subtree(i));
    _Destroy (node);
}


CL_BTreeNodeHandle CL_HeapBTreeNodeSpace::CreateNode ()
{
    CL_GenericBTreeNode* p = _BuildNode ();
    if (p)
        _SetHandle (*p, (CL_BTreeNodeHandle) p);
    return (CL_BTreeNodeHandle) p;
}


// static long time = 0; // DEBUG
// static FILE* theFile = fopen ("g:/logfile", "w"); // DEBUG

CL_GenericBTreeNode*  CL_HeapBTreeNodeSpace::BorrowNode
(CL_BTreeNodeHandle h) const
{
    // if (h) fprintf (theFile, "%8lx %08ld borrowed\n", h, time++); // DEBUG
    return (CL_GenericBTreeNode*) h;
}


void CL_HeapBTreeNodeSpace::ReturnNode (CL_GenericBTreeNode* /* h */) const
{
    // fprintf (theFile, "%8lx %08ld returned\n",  h, time++); // DEBUG
}


void CL_HeapBTreeNodeSpace::DestroyNode (CL_GenericBTreeNode* node)
{
    // fprintf (theFile, "%8lx %08ld destroyed\n", node, time++); // DEBUG
    _Destroy (node);
}




 
////////////////////////////////////////////////////////////////////////////
//                     CL_GenericBTree       definitions                  //
////////////////////////////////////////////////////////////////////////////



CL_GenericBTree::CL_GenericBTree (CL_AbstractComparator& cmp,
                                  short order, CL_BTreeNodeSpace* space)
: _comparator (cmp)
{
    _order = maxl (order, 2);
    if (space) {
        _nodeSpace = space;
        _ownNodeSpace = FALSE;
    }
    else {
        _nodeSpace = new CL_HeapBTreeNodeSpace (_order, *this, cmp);
        _ownNodeSpace = TRUE;
    }
}


CL_GenericBTree::~CL_GenericBTree ()
{
    if (_ownNodeSpace)
        delete _nodeSpace;
}


CL_VoidPtr CL_GenericBTree::Find (CL_VoidPtr item) const
{
    short pos;
    bool found;
    CL_VoidPtr ret_val = NULL;

    CL_BTreeNodeHandle tmp_handle = _nodeSpace->RootHandle ();
    CL_GenericBTreeNode* tmp_ptr;
    do {
        tmp_ptr = _nodeSpace->BorrowNode (tmp_handle);
        found = tmp_ptr->Search (item, pos);
    if (found || tmp_ptr->_isLeaf) break;
        tmp_handle = tmp_ptr->_subtree [pos+1];
        _nodeSpace->ReturnNode (tmp_ptr);
    } while (1);
    if (found)
        ret_val = tmp_ptr->_item [pos];
    _nodeSpace->ReturnNode (tmp_ptr);
    return ret_val;
}




CL_VoidPtr CL_GenericBTree::ItemWithRank (long rank) const
{
    short pos;
    bool found;
    CL_VoidPtr itm;

    CL_GenericBTreeNode* tmp_ptr, *p1;
    tmp_ptr = _nodeSpace->BorrowRoot ();
    if (!tmp_ptr || tmp_ptr->_keyCount <= 0)
        return NULL;
    rank = minl (maxl (rank, 0), tmp_ptr->_subtreeSize-1);
    do {
        if (tmp_ptr->_isLeaf) {
            assert ((0 <= rank && rank <= tmp_ptr->_keyCount-1),
                    ("Internal error: CL_GenericBTree::ItemWithRank:"
                     "bad key count %d rank %ld", tmp_ptr->_keyCount, rank));
            CL_VoidPtr ret = tmp_ptr->_item[rank];
            _nodeSpace->ReturnNode (tmp_ptr);
            return ret;
        }
        // We're in a non-leaf, so find the subtree to descend into
        // (if any)
        short i;
        for (i = 0; i < tmp_ptr->_keyCount; i++) {
            p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
            if (p1->_subtreeSize > rank)
                break;
            rank -= p1->_subtreeSize; // Account for i-th subtree
            _nodeSpace->ReturnNode (p1);
            if (rank == 0) {
                // We've got the item we wanted
                CL_VoidPtr ret = tmp_ptr->_item[i];
                _nodeSpace->ReturnNode (tmp_ptr);
                return ret;
            }
            rank--;               // Account for i-th key in node
        }
        if (i >= tmp_ptr->_keyCount) {
            // Descend into rightmost subtree
            p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
        }
        _nodeSpace->ReturnNode (tmp_ptr);
        tmp_ptr = p1;
    } while (1);
}


long CL_GenericBTree::RankOf (CL_VoidPtr item) const
{
    short pos;
    bool found;
    CL_VoidPtr itm;
    long count = 0;

    CL_GenericBTreeNode* tmp_ptr, *p1;
    tmp_ptr = _nodeSpace->BorrowRoot ();
    if (!tmp_ptr || tmp_ptr->_keyCount <= 0)
        return 0;
    do {
        found = tmp_ptr->Search (item, pos);
        if (tmp_ptr->_isLeaf) {
            _nodeSpace->ReturnNode (tmp_ptr);
            count += found ? pos : pos+1;
            return count;
        }
        // We're in a non-leaf, so find the subtree to descend into
        short i;
        for (i = 0; i <= pos; i++) {
            p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
            count += p1->_subtreeSize; // Account for i-th subtree
            _nodeSpace->ReturnNode (p1);
        }
        if (found)  {
            _nodeSpace->ReturnNode (tmp_ptr);
            return count + pos;
        }
        count += pos+1; // Account for the keys we compared
        p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
        _nodeSpace->ReturnNode (tmp_ptr);
        tmp_ptr = p1;
    } while (1);
}



long CL_GenericBTree::Size() const
{
    CL_GenericBTreeNode* node = _nodeSpace->BorrowRoot ();
    long size = node->_subtreeSize;
    _nodeSpace->ReturnNode (node);
    return size;
}


   


bool CL_GenericBTree::Add (CL_VoidPtr item)
{
    bool        ans;
    CL_GenericBTreeNode* aNode, *tmpNode, *root;

    root = _nodeSpace->BorrowRoot ();
    if (root->_keyCount < (2*_order - 1)) {
        ans = _InsertNonFull (root, item);
        return ans;
    }

    // Root is full; create a new empty root
    aNode = _nodeSpace->MakeNode(); // aNode  will be the new root 
    CL_BTreeNodeHandle h = aNode->Handle();
    aNode->_subtree [0] = root->Handle();
    aNode->_isLeaf = FALSE;
    aNode->_subtreeSize = root->_subtreeSize;
    _SplitChild (aNode, 0, root);
    _nodeSpace->ReturnNode (root);

    _nodeSpace->NewRoot (h);

    // Now add the key 
    ans = _InsertNonFull (aNode, item);
    return ans;
}








 
 
//
// Private methods
//
 
bool CL_GenericBTree::_InsertNonFull (CL_GenericBTreeNode* x, CL_VoidPtr item)
{
    short pos;
    CL_GenericBTreeNode* y, *z = x;
    CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
    // We need a stack for updating the subtree sizes
    short sp = 0;
    bool found = FALSE;
    
    while (z && !(found = z->Search (item, pos))) {
        stack[sp++] = z;
    if (z->_isLeaf) break;
        pos++;
        y =  _nodeSpace->BorrowNode (z->_subtree[pos]);
        if (y->_keyCount == 2*_order-1) {
            _SplitChild (z, pos, y);
            if (_comparator (item, z->_item[pos]) >= 0) {
                pos++;
                _nodeSpace->ReturnNode (y);
                y = _nodeSpace->BorrowNode (z->_subtree[pos]);
            }
        }
        z = y;
    }

    if (!found) {