Quelle skiplist.c Sprache: C

/*
* Datastructures: GAP package providing common datastructures.
* Licensed under the GPL 2 or later.
*/

#include "skiplist.h"

static Obj FuncDS_Skiplist_RemoveNode(Obj self, Obj lst, Obj nx)
{
    UInt level, len;
    Obj  node, x;
    GAP_ASSERT(IS_PLIST(lst));
    len = LEN_PLIST(lst);
    GAP_ASSERT(IS_PLIST(nx));
    GAP_ASSERT(len >= 2 && ELM_PLIST(lst, 2) && IS_PLIST(ELM_PLIST(lst, 2)) &&
               LEN_PLIST(ELM_PLIST(lst, 2)) >= 2 &&
               nx == ELM_PLIST(ELM_PLIST(lst, 2), 2));
    for (level = len; level > 1; level--) {
        node = ELM_PLIST(lst, level);
        GAP_ASSERT(node);
        GAP_ASSERT(IS_PLIST(node));
        if (LEN_PLIST(node) >= level && ELM_PLIST(node, level) == nx) {
            if (LEN_PLIST(nx) < level) {
                SET_ELM_PLIST(node, level, 0);
                SET_LEN_PLIST(node, level - 1);
            }
            else {
                x = ELM_PLIST(nx, level);
                SET_ELM_PLIST(node, level, x);
            }
        }
    }
    return 0;
}

static Obj FuncDS_Skiplist_Scan(Obj self, Obj sl, Obj val, Obj lessFunc)
{
    Obj  ptr;
    UInt level;
    Obj  lst;
    Obj  nx;
    Obj  o;
    ptr = sl;
    GAP_ASSERT(IS_PLIST(ptr));
    level = LEN_PLIST(ptr);
    lst = NEW_PLIST(T_PLIST_DENSE, level);
    SET_LEN_PLIST(lst, level);
    while (level > 1) {
        if (LEN_PLIST(ptr) < level) {
            SET_ELM_PLIST(lst, level, ptr);    // no need for CHANGED_BAG
                                               // calls, ptr is in the
                                               // skiplist
            level--;
        }
        else {
            nx = ELM_PLIST(ptr, level);
            GAP_ASSERT(nx);
            GAP_ASSERT(IS_PLIST(nx));
            GAP_ASSERT(LEN_PLIST(nx) >= 1);
            GAP_ASSERT(ELM_PLIST(nx, 1));
            o = ELM_PLIST(nx, 1);
            if (True != CALL_2ARGS(lessFunc, o, val)) {
                SET_ELM_PLIST(lst, level, ptr);
                level--;
            }
            else {
                ptr = nx;
            }
        }
    }
    CHANGED_BAG(lst);    // just in case
    return lst;
}

static StructGVarFunc GVarFuncs[] = {
    GVAR_FUNC_3ARGS(DS_Skiplist_Scan, skiplist, val, lessFunc),
    GVAR_FUNC_2ARGS(DS_Skiplist_RemoveNode, lst, nx),
    { 0 }
};

static Int InitKernel(void)
{
    InitHdlrFuncsFromTable(GVarFuncs);

    return 0;
}

static Int InitLibrary(void)
{
    InitGVarFuncsFromTable(GVarFuncs);
    return 0;
}

struct DatastructuresModule SkiplistModule = {
    .initKernel = InitKernel, .initLibrary = InitLibrary,
};

quality79%

¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.