ttree.cpp

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

//-< TTREE.CPP >-----------------------------------------------------*--------*
// FastDB                    Version 1.0         (c) 1999  GARRET    *     ?  *
// (Main Memory Database Management System)                          *   /\|  *
//                                                                   *  /  \  *
//                          Created:     20-Nov-98    K.A. Knizhnik  * / [] \ *
//                          Last update:  6-Jan-99    K.A. Knizhnik  * GARRET *
//-------------------------------------------------------------------*--------*
// T-Tree implementation
//-------------------------------------------------------------------*--------*

#define INSIDE_FASTDB

#include "fastdb.h"
#include "ttree.h"

BEGIN_FASTDB_NAMESPACE

#ifdef USE_LOCALE_SETTINGS
#ifdef IGNORE_CASE
#define strcmp(x, y) stricoll(x, y)
#define strncmp(x, y, n) strincmp(x, y, n)
#else
#define strcmp(x, y) strcoll(x, y)
#endif
#else
#ifdef IGNORE_CASE
#define strcmp(x, y) stricmp(x, y)
#define strncmp(x, y, n) strincmp(x, y, n)
#endif
#endif

inline int keycmp(void* p, void* q, int type, int sizeofType, dbUDTComparator comparator)
{
    switch (type) {
      case dbField::tpBool:
        return *(bool*)p - *(bool*)q;
      case dbField::tpInt1:
        return *(int1*)p - *(int1*)q;
      case dbField::tpInt2:
        return *(int2*)p - *(int2*)q;
      case dbField::tpInt4:
        return *(int4*)p < *(int4*)q ? -1 : *(int4*)p == *(int4*)q ? 0 : 1;
      case dbField::tpInt8:
        return *(db_int8*)p < *(db_int8*)q ? -1 : *(db_int8*)p == *(db_int8*)q ? 0 : 1;
      case dbField::tpReference:
        return *(oid_t*)p < *(oid_t*)q ? -1 : *(oid_t*)p == *(oid_t*)q ? 0 : 1;
      case dbField::tpReal4:
        return *(real4*)p < *(real4*)q ? -1 : *(real4*)p == *(real4*)q ? 0 : 1;
      case dbField::tpReal8:
        return *(real8*)p < *(real8*)q ? -1 : *(real8*)p == *(real8*)q ? 0 : 1;
      case dbField::tpRawBinary:
        return comparator(p, q, sizeofType);
      default:
        assert(false);
        return 0;
    }
}

void dbTtree::find(dbDatabase* db, oid_t treeId, dbSearchContext& sc)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->find(db, sc);
    }
}

void dbTtree::prefixSearch(dbDatabase* db, oid_t treeId, dbSearchContext& sc)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->prefixSearch(db, sc);
    }
}

oid_t dbTtree::allocate(dbDatabase* db)
{
    oid_t oid = db->allocateObject(dbTtreeMarker);
    dbTtree* tree = (dbTtree*)db->get(oid);
    tree->root = 0;
    return oid;
}

void dbTtree::insert(dbDatabase* db, oid_t treeId, oid_t recordId, 
                     int type, int sizeofType, dbUDTComparator comparator, int offs)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId == 0) {
        oid_t nodeId = dbTtreeNode::allocate(db, recordId);
        ((dbTtree*)db->put(treeId))->root = nodeId;
    } else { 
        byte* rec = (byte*)db->getRow(recordId);
        byte* key = rec + offs;
        if (type == dbField::tpString) { 
            key = rec + ((dbVarying*)key)->offs;
        }
        oid_t nodeId = rootId;
        dbTtreeNode::insert(db, nodeId, recordId, key, type, sizeofType, comparator, offs);
        if (rootId != nodeId) { 
            ((dbTtree*)db->put(treeId))->root = nodeId;
        }
    }
}


void dbTtree::remove(dbDatabase* db, oid_t treeId, oid_t recordId, 
                     int type, int sizeofType, dbUDTComparator comparator, int offs)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    byte* rec = (byte*)db->getRow(recordId);
    byte* key = rec + offs;
    if (type == dbField::tpString) { 
        key = rec + ((dbVarying*)key)->offs;
    }
    oid_t nodeId = rootId;
    int h = dbTtreeNode::remove(db, nodeId, recordId, key, type, sizeofType, comparator, offs);
    assert(h >= 0);
    if (nodeId != rootId) { 
        ((dbTtree*)db->put(treeId))->root = nodeId;
    }
}   


void dbTtree::purge(dbDatabase* db, oid_t treeId) 
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    dbTtreeNode::purge(db, rootId);
    ((dbTtree*)db->put(treeId))->root = 0;
}
    
void dbTtree::drop(dbDatabase* db, oid_t treeId) 
{
    purge(db, treeId);
    db->freeObject(treeId);
}
    

void dbTtree::traverseForward(dbDatabase* db, oid_t treeId,
                              dbAnyCursor* cursor)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->traverseForward(db, cursor);
    }
}

void dbTtree::traverseBackward(dbDatabase* db, oid_t treeId,
                              dbAnyCursor* cursor)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->traverseBackward(db, cursor);
    }
}


void dbTtree::traverseForward(dbDatabase* db, oid_t treeId,
                             dbAnyCursor* cursor, dbExprNode* condition)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->traverseForward(db, cursor,condition);
    }
}


void dbTtree::traverseBackward(dbDatabase* db, oid_t treeId,
                              dbAnyCursor* cursor, dbExprNode* condition)
{
    oid_t rootId = ((dbTtree*)db->get(treeId))->root;
    if (rootId != 0) { 
        ((dbTtreeNode*)db->get(rootId))->traverseBackward(db,cursor,condition);
    }
}

static inline int prefcmp(char const* key, char const* prefix) { 
    return strncmp(key, prefix, strlen(prefix));
}

bool dbTtreeNode::prefixSearch(dbDatabase* db, dbSearchContext& sc)
{
    char* rec;
    int   l, r, m, n = nItems;

    sc.probes += 1;
    dbTable* table = (dbTable*)db->getRow(sc.cursor->table->tableId);

    assert (sc.type == dbField::tpString);
    rec = (char*)db->getRow(item[0]);
    char* key = sc.firstKey;
    if (prefcmp(key, rec+((dbVarying*)(rec+sc.offs))->offs) > 0) {
        rec = (char*)db->getRow(item[n-1]);
        if (prefcmp(key, rec+((dbVarying*)(rec+sc.offs))->offs) > 0) { 
            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]);
            if (prefcmp(sc.firstKey, rec + ((dbVarying*)(rec+sc.offs))->offs) > 0) {
                l = m+1;
            } else { 
                r = m;
            }
        }
        while (r < n) { 
            rec = (char*)db->getRow(item[r]);
            if (prefcmp(key, rec + ((dbVarying*)(rec+sc.offs))->offs) < 0) { 
                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 (prefcmp(key, rec + ((dbVarying*)(rec+sc.offs))->offs) < 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);
    } 
    return false;
}


bool dbTtreeNode::find(dbDatabase* db, dbSearchContext& sc)
{
    char* rec;
    int   diff;
    int   l, r, m, n = nItems;

    sc.probes += 1;
    dbTable* table = (dbTable*)db->getRow(sc.cursor->table->tableId);

    if (sc.type == dbField::tpString) { 
        if (sc.firstKey != NULL) { 
            rec = (char*)db->getRow(item[0]);
            diff = strcmp(sc.firstKey, rec+((dbVarying*)(rec+sc.offs))->offs);
            if (diff >= sc.firstKeyInclusion) {     
                rec = (char*)db->getRow(item[n-1]);
                diff = strcmp(sc.firstKey, 
                              rec+((dbVarying*)(rec+sc.offs))->offs);
                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 = strcmp(sc.firstKey, 
                                  rec + ((dbVarying*)(rec+sc.offs))->offs);
                    if (diff >= sc.firstKeyInclusion) {
                        l = m+1;
                    } else { 
                        r = m;
                    }
                }
                while (r < n) { 
                    rec = (char*)db->getRow(item[r]);
                    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[r], table, sc.cursor)) 
                    {
                        if (!sc.cursor->add(item[r])) { 
                            return false;
                        }
                    }
                    r += 1;
                }