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_v2.h"
00036 #include "helpers.h"
00037
00038
00039
00040
00041 #include "v2-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 "v2-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 "v2-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_V2 (
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_V2_FLAT(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00080 }
00081 else {
00082 return dgl_dijkstra_V2_TREE(pgraph,ppReport,pDistance,nStart,nDestination,fnClip,pvClipArg,pCache);
00083 }
00084 }
00085
00086
00087 int dgl_depthfirst_spanning_V2(
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_V2_FLAT(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00098 }
00099 else {
00100 return dgl_span_depthfirst_spanning_V2_TREE(pgraphIn,pgraphOut,nVertex,pvVisited,fnClip,pvClipArg);
00101 }
00102 }
00103
00104 int dgl_minimum_spanning_V2(
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_V2_FLAT(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00114 }
00115 else {
00116 return dgl_span_minimum_spanning_V2_TREE(pgraphIn,pgraphOut,nVertex,fnClip,pvClipArg);
00117 }
00118 }
00119
00120
00121 int dgl_initialize_V2( dglGraph_s * pgraph )
00122 {
00123 if ( pgraph->pNodeTree == NULL ) pgraph->pNodeTree = avl_create( dglTreeNode2Compare, NULL, dglTreeGetAllocator() );
00124 if ( pgraph->pNodeTree == NULL ) {
00125 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00126 return -pgraph->iErrno;
00127 }
00128 if ( pgraph->pEdgeTree == NULL ) pgraph->pEdgeTree = avl_create( dglTreeEdgeCompare, NULL, dglTreeGetAllocator() );
00129 if ( pgraph->pEdgeTree == NULL ) {
00130 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00131 return -pgraph->iErrno;
00132 }
00133 return 0;
00134 }
00135
00136 int dgl_release_V2( dglGraph_s * pgraph )
00137 {
00138 pgraph->iErrno = 0;
00139
00140 if ( pgraph->pNodeTree ) avl_destroy( pgraph->pNodeTree, dglTreeNodeCancel );
00141 if ( pgraph->pEdgeTree ) avl_destroy( pgraph->pEdgeTree, dglTreeEdgeCancel );
00142 if ( pgraph->pNodeBuffer ) free( pgraph->pNodeBuffer );
00143 if ( pgraph->pEdgeBuffer ) free( pgraph->pEdgeBuffer );
00144 if ( pgraph->edgePrioritizer.pvAVL ) avl_destroy( pgraph->edgePrioritizer.pvAVL, dglTreeEdgePri32Cancel );
00145 if ( pgraph->nodePrioritizer.pvAVL ) avl_destroy( pgraph->nodePrioritizer.pvAVL, dglTreeNodePri32Cancel );
00146
00147 return 0;
00148 }
00149
00150
00151 int dgl_write_V2( dglGraph_s * pgraph , int fd )
00152 {
00153 long nret , cnt , tot;
00154
00155 pgraph->iErrno = 0;
00156
00157 if ( write( fd , & pgraph->Version , 1 ) != 1 )
00158 {
00159 pgraph->iErrno = DGL_ERR_Write;
00160 return -pgraph->iErrno;
00161 }
00162
00163 if ( write( fd , & pgraph->Endian , 1 ) != 1 )
00164 {
00165 pgraph->iErrno = DGL_ERR_Write;
00166 return -pgraph->iErrno;
00167 }
00168
00169 if ( write( fd , & pgraph->NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00170 {
00171 pgraph->iErrno = DGL_ERR_Write;
00172 return -pgraph->iErrno;
00173 }
00174
00175 if ( write( fd , & pgraph->EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00176 {
00177 pgraph->iErrno = DGL_ERR_Write;
00178 return -pgraph->iErrno;
00179 }
00180
00181 for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00182 {
00183 if ( write( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00184 {
00185 pgraph->iErrno = DGL_ERR_Write;
00186 return -pgraph->iErrno;
00187 }
00188 }
00189
00190 if ( write( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00191 {
00192 pgraph->iErrno = DGL_ERR_Write;
00193 return -pgraph->iErrno;
00194 }
00195
00196 if ( write( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00197 {
00198 pgraph->iErrno = DGL_ERR_Write;
00199 return -pgraph->iErrno;
00200 }
00201
00202 if ( write( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00203 {
00204 pgraph->iErrno = DGL_ERR_Write;
00205 return -pgraph->iErrno;
00206 }
00207
00208 if ( write( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00209 {
00210 pgraph->iErrno = DGL_ERR_Write;
00211 return -pgraph->iErrno;
00212 }
00213
00214 if ( write( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00215 {
00216 pgraph->iErrno = DGL_ERR_Write;
00217 return -pgraph->iErrno;
00218 }
00219
00220 if ( write( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00221 {
00222 pgraph->iErrno = DGL_ERR_Write;
00223 return -pgraph->iErrno;
00224 }
00225
00226 if ( write( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00227 {
00228 pgraph->iErrno = DGL_ERR_Write;
00229 return -pgraph->iErrno;
00230 }
00231
00232 if ( write( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00233 {
00234 pgraph->iErrno = DGL_ERR_Write;
00235 return -pgraph->iErrno;
00236 }
00237
00238 for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00239 {
00240 if ( (nret = write( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00241 {
00242 pgraph->iErrno = DGL_ERR_Write;
00243 return -pgraph->iErrno;
00244 }
00245 }
00246
00247 for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00248 {
00249 if ( (nret = write( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00250 {
00251 pgraph->iErrno = DGL_ERR_Write;
00252 return -pgraph->iErrno;
00253 }
00254 }
00255
00256 return 0;
00257 }
00258
00259
00260 int dgl_read_V2( dglGraph_s * pgraph , int fd , int version )
00261 {
00262 long nret , cnt , tot;
00263 dglByte_t Endian;
00264 dglInt32_t NodeAttrSize , EdgeAttrSize;
00265 int i, cn, fSwap;
00266 dglInt32_t * pn;
00267
00268 if ( read( fd , & Endian , 1 ) != 1 )
00269 {
00270 pgraph->iErrno = DGL_ERR_Read;
00271 return -pgraph->iErrno;
00272 }
00273
00274 fSwap = 0;
00275 #ifdef DGL_ENDIAN_BIG
00276 if ( Endian == DGL_ENDIAN_LITTLE ) fSwap = 1;
00277 #else
00278 if ( Endian == DGL_ENDIAN_BIG ) fSwap = 1;
00279 #endif
00280
00281 if ( read( fd , & NodeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00282 {
00283 pgraph->iErrno = DGL_ERR_Read;
00284 return -pgraph->iErrno;
00285 }
00286 if ( fSwap ) dgl_swapInt32Bytes( & NodeAttrSize );
00287
00288 if ( read( fd , & EdgeAttrSize , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00289 {
00290 pgraph->iErrno = DGL_ERR_Read;
00291 return -pgraph->iErrno;
00292 }
00293 if ( fSwap ) dgl_swapInt32Bytes( & EdgeAttrSize );
00294
00295 if ( (nret = dglInitialize( pgraph, version, NodeAttrSize, EdgeAttrSize, NULL )) < 0 )
00296 {
00297 return nret;
00298 }
00299
00300 for ( cnt = 0 ; cnt < 16 ; cnt ++ )
00301 {
00302 if ( (nret=read( fd , & pgraph->aOpaqueSet[ cnt ] , sizeof( dglInt32_t ) )) != sizeof( dglInt32_t ) )
00303 {
00304 pgraph->iErrno = DGL_ERR_Read;
00305 return -pgraph->iErrno;
00306 }
00307 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->aOpaqueSet[ cnt ] );
00308 }
00309
00310 if ( read( fd , & pgraph->nnCost , sizeof( dglInt64_t ) ) != sizeof( dglInt64_t ) )
00311 {
00312 pgraph->iErrno = DGL_ERR_Read;
00313 return -pgraph->iErrno;
00314 }
00315 if ( fSwap ) dgl_swapInt64Bytes( & pgraph->nnCost );
00316
00317 if ( read( fd , & pgraph->cNode , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00318 {
00319 pgraph->iErrno = DGL_ERR_Read;
00320 return -pgraph->iErrno;
00321 }
00322 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cNode );
00323
00324 if ( read( fd , & pgraph->cHead , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00325 {
00326 pgraph->iErrno = DGL_ERR_Read;
00327 return -pgraph->iErrno;
00328 }
00329 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cHead );
00330
00331 if ( read( fd , & pgraph->cTail , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00332 {
00333 pgraph->iErrno = DGL_ERR_Read;
00334 return -pgraph->iErrno;
00335 }
00336 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cTail );
00337
00338 if ( read( fd , & pgraph->cAlone , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00339 {
00340 pgraph->iErrno = DGL_ERR_Read;
00341 return -pgraph->iErrno;
00342 }
00343 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cAlone );
00344
00345 if ( read( fd , & pgraph->cEdge , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00346 {
00347 pgraph->iErrno = DGL_ERR_Read;
00348 return -pgraph->iErrno;
00349 }
00350 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->cEdge );
00351
00352 if ( read( fd , & pgraph->iNodeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00353 {
00354 pgraph->iErrno = DGL_ERR_Read;
00355 return -pgraph->iErrno;
00356 }
00357 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iNodeBuffer );
00358
00359 if ( read( fd , & pgraph->iEdgeBuffer , sizeof( dglInt32_t ) ) != sizeof( dglInt32_t ) )
00360 {
00361 pgraph->iErrno = DGL_ERR_Read;
00362 return -pgraph->iErrno;
00363 }
00364 if ( fSwap ) dgl_swapInt32Bytes( & pgraph->iEdgeBuffer );
00365
00366 if ( (pgraph->pNodeBuffer = malloc( pgraph->iNodeBuffer )) == NULL )
00367 {
00368 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00369 return -pgraph->iErrno;
00370 }
00371
00372 if ( (pgraph->pEdgeBuffer = malloc( pgraph->iEdgeBuffer )) == NULL )
00373 {
00374 free( pgraph->pNodeBuffer );
00375 pgraph->iErrno = DGL_ERR_MemoryExhausted;
00376 return -pgraph->iErrno;
00377 }
00378
00379 for( tot = 0 , cnt = pgraph->iNodeBuffer ; tot < cnt ; tot += nret )
00380 {
00381 if ( (nret = read( fd , & pgraph->pNodeBuffer[ tot ] , cnt - tot )) <= 0 )
00382 {
00383 free( pgraph->pNodeBuffer );
00384 free( pgraph->pEdgeBuffer );
00385 pgraph->iErrno = DGL_ERR_Read;
00386 return -pgraph->iErrno;
00387 }
00388 }
00389 if ( fSwap ) {
00390 pn = (dglInt32_t*) pgraph->pNodeBuffer;
00391 cn = pgraph->iNodeBuffer / sizeof(dglInt32_t);
00392 for ( i = 0 ; i < cn ; i ++ ) {
00393 dgl_swapInt32Bytes( & pn[i] );
00394 }
00395 }
00396
00397 for( tot = 0 , cnt = pgraph->iEdgeBuffer ; tot < cnt ; tot += nret )
00398 {
00399 if ( (nret = read( fd , & pgraph->pEdgeBuffer[ tot ] , cnt - tot )) <= 0 )
00400 {
00401 free( pgraph->pNodeBuffer );
00402 free( pgraph->pEdgeBuffer );
00403 pgraph->iErrno = DGL_ERR_Read;
00404 return -pgraph->iErrno;
00405 }
00406 }
00407 if ( fSwap ) {
00408 pn = (dglInt32_t*) pgraph->pEdgeBuffer;
00409 cn = pgraph->iEdgeBuffer / sizeof(dglInt32_t);
00410 for ( i = 0 ; i < cn ; i ++ ) {
00411 dgl_swapInt32Bytes( & pn[i] );
00412 }
00413 }
00414
00415 pgraph->Flags |= 0x1;
00416 return 0;
00417 }