nodemgmt-template.c

Go to the documentation of this file.
00001 /* LIBDGL -- a Directed Graph Library implementation
00002  * Copyright (C) 2002 Roberto Micarelli
00003  *
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017  */
00018 
00019 /*
00020  * best view with tabstop=4
00021  */
00022 
00023 int DGL_ADD_NODE_FUNC(dglGraph_s * pgraph,
00024                       dglInt32_t nId, void *pvNodeAttr, dglInt32_t nFlags)
00025 {
00026     DGL_T_NODEITEM_TYPE *pNodeItem;
00027     dglInt32_t *pnode;
00028 
00029     if (pgraph->Flags & DGL_GS_FLAT) {
00030         pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00031         return -pgraph->iErrno;
00032     }
00033 
00034     if ((pNodeItem = DGL_T_NODEITEM_Add(pgraph->pNodeTree, nId)) == NULL) {
00035         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00036         return -pgraph->iErrno;
00037     }
00038 
00039     if (DGL_T_NODEITEM_NodePTR(pNodeItem) == NULL) {
00040         if ((pnode = DGL_NODE_ALLOC(pgraph->NodeAttrSize)) == NULL) {
00041             pgraph->iErrno = DGL_ERR_MemoryExhausted;
00042             return -pgraph->iErrno;
00043         }
00044         memset(pnode, 0, DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
00045         DGL_NODE_ID(pnode) = nId;
00046         DGL_NODE_STATUS(pnode) = DGL_NS_ALONE;
00047         DGL_T_NODEITEM_Set_NodePTR(pNodeItem, pnode);
00048         pgraph->cNode++;
00049         pgraph->cAlone++;
00050     }
00051     else {
00052         /* node already exists */
00053         pgraph->iErrno = DGL_ERR_NodeAlreadyExist;
00054         return -pgraph->iErrno;
00055     }
00056     return 0;
00057 }
00058 
00059 #if !defined(_DGL_V1)
00060 /*
00061  * Delete the link from the node's out-edgeset
00062  */
00063 int DGL_DEL_NODE_OUTEDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nNode,
00064                               dglInt32_t nEdge)
00065 {
00066     DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
00067     dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
00068     dglEdgesetTraverser_s t;
00069 
00070     findNodeItem.nKey = nNode;
00071 
00072     if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
00073         pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00074         if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
00075             return 0;
00076         }
00077         if ((pnEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem)) != NULL) {
00078             if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
00079                 for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t);
00080                      pnEdge; pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
00081                     ) {
00082                     if (DGL_EDGE_ID(pnEdge) == nEdge) {
00083                         register dglInt32_t *pnSet;
00084                         register int i1, i2, c;
00085 
00086                         c = pnEdgeset[0];
00087 
00088                         if ((pnSet =
00089                              malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
00090                             pgraph->iErrno = DGL_ERR_MemoryExhausted;
00091                             return -pgraph->iErrno;
00092                         }
00093 
00094                         for (i1 = 0, i2 = 0; i2 < c; i2++) {
00095                             if (pnEdgeset[1 + i2] != nEdge) {
00096                                 pnSet[1 + i1++] = pnEdgeset[1 + i2];
00097                             }
00098                         }
00099                         pnSet[0] = i1;
00100 
00101                         free(pnEdgeset);
00102                         DGL_T_NODEITEM_Set_OutEdgesetPTR(pNodeItem, pnSet);
00103                         break;
00104                     }
00105                 }
00106             }
00107         }
00108         {                       /* check alone status */
00109             dglInt32_t *pIn, *pOut, *pNode;
00110 
00111             pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00112             pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00113             pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00114             if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
00115                 (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
00116                 ) {
00117                 if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
00118                     pgraph->cHead--;
00119                 if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
00120                     pgraph->cTail--;
00121                 DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
00122                 pgraph->cAlone++;
00123             }
00124         }
00125     }
00126     return 0;
00127 }
00128 
00129 int DGL_DEL_NODE_INEDGE_FUNC(dglGraph_s * pgraph, dglInt32_t nNode,
00130                              dglInt32_t nEdge)
00131 {
00132     DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
00133     dglInt32_t *pnEdgeset, *pnEdge, *pnNode;
00134     dglEdgesetTraverser_s t;
00135 
00136     findNodeItem.nKey = nNode;
00137 
00138     if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) != NULL) {
00139         pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00140         if (DGL_NODE_STATUS(pnNode) == DGL_NS_ALONE) {
00141             return 0;
00142         }
00143         if ((pnEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem)) != NULL) {
00144             if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &t, pnEdgeset) >= 0) {
00145                 for (pnEdge = DGL_EDGESET_T_FIRST_FUNC(&t);
00146                      pnEdge; pnEdge = DGL_EDGESET_T_NEXT_FUNC(&t)
00147                     ) {
00148                     if (DGL_EDGE_ID(pnEdge) == nEdge) {
00149                         register dglInt32_t *pnSet;
00150                         register int i1, i2, c;
00151 
00152                         c = pnEdgeset[0];
00153 
00154                         if ((pnSet =
00155                              malloc(sizeof(dglInt32_t) * (c + 1))) == NULL) {
00156                             pgraph->iErrno = DGL_ERR_MemoryExhausted;
00157                             return -pgraph->iErrno;
00158                         }
00159 
00160                         for (i1 = 0, i2 = 0; i2 < c; i2++) {
00161                             if (pnEdgeset[1 + i2] != nEdge) {
00162                                 pnSet[1 + i1++] = pnEdgeset[1 + i2];
00163                             }
00164                         }
00165                         pnSet[0] = i1;
00166 
00167                         free(pnEdgeset);
00168                         DGL_T_NODEITEM_Set_InEdgesetPTR(pNodeItem, pnSet);
00169                         break;
00170                     }
00171                 }
00172             }
00173         }
00174         {                       /* check alone status */
00175             dglInt32_t *pIn, *pOut, *pNode;
00176 
00177             pOut = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00178             pIn = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00179             pNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00180             if ((pOut == NULL || DGL_EDGESET_EDGECOUNT(pOut) == 0) &&
00181                 (pIn == NULL || DGL_EDGESET_EDGECOUNT(pIn) == 0)
00182                 ) {
00183                 if (DGL_NODE_STATUS(pNode) & DGL_NS_HEAD)
00184                     pgraph->cHead--;
00185                 if (DGL_NODE_STATUS(pNode) & DGL_NS_TAIL)
00186                     pgraph->cTail--;
00187                 DGL_NODE_STATUS(pNode) = DGL_NS_ALONE;
00188                 pgraph->cAlone++;
00189             }
00190         }
00191     }
00192     return 0;
00193 }
00194 #endif
00195 
00196 int DGL_DEL_NODE_FUNC(dglGraph_s * pgraph, dglInt32_t nNodeId)
00197 {
00198 #if defined(_DGL_V1)
00199     pgraph->iErrno = DGL_ERR_NotSupported;
00200     return -pgraph->iErrno;
00201 #else
00202     DGL_T_NODEITEM_TYPE *pNodeItem, findNodeItem;
00203     dglInt32_t *pEdgeset;
00204     dglInt32_t *pnode;
00205     dglInt32_t *pEdge;
00206     dglEdgesetTraverser_s trav;
00207 
00208     dglTreeEdge_s *pEdgeItem;
00209 
00210     if (pgraph->Flags & DGL_GS_FLAT) {
00211         pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00212         return -pgraph->iErrno;
00213     }
00214 
00215     if (pgraph->pNodeTree == NULL) {
00216         pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00217         return -pgraph->iErrno;
00218     }
00219 
00220     findNodeItem.nKey = nNodeId;
00221     if ((pNodeItem = avl_find(pgraph->pNodeTree, &findNodeItem)) == NULL) {
00222         pgraph->iErrno = DGL_ERR_NodeNotFound;
00223         return -pgraph->iErrno;
00224     }
00225 
00226     pnode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00227 
00228     if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
00229         goto node_is_alone;
00230 
00231     pEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(pNodeItem);
00232 
00233     if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
00234         return -pgraph->iErrno;
00235     for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav);
00236          pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
00237         ) {
00238         if (DGL_EDGE_TAILNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
00239             if (DGL_DEL_NODE_INEDGE_FUNC
00240                 (pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge),
00241                  DGL_EDGE_ID(pEdge)) < 0) {
00242                 return -pgraph->iErrno;
00243             }
00244         }
00245         if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
00246             /* prioritizer sync
00247              */
00248             if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00249                 if (dgl_edge_prioritizer_del
00250                     (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
00251                     return -pgraph->iErrno;
00252                 }
00253             }
00254             /*
00255              */
00256             pgraph->cEdge--;
00257             pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);
00258 
00259             avl_delete(pgraph->pEdgeTree, pEdgeItem);
00260             dglTreeEdgeCancel(pEdgeItem, NULL);
00261         }
00262     }
00263     DGL_EDGESET_T_RELEASE_FUNC(&trav);
00264 
00265     pEdgeset = DGL_T_NODEITEM_InEdgesetPTR(pNodeItem);
00266 
00267     if (DGL_EDGESET_T_INITIALIZE_FUNC(pgraph, &trav, pEdgeset) < 0)
00268         return -pgraph->iErrno;
00269     for (pEdge = DGL_EDGESET_T_FIRST_FUNC(&trav);
00270          pEdge; pEdge = DGL_EDGESET_T_NEXT_FUNC(&trav)
00271         ) {
00272         if (DGL_EDGE_HEADNODE_OFFSET(pEdge) != DGL_NODE_ID(pnode)) {
00273             if (DGL_DEL_NODE_OUTEDGE_FUNC
00274                 (pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge),
00275                  DGL_EDGE_ID(pEdge)) < 0) {
00276                 return -pgraph->iErrno;
00277             }
00278         }
00279         if ((pEdgeItem = trav.pvCurrentItem) != NULL) {
00280             /* prioritizer sync
00281              */
00282             if (pgraph->nOptions & DGL_GO_EdgePrioritize_COST) {
00283                 if (dgl_edge_prioritizer_del
00284                     (pgraph, DGL_EDGE_ID(pEdge), DGL_EDGE_COST(pEdge)) < 0) {
00285                     return -pgraph->iErrno;
00286                 }
00287             }
00288             /*
00289              */
00290             pgraph->cEdge--;
00291             pgraph->nnCost -= (dglInt64_t) DGL_EDGE_COST(pEdge);
00292 
00293             avl_delete(pgraph->pEdgeTree, pEdgeItem);
00294             dglTreeEdgeCancel(pEdgeItem, NULL);
00295         }
00296     }
00297     DGL_EDGESET_T_RELEASE_FUNC(&trav);
00298 
00299     if (DGL_NODE_STATUS(pnode) & DGL_NS_HEAD)
00300         pgraph->cHead--;
00301     if (DGL_NODE_STATUS(pnode) & DGL_NS_TAIL)
00302         pgraph->cTail--;
00303 
00304   node_is_alone:
00305     if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE)
00306         pgraph->cAlone--;
00307     pgraph->cNode--;
00308 
00309     avl_delete(pgraph->pNodeTree, pNodeItem);
00310     DGL_T_NODEITEM_Cancel(pNodeItem, NULL);
00311 
00312     return 0;
00313 #endif
00314 }
00315 
00316 dglInt32_t *DGL_GET_NODE_FUNC(dglGraph_s * pgraph, dglInt32_t nodeid)
00317 {
00318     register dglInt32_t top;    /* top of table */
00319     register dglInt32_t pos;    /* current position to compare */
00320     register dglInt32_t bot;    /* bottom of table */
00321     register dglInt32_t *pref;
00322     register int cwords;        /* size of a node in words of 32 bit */
00323     register dglTreeNode_s *ptreenode;
00324     dglTreeNode_s findnode;
00325     dglInt32_t id;
00326 
00327     pgraph->iErrno = 0;
00328     if (pgraph->Flags & DGL_GS_FLAT) {
00329         cwords = DGL_NODE_WSIZE(pgraph->NodeAttrSize);
00330         /*bot    = pgraph->iNodeBuffer / DGL_NODE_SIZEOF(pgraph->NodeAttrSize); */
00331         bot = pgraph->cNode;
00332         top = 0;
00333         pos = 0;
00334         pref = (dglInt32_t *) pgraph->pNodeBuffer;
00335 
00336         /* perform a binary search
00337          */
00338         while (top != bot) {
00339             pos = top + (bot - top) / 2;
00340             id = DGL_NODE_ID(&pref[pos * cwords]);
00341             if (id == nodeid) {
00342                 break;
00343             }
00344             else if (nodeid < id) {
00345                 bot = pos;
00346             }
00347             else if (nodeid > id) {
00348                 top = pos + 1;
00349             }
00350         }
00351         if (top == bot) {
00352             return NULL;
00353         }
00354         return &pref[pos * cwords];
00355     }
00356     else {
00357         findnode.nKey = nodeid;
00358         ptreenode = avl_find(pgraph->pNodeTree, &findnode);
00359         if (ptreenode && ptreenode->pv) {
00360             return ptreenode->pv;
00361         }
00362         return NULL;
00363     }
00364 }
00365 
00366 /*
00367  * if graph is FLAT retrieve the edge area from the pEdgeBuffer
00368  * if graph is TREE retrieve the node from the pNodeTree avl and return pv field
00369  */
00370 dglInt32_t *DGL_GET_NODE_OUTEDGESET_FUNC(dglGraph_s * pgraph,
00371                                          dglInt32_t * pnode)
00372 {
00373     DGL_T_NODEITEM_TYPE *ptreenode, findnode;
00374     dglInt32_t *pEdgeset;
00375 
00376     pgraph->iErrno = 0;
00377 
00378     if (pnode == NULL) {
00379         pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00380         return NULL;
00381     }
00382 
00383     if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
00384         pgraph->iErrno = DGL_ERR_NodeIsAComponent;
00385         return NULL;
00386     }
00387 
00388     if (pgraph->Flags & DGL_GS_FLAT) {
00389         pEdgeset =
00390             DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
00391         return pEdgeset;
00392     }
00393     else {
00394         findnode.nKey = DGL_NODE_ID(pnode);
00395         ptreenode = avl_find(pgraph->pNodeTree, &findnode);
00396         if (ptreenode && DGL_T_NODEITEM_OutEdgesetPTR(ptreenode)) {
00397             return DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
00398         }
00399         return NULL;
00400     }
00401 }
00402 
00403 dglInt32_t *DGL_GET_NODE_INEDGESET_FUNC(dglGraph_s * pgraph,
00404                                         dglInt32_t * pnode)
00405 {
00406 #if defined(_DGL_V1)
00407     pgraph->iErrno = DGL_ERR_NotSupported;
00408     return NULL;
00409 #endif
00410 
00411 #if defined(_DGL_V2)
00412     DGL_T_NODEITEM_TYPE *ptreenode, findnode;
00413     dglInt32_t *pEdgeset;
00414 
00415     pgraph->iErrno = 0;
00416 
00417     if (pnode == NULL) {
00418         pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00419         return NULL;
00420     }
00421 
00422     if (DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) {
00423         pgraph->iErrno = DGL_ERR_NodeIsAComponent;
00424         return NULL;
00425     }
00426 
00427     if (pgraph->Flags & DGL_GS_FLAT) {
00428         pEdgeset =
00429             DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnode));
00430         pEdgeset +=
00431             DGL_EDGESET_WSIZE(DGL_EDGESET_EDGECOUNT(pEdgeset),
00432                               pgraph->EdgeAttrSize);
00433         return pEdgeset;
00434     }
00435     else {
00436         findnode.nKey = DGL_NODE_ID(pnode);
00437         ptreenode = avl_find(pgraph->pNodeTree, &findnode);
00438         if (ptreenode && DGL_T_NODEITEM_InEdgesetPTR(ptreenode)) {
00439             return DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
00440         }
00441         return NULL;
00442     }
00443 #endif
00444 }

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1