misc-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 /*
00024  * Edge Traversing
00025  */
00026 int DGL_EDGE_T_INITIALIZE_FUNC( dglGraph_s * pGraph , dglEdgeTraverser_s * pT , dglEdgePrioritizer_s * pEP ) {
00027 #if defined(_DGL_V1)
00028         pGraph->iErrno = DGL_ERR_NotSupported;
00029         return -pGraph->iErrno;
00030 #else
00031         if ( pGraph->Flags & DGL_GS_FLAT ) {
00032                 if ( pEP && pEP->pvAVL ) {
00033                         if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) {
00034                                 pGraph->iErrno = DGL_ERR_MemoryExhausted;
00035                                 return -pGraph->iErrno;
00036                         }
00037                         avl_t_init( pT->pvAVLT , pEP->pvAVL );
00038                         pT->pnEdge = NULL;
00039                         pT->pEdgePrioritizer = pEP;
00040                 }
00041                 else {
00042                         pT->pvAVLT = NULL;
00043                         pT->pnEdge = NULL;
00044                         pT->pEdgePrioritizer = NULL;
00045                 }
00046         }
00047         else {
00048                 if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) {
00049                         pGraph->iErrno = DGL_ERR_MemoryExhausted;
00050                         return -pGraph->iErrno;
00051                 }
00052                 if ( pEP && pEP->pvAVL ) {
00053                         avl_t_init( pT->pvAVLT , pEP->pvAVL );
00054                         pT->pnEdge = NULL;
00055                         pT->pEdgePrioritizer = pEP;
00056                 }
00057                 else {
00058                         avl_t_init( pT->pvAVLT , pGraph->pEdgeTree );
00059                         pT->pnEdge = NULL;
00060                         pT->pEdgePrioritizer = NULL;
00061                 }
00062         }
00063         pT->pGraph = pGraph;
00064         return 0;
00065 #endif
00066 }
00067 
00068 void DGL_EDGE_T_RELEASE_FUNC( dglEdgeTraverser_s * pT ) {
00069 #if defined(_DGL_V1)
00070         pT->pGraph->iErrno = DGL_ERR_NotSupported;
00071 #else
00072         if ( pT->pvAVLT ) free( pT->pvAVLT );
00073         pT->pvAVLT = NULL;
00074         pT->pnEdge = NULL;
00075         pT->pEdgePrioritizer = NULL;
00076 #endif
00077 }
00078 
00079 dglInt32_t * DGL_EDGE_T_FIRST_FUNC( dglEdgeTraverser_s * pT ) {
00080 #if defined(_DGL_V1)
00081         pT->pGraph->iErrno = DGL_ERR_NotSupported;
00082         return NULL;
00083 #else
00084         dglGraph_s * pG = pT->pGraph;
00085 
00086         pT->pnEdge = NULL;
00087         if ( pT->pvAVLT && pT->pEdgePrioritizer ) {
00088                 dglEdgePrioritizer_s * pPri = pT->pEdgePrioritizer;
00089                 dglTreeEdgePri32_s * pItem;
00090 
00091                 pItem = avl_t_first( pT->pvAVLT, pPri->pvAVL );
00092                 if ( pItem ) {
00093 /*
00094 printf("edge_t_first: cEdge=%ld\n", pItem->cnData);
00095 */
00096                         pPri->cEdge = pItem->cnData;
00097                         pPri->iEdge = 0;
00098                         if ( pPri->iEdge < pPri->cEdge ) {
00099                                 pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
00100                                 pPri->iEdge++;
00101                         }
00102                 }
00103                 pPri->pEdgePri32Item = pItem;
00104         }
00105         else if ( pT->pvAVLT ) {
00106                 dglTreeEdge_s * pEdgeItem;
00107 
00108                 if ( (pEdgeItem = avl_t_first( pT->pvAVLT, pG->pEdgeTree )) == NULL ) {
00109                         pT->pnEdge = NULL;
00110                 }
00111                 else {
00112                         pT->pnEdge = pEdgeItem->pv;
00113                 }
00114         }
00115         else {
00116                 if ( pG->cEdge > 0 ) pT->pnEdge = (dglInt32_t*)pG->pEdgeBuffer;
00117                 else pT->pnEdge = NULL;
00118         }
00119         return pT->pnEdge;
00120 #endif
00121 }
00122 
00123 dglInt32_t * DGL_EDGE_T_NEXT_FUNC( dglEdgeTraverser_s * pT )
00124 {
00125 #if defined(_DGL_V1)
00126         pT->pGraph->iErrno = DGL_ERR_NotSupported;
00127         return NULL;
00128 #else
00129         dglGraph_s * pG = pT->pGraph;
00130 
00131         pT->pnEdge = NULL;
00132 
00133         if ( pT->pvAVLT && pT->pEdgePrioritizer ) {
00134                 dglEdgePrioritizer_s * pPri = pT->pEdgePrioritizer;
00135                 dglTreeEdgePri32_s * pItem = pPri->pEdgePri32Item;
00136 
00137                 if (pItem && pPri->iEdge < pPri->cEdge) {
00138                         pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
00139                         pPri->iEdge++;
00140                 }
00141                 else {
00142                         if ( (pItem = avl_t_next(pT->pvAVLT)) != NULL ) {
00143                                 pPri->cEdge = pItem->cnData;
00144                                 pPri->iEdge = 0;
00145                                 if ( pPri->iEdge < pPri->cEdge ) {
00146                                         pT->pnEdge = DGL_GET_EDGE_FUNC(pG, pItem->pnData[pPri->iEdge]);
00147                                         pPri->iEdge++;
00148                                 }
00149                         }
00150                         pPri->pEdgePri32Item = pItem;
00151                 }
00152         }
00153         else if ( pT->pvAVLT ) {
00154                 dglTreeEdge_s * pItem;
00155 
00156                 if ( (pItem = avl_t_next( pT->pvAVLT )) != NULL ) {
00157                         pT->pnEdge = pItem->pv;
00158                 }
00159         }
00160         else {
00161                 pT->pnEdge += DGL_NODE_WSIZE( pG->EdgeAttrSize);
00162                 if (pT->pnEdge >= (dglInt32_t*)(pG->pEdgeBuffer + pG->iEdgeBuffer) ) {
00163                         pT->pnEdge = NULL;
00164                 }
00165         }
00166         return pT->pnEdge;
00167 #endif
00168 }
00169 
00170 
00171 /*
00172  * Node Traversing
00173  */
00174 int DGL_NODE_T_INITIALIZE_FUNC( dglGraph_s * pGraph , dglNodeTraverser_s * pT ) {
00175         if ( pGraph->Flags & DGL_GS_FLAT ) {
00176                 pT->pnNode = NULL;
00177                 pT->pvAVLT = NULL;
00178         }
00179         else {
00180                 if ( (pT->pvAVLT = malloc( sizeof(struct avl_traverser) )) == NULL ) {
00181                         pGraph->iErrno = DGL_ERR_MemoryExhausted;
00182                         return -pGraph->iErrno;
00183                 }
00184                 avl_t_init( pT->pvAVLT , pGraph->pNodeTree );
00185                 pT->pnNode = NULL;
00186         }
00187         pT->pGraph = pGraph;
00188         return 0;
00189 }
00190 
00191 void DGL_NODE_T_RELEASE_FUNC( dglNodeTraverser_s * pT ) {
00192         if ( pT->pvAVLT ) free( pT->pvAVLT );
00193         pT->pvAVLT = NULL;
00194         pT->pnNode = NULL;
00195 }
00196 
00197 dglInt32_t * DGL_NODE_T_FIRST_FUNC( dglNodeTraverser_s * pT )
00198 {
00199         DGL_T_NODEITEM_TYPE * pNodeItem;
00200 
00201         if ( pT->pvAVLT ) {
00202                 if ( (pNodeItem = avl_t_first( pT->pvAVLT, pT->pGraph->pNodeTree )) == NULL )
00203                         pT->pnNode = NULL;
00204                 else
00205                         pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00206         }
00207         else {
00208                 if ( pT->pGraph->cNode > 0 ) pT->pnNode = (dglInt32_t*)pT->pGraph->pNodeBuffer;
00209                 else pT->pnNode = NULL;
00210         }
00211         return pT->pnNode;
00212 }
00213 
00214 dglInt32_t * DGL_NODE_T_NEXT_FUNC( dglNodeTraverser_s * pT )
00215 {
00216         DGL_T_NODEITEM_TYPE * pNodeItem;
00217 
00218         if ( pT->pvAVLT ) {
00219                 if ( (pNodeItem = avl_t_next( pT->pvAVLT )) == NULL )
00220                         pT->pnNode = NULL;
00221                 else
00222                         pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00223         }
00224         else {
00225                 pT->pnNode += DGL_NODE_WSIZE( pT->pGraph->NodeAttrSize );
00226                 if ( pT->pnNode >= (dglInt32_t*)(pT->pGraph->pNodeBuffer + pT->pGraph->iNodeBuffer) ) pT->pnNode = NULL;
00227         }
00228         return pT->pnNode;
00229 }
00230 
00231 dglInt32_t * DGL_NODE_T_FIND_FUNC( dglNodeTraverser_s * pT , dglInt32_t nNodeId )
00232 {
00233         DGL_T_NODEITEM_TYPE * pNodeItem , findItem;
00234 
00235         if ( pT->pvAVLT ) {
00236                 findItem.nKey = nNodeId;
00237                 if ( (pNodeItem = avl_t_find( pT->pvAVLT , pT->pGraph->pNodeTree , &findItem )) == NULL )
00238                         pT->pnNode = NULL;
00239                 else
00240                         pT->pnNode = DGL_T_NODEITEM_NodePTR(pNodeItem);
00241         }
00242         else {
00243                 pT->pnNode = DGL_GET_NODE_FUNC(pT->pGraph, nNodeId);
00244         }
00245         return pT->pnNode;
00246 }
00247 
00248 
00249 /*
00250  * Edgeset Traversing
00251  */
00252 int     DGL_EDGESET_T_INITIALIZE_FUNC(
00253                         dglGraph_s * pGraph ,
00254                         dglEdgesetTraverser_s * pT ,
00255                         dglInt32_t * pnEdgeset
00256                         )
00257 {
00258         pT->pGraph = pGraph;
00259         pT->pnEdgeset = pnEdgeset;
00260         pT->cEdge = (pnEdgeset)?*pnEdgeset:0;
00261         pT->iEdge = 0;
00262         return 0;
00263 }
00264 
00265 
00266 void DGL_EDGESET_T_RELEASE_FUNC( dglEdgesetTraverser_s * pT )
00267 {
00268 }
00269 
00270 dglInt32_t * DGL_EDGESET_T_FIRST_FUNC( dglEdgesetTraverser_s * pT )
00271 {
00272 #if defined(_DGL_V2)
00273         dglInt32_t * pnOffset;
00274         dglTreeEdge_s * pEdgeItem, EdgeItem;
00275 #endif
00276 
00277         if ( pT->cEdge == 0 ) return NULL;
00278         pT->iEdge = 1;
00279 #if defined(_DGL_V1)
00280         return pT->pnEdgeset + 1;
00281 #endif
00282 #if defined(_DGL_V2)
00283         pnOffset = pT->pnEdgeset + 1;   
00284         if ( pT->pGraph->Flags & DGL_GS_FLAT ) {
00285                 pT->pvCurrentItem = NULL;
00286                 return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset);
00287         }
00288         else {
00289                 EdgeItem.nKey = *pnOffset;
00290                 if ( (pEdgeItem = avl_find( pT->pGraph->pEdgeTree, &EdgeItem )) != NULL) {
00291                         pT->pvCurrentItem = pEdgeItem;
00292                         return pEdgeItem->pv;
00293                 }
00294         }
00295 #endif
00296         return NULL;
00297 }
00298 
00299 
00300 dglInt32_t * DGL_EDGESET_T_NEXT_FUNC( dglEdgesetTraverser_s * pT )
00301 {
00302 #if defined(_DGL_V2)
00303         dglInt32_t * pnOffset;
00304         dglTreeEdge_s * pEdgeItem, EdgeItem;
00305 #endif
00306 
00307         if ( pT->cEdge > 0 && pT->iEdge < pT->cEdge ) {
00308 #if defined(_DGL_V1)
00309                 return DGL_EDGESET_EDGE_PTR(pT->pnEdgeset, pT->iEdge++, pT->pGraph->EdgeAttrSize);
00310 #endif
00311 #if defined(_DGL_V2)
00312                 pnOffset = pT->pnEdgeset + 1 + pT->iEdge++;     
00313                 if ( pT->pGraph->Flags & DGL_GS_FLAT ) {
00314                         return DGL_EDGEBUFFER_SHIFT(pT->pGraph, *pnOffset);
00315                 }
00316                 else {
00317                         EdgeItem.nKey = *pnOffset;
00318                         if ( (pEdgeItem = avl_find( pT->pGraph->pEdgeTree, &EdgeItem )) != NULL) {
00319                                 pT->pvCurrentItem = pEdgeItem;
00320                                 return pEdgeItem->pv;
00321                         }
00322                 }
00323 #endif
00324         }
00325         return NULL;
00326 }
00327 
00328 
00329 /*
00330  * Flatten the graph
00331  */
00332 int DGL_FLATTEN_FUNC( dglGraph_s * pgraph )
00333 {
00334         register DGL_T_NODEITEM_TYPE * ptreenode;
00335 #if defined(_DGL_V2)
00336         register dglTreeEdge_s * ptreeEdge;
00337         int i;
00338 #endif
00339         register dglInt32_t *   pEdge;
00340         register dglInt32_t *   pnode;
00341         register dglInt32_t *   pnodescan;
00342         dglInt32_t *                            pOutEdgeset;
00343         dglInt32_t *                            pInEdgeset;
00344         int                                     cOutEdgeset;
00345         int                                     cInEdgeset;
00346 
00347         struct avl_traverser    avlTraverser;
00348 
00349         if ( pgraph->Flags & DGL_GS_FLAT )
00350         {
00351                 pgraph->iErrno = DGL_ERR_BadOnFlatGraph;
00352                 return -pgraph->iErrno;
00353         }
00354 
00355         pgraph->pNodeBuffer = NULL; /* should be already */
00356         pgraph->iNodeBuffer = 0;
00357         pgraph->pEdgeBuffer = NULL;
00358         pgraph->iEdgeBuffer = 0;
00359 
00360 
00361 #if defined(_DGL_V2)
00362 /*
00363 printf("flatten: traversing edges\n");
00364 */
00365         avl_t_init( & avlTraverser, pgraph->pEdgeTree );
00366 
00367         for     (
00368                         ptreeEdge = avl_t_first( & avlTraverser , pgraph->pEdgeTree ) ;
00369                         ptreeEdge ;
00370                         ptreeEdge = avl_t_next( & avlTraverser )
00371                 )
00372         {
00373                 pEdge = ptreeEdge->pv;
00374 
00375 /*
00376 printf( "flatten: add edge %ld to edge buffer\n", DGL_EDGE_ID(pEdge) );
00377 */
00378 
00379                 pgraph->pEdgeBuffer = realloc(
00380                                 pgraph->pEdgeBuffer , 
00381                                 pgraph->iEdgeBuffer + DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize)
00382                                 );
00383 
00384                 if ( pgraph->pEdgeBuffer == NULL ) {
00385                         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00386                         return -pgraph->iErrno;
00387                 }
00388 
00389                 memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer, pEdge, DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize) );
00390 
00391                 pgraph->iEdgeBuffer += DGL_EDGE_SIZEOF(pgraph->EdgeAttrSize);
00392         }
00393 #endif
00394 
00395 /*
00396 printf("flatten: traversing nodes\n");
00397 */
00398         avl_t_init( & avlTraverser, pgraph->pNodeTree );
00399 
00400         for     (
00401                         ptreenode = avl_t_first( & avlTraverser , pgraph->pNodeTree ) ;
00402                         ptreenode ;
00403                         ptreenode = avl_t_next( & avlTraverser )
00404                 )
00405         {
00406                 pnode       = DGL_T_NODEITEM_NodePTR(ptreenode);
00407                 pOutEdgeset = DGL_T_NODEITEM_OutEdgesetPTR(ptreenode);
00408                 pInEdgeset  = DGL_T_NODEITEM_InEdgesetPTR(ptreenode);
00409 
00410                 if ( !(DGL_NODE_STATUS(pnode) & DGL_NS_ALONE) )
00411                 {
00412                         cOutEdgeset = (pOutEdgeset) ?
00413                                         DGL_EDGESET_SIZEOF(DGL_EDGESET_EDGECOUNT(pOutEdgeset), pgraph->EdgeAttrSize) :
00414                                         sizeof(dglInt32_t);
00415 
00416 #if !defined(_DGL_V1)
00417                         cInEdgeset = (pInEdgeset) ?
00418                                         DGL_EDGESET_SIZEOF(DGL_EDGESET_EDGECOUNT(pInEdgeset),  pgraph->EdgeAttrSize) :
00419                                         sizeof(dglInt32_t);
00420 #else
00421                         cInEdgeset = 0;
00422 #endif
00423 
00424                         pgraph->pEdgeBuffer = realloc( pgraph->pEdgeBuffer ,
00425                                         pgraph->iEdgeBuffer + cOutEdgeset + cInEdgeset );
00426 
00427                         if ( pgraph->pEdgeBuffer == NULL )
00428                         {
00429                                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00430                                 return -pgraph->iErrno;
00431                         }
00432 
00433                         {
00434                         dglInt32_t nDummy = 0;
00435 
00436                         memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer , (pOutEdgeset)?pOutEdgeset:&nDummy , cOutEdgeset );
00437 #if !defined(_DGL_V1)
00438                         memcpy( pgraph->pEdgeBuffer + pgraph->iEdgeBuffer + cOutEdgeset , (pInEdgeset)?pInEdgeset:&nDummy, cInEdgeset );
00439 #endif
00440                         }
00441 
00442                         DGL_NODE_EDGESET_OFFSET(pnode) = pgraph->iEdgeBuffer;
00443 
00444                         pgraph->iEdgeBuffer += cOutEdgeset + cInEdgeset;
00445                 }
00446 
00447                 pgraph->pNodeBuffer = realloc(pgraph->pNodeBuffer, pgraph->iNodeBuffer + DGL_NODE_SIZEOF(pgraph->NodeAttrSize));
00448 
00449                 if ( pgraph->pNodeBuffer == NULL )
00450                 {
00451                         pgraph->iErrno = DGL_ERR_MemoryExhausted;
00452                         return -pgraph->iErrno;
00453                 }
00454 
00455                 memcpy( pgraph->pNodeBuffer + pgraph->iNodeBuffer , pnode , DGL_NODE_SIZEOF(pgraph->NodeAttrSize) );
00456                 pgraph->iNodeBuffer += DGL_NODE_SIZEOF(pgraph->NodeAttrSize);
00457         }
00458 
00459 #if defined(_DGL_V2)
00460         if ( pgraph->pEdgeTree ) {
00461                 avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00462                 pgraph->pEdgeTree = NULL;
00463         }
00464 #endif
00465 
00466         if ( pgraph->pNodeTree ) {
00467                 avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00468                 pgraph->pNodeTree = NULL;
00469         }
00470 
00471         pgraph->Flags |= DGL_GS_FLAT; /* flattened */
00472 
00473         /*
00474          * convert node-id to node-offset
00475          */
00476         DGL_FOREACH_NODE(pgraph, pnodescan)
00477         {
00478                 if ( !(DGL_NODE_STATUS(pnodescan) & DGL_NS_ALONE) )
00479                 {
00480                         pOutEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pnodescan));
00481 
00482 #if defined(_DGL_V2)
00483                         for( i = 0 ; i < pOutEdgeset[0] ; i ++ ) {
00484 /*
00485 printf("flatten: node %ld: scan out edge %ld/%ld - %ld\n", DGL_NODE_ID(pnodescan), i+1, pOutEdgeset[0], pOutEdgeset[i+1]);
00486 */
00487                                 pEdge = DGL_GET_EDGE_FUNC(pgraph, pOutEdgeset[i+1]);
00488                                 if (pEdge == NULL) {
00489                                         pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00490                                         return -pgraph->iErrno;
00491                                 }
00492                                 /*
00493 printf("         retrieved id %ld\n", DGL_EDGE_ID(pEdge) );
00494 */
00495                                 pOutEdgeset[i+1] = DGL_EDGEBUFFER_OFFSET(pgraph,pEdge);
00496                         }
00497 
00498                         pInEdgeset = pOutEdgeset + pOutEdgeset[0] + 1;
00499 
00500                         for( i = 0 ; i < pInEdgeset[0] ; i ++ ) {
00501                                         /*
00502 printf("flatten: node %ld: scan in edge %ld/%ld - %ld\n",
00503                            DGL_NODE_ID(pnodescan), i+1, pInEdgeset[0], pInEdgeset[i+1]);
00504                            */
00505                                 pEdge = DGL_GET_EDGE_FUNC(pgraph, pInEdgeset[i+1]);
00506                                 if (pEdge == NULL) {
00507                                         pgraph->iErrno = DGL_ERR_UnexpectedNullPointer;
00508                                         return -pgraph->iErrno;
00509                                 }
00510                                 /*
00511 printf("         retrieved id %ld\n", DGL_EDGE_ID(pEdge) );
00512 */
00513                                 pInEdgeset[i+1] = DGL_EDGEBUFFER_OFFSET(pgraph,pEdge);
00514                         }
00515 #endif
00516 
00517 #if defined(_DGL_V2)
00518                         {
00519                         int iEdge;
00520                         DGL_FOREACH_EDGE(pgraph, pOutEdgeset, pEdge, iEdge)
00521 #else
00522                         DGL_FOREACH_EDGE(pgraph, pOutEdgeset, pEdge)
00523 #endif
00524                         {
00525                                 if ( (pnode = DGL_GET_NODE_FUNC( pgraph, DGL_EDGE_HEADNODE_OFFSET(pEdge))) == NULL )
00526                                 {
00527                                         pgraph->iErrno = DGL_ERR_HeadNodeNotFound;
00528                                         return -pgraph->iErrno;
00529                                 }
00530                                 DGL_EDGE_HEADNODE_OFFSET(pEdge) = DGL_NODEBUFFER_OFFSET(pgraph, pnode);
00531 
00532                                 if ( (pnode = DGL_GET_NODE_FUNC( pgraph , DGL_EDGE_TAILNODE_OFFSET(pEdge))) == NULL )
00533                                 {
00534                                         pgraph->iErrno = DGL_ERR_TailNodeNotFound;
00535                                         return -pgraph->iErrno;
00536                                 }
00537                                 DGL_EDGE_TAILNODE_OFFSET(pEdge) = DGL_NODEBUFFER_OFFSET(pgraph, pnode);
00538                         }
00539 #if defined(_DGL_V2)
00540                         }
00541 #endif
00542                 }
00543         }
00544 
00545         return 0;
00546 }
00547 
00548 
00549 int DGL_UNFLATTEN_FUNC( dglGraph_s * pgraph )
00550 {
00551         register dglInt32_t *           pHead;
00552         register dglInt32_t *           pTail;
00553         register dglInt32_t *           pEdge;
00554         register dglInt32_t *           pEdgeset;
00555         int                                                     nret;
00556 
00557         if ( ! (pgraph->Flags & DGL_GS_FLAT) )
00558         {
00559                 pgraph->iErrno = DGL_ERR_BadOnTreeGraph;
00560                 return -pgraph->iErrno;
00561         }
00562 
00563         /*
00564          * unflag it now to avoid DGL_ADD_EDGE_FUNC() failure
00565          */
00566         pgraph->Flags &= ~DGL_GS_FLAT;
00567         pgraph->cNode = 0;
00568         pgraph->cEdge = 0;
00569         pgraph->cHead = 0;
00570         pgraph->cTail = 0;
00571         pgraph->cAlone = 0;
00572         pgraph->nnCost = (dglInt64_t)0;
00573 
00574         if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( DGL_T_NODEITEM_Compare, NULL, dglTreeGetAllocator() );
00575         if ( pgraph->pNodeTree == NULL ) {
00576                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00577                 return -pgraph->iErrno;
00578         }
00579 #if defined(_DGL_V1)
00580         pgraph->pEdgeTree = NULL;
00581 #else
00582         if ( pgraph->pEdgeTree == NULL ) pgraph->pEdgeTree = avl_create( dglTreeEdgeCompare, NULL, dglTreeGetAllocator() );
00583         if ( pgraph->pEdgeTree == NULL ) {
00584                 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00585                 return -pgraph->iErrno;
00586         }
00587 #endif
00588 
00589         DGL_FOREACH_NODE(pgraph,pHead)
00590         {
00591                 if ( DGL_NODE_STATUS(pHead) & DGL_NS_HEAD )
00592                 {
00593                         pEdgeset = DGL_EDGEBUFFER_SHIFT(pgraph, DGL_NODE_EDGESET_OFFSET(pHead));
00594 
00595 #if defined(_DGL_V2)
00596                         {
00597                         int iEdge;
00598                         DGL_FOREACH_EDGE(pgraph, pEdgeset, pEdge, iEdge)
00599 #else
00600                         DGL_FOREACH_EDGE(pgraph, pEdgeset, pEdge)
00601 #endif
00602                         {
00603                                 pTail = DGL_NODEBUFFER_SHIFT(pgraph, DGL_EDGE_TAILNODE_OFFSET(pEdge));
00604 
00605                                 nret = DGL_ADD_EDGE_FUNC( pgraph,
00606                                                         DGL_NODE_ID(pHead),
00607                                                         DGL_NODE_ID(pTail),
00608                                                         DGL_EDGE_COST(pEdge),
00609                                                         DGL_EDGE_ID(pEdge),
00610                                                         DGL_NODE_ATTR_PTR(pHead),
00611                                                         DGL_NODE_ATTR_PTR(pTail),
00612                                                         DGL_EDGE_ATTR_PTR(pEdge),
00613                                                         0 );
00614 
00615                                 if ( nret < 0 ) {
00616                                         goto error;
00617                                 }
00618                         }
00619 #if defined(_DGL_V2)
00620                         }
00621 #endif
00622                 }
00623                 else if ( DGL_NODE_STATUS(pHead) & DGL_NS_ALONE ) {
00624                         nret = DGL_ADD_NODE_FUNC( pgraph, 
00625                                                 DGL_NODE_ID(pHead),
00626                                                 DGL_NODE_ATTR_PTR(pHead),
00627                                                 0 );
00628                         if ( nret < 0 ) {
00629                                 goto error;
00630                         }
00631                 }
00632         }
00633 
00634         /* move away flat-state data
00635          */
00636         if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer );
00637         if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer );
00638         pgraph->pNodeBuffer = NULL;
00639         pgraph->pEdgeBuffer = NULL;
00640         return 0;
00641 
00642 error:
00643         if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00644         if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00645         pgraph->pNodeTree = NULL;
00646         pgraph->pEdgeTree = NULL;
00647         pgraph->Flags |= DGL_GS_FLAT;
00648         return nret;
00649 }
00650 

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