00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <stdio.h>
00024 #include <string.h>
00025 #include <sys/types.h>
00026 #include <sys/stat.h>
00027 #include <unistd.h>
00028 #include <stdlib.h>
00029 #include <errno.h>
00030
00031
00032 #include "type.h"
00033 #include "tree.h"
00034 #include "graph.h"
00035 #include "graph_v1.h"
00036 #include "helpers.h"
00037
00038
00039
00040
00041 #include "v1-defs.h"
00042 #include "sp-template.c"
00043 #include "nodemgmt-template.c"
00044 #include "edgemgmt-template.c"
00045 #include "misc-template.c"
00046
00047
00048
00049
00050 #define DGL_DEFINE_TREE_PROCS 1
00051 #include "v1-defs.h"
00052 #include "sp-template.c"
00053 #include "span-template.c"
00054 #undef DGL_DEFINE_TREE_PROCS
00055
00056
00057
00058
00059 #define DGL_DEFINE_FLAT_PROCS 1
00060 #include "v1-defs.h"
00061 #include "sp-template.c"
00062 #include "span-template.c"
00063 #undef DGL_DEFINE_FLAT_PROCS
00064
00065
00066
00067 int dgl_dijkstra_V1 (
00068 dglGraph_s * pgraph ,
00069 dglSPReport_s ** ppReport ,
00070 dglInt32_t * pDistance ,
00071 dglInt32_t nStart ,
00072 dglInt32_t nDestination ,
00073 dglSPClip_fn fnClip,
00074 void * pvClipArg,
00075 dglSPCache_s * pCache
00076 )
00077 {
00078 if ( pgraph->Flags & DGL_GS_FLAT ) {
00079 return dgl_dijkstra_V1_FLAT(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00080 }
00081 else {
00082 return dgl_dijkstra_V1_TREE(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00083 }
00084 }
00085
00086
00087 int dgl_depthfirst_spanning_V1(
00088 dglGraph_s * pgraphIn ,
00089 dglGraph_s * pgraphOut ,
00090 dglInt32_t nVertex ,
00091 void * pvVisited ,
00092 dglSpanClip_fn fnClip ,
00093 void * pvClipArg
00094 )
00095 {
00096 if ( pgraphIn->Flags & DGL_GS_FLAT ) {
00097 return dgl_span_depthfirst_spanning_V1_FLAT(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00098 }
00099 else {
00100 return dgl_span_depthfirst_spanning_V1_TREE(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00101 }
00102 }
00103
00104 int dgl_minimum_spanning_V1(
00105 dglGraph_s * pgraphIn ,
00106 dglGraph_s * pgraphOut ,
00107 dglInt32_t nVertex ,
00108 dglSpanClip_fn fnClip ,
00109 void * pvClipArg
00110 )
00111 {
00112 if ( pgraphIn->Flags & DGL_GS_FLAT ) {
00113 return dgl_span_minimum_spanning_V1_FLAT(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00114 }
00115 else {
00116 return dgl_span_minimum_spanning_V1_TREE(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00117 }
00118 }
00119
00120
00121 int dgl_initialize_V1( dglGraph_s * pgraph )
00122 {
00123 if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( dglTreeNodeCompare, NULL, dglTreeGetAllocator() );
00124 if ( pgraph->pNodeTree == NULL ) {
00125 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00126 return -pgraph->iErrno;
00127 }
00128 pgraph->pEdgeTree = NULL;
00129 return 0;
00130 }
00131
00132 int dgl_release_V1( dglGraph_s * pgraph )
00133 {
00134 pgraph->iErrno = 0;
00135
00136 if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00137 if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00138 if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer );
00139 if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer );
00140 if ( pgraph->edgePrioritizer.pvAVL ) avl_destroy( pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel );
00141 if ( pgraph->nodePrioritizer.pvAVL ) avl_destroy( pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel );
00142
00143 return 0;
00144 }
00145
00146
00147 int dgl_write_V1( dglGraph_s * pgraph , int fd )
00148 {
00149 long nret , cnt , tot;
00150
00151 pgraph->iErrno = 0;
00152
00153 if ( write( fd , & pgraph->Version , 1 ) != 1 )
00154 {
00155 pgraph->iErrno = DGL_ERR_Write;
00156 return -pgraph->iErrno;
00157 }
00158
00159 if ( write( fd , & pgraph->Endian , 1 ) != 1 )
00160 {
00161 pgraph->iErrno = DGL_ERR_Write;
00162 return -pgraph->iErrno;
00163 }
00164
00165 if ( write( fd , & pgraph->NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00166 {
00167 pgraph->iErrno = DGL_ERR_Write;
00168 return -pgraph->iErrno;
00169 }
00170
00171 if ( write( fd , & pgraph->EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00172 {
00173 pgraph->iErrno = DGL_ERR_Write;
00174 return -pgraph->iErrno;
00175 }
00176
00177 for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00178 {
00179 if ( write( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00180 {
00181 pgraph->iErrno = DGL_ERR_Write;
00182 return -pgraph->iErrno;
00183 }
00184 }
00185
00186 if ( write( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00187 {
00188 pgraph->iErrno = DGL_ERR_Write;
00189 return -pgraph->iErrno;
00190 }
00191
00192 if ( write( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00193 {
00194 pgraph->iErrno = DGL_ERR_Write;
00195 return -pgraph->iErrno;
00196 }
00197
00198 if ( write( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00199 {
00200 pgraph->iErrno = DGL_ERR_Write;
00201 return -pgraph->iErrno;
00202 }
00203
00204 if ( write( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00205 {
00206 pgraph->iErrno = DGL_ERR_Write;
00207 return -pgraph->iErrno;
00208 }
00209
00210 if ( write( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00211 {
00212 pgraph->iErrno = DGL_ERR_Write;
00213 return -pgraph->iErrno;
00214 }
00215
00216 if ( write( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00217 {
00218 pgraph->iErrno = DGL_ERR_Write;
00219 return -pgraph->iErrno;
00220 }
00221
00222 if ( write( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00223 {
00224 pgraph->iErrno = DGL_ERR_Write;
00225 return -pgraph->iErrno;
00226 }
00227
00228 if ( write( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00229 {
00230 pgraph->iErrno = DGL_ERR_Write;
00231 return -pgraph->iErrno;
00232 }
00233
00234 for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00235 {
00236 if ( (nret = write( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00237 {
00238 pgraph->iErrno = DGL_ERR_Write;
00239 return -pgraph->iErrno;
00240 }
00241 }
00242
00243 for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00244 {
00245 if ( (nret = write( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00246 {
00247 pgraph->iErrno = DGL_ERR_Write;
00248 return -pgraph->iErrno;
00249 }
00250 }
00251
00252 return 0;
00253 }
00254
00255
00256 int dgl_read_V1( dglGraph_s * pgraph , int fd )
00257 {
00258 long nret , cnt , tot;
00259 dglByte_t Endian;
00260 dglInt32_t NodeAttrSize , EdgeAttrSize;
00261 int i, cn, fSwap;
00262 dglInt32_t * pn;
00263
00264 if ( read( fd , & Endian , 1 ) != 1 )
00265 {
00266 pgraph->iErrno = DGL_ERR_Read;
00267 return -pgraph->iErrno;
00268 }
00269
00270 fSwap = 0;
00271 #ifdef DGL_ENDIAN_BIG
00272 if ( Endian == DGL_ENDIAN_LITTLE ) fSwap = 1;
00273 #else
00274 if ( Endian == DGL_ENDIAN_BIG ) fSwap = 1;
00275 #endif
00276
00277 if ( read( fd , & NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00278 {
00279 pgraph->iErrno = DGL_ERR_Read;
00280 return -pgraph->iErrno;
00281 }
00282 if ( fSwap ) dgl_swapInt32Bytes( & NodeAttrSize );
00283
00284 if ( read( fd , & EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00285 {
00286 pgraph->iErrno = DGL_ERR_Read;
00287 return -pgraph->iErrno;
00288 }
00289 if ( fSwap ) dgl_swapInt32Bytes( & EdgeAttrSize );
00290
00291 if ( (nret = dglInitialize( pgraph, 1, NodeAttrSize, EdgeAttrSize, NULL )) < 0 )
00292 {
00293 return nret;
00294 }
00295
00296 for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00297 {
00298 if ( (nret=read( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) )) != sizeof( dglInt32_t ) )
00299 {
00300 pgraph->iErrno = DGL_ERR_Read;
00301 return -pgraph->iErrno;
00302 }
00303 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->aOpaqueSet[ cnt ] );
00304 }
00305
00306 if ( read( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00307 {
00308 pgraph->iErrno = DGL_ERR_Read;
00309 return -pgraph->iErrno;
00310 }
00311 if ( fSwap ) dgl_swapInt64Bytes( & pgraph->nnCost );
00312
00313 if ( read( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00314 {
00315 pgraph->iErrno = DGL_ERR_Read;
00316 return -pgraph->iErrno;
00317 }
00318 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cNode );
00319
00320 if ( read( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00321 {
00322 pgraph->iErrno = DGL_ERR_Read;
00323 return -pgraph->iErrno;
00324 }
00325 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cHead );
00326
00327 if ( read( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00328 {
00329 pgraph->iErrno = DGL_ERR_Read;
00330 return -pgraph->iErrno;
00331 }
00332 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cTail );
00333
00334 if ( read( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00335 {
00336 pgraph->iErrno = DGL_ERR_Read;
00337 return -pgraph->iErrno;
00338 }
00339 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cAlone );
00340
00341 if ( read( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00342 {
00343 pgraph->iErrno = DGL_ERR_Read;
00344 return -pgraph->iErrno;
00345 }
00346 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cEdge );
00347
00348 if ( read( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00349 {
00350 pgraph->iErrno = DGL_ERR_Read;
00351 return -pgraph->iErrno;
00352 }
00353 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iNodeBuffer );
00354
00355 if ( read( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00356 {
00357 pgraph->iErrno = DGL_ERR_Read;
00358 return -pgraph->iErrno;
00359 }
00360 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iEdgeBuffer );
00361
00362 if ( (pgraph->pNodeBuffer = malloc( pgraph->iNodeBuffer )) == NULL )
00363 {
00364 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00365 return -pgraph->iErrno;
00366 }
00367
00368 if ( (pgraph->pEdgeBuffer = malloc( pgraph->iEdgeBuffer )) == NULL )
00369 {
00370 free( pgraph->pNodeBuffer );
00371 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00372 return -pgraph->iErrno;
00373 }
00374
00375 for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00376 {
00377 if ( (nret = read( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00378 {
00379 free( pgraph->pNodeBuffer );
00380 free( pgraph->pEdgeBuffer );
00381 pgraph->iErrno = DGL_ERR_Read;
00382 return -pgraph->iErrno;
00383 }
00384 }
00385 if ( fSwap ) {
00386 pn = (dglInt32_t*) pgraph->pNodeBuffer;
00387 cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00388 for ( i = 0 ; i < cn ; i ++ ) {
00389 dgl_swapInt32Bytes( & pn[i] );
00390 }
00391 }
00392
00393 for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00394 {
00395 if ( (nret = read( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00396 {
00397 free( pgraph->pNodeBuffer );
00398 free( pgraph->pEdgeBuffer );
00399 pgraph->iErrno = DGL_ERR_Read;
00400 return -pgraph->iErrno;
00401 }
00402 }
00403 if ( fSwap ) {
00404 pn = (dglInt32_t*) pgraph->pEdgeBuffer;
00405 cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00406 for ( i = 0 ; i < cn ; i ++ ) {
00407 dgl_swapInt32Bytes( & pn[i] );
00408 }
00409 }
00410
00411 pgraph->Flags |= 0x1;
00412 return 0;
00413 }