nodemgmt-template.c

Go to the documentation of this file.

/* LIBDGL -- a Directed Graph Library implementation
 * SPDX-FileCopyrightText: 2002 Roberto Micarelli
 * SPDX-FileCopyrightText: GRASS Development Team
 * SPDX-License-Identifier: GPL-2.0-or-later
 */
 
/*
 * best view with tabstop=4
 */
 
#include <grass/gis.h>
 
int DGL_ADD_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nId,
                      void *pvNodeAttr G_UNUSED, dglInt32_t nFlags G_UNUSED)
{
    DGL_T_NODEITEM_TYPE *pNodeItem;
    dglInt32_t *pnode;
 
    if (pgraph->Flags & DGL_GS_FLAT) {
        pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
        return -pgraph->iErrno;
    }
 
    if ((pNodeItem = DGL_T_NODEITEM_Add(pgraph->pNodeTree, nId)) == NULL) {
        pgraph->iErrno = DGL_ERR_MemoryExhausted;
        return -pgraph->iErrno;
    }
 
    if (DGL_T_NODEITEM_NodePTR(pNodeItem) == NULL) {
        if ((pnode = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
            pgraph->iErrno = DGL_ERR_MemoryExhausted;
            return -pgraph->iErrno;
        }
        memset(pnode, 0, DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
        DGL_NODE_ID(pnode) = nId;
        DGL_NODE_STATUS(pnode) = DGL_NS_ALONE;
        DGL_T_NODEITEM_Set_NodePTR(pNodeItem, pnode);
        pgraph->cNode++;
        pgraph->cAlone++;
    }
    else {
        /* node already exists */
        pgraph->iErrno = DGL_ERR_NodeAlreadyExist;
        return -pgraph->iErrno;
    }
    return 0;
}
 
#if !defined(_DGL_V1)
/*
 * Delete the link from the node's out-edgeset
 */
int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode,
                              dglInt32_t nEdge)
{
    DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
    dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
    dglEdgesetTraverser_s t;
 
    findNodeItem.nKey = nNode;
 
    if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
        pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
        if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
            return 0;
        }
        if ((pnEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem)) != NULL) {
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
                for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t); pnEdge;
                     pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)) {
                    if (DGL_EDGE_ID(pnEdge) == nEdge) {
                        register dglInt32_t *pnSet;
                        register int i1, i2, c;
 
                        c = pnEdgeset[0];
 
                        if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) ==
                            NULL) {
                            pgraph->iErrno = DGL_ERR_MemoryExhausted;
                            return -pgraph->iErrno;
                        }
 
                        for (i1 = 0, i2 = 0; i2 < c; i2++) {
                            if (pnEdgeset[1 + i2] != nEdge) {
                                pnSet[1 + i1++] = pnEdgeset[1 + i2];
                            }
                        }
                        pnSet[0] = i1;
 
                        free(pnEdgeset);
                        DGL_T_NODEITEM_Set_OutEdgesetPTR(pNodeItem, pnSet);
                        break;
                    }
                }
            }
        }
        { /* check alone status */
            dglInt32_t *pIn, *pOut, *pNode;
 
            pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
            pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
            pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
            if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
                (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)) {
                if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
                    pgraph->cHead--;
                if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
                    pgraph->cTail--;
                DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
                pgraph->cAlone++;
            }
        }
    }
    return 0;
}
 
int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s *pgraph, dglInt32_t nNode,
                             dglInt32_t nEdge)
{
    DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
    dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
    dglEdgesetTraverser_s t;
 
    findNodeItem.nKey = nNode;
 
    if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
        pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
        if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
            return 0;
        }
        if ((pnEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem)) != NULL) {
            if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
                for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t); pnEdge;
                     pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)) {
                    if (DGL_EDGE_ID(pnEdge) == nEdge) {
                        register dglInt32_t *pnSet;
                        register int i1, i2, c;
 
                        c = pnEdgeset[0];
 
                        if ((pnSet = malloc(sizeof(dglInt32_t) * (c + 1))) ==
                            NULL) {
                            pgraph->iErrno = DGL_ERR_MemoryExhausted;
                            return -pgraph->iErrno;
                        }
 
                        for (i1 = 0, i2 = 0; i2 < c; i2++) {
                            if (pnEdgeset[1 + i2] != nEdge) {
                                pnSet[1 + i1++] = pnEdgeset[1 + i2];
                            }
                        }
                        pnSet[0] = i1;
 
                        free(pnEdgeset);
                        DGL_T_NODEITEM_Set_InEdgesetPTR(pNodeItem, pnSet);
                        break;
                    }
                }
            }
        }
        { /* check alone status */
            dglInt32_t *pIn, *pOut, *pNode;
 
            pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
            pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
            pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
            if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
                (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)) {
                if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
                    pgraph->cHead--;
                if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
                    pgraph->cTail--;
                DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
                pgraph->cAlone++;
            }
        }
    }
    return 0;
}
#endif
 
int DGL_DEL_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nNodeId G_UNUSED)
{
#if defined(_DGL_V1)
    pgraph->iErrno = DGL_ERR_NotSupported;
    return -pgraph->iErrno;
#else
    DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
    dglInt32_t *pEdgeset;
    dglInt32_t *pnode;
    dglInt32_t *pEdge;
    dglEdgesetTraverser_s trav;
 
    dglTreeEdge_s *pEdgeItem;
 
    if (pgraph->Flags & DGL_GS_FLAT) {
        pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
        return -pgraph->iErrno;
    }
 
    if (pgraph->pNodeTree == NULL) {
        pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
        return -pgraph->iErrno;
    }
 
    findNodeItem.nKey = nNodeId;
    if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) == NULL) {
        pgraph->iErrno = DGL_ERR_NodeNotFound;
        return -pgraph->iErrno;
    }
 
    pnode = DGL_T_NODEITEM_NodePTR(pNodeItem);
 
    if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
        goto node_is_alone;
 
    pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
 
    if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
        return -pgraph->iErrno;
    for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav); pEdge;
         pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)) {
        if (DGL_EDGE_TAILNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
            if (DGL_DEL_NODE_INEDGE_FUNC(pgraph,
                                         DGL_EDGE_TAILNODE_OFFSET(pEdge),
                                         DGL_EDGE_ID(pEdge)) < 0) {
                return -pgraph->iErrno;
            }
        }
        if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
            /* prioritizer sync
             */
            if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
                if (dgl_edge_prioritizer_del(pgraph, DGL_EDGE_ID(pEdge),
                                             DGL_EDGE_COST(pEdge)) < 0) {
                    return -pgraph->iErrno;
                }
            }
            /*
             */
            pgraph->cEdge--;
            pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);
 
            avl_delete(pgraph->pEdgeTree, pEdgeItem);
            dglTreeEdgeCancel(pEdgeItem, NULL);
        }
    }
    DGL_EDGESET_T_RELEASE_FUNC(&trav);
 
    pEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
 
    if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
        return -pgraph->iErrno;
    for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav); pEdge;
         pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)) {
        if (DGL_EDGE_HEADNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
            if (DGL_DEL_NODE_OUTEDGE_FUNC(pgraph,
                                          DGL_EDGE_HEADNODE_OFFSET(pEdge),
                                          DGL_EDGE_ID(pEdge)) < 0) {
                return -pgraph->iErrno;
            }
        }
        if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
            /* prioritizer sync
             */
            if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
                if (dgl_edge_prioritizer_del(pgraph, DGL_EDGE_ID(pEdge),
                                             DGL_EDGE_COST(pEdge)) < 0) {
                    return -pgraph->iErrno;
                }
            }
            /*
             */
            pgraph->cEdge--;
            pgraph->nnCost -= (dglInt64_t)DGL_EDGE_COST(pEdge);
 
            avl_delete(pgraph->pEdgeTree, pEdgeItem);
            dglTreeEdgeCancel(pEdgeItem, NULL);
        }
    }
    DGL_EDGESET_T_RELEASE_FUNC(&trav);
 
    if (DGL_NODE_STATUS(pnode) & DGL_NS_HEAD)
        pgraph->cHead--;
    if (DGL_NODE_STATUS(pnode) & DGL_NS_TAIL)
        pgraph->cTail--;
 
node_is_alone:
    if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
        pgraph->cAlone--;
    pgraph->cNode--;
 
    avl_delete(pgraph->pNodeTree, pNodeItem);
    DGL_T_NODEITEM_Cancel(pNodeItem, NULL);
 
    return 0;
#endif
}
 
dglInt32_t *DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
{
    register dglInt32_t top; /* top of table */
    register dglInt32_t pos; /* current position to compare */
    register dglInt32_t bot; /* bottom of table */
    register dglInt32_t *pref;
    register int cwords; /* size of a node in words of 32 bit */
    register dglTreeNode_s *ptreenode;
    dglTreeNode_s findnode;
    dglInt32_t id;
 
    pgraph->iErrno = 0;
    if (pgraph->Flags & DGL_GS_FLAT) {
        cwords = DGL_NODE_WSIZE(pgraph->NodeAttrSize);
        /*bot    = pgraph->iNodeBuffer / DGL_NODE_SIZEOF(pgraph->NodeAttrSize);
         */
        bot = pgraph->cNode;
        top = 0;
        pos = 0;
        pref = (dglInt32_t *)pgraph->pNodeBuffer;
 
        /* perform a binary search
         */
        while (top != bot) {
            pos = top + (bot - top) / 2;
            id = DGL_NODE_ID(&pref[pos * cwords]);
            if (id == nodeid) {
                break;
            }
            else if (nodeid < id) {
                bot = pos;
            }
            else if (nodeid > id) {
                top = pos + 1;
            }
        }
        if (top == bot) {
            return NULL;
        }
        return &pref[pos * cwords];
    }
    else {
        findnode.nKey = nodeid;
        ptreenode = avl_find(pgraph->pNodeTree, &findnode);
        if (ptreenode && ptreenode->pv) {
            return ptreenode->pv;
        }
        return NULL;
    }
}
 
/*
 * if graph is FLAT retrieve the edge area from the pEdgeBuffer
 * if graph is TREE retrieve the node from the pNodeTree avl and return pv field
 */
dglInt32_t *DGL_GET_NODE_OUTEDGESET_FUNC(dglGraph_s *pgraph, dglInt32_t *pnode)
{
    DGL_T_NODEITEM_TYPE *ptreenode, findnode;
    dglInt32_t *pEdgeset;
 
    pgraph->iErrno = 0;
 
    if (pnode == NULL) {
        pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
        return NULL;
    }
 
    if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
        pgraph->iErrno = DGL_ERR_NodeIsAComponent;
        return NULL;
    }
 
    if (pgraph->Flags & DGL_GS_FLAT) {
        pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
        return pEdgeset;
    }
    else {
        findnode.nKey = DGL_NODE_ID(pnode);
        ptreenode = avl_find(pgraph->pNodeTree, &findnode);
        if (ptreenode && DGL_T_NODEITEM_OutEdgesetPTR(ptreenode)) {
            return DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
        }
        return NULL;
    }
}
 
dglInt32_t *DGL_GET_NODE_INEDGESET_FUNC(dglGraph_s *pgraph,
                                        dglInt32_t *pnode G_UNUSED)
{
#if defined(_DGL_V1)
    pgraph->iErrno = DGL_ERR_NotSupported;
    return NULL;
#endif
 
#if defined(_DGL_V2)
    DGL_T_NODEITEM_TYPE *ptreenode, findnode;
    dglInt32_t *pEdgeset;
 
    pgraph->iErrno = 0;
 
    if (pnode == NULL) {
        pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
        return NULL;
    }
 
    if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
        pgraph->iErrno = DGL_ERR_NodeIsAComponent;
        return NULL;
    }
 
    if (pgraph->Flags & DGL_GS_FLAT) {
        pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
        pEdgeset += DGL_EDGESET_WSIZE(DGL_EDGESET_EDGECOUNT(pEdgeset),
                                      pgraph->EdgeAttrSize);
        return pEdgeset;
    }
    else {
        findnode.nKey = DGL_NODE_ID(pnode);
        ptreenode = avl_find(pgraph->pNodeTree, &findnode);
        if (ptreenode && DGL_T_NODEITEM_InEdgesetPTR(ptreenode)) {
            return DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
        }
        return NULL;
    }
#endif
}