dvdatabase.c

DataDraw is an ultra-fast persistent database for high performance programs written in C. It s so fa

        freeSpace = dvAllocatedRootModuleTable() - dvUsedRootModuleTable();
    }
    if(freeSpace < spaceNeeded) {
        dvSetAllocatedRootModuleTable(dvAllocatedRootModuleTable() + spaceNeeded - freeSpace +
            (dvAllocatedRootModuleTable() >> 2));
        utResizeArray(dvRoots.ModuleTable, dvAllocatedRootModuleTable());
    }
}

/*----------------------------------------------------------------------------------------
  Allocate memory for a new Root.ModuleTable array.
----------------------------------------------------------------------------------------*/
void dvRootAllocModuleTables(
    dvRoot Root,
    uint32 numModuleTables)
{
    uint32 freeSpace = dvAllocatedRootModuleTable() - dvUsedRootModuleTable();
    uint32 elementSize = sizeof(dvModule);
    uint32 usedHeaderSize = (sizeof(dvRoot) + elementSize - 1)/elementSize;
    uint32 freeHeaderSize = (sizeof(dvRoot) + sizeof(uint32) + elementSize - 1)/elementSize;
    uint32 spaceNeeded = utMax(numModuleTables + usedHeaderSize, freeHeaderSize);

#if defined(DD_DEBUG)
    utAssert(dvRootGetNumModuleTable(Root) == 0);
#endif
    if(numModuleTables == 0) {
        return;
    }
    if(freeSpace < spaceNeeded) {
        allocMoreRootModuleTables(spaceNeeded);
    }
    dvRootSetModuleTableIndex(Root, dvUsedRootModuleTable() + usedHeaderSize);
    dvRootSetNumModuleTable(Root, numModuleTables);
    *(dvRoot *)(void *)(dvRoots.ModuleTable + dvUsedRootModuleTable()) = Root;
    memset(dvRootGetModuleTables(Root), 0xff, numModuleTables*elementSize);
    dvSetUsedRootModuleTable(dvUsedRootModuleTable() + spaceNeeded);
}

/*----------------------------------------------------------------------------------------
  Wrapper around dvRootGetModuleTables for the database manager.
----------------------------------------------------------------------------------------*/
static void *getRootModuleTables(
    uint64 objectNumber,
    uint32 *numValues)
{
    dvRoot Root = dvIndex2Root(objectNumber);

    *numValues = dvRootGetNumModuleTable(Root);
    return dvRootGetModuleTables(Root);
}

/*----------------------------------------------------------------------------------------
  Wrapper around dvRootAllocModuleTables for the database manager.
----------------------------------------------------------------------------------------*/
static void *allocRootModuleTables(
    uint64 objectNumber,
    uint32 numValues)
{
    dvRoot Root = dvIndex2Root(objectNumber);

    dvRootSetModuleTableIndex(Root, 0);
    dvRootSetNumModuleTable(Root, 0);
    if(numValues == 0) {
        return NULL;
    }
    dvRootAllocModuleTables(Root, numValues);
    return dvRootGetModuleTables(Root);
}

/*----------------------------------------------------------------------------------------
  Free memory used by the Root.ModuleTable array.
----------------------------------------------------------------------------------------*/
void dvRootFreeModuleTables(
    dvRoot Root)
{
    uint32 elementSize = sizeof(dvModule);
    uint32 usedHeaderSize = (sizeof(dvRoot) + elementSize - 1)/elementSize;
    uint32 freeHeaderSize = (sizeof(dvRoot) + sizeof(uint32) + elementSize - 1)/elementSize;
    uint32 size = utMax(dvRootGetNumModuleTable(Root) + usedHeaderSize, freeHeaderSize);
    dvModule *dataPtr = dvRootGetModuleTables(Root) - usedHeaderSize;

    if(dvRootGetNumModuleTable(Root) == 0) {
        return;
    }
    *(dvRoot *)(void *)(dataPtr) = dvRootNull;
    *(uint32 *)(void *)(((dvRoot *)(void *)dataPtr) + 1) = size;
    dvRootSetNumModuleTable(Root, 0);
    dvSetFreeRootModuleTable(dvFreeRootModuleTable() + size);
}

/*----------------------------------------------------------------------------------------
  Resize the Root.ModuleTable array.
----------------------------------------------------------------------------------------*/
void dvRootResizeModuleTables(
    dvRoot Root,
    uint32 numModuleTables)
{
    uint32 freeSpace = dvAllocatedRootModuleTable() - dvUsedRootModuleTable();
    uint32 elementSize = sizeof(dvModule);
    uint32 usedHeaderSize = (sizeof(dvRoot) + elementSize - 1)/elementSize;
    uint32 freeHeaderSize = (sizeof(dvRoot) + sizeof(uint32) + elementSize - 1)/elementSize;
    uint32 newSize = utMax(numModuleTables + usedHeaderSize, freeHeaderSize);
    uint32 oldSize = utMax(dvRootGetNumModuleTable(Root) + usedHeaderSize, freeHeaderSize);
    dvModule *dataPtr;

    if(numModuleTables == 0) {
        if(dvRootGetNumModuleTable(Root) != 0) {
            dvRootFreeModuleTables(Root);
        };
        return;
    }
    if(dvRootGetNumModuleTable(Root) == 0) {
        dvRootAllocModuleTables(Root, newSize);
        return;
    };
    if(freeSpace < newSize) {
        allocMoreRootModuleTables(newSize);
    }
    dataPtr = dvRootGetModuleTables(Root) - usedHeaderSize;
    memcpy((void *)(dvRoots.ModuleTable + dvUsedRootModuleTable()), dataPtr,
        elementSize*utMin(oldSize, newSize));
    if(newSize > oldSize) {
        memset(dvRoots.ModuleTable + dvUsedRootModuleTable() + oldSize, 0xff,
            elementSize*(newSize - oldSize));
    }
    *(dvRoot *)(void *)dataPtr = dvRootNull;
    *(uint32 *)(void *)(((dvRoot *)(void *)dataPtr) + 1) = oldSize;
    dvSetFreeRootModuleTable(dvFreeRootModuleTable() + oldSize);
    dvRootSetModuleTableIndex(Root, dvUsedRootModuleTable() + usedHeaderSize);
    dvRootSetNumModuleTable(Root, numModuleTables);
    dvSetUsedRootModuleTable(dvUsedRootModuleTable() + newSize);
}

static void addRootModpathToHashTable(dvRoot Root, dvModpath _Modpath);
/*----------------------------------------------------------------------------------------
  Increase the size of the hash table.
----------------------------------------------------------------------------------------*/
static void resizeRootModpathHashTable(
    dvRoot Root)
{
    dvModpath _Modpath;
    dvModpath *Modpaths;
    uint32 numModpaths = dvRootGetNumModpathTable(Root) << 1;

    if(numModpaths == 0) {
        numModpaths = 2;
        dvRootAllocModpathTables(Root, 2);
    } else {
        dvRootResizeModpathTables(Root, numModpaths);
    }
    Modpaths = dvRootGetModpathTables(Root);
    /* Zero out the table */
    while(numModpaths-- != 0) {
        *Modpaths++ = dvModpathNull;
    }
    dvRootSetNumModpath(Root, 0);
    dvForeachRootModpath(Root, _Modpath) {
        if(dvModpathGetSym(_Modpath) != utSymNull) {
            addRootModpathToHashTable(Root, _Modpath);
        }
    } dvEndForeachRootModpath;
}

/*----------------------------------------------------------------------------------------
  Add an  to the Root.  If the table is near full, build a new one twice
  as big, delete the old one, and return the new one.
----------------------------------------------------------------------------------------*/
static void addRootModpathToHashTable(
    dvRoot Root,
    dvModpath _Modpath)
{
    dvModpath nextModpath;
    uint32 index;

    if(dvRootGetNumModpath(Root) >= dvRootGetNumModpathTable(Root)) {
        resizeRootModpathHashTable(Root);
        return;
    }
    index = (dvRootGetNumModpathTable(Root) - 1) & utSymGetHashValue(dvModpathGetSym(_Modpath));
    nextModpath = dvRootGetiModpathTable(Root, index);
    dvModpathSetNextTableRootModpath(_Modpath, nextModpath);
    dvRootSetiModpathTable(Root, index, _Modpath);
    dvRootSetNumModpath(Root, dvRootGetNumModpath(Root) + 1);
}

/*----------------------------------------------------------------------------------------
  Remove the Modpath from the hash table.
----------------------------------------------------------------------------------------*/
static void removeRootModpathFromHashTable(
   dvRoot Root,
   dvModpath _Modpath)
{
    uint32 index = (dvRootGetNumModpathTable(Root) - 1) & utSymGetHashValue(dvModpathGetSym(_Modpath));
    dvModpath prevModpath, nextModpath;
    
    nextModpath = dvRootGetiModpathTable(Root, index);
    if(nextModpath == _Modpath) {
        dvRootSetiModpathTable(Root, index, dvModpathGetNextTableRootModpath(nextModpath));
    } else {
        do {
            prevModpath = nextModpath;
            nextModpath = dvModpathGetNextTableRootModpath(nextModpath);
        } while(nextModpath != _Modpath);
        dvModpathSetNextTableRootModpath(prevModpath, dvModpathGetNextTableRootModpath(_Modpath));
    }
    dvRootSetNumModpath(Root, dvRootGetNumModpath(Root) - 1);
    dvModpathSetNextTableRootModpath(_Modpath, dvModpathNull);
}

/*----------------------------------------------------------------------------------------
  Find the Modpath from the Root and its name.
----------------------------------------------------------------------------------------*/
dvModpath dvRootFindModpath(
    dvRoot Root,
    utSym sym)
{
    uint32 mask = dvRootGetNumModpathTable(Root) - 1;
    dvModpath _Modpath;

    if(mask + 1 != 0) {
        _Modpath = dvRootGetiModpathTable(Root, utSymGetHashValue(sym) & mask);
        while(_Modpath != dvModpathNull) {
            if(dvModpathGetSym(_Modpath) == sym) {
                return _Modpath;
            }
            _Modpath = dvModpathGetNextTableRootModpath(_Modpath);
        }
    }
    return dvModpathNull;
}

/*----------------------------------------------------------------------------------------
  Find the Modpath from the Root and its name.
----------------------------------------------------------------------------------------*/
void dvRootRenameModpath(
    dvRoot Root,
    dvModpath _Modpath,
    utSym sym)
{
    if(dvModpathGetSym(_Modpath) != utSymNull) {
        removeRootModpathFromHashTable(Root, _Modpath);
    }
    dvModpathSetSym(_Modpath, sym);
    if(sym != utSymNull) {
        addRootModpathToHashTable(Root, _Modpath);
    }
}

/*----------------------------------------------------------------------------------------
  Add the Modpath to the head of the list on the Root.
----------------------------------------------------------------------------------------*/
void dvRootInsertModpath(
    dvRoot Root,
    dvModpath _Modpath)
{
#if defined(DD_DEBUG)
    if(Root == dvRootNull) {
        utExit("Non-existent Root");
    }
    if(_Modpath == dvModpathNull) {
        utExit("Non-existent Modpath");
    }
    if(dvModpathGetRoot(_Modpath) != dvRootNull) {
        utExit("Attempting to add dv to Root twice");
    }
#endif
    dvModpathSetNextRootModpath(_Modpath, dvRootGetFirstModpath(Root));
    if(dvRootGetFirstModpath(Root) != dvModpathNull) {
        dvModpathSetPrevRootModpath(dvRootGetFirstModpath(Root), _Modpath);
    }
    dvRootSetFirstModpath(Root, _Modpath);
    dvModpathSetPrevRootModpath(_Modpath, dvModpathNull);
    if(dvRootGetLastModpath(Root) == dvModpathNull) {
        dvRootSetLastModpath(Root, _Modpath);
    }
    dvModpathSetRoot(_Modpath, Root);
    if(dvModpathGetSym(_Modpath) != utSymNull) {
        addRootModpathToHashTable(Root, _Modpath);
    }
}

/*----------------------------------------------------------------------------------------
  Add the Modpath to the end of the list on the Root.
----------------------------------------------------------------------------------------*/
void dvRootAppendModpath(
    dvRoot Root,
    dvModpath _Modpath)
{
#if defined(DD_DEBUG)
    if(Root == dvRootNull) {
        utExit("Non-existent Root");
    }
    if(_Modpath == dvModpathNull) {
        utExit("Non-existent Modpath");
    }
    if(dvModpathGetRoot(_Modpath) != dvRootNull) {
        utExit("Attempting to add dv to Root twice");
    }
#endif
    dvModpathSetPrevRootModpath(_Modpath, dvRootGetLastModpath(Root));
    if(dvRootGetLastModpath(Root) != dvModpathNull) {
        dvModpathSetNextRootModpath(dvRootGetLastModpath(Root), _Modpath);
    }
    dvRootSetLastModpath(Root, _Modpath);
    dvModpathSetNextRootModpath(_Modpath, dvModpathNull);
    if(dvRootGetFirstModpath(Root) == dvModpathNull) {
        dvRootSetFirstModpath(Root, _Modpath);
    }
    dvModpathSetRoot(_Modpath, Root);
    if(dvModpathGetSym(_Modpath) != utSymNull) {
        addRootModpathToHashTable(Root, _Modpath);
    }
}

/*----------------------------------------------------------------------------------------
  Insert the Modpath to the Root after the previous Modpath.
----------------------------------------------------------------------------------------*/
void dvRootInsertAfterModpath(
    dvRoot Root,
    dvModpath prevModpath,
    dvModpath _Modpath)