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

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5