scout.c

   1 #include <stdlib.h>
   2 #define __LIBSCOUT_INTERNAL__
   3 #include "scout.h"
   4
   5 typedef struct scnode scnode;
   6 typedef struct scway scway;
   7 typedef struct scwaypoint scwaypoint;
   8
   9 scway *scaddway(scnode *from, const scnode *to, int len)
  10 {
  11         scway *way = malloc(sizeof(scway));
  12         way->lto = to;
  13         way->alt = NULL;
  14         way->len = len;
  15         scway *apar, *par = NULL;
  16         for (apar = from->way; apar != NULL; par = apar, apar = apar->alt);
  17         if (par)
  18                 par->alt = way;
  19         else
  20                 from->way = way;
  21         return way;
  22 }
  23
  24 scwaypoint *scout(const scnode *from, const scnode *to, scwaypoint *stack)
  25 {
  26         scwaypoint *wayp = NULL;
  27         if (from == to)
  28                 return __scallocwayp(from, NULL);
  29         for (scway *way = from->way; way != NULL; way = way->alt) {
  30                 scwaypoint *stackend;
  31                 if ((stackend = __scstackfindgetend(stack, way)) == NULL)
  32                         continue;
  33                 scwaypoint *twayp = __scallocwayp(from, way);
  34                 stackend->nxt = twayp;
  35                 scwaypoint *nwayp = scout(way->lto, to, stack)
  36                 if (wayp && wayp->len <= (twayp->len = __scstackgetlen(twayp)))
  37                         __scstackfree(wayp);
  38                 wayp = twayp;
  39         }
  40         return wayp;
  41 }
  42
  43 scwaypoint *__scallocwayp(const scnode *node, const scway *way)
  44 {
  45         scwaypoint *wayp = malloc(sizeof(scwaypoint));
  46         wayp->nod = node;
  47         wayp->way = way;
  48         wayp->nxt = NULL;
  49         wayp->len = way->len;
  50 }
  51
  52 scwaypoint *__scstackfindgetend(scwaypoint *stack, const scway *way)
  53 {
  54         scwaypoint *asptr, *sptr;
  55         for (asptr = stack; asptr != NULL; sptr = asptr, asptr = asptr->nxt)
  56                 if (asptr->nod == way->lto)
  57                         return NULL;
  58         return sptr;
  59 }
  60
  61 void __scstackfree(scwaypoint *stack)
  62 {
  63         for (scwaypoint *sptr = stack; sptr != NULL; sptr = sptr->nxt)
  64                 free(sptr);
  65 }