Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/sources/formale Sprachen/GAP/pkg/datastructures/src/ (Algebra von RWTH Aachen Version 4.15.1^©) Datei vom 14.9.2025 mit Größe 2 kB

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.1 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.