42 #if !defined(DGL_DEFINE_TREE_PROCS) && !defined(DGL_DEFINE_FLAT_PROCS)
86 VisitedItem.
nKey = nDestination;
92 PredistItem.
nKey = nDestination;
114 unsigned char *pstack =
NULL;
123 VisitedItem.
nKey = nDestination;
129 PredistItem.
nKey = nDestination;
135 for (PredistItem.
nKey = nDestination,
141 if (pPredistItem->
nFrom < 0) {
188 if (arc.
nFrom == nStart)
192 if (pPredistItem ==
NULL) {
203 pReport->
cArc = istack;
237 #if defined(DGL_DEFINE_TREE_PROCS) || defined(DGL_DEFINE_FLAT_PROCS)
239 #define __EDGELOOP_BODY_1(f) \
241 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
244 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
246 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \
247 pgraph->iErrno = DGL_ERR_BadEdge; \
250 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
252 clipInput.pnPrevEdge = NULL; \
253 clipInput.pnNodeFrom = pStart; \
254 clipInput.pnEdge = pEdge; \
255 clipInput.pnNodeTo = pDestination; \
256 clipInput.nFromDistance = 0; \
257 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \
259 pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) ); \
260 if ( pPredistItem == NULL ) goto sp_error; \
261 pPredistItem->nFrom = nStart; \
262 pPredistItem->pnEdge = pEdge; \
263 pPredistItem->nCost = clipOutput.nEdgeCost; \
264 pPredistItem->nDistance = clipOutput.nEdgeCost; \
265 pPredistItem->bFlags = (f); \
266 heapvalue.pv = pEdge; \
267 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \
268 pgraph->iErrno = DGL_ERR_HeapError; \
272 #define __EDGELOOP_BODY_2(f) \
274 pDestination = _DGL_EDGE_TAILNODE(pgraph, pEdge); \
276 else if ( pgraph->Version == 3 ) { \
277 pDestination = _DGL_EDGE_HEADNODE(pgraph, pEdge); \
279 if ( !(DGL_NODE_STATUS(pDestination) & DGL_NS_TAIL) && pgraph->Version < 3) { \
280 pgraph->iErrno = DGL_ERR_BadEdge; \
283 clipOutput.nEdgeCost = DGL_EDGE_COST(pEdge); \
285 clipInput.pnPrevEdge = pEdge_prev; \
286 clipInput.pnNodeFrom = pStart; \
287 clipInput.pnEdge = pEdge; \
288 clipInput.pnNodeTo = pDestination; \
289 clipInput.nFromDistance = fromDist; \
290 if ( fnClip( pgraph , & clipInput , & clipOutput , pvClipArg ) ) continue; \
292 findPredist.nKey = DGL_NODE_ID(pDestination); \
293 if ( (pPredistItem = avl_find( pCache->pvPredist, &findPredist)) == NULL ) { \
294 if ( (pPredistItem = dglTreePredistAdd( pCache->pvPredist, DGL_NODE_ID(pDestination) )) == NULL ) { \
295 pgraph->iErrno = DGL_ERR_MemoryExhausted; \
300 if ( pPredistItem->nDistance <= fromDist + clipOutput.nEdgeCost ) { \
304 pPredistItem->nFrom = DGL_NODE_ID(pStart); \
305 pPredistItem->pnEdge = pEdge; \
306 pPredistItem->nCost = clipOutput.nEdgeCost; \
307 pPredistItem->nDistance = fromDist + clipOutput.nEdgeCost; \
308 pPredistItem->bFlags = (f); \
309 heapvalue.pv = pEdge; \
310 if ( dglHeapInsertMin( & pCache->NodeHeap, pPredistItem->nDistance , f , heapvalue ) < 0 ) { \
311 pgraph->iErrno = DGL_ERR_HeapError; \
367 if (pCache ==
NULL) {
376 nDestination)) !=
NULL) {
382 (pgraph, pCache, pDistance, nStart, nDestination) >= 0) {
438 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
445 __EDGELOOP_BODY_1(0);
450 pEdgeset = _DGL_INEDGESET(pgraph, pStart);
459 __EDGELOOP_BODY_1(1);
481 if (heapnode.
flags == 0) {
482 pStart = _DGL_EDGE_TAILNODE(pgraph, pEdge);
485 pStart = _DGL_EDGE_HEADNODE(pgraph, pEdge);
511 goto destination_found;
524 goto destination_found;
557 pEdgeset = _DGL_OUTEDGESET(pgraph, pStart);
564 __EDGELOOP_BODY_2(0);
569 pEdgeset = _DGL_INEDGESET(pgraph, pStart);
578 __EDGELOOP_BODY_2(1);
590 goto destination_found;
595 if (pCache == &spCache) {
605 if (*ppReport ==
NULL) {
614 (pgraph, pCache, pDistance, nStart, nDestination) < 0) {
621 if (pCache == &spCache) {
int DGL_EDGESET_T_INITIALIZE_FUNC(dglGraph_s *pGraph, dglEdgesetTraverser_s *pT, dglInt32_t *pnEdgeset)
dglTreeTouchI32_s * dglTreeTouchI32Add(void *pavl, dglInt32_t nKey)
int dglTreePredistCompare(const void *pvPredistA, const void *pvPredistB, void *pvParam)
void dglHeapFree(dglHeap_s *pheap, dglHeapCancelItem_fn pfnCancelItem)
void dglHeapInit(dglHeap_s *pheap)
#define DGL_ERR_HeadNodeNotFound
#define DGL_EDGE_STATUS(p)
#define DGL_EDGE_TAILNODE_OFFSET
dglInt32_t * DGL_GET_NODE_FUNC(dglGraph_s *pgraph, dglInt32_t nodeid)
#define DGL_NODEBUFFER_SHIFT
dglInt32_t nDestinationNode
#define DGL_ERR_MemoryExhausted
void * dglTreeGetAllocator()
int DGL_SP_CACHE_INITIALIZE_FUNC(dglGraph_s *pgraph, dglSPCache_s *pCache, dglInt32_t nStart)
#define DGL_ERR_TailNodeNotFound
#define DGL_SP_CACHE_REPORT_FUNC
unsigned char * dgl_mempop(unsigned char *pstack, long *istack, long size)
void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam)
void dglTreePredistCancel(void *pvPredist, void *pvParam)
unsigned char * dgl_mempush(unsigned char *pstack, long *istack, long size, void *pv)
dglInt32_t * DGL_EDGESET_T_NEXT_FUNC(dglEdgesetTraverser_s *pT)
dglInt32_t * DGL_EDGESET_T_FIRST_FUNC(dglEdgesetTraverser_s *pT)
int dglTreeTouchI32Compare(const void *pvTouchI32A, const void *pvTouchI32B, void *pvParam)
int(* dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *)
void dglFreeSPReport(dglGraph_s *pgraph, dglSPReport_s *pSPReport)
#define DGL_ERR_UnexpectedNullPointer
#define DGL_SP_CACHE_DISTANCE_FUNC
int dglHeapExtractMin(dglHeap_s *pheap, dglHeapNode_s *pnoderet)
#define DGL_EDGE_HEADNODE_OFFSET
void DGL_SP_CACHE_RELEASE_FUNC(dglGraph_s *pgraph, dglSPCache_s *pCache)
void DGL_EDGESET_T_RELEASE_FUNC(dglEdgesetTraverser_s *pT)