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