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