ttree.cpp

最新版本！fastdb是高效的内存数据库系统

                if (right != 0) { 
                    return ((dbTtreeNode*)db->get(right))->find(db, sc); 
                } 
                return true;    
            }
        }       
        if (left != 0) { 
            if (!((dbTtreeNode*)db->get(left))->find(db, sc)) { 
                return false;
            }
        }
        for (l = 0; l < n; l++) { 
            rec = (char*)db->getRow(item[l]);
            if ((sc.lastKey != NULL 
                 && strcmp(rec + ((dbVarying*)(rec+sc.offs))->offs, 
                           sc.lastKey) >= sc.lastKeyInclusion) ||
                (sc.prefixLength != 0
                 && memcmp(rec + ((dbVarying*)(rec+sc.offs))->offs,
                           sc.firstKey,
                           sc.prefixLength) != 0))
            {
                return false;
            }
            if (!sc.condition || db->evaluate(sc.condition, item[l], table, sc.cursor)) {
                if (!sc.cursor->add(item[l])) { 
                    return false;
                }
            }
        }
        if (right != 0) { 
            return ((dbTtreeNode*)db->get(right))->find(db, sc);
        } 
    } else { 
        if (sc.firstKey != NULL) { 
            rec = (char*)db->getRow(item[0]);
            diff = keycmp(sc.firstKey, rec+sc.offs, sc.type, sc.sizeofType, sc.comparator);
            if (diff >= sc.firstKeyInclusion) {     
                rec = (char*)db->getRow(item[n-1]);
                diff = keycmp(sc.firstKey, rec+sc.offs, sc.type, sc.sizeofType, sc.comparator);
                if (diff >= sc.firstKeyInclusion) {
                    if (right != 0) { 
                        return ((dbTtreeNode*)db->get(right))->find(db, sc); 
                    } 
                    return true;
                }
                for (l = 0, r = n; l < r;) { 
                    m = (l + r) >> 1;
                    rec = (char*)db->getRow(item[m]);
                    diff = keycmp(sc.firstKey, rec+sc.offs, sc.type, sc.sizeofType, sc.comparator);
                    if (diff >= sc.firstKeyInclusion) {
                        l = m+1;
                    } else { 
                        r = m;
                    }
                }
                while (r < n) { 
                    rec = (char*)db->getRow(item[r]);
                    if (sc.lastKey != NULL 
                        && keycmp(rec+sc.offs, sc.lastKey, sc.type, sc.sizeofType, sc.comparator) 
                           >= sc.lastKeyInclusion) 
                    { 
                        return false;
                    }
                    if (!sc.condition 
                        || db->evaluate(sc.condition, item[r], table, sc.cursor)) 
                    {
                        if (!sc.cursor->add(item[r])) { 
                            return false;
                        }
                    }
                    r += 1;
                }
                if (right != 0) { 
                    return ((dbTtreeNode*)db->get(right))->find(db, sc); 
                } 
                return true;    
            }
        }       
        if (left != 0) { 
            if (!((dbTtreeNode*)db->get(left))->find(db, sc)) { 
                return false;
            }
        }
        for (l = 0; l < n; l++) { 
            rec = (char*)db->getRow(item[l]);
            if (sc.lastKey != NULL && keycmp(rec+sc.offs, sc.lastKey, sc.type, sc.sizeofType, sc.comparator) 
                >= sc.lastKeyInclusion) 
            {
                return false;
            }
            if (!sc.condition || db->evaluate(sc.condition, item[l], table, sc.cursor)) { 
                if (!sc.cursor->add(item[l])) { 
                    return false;
                }
            }
        }
        if (right != 0) { 
            return ((dbTtreeNode*)db->get(right))->find(db, sc);
        } 
    }
    return true;
}


oid_t dbTtreeNode::allocate(dbDatabase* db, oid_t recordId)
{
    oid_t nodeId = db->allocateObject(dbTtreeNodeMarker);
    dbTtreeNode* node = (dbTtreeNode*)db->get(nodeId);
    node->nItems = 1;
    node->item[0] = recordId;
    node->left = node->right = 0;
    node->balance = 0;
    return nodeId;
}

bool dbTtreeNode::insert(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 || diff == 0) && node->nItems != pageSize) { 
            node = (dbTtreeNode*)db->put(nodeId);
            for (int i = n; i > 0; i--) node->item[i] = node->item[i-1];
            node->item[0] = recordId;
            node->nItems += 1;
            return false;
        } 
        if (leftId == 0) { 
            leftId = allocate(db, recordId);
            node = (dbTtreeNode*)db->put(nodeId);
            node->left = leftId;
        } else {
            oid_t childId = leftId;
            bool grow = insert(db, childId, recordId, key, type, sizeofType, comparator, offs);
            if (childId != leftId) { 
                ((dbTtreeNode*)db->put(nodeId))->left = leftId = 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* left = (dbTtreeNode*)db->put(leftId);
            node = (dbTtreeNode*)db->get(nodeId);
            if (left->balance < 0) { // single LL turn
                node->left = left->right;
                left->right = nodeId;
                node->balance = 0;
                left->balance = 0;
                nodeId = leftId;
            } else { // double LR turn
                oid_t rightId = left->right;
                dbTtreeNode* right = (dbTtreeNode*)db->put(rightId);
                left = (dbTtreeNode*)db->get(leftId);
                node = (dbTtreeNode*)db->get(nodeId);
                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 false;
        }
    } 
    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) { 
        oid_t rightId = node->right;
        if ((rightId == 0 || diff == 0) && node->nItems != pageSize) { 
            node = (dbTtreeNode*)db->put(nodeId);
            node->item[n] = recordId;
            node->nItems += 1;
            return false;
        }
        if (rightId == 0) { 
            rightId = allocate(db, recordId);
            node = (dbTtreeNode*)db->put(nodeId);
            node->right = rightId;
        } 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 {