ttree.cpp

fastdb-2.92的源码

        } else { 
            oid_t childId = rightId;
            bool grow = insert(db, childId, recordId, key, type, sizeofType, comparator, offs);
            if (childId != rightId) { 
                ((dbTtreeNode*)db->put(nodeId))->right = rightId = childId;
            }
            if (!grow) return false;
        }
        node = (dbTtreeNode*)db->put(nodeId);
        if (node->balance < 0) { 
            node->balance = 0;
            return false;
        } else if (node->balance == 0) { 
            node->balance = 1;
            return true;
        } else { 
            dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);
            node = (dbTtreeNode*)db->get(nodeId);
            if (right->balance > 0) { // single RR turn
                node->right = right->left;
                right->left = nodeId;
                node->balance = 0;
                right->balance = 0;
                nodeId = rightId;
            } else { // double RL turn
                oid_t leftId = right->left;
                dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);
                right = (dbTtreeNode*)db->get(rightId);
                node = (dbTtreeNode*)db->get(nodeId);
                right->left = left->right;
                left->right = rightId;
                node->right = left->left;
                left->left = nodeId;
                node->balance = (left->balance > 0) ? -1 : 0;
                right->balance = (left->balance < 0) ? 1 : 0;
                left->balance = 0;
                nodeId = leftId;
            }
            return false;
        }
    }
    int l = 1, r = n-1;
    if (type == dbField::tpString) { 
        while (l < r)  {
            int i = (l+r) >> 1;
            rec = (char*)db->getRow(node->item[i]);
            diff = strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs);
            if (diff > 0) { 
                l = i + 1;
            } else { 
                r = i;
                if (diff == 0) { 
                    break;
                }
            }
        }
    } else { 
        while (l < r)  {
            int i = (l+r) >> 1;
            rec = (char*)db->getRow(node->item[i]);
            diff = keycmp(key, rec+offs, type, sizeofType, comparator);
            if (diff > 0) { 
                l = i + 1;
            } else { 
                r = i;
                if (diff == 0) { 
                    break;
                }
            }
        }
    }
    // Insert before item[r]
    node = (dbTtreeNode*)db->put(nodeId);
    if (n != pageSize) {
        for (int i = n; i > r; i--) node->item[i] = node->item[i-1]; 
        node->item[r] = recordId;
        node->nItems += 1;
        return false;
    } else { 
        oid_t reinsertId;
        if (node->balance >= 0) { 
            reinsertId = node->item[0];
            for (int i = 1; i < r; i++) node->item[i-1] = node->item[i]; 
            node->item[r-1] = recordId;
        } else { 
            reinsertId = node->item[n-1];
            for (int i = n-1; i > r; i--) node->item[i] = node->item[i-1]; 
            node->item[r] = recordId;
        }
        rec = (char*)db->getRow(reinsertId);
        key = rec + offs;
        if (type == dbField::tpString) { 
            key = rec + ((dbVarying*)key)->offs;
        }
        return insert(db, nodeId, reinsertId, key, type, sizeofType, comparator, offs);
    }
}

inline int dbTtreeNode::balanceLeftBranch(dbDatabase* db, oid_t& nodeId)
{
    dbTtreeNode* node = (dbTtreeNode*)db->put(nodeId);
    if (node->balance < 0) { 
        node->balance = 0;
        return 1;
    } else if (node->balance == 0) { 
        node->balance = 1;
        return 0;
    } else { 
        oid_t rightId = node->right;
        dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);
        node = (dbTtreeNode*)db->get(nodeId);
        if (right->balance >= 0) { // single RR turn
            node->right = right->left;
            right->left = nodeId;
            if (right->balance == 0) { 
                node->balance = 1;
                right->balance = -1;
                nodeId = rightId;
                return 0;
            } else { 
                node->balance = 0;
                right->balance = 0;
                nodeId = rightId;
                return 1;
            }
        } else { // double RL turn
            oid_t leftId = right->left;
            dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);
            node = (dbTtreeNode*)db->get(nodeId);
            right = (dbTtreeNode*)db->get(rightId);
            right->left = left->right;
            left->right = rightId;
            node->right = left->left;
            left->left = nodeId;
            node->balance = left->balance > 0 ? -1 : 0;
            right->balance = left->balance < 0 ? 1 : 0;
            left->balance = 0;
            nodeId = leftId;
            return 1;
        }
    }
}


inline int dbTtreeNode::balanceRightBranch(dbDatabase* db, oid_t& nodeId)
{
    dbTtreeNode* node = (dbTtreeNode*)db->put(nodeId);
    if (node->balance > 0) { 
        node->balance = 0;
        return 1;
    } else if (node->balance == 0) { 
        node->balance = -1;
        return 0;
    } else { 
        oid_t leftId = node->left;
        dbTtreeNode* left = (dbTtreeNode*)db->put(leftId);
        node = (dbTtreeNode*)db->get(nodeId);
        if (left->balance <= 0) { // single LL turn
            node->left = left->right;
            left->right = nodeId;
            if (left->balance == 0) { 
                node->balance = -1;
                left->balance = 1;
                nodeId = leftId;
                return 0;
            } else { 
                node->balance = 0;
                left->balance = 0;
                nodeId = leftId;
                return 1;
            }
        } else { // double LR turn
            oid_t rightId = left->right;
            dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);
            node = (dbTtreeNode*)db->get(nodeId);
            left = (dbTtreeNode*)db->get(leftId);
            left->right = right->left;
            right->left = leftId;
            node->left = right->right;
            right->right = nodeId;
            node->balance = right->balance < 0 ? 1 : 0;
            left->balance = right->balance > 0 ? -1 : 0;
            right->balance = 0;
            nodeId = rightId;
            return 1;
        }
    }
}

int dbTtreeNode::remove(dbDatabase* db, oid_t& nodeId, oid_t recordId, 
                        void* key, int type, int sizeofType, dbUDTComparator comparator, int offs)
{
    dbTtreeNode* node = (dbTtreeNode*)db->get(nodeId);
    char* rec = (char*)db->getRow(node->item[0]);
    int n = node->nItems;
    int diff = (type == dbField::tpString)
             ? strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs)
             : keycmp(key, rec+offs, type, sizeofType, comparator);
    if (diff <= 0) { 
        oid_t leftId = node->left;
        if (leftId != 0) { 
            oid_t childId = leftId;
            int h = remove(db, childId, recordId, key, type, sizeofType, comparator, offs);
            if (childId != leftId) { 
                ((dbTtreeNode*)db->put(nodeId))->left = childId;
            }
            if (h > 0) { 
                return balanceLeftBranch(db, nodeId);
            } else if (h == 0) { 
                return 0;
            }
        }
        assert (diff == 0);
    }
    rec = (char*)db->getRow(node->item[n-1]);
    diff = (type == dbField::tpString)
        ? strcmp((char*)key, rec + ((dbVarying*)(rec+offs))->offs)
        : keycmp(key, rec+offs, type, sizeofType, comparator);
    if (diff <= 0) {        
        for (int i = 0; i < n; i++) { 
            if (node->item[i] == recordId) { 
                if (n == 1) { 
                    if (node->right == 0) { 
                        db->freeObject(nodeId);
                        nodeId = node->left;
                        return 1;
                    } else if (node->left == 0) { 
                        db->freeObject(nodeId);
                        nodeId = node->right;
                        return 1;
                    } 
                } 
                node = (dbTtreeNode*)db->put(nodeId);
                oid_t leftId = node->left, rightId = node->right;
                if (n <= minItems) { 
                    if (leftId != 0 && node->balance <= 0) {  
                        dbTtreeNode* left = (dbTtreeNode*)db->get(leftId);
                        while (left->right != 0) { 
                            left = (dbTtreeNode*)db->get(left->right);
                        }
                        while (--i >= 0) { 
                            node->item[i+1] = node->item[i];
                        }
                        node->item[0] = left->item[left->nItems-1];
                        rec = (char*)db->getRow(node->item[0]);
                        key = rec + offs;
                        if (type == dbField::tpString) { 
                            key = rec + ((dbVarying*)key)->offs;
                        }
                        oid_t childId = leftId;
                        int h = remove(db, childId, node->item[0], 
                                       key, type, sizeofType, comparator, offs);
                        if (childId != leftId) { 
                            ((dbTtreeNode*)db->get(nodeId))->left = childId;
                        }
                        if (h > 0) {
                            h = balanceLeftBranch(db, nodeId);
                        }
                        return h;
                    } else if (node->right != 0) { 
                        dbTtreeNode* right = (dbTtreeNode*)db->get(rightId);
                        while (right->left != 0) { 
                            right = (dbTtreeNode*)db->get(right->left);
                        }
                        while (++i < n) { 
                            node->item[i-1] = node->item[i];
                        }
                        node->item[n-1] = right->item[0];
                        rec = (char*)db->getRow(node->item[n-1]);
                        key = rec + offs;
                        if (type == dbField::tpString) { 
                            key = rec + ((dbVarying*)key)->offs;
                        }
                        oid_t childId = rightId;
                        int h = remove(db, childId, node->item[n-1], 
                                       key, type, sizeofType, comparator, offs);
                        if (childId != rightId) { 
                            ((dbTtreeNode*)db->get(nodeId))->right = childId;
                        }
                        if (h > 0) {
                            h = balanceRightBranch(db, nodeId);
                        }
                        return h;
                    }
                }
                while (++i < n) { 
                    node->item[i-1] = node->item[i];
                }
                node->nItems -= 1;
                return 0;
            }
        }
    }
    oid_t rightId = node->right;
    if (rightId != 0) { 
        oid_t childId = rightId;
        int h = remove(db, childId, recordId, key, type, sizeofType, comparator, offs);
        if (childId != rightId) { 
            ((dbTtreeNode*)db->put(nodeId))->right = childId;
        }
        if (h > 0) { 
            return balanceRightBranch(db, nodeId);
        } else { 
            return h;
        }
    }
    return -1;
}

void dbTtreeNode::purge(dbDatabase* db, oid_t nodeId)
{
    if (nodeId != 0) { 
        dbTtreeNode* node = (dbTtreeNode*)db->get(nodeId);
        oid_t leftId = node->left;
        oid_t rightId = node->right;
        db->freeObject(nodeId);
        purge(db, leftId);
        purge(db, rightId);
    }    
}

bool dbTtreeNode::traverseForward(dbDatabase* db, dbAnyCursor* cursor)
{
    if (left != 0) { 
        if (!((dbTtreeNode*)db->get(left))->traverseForward(db, cursor)) {
            return false;
        }
    }
    for (int i = 0, n = nItems; i < n; i++) { 
        if (!cursor->add(item[i])) { 
            return false;
        }
    }
    if (right != 0) { 
        return ((dbTtreeNode*)db->get(right))->traverseForward(db, cursor);
    }
    return true;
}

bool dbTtreeNode::traverseBackward(dbDatabase* db, dbAnyCursor* cursor)
{
    if (right != 0) { 
        if (!((dbTtreeNode*)db->get(right))->traverseBackward(db, cursor)) {
            return false;
        }
    }
    for (int i = nItems; --i >= 0;) { 
        if (!cursor->add(item[i])) { 
            return false;
        }
    }
    if (left != 0) { 
        return ((dbTtreeNode*)db->get(left))->traverseBackward(db, cursor);
    }
    return true;
}

bool dbTtreeNode::traverseForward(dbDatabase* db, dbAnyCursor* cursor,
                                  dbExprNode* condition)
{
    if (left != 0) { 
        if (!((dbTtreeNode*)db->get(left))->traverseForward(db, cursor, 
                                                            condition)) 
        {
            return false;
        }
    }
    dbTable* table = (dbTable*)db->getRow(cursor->table->tableId);
    for (int i = 0, n = nItems; i < n; i++) { 
        if (db->evaluate(condition, item[i], table, cursor)) { 
            if (!cursor->add(item[i])) { 
                return false;
            }
        }
    }
    if (right != 0) { 
        return ((dbTtreeNode*)db->get(right))->traverseForward(db, cursor, 
                                                               condition);
    }
    return true;
}

bool dbTtreeNode::traverseBackward(dbDatabase* db, dbAnyCursor* cursor,
                                   dbExprNode* condition)
{
    if (right != 0) { 
        if (!((dbTtreeNode*)db->get(right))->traverseBackward(db, cursor,
                                                             condition)) 
        {
            return false;
        }
    }
    dbTable* table = (dbTable*)db->getRow(cursor->table->tableId);
    for (int i = nItems; --i >= 0;) { 
        if (db->evaluate(condition, item[i], table, cursor)) { 
            if (!cursor->add(item[i])) { 
                return false;
            }
        }
    }
    if (left != 0) { 
        return ((dbTtreeNode*)db->get(left))->traverseBackward(db, cursor,
                                                              condition);
    }
    return true;
}