gbtree.cpp

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

        short n = z->_keyCount;
        if (n > 0) {
            z->ShiftRightAt (pos+1);
            z->_item[pos+1] = item;
        }
        else 
            z->_item[0] = item;
        z->_keyCount++;
        for (short i = 0; i < sp; i++) {
            stack[i]->_subtreeSize++;
        }
    }
    for (short i = 0; i < sp; i++) {
        _nodeSpace->WriteBack (stack[i]);
    }
    return !found;
}  


void CL_GenericBTree::_SplitChild (CL_GenericBTreeNode* x,
                                   short i, CL_GenericBTreeNode* y) 
{
    CL_GenericBTreeNode* z = _nodeSpace->MakeNode();
    z->MoveSubNode (*y, _order, 0, _order-1);
    z->_isLeaf = y->_isLeaf;
    z->_keyCount = y->_keyCount = _order-1;
    x->ShiftRightAt (i); 
        // We shouldn't shift subtree[i], but it shouldn't matter
    x->_subtree[i+1] = z->Handle();
    x->_item [i] = y->_item [_order-1];
    x->_keyCount++;

    // Recompute _subtreeSize for y and z
    long size = 0;
    if (!z->_isLeaf) {
        for (short j = 0; j <= z->_keyCount; j++) {
            CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
                (z->_subtree[j]);
            size += p->_subtreeSize;
            _nodeSpace->ReturnNode (p);
        }
    }
    size += z->_keyCount;
    z->_subtreeSize = size;
    y->_subtreeSize -= size+1;
    _nodeSpace->WriteBack (z);
    _nodeSpace->NodeModified (y);
    _nodeSpace->NodeModified (x);
}
 







 






CL_VoidPtr CL_GenericBTree::Remove (CL_VoidPtr key)
{
    CL_GenericBTreeNode* root = _nodeSpace->BorrowRoot();
    CL_GenericBTreeNode* node = root;
    CL_VoidPtr retVal;
    
    if (!node || node->_keyCount == 0) // Empty root
        return (CL_VoidPtr) NULL;
    short pos;
    if (node->_keyCount == 1 && node->_isLeaf) {
        // Tree has only one key
        if (_comparator (key, node->_item[0]) == 0) {
            node->_keyCount = node->_subtreeSize = 0;
            _nodeSpace->WriteBack (node);
            return node->_item[0];
        }
        return NULL;
    }
    CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
    // We need a stack for updating the subtree sizes
    short sp = 0;
    short index = 0;
    bool found = FALSE;

    CL_GenericBTreeNode* q;
    // stack[sp++] = node;
    enum {SEARCHING, DESCENDING} state = SEARCHING;
    DeleteActionEnum action;
    while (1) {
        if (state == SEARCHING) {
            found = node->Search (key, index);
            if (found)
                retVal = node->_item[index];
        }
        q = _DescendInto (node, index+1, action);
        if (node == root &&  node->_keyCount == 0) {
            _nodeSpace->DestroyNode (node);
        }
        else {
            // We should add the root to the stack only if it wasn't
            // already destroyed
            stack [sp++] = node;
        }            
    if (!q) break;
        // _DescendInto may have caused our key to be copied into q.
        // If so, it would be copied into either q->_item[0] or
        // q->_item[_order-1]  (because of a right or left rotation,
        // respectively) or into q->_item[_order-1] (because of a merge).
        if (found) {
            state = DESCENDING;
            if (action == RotateRight) {
                index = 0;
            }
            else if (action == RotateLeft || action == Merge) {
                index = _order-1;
            }
            else // No rotation or merge was done
                break;
        }
        node = q;
    }
    if (!found) {
        // The key is not in the tree
        for (short i = 0; i < sp; i++)
            _nodeSpace->WriteBack(stack[i]);
        return (CL_VoidPtr) NULL;
    }
    if (node->_isLeaf) {
        // Key found in leaf
        node->ShiftLeftAt (index+1);
    }
    else {
        // The key is in an internal node, so we'll replace it by its
        // inorder successor:
        CL_GenericBTreeNode* p = q;
        while (1) {
            stack[sp++] = p;
        if (p->_isLeaf) break;
            p = _DescendInto (p, 0, action);
        }
        node->_item[index] = p->_item[0];
        p->ShiftLeftAt(1);
    }

    // Now update subtree sizes along search path
    short i = 0;
    if (stack[0]->_keyCount == 0) {
        i = 1;
    }
    for (; i < sp; i++) {
        stack[i]->_subtreeSize--;
        _nodeSpace->WriteBack (stack[i]);
    }
    return retVal;
}


CL_GenericBTreeNode* CL_GenericBTree::_DescendInto
    (CL_GenericBTreeNode* node, short subtreeIndex, DeleteActionEnum& action)
{
    CL_GenericBTreeNode* child, *sibling, *p;
    child = _nodeSpace->BorrowNode (node->_subtree[subtreeIndex]);
    if (!child || child->_keyCount >= _order) {
        action = NoAction;
        return child;
    }
    if (subtreeIndex == 0) {
        sibling = _nodeSpace->BorrowNode (node->_subtree[1]);
        p = _Adjust (node, 0, child, sibling, action);
    }
    else {
        sibling = _nodeSpace->BorrowNode
            (node->_subtree[subtreeIndex-1]);
        p = _Adjust (node, subtreeIndex-1, sibling, child, action);
    }
    if (action != Merge)
        _nodeSpace->ReturnNode (sibling);
    return p;
}



CL_GenericBTreeNode* CL_GenericBTree::_Adjust
  (CL_GenericBTreeNode* node, short index,
   CL_GenericBTreeNode* c0, CL_GenericBTreeNode* c1, DeleteActionEnum& action)
{
    assert ((c0 != NULL && c1 != NULL),
            ("BTree::Adjust: assertion failed: line %d\n", __LINE__));
    assert ((c0->_keyCount == _order-1 || c1->_keyCount == _order-1),
            ("BTree::Adjust: assertion failed: line %d\n", __LINE__));
            
    if (c0->_keyCount == _order-1 && c1->_keyCount == _order-1) {
        // Merge the two nodes
        c0->_item[_order-1] = node->_item[index];
        c0->MoveSubNode (*c1, 0, _order, _order-1);
        c0->_keyCount = 2*_order-1;
        c0->_subtreeSize += c1->_subtreeSize+1;
        
        _nodeSpace->DestroyNode (c1);
        if (node->_keyCount > 1) {
            node->ShiftLeftAt (index+1);
            node->_subtree[index] = c0->Handle();
        }
        else {
            _nodeSpace->NewRoot (c0->Handle());
        }
        action = Merge;
        return c0;
    }
    if (c0->_keyCount >= _order) {
        // Rotate right
        c1->ShiftRightAt (0);
        c1->_item[0] = node->_item[index];
        c1->_subtree[0] = c0->_subtree[c0->_keyCount];
        node->_item[index] = c0->_item[c0->_keyCount-1];
        c0->_keyCount--;
        c1->_keyCount++;
        CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
            (c1->_subtree[0]);
        long xfr = (p) ? p->_subtreeSize+1 : 1;
        c1->_subtreeSize += xfr;
        c0->_subtreeSize -= xfr;
        if (p)
            _nodeSpace->ReturnNode (p);
        _nodeSpace->NodeModified (c0);
        action = RotateRight;
        return c1;
    }
    else {
        // c1->keyCount >= order, so rotate left
        c0->_item[_order-1] = node->_item[index];
        c0->_subtree[_order] = c1->_subtree[0];
        c0->_keyCount++;
        node->_item[index] = c1->_item[0];
        CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
            (c0->_subtree[_order]);
        long xfr = (p) ? p->_subtreeSize+1 : 1;
        c1->_subtreeSize -= xfr;
        c0->_subtreeSize += xfr;
        c1->ShiftLeftAt(1);
        if (p)
            _nodeSpace->ReturnNode (p);
        _nodeSpace->NodeModified (c1);
        action = RotateLeft; 
        return c0;
    }
}

            
        
    


CL_VoidPtr CL_GenericBTree::ExtractMin ()
{
    CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
    // We need a stack for updating the subtree sizes
    short sp = 0;
    CL_GenericBTreeNode* node = _nodeSpace->BorrowRoot();
    if (node->_keyCount == 0)
        return NULL;
    stack[sp++] = node;
    DeleteActionEnum action;
    while (!node->_isLeaf) {
        node = _DescendInto (node, 0, action);
        stack[sp++] = node;
    }
    CL_VoidPtr item = node->_item[0];
    node->ShiftLeftAt(1);
    for (short i = 0; i < sp; i++) {
        stack[i]->_subtreeSize--;
        _nodeSpace->WriteBack (stack[i]);
    }
    return item;
}




///////////////////////////////////////////////////////////////////
//                  BTreeIterator methods                        //
///////////////////////////////////////////////////////////////////


 


// The  BTreeIterator  remembers and   manipulates  the  search path  to  a
// particular key in the tree.
// 
// A search path is a sequence of pairs of the form <node#, subtree#>, with
// the  first pair <root,  subtree#> and the   last pair being  of the form
// <node#,  key#>. It completely   specifies the path   from the root  to a
// particular key in the tree.
//
// The Iterator maintains the invariant that the path specified by the
// current values in the array represents the path to the key that was
// returned by the most recent call to Next().

 
struct PathStruct {
public:
    CL_BTreeNodeHandle _handle;
    short              _indexInNode;
};


CL_GenericBTreeIterator::CL_GenericBTreeIterator
(const CL_GenericBTree& tree) :_tree (tree)
{
    _path = new PathStruct [MAX_BTREE_HEIGHT];
    _length = 0;
    Reset();
}

CL_GenericBTreeIterator::CL_GenericBTreeIterator
    (const CL_GenericBTreeIterator& itr)
: _tree (itr._tree)
{
    _path = new PathStruct [MAX_BTREE_HEIGHT];
    if (_path) {
        _length = itr._length;
        for (register short i = 0; i < _length; i++)
            ((PathStruct*) _path)[i] = ((PathStruct*) itr._path)[i];
    }
    else
        _length = 0;
    _index = itr._index;
}


CL_GenericBTreeIterator::~CL_GenericBTreeIterator()
{
    if (_path)
        delete [] (PathStruct*) _path;
}



void CL_GenericBTreeIterator::BeginFrom (CL_VoidPtr item)
{
    short pos;
    bool found;

    if (!_path) // Memory allocation failed?
        return;
    _length = 0;
    _index  = -1;
    if (_tree.Size() <= 0)
        return;
    PathStruct* path = (PathStruct*) _path;

    register CL_BTreeNodeSpace* space =  _tree.NodeSpace();
    CL_BTreeNodeHandle tmp_handle = space->RootHandle ();
    CL_GenericBTreeNode* tmp_ptr, *p;
    do {
        tmp_ptr = space->BorrowNode (tmp_handle);
        found = tmp_ptr->Search (item, pos);
        path[_length]._handle = tmp_handle;
        _index += path[_length]._indexInNode = found ? pos : pos+1;
        _length++;
    if (tmp_ptr->_isLeaf) break;
        for (register long i = 0; i <= pos; i++) {
            CL_GenericBTreeNode* p = space->BorrowNode
                (tmp_ptr->_subtree[i]);
            _index += p->_subtreeSize;
            space->ReturnNode (p);
        }
    if (found) break;
        tmp_handle = tmp_ptr->_subtree [pos+1];
        space->ReturnNode (tmp_ptr);
    } while (1);
    if (!tmp_ptr->_isLeaf) {
        // We're in an internal node; so move down to the leaf
        tmp_handle = tmp_ptr->_subtree[pos];
        do {
            p = space->BorrowNode (tmp_handle);
            path[_length]._handle = tmp_handle;
            path[_length]._indexInNode = p->_keyCount;
            _length++;
            tmp_handle = p->_subtree[p->_keyCount]; // Rightmost subtree
            space->ReturnNode (p);
        } while (tmp_handle);
    }
    path[_length-1]._indexInNode--;  // So that the first call to Next gives
                                     // the nearest key >= the given key
    space->ReturnNode (tmp_ptr);
}





void CL_GenericBTreeIterator::Reset ()
{
    if (!_path) // Memory allocation failed?
        return;
    _length = 1;
    PathStruct* path = (PathStruct*) _path;
    path[0]._handle = _tree.NodeSpace()->RootHandle();
    path[0]._indexInNode = -1;
    _index = -1;
}





CL_VoidPtr CL_GenericBTreeIterator::Next ()
{
    if (_index >= _tree.Size())
        return NULL;
    CL_VoidPtr retVal;
    
    if (!_path || _length == 0)
        return NULL;
    PathStruct* path = (PathStruct*) _path;
    CL_GenericBTreeNode* node;
    short  ndx = path[_length-1]._indexInNode;
    register CL_BTreeNodeSpace* space =  _tree.NodeSpace();
    node = space->BorrowNode (path[_length-1]._handle);

    _index++;
    if (! node->_isLeaf) {
        // Move to the next right subtree
        path[_length-1]._indexInNode++;
        CL_BTreeNodeHandle handle = node->_subtree [ndx+1];
        while (!node->_isLeaf) {
            path[_length]._handle = handle;
            path[_length]._indexInNode = 0;
            _length++;
            space->ReturnNode (node);
            node = space->BorrowNode (handle);
            handle = node->_subtree[0];
        };
        retVal = node->_item[0];
        space->ReturnNode (node);
        return retVal;
    }
    
    // We're in a leaf
    if (ndx >= node->_keyCount-1) {
            // We're at far right of the leaf, so move up
        do {
            _length--;
            space->ReturnNode (node);
        if (_length <= 0) break;
            node = space->BorrowNode (path[_length-1]._handle);
            ndx = path[_length-1]._indexInNode;
        } while (ndx >= node->_keyCount);
        if (_length) {
            retVal = node->_item[ndx];
            space->ReturnNode (node);
        }
        else
            retVal = NULL;
        return retVal;
    }
    // We're in the middle or at left end of a leaf
    path[_length-1]._indexInNode++;
    retVal = node->_item[path[_length-1]._indexInNode];
    space->ReturnNode (node);
    return retVal;
}




bool CL_GenericBTreeIterator::More ()
{
    return _index < _tree.Size()-1;
}