home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 1 / GoldFishApril1994_CD1.img / d1xx / d169 / src / dres / notinlib / graph.c next >
Text File  |  1988-11-22  |  6KB  |  256 lines
  1.  
  2.  
  3. /*
  4.  *  GRAPH.C
  5.  */
  6.  
  7. #define GRAPH    struct _GRAPH
  8. #define GNODE    struct _GNODE
  9. #define GCTRL    struct _GCTRL
  10.  
  11. /*
  12.  *  Flags field:    The upper 4 bits are copied to the lower 4 bits after
  13.  *            the flags are processed, allowing for 'temporary'
  14.  *            conditions.
  15.  *
  16.  *  FL_SKIP        Propogate a skip condition.  As soon as the next node
  17.  *            is ready to begin processing, cause it not to run
  18.  *            its function and propogate the FL_SKIP to all of its
  19.  *            children, and all of their children, etc...
  20.  *
  21.  *  FL_SRC        Infinite source, this arc is always ready with the
  22.  *            given value.
  23.  */
  24.  
  25. GLINK {
  26.     MINNODE FNode;    /*  link from, list based at node    */
  27.     MINNODE TNode;    /*  link to, list based at node     */
  28.     GNODE   *FGNode;    /*  from this node            */
  29.     GNODE   *TGNode;    /*  to this node            */
  30.     long    FromId;    /*  Identify value slot for source    */
  31.     long    ToId;    /*  Identify value slot for destination */
  32.     long    Value;    /*  value to pass to 'to' node          */
  33.     ubyte   Ready;    /*  value pending, else no value pending*/
  34.     ubyte   Flags;    /*  FL_SKIP,FL_NULL,FL_SRC        */
  35.     ubyte   XFlags;    /*  XL_READ                */
  36.     ubyte   filler;
  37. };
  38.  
  39. GNODE {
  40.     MINNODE GNode;    /*  master list node            */
  41.     GRAPH   *Graph;    /*  owning graph            */
  42.     APTR    Func;    /*  Function                */
  43.     long    Arg;    /*  Argument                */
  44.     short   WaitCnt;    /*  # parents who are not ready     */
  45.     MINLIST ChildList;    /*  list of children            */
  46.     MINLIST ParentList; /*  list of parents            */
  47.     MINLIST WakeUpList; /*  WakeUp tasks waiting for an ARC to clear    */
  48. };
  49.  
  50. GRAPH {
  51.     MINLIST GNodes;    /*  list of all graphs in node    */
  52.     long    A45[2];    /*  global base registers    */
  53.     long    UsrLen;
  54. };
  55.  
  56. GRAPH *
  57. AllocGraph(usrdatalen)
  58. {
  59.     GRAPH *graph = AllocMem(sizeof(GRAPH), MEMF_PUBLIC|MEMF_CLEAR);
  60.     NewList(&graph->GNodes);
  61.     graph->a45[0] = A4;
  62.     graph->a45[1] = A5;
  63.     graph->UsrLen = usrdatalen;
  64. }
  65.  
  66. GNODE *
  67. AllocGraphNode(graph, func, arg, usrdata/NULL)
  68. GRAPH *graph;
  69. long arg;
  70. {
  71.     GNODE *gnode = AllocMem(sizeof(GNODE), MEMF_PUBLIC|MEMF_CLEAR);
  72.     AddTail(&graph->GNodes, &gnode->GNode);
  73.     gnode->Graph = graph;
  74.     gnode->Func  = func;
  75.     gnode->Arg     = arg;
  76.     NewList(&gnode->ChildList);
  77.     NewList(&gnode->ParentList);
  78.     NewList(&gnode->WakeUpList);
  79. }
  80.  
  81. /*
  82.  *  Remove all arcs and free a graph node
  83.  */
  84.  
  85. FreeGraphNode(gnode)
  86. GNODE *gnode;
  87. {
  88.     Forbid();
  89.     Remove(gnode);
  90.     while (glink = GetHead(&gnode->ChildList))
  91.     RemGraphArc(gnode, glink->FGTNode);
  92.     while (glink = GetHeadOff(&gnode->ParentList, 8))
  93.     RemGraphArc(glink->FGFNode, gnode);
  94.     Permit();
  95.     FreeMem(gnode, sizeof(GNODE));
  96. };
  97.  
  98. FreeGraph(graph)
  99. GRAPH *graph;
  100. {
  101.     Forbid();
  102.     while (gnode = GetHead(&graph->GNodes))
  103.     FreeGraphNode(gnode);
  104.     Permit();
  105.     FreeMem(graph, sizeof(GRAPH));
  106. }
  107.  
  108. /*
  109.  *  Set the user data for a given node.  The data is copied into an
  110.  *  equivalent buffer for the node.
  111.  */
  112.  
  113. SetUserData(gnode, usrdata/NULL)
  114. GNODE *gnode;
  115. {
  116. }
  117.  
  118. /*
  119.  *  Add a directed arc to the graph.  Set the arc to 'not ready' and
  120.  *  increment the child node's WaitCnt
  121.  */
  122.  
  123. AddGraphArc(from, to)
  124. GNODE *from, *to;
  125. {
  126.     GLINK *glink = AllocMem(sizeof(GLINK), MEMF_PUBLIC);
  127.  
  128.     Forbid();
  129.     AddTail(&from->ChildList, &glink->FNode);
  130.     AddTail(&to->ParentList, &glink->TNode);
  131.     glink->FGNode = from;
  132.     glink->FTNode = to;
  133.     ++to->WaitCnt;
  134.     Permit();
  135. }
  136.  
  137. chklink(glink, gnode)
  138. GLINK *glink;
  139. GNODE *gnode;
  140. {
  141.     if (glink->TGNode == gnode)
  142.     return(glink);
  143.     return(NULL);
  144. }
  145.  
  146. RemGraphArc(from, to)
  147. GNODE *from, *to;
  148. {
  149.     GLINK *glink;
  150.  
  151.     Forbid();
  152.     if (glink = SearchFwdNode(GetHead(&from->ChildList), chklink, 0, to)) {
  153.     Remove(&glink->FNode);
  154.     Remove(&glink->TNode);
  155.     if (!glink->Ready) {
  156.         if (--to->WaitCnt == 0 && GetHeadOff(&to->ParentList, 8))
  157.         GHandler(to);
  158.     }
  159.     }
  160.     Permit();
  161. }
  162.  
  163. SetGNodeFunc(gnode, func)
  164. GNODE *gnode;
  165. APTR func;
  166. {
  167.     gnode->Func = func;
  168. }
  169.  
  170. SetGNodeArg(gnode, arg)
  171. GNODE *gnode;
  172. {
  173.     gnode->Arg = arg;
  174. }
  175.  
  176. APTR
  177. GetGNodeFunc(gnode)
  178. GNODE *gnode;
  179. {
  180.     return(gnode->Func);
  181. }
  182.  
  183. long
  184. GetGNodeArg(gnode)
  185. GNODE *gnode;
  186. {
  187.     return(gnode->Arg);
  188. }
  189.  
  190. /*
  191.  *  This function may ONLY be called by a node function, and retrieves
  192.  *  the value from one of the parent arcs (arcs comming in).  When the
  193.  *  node function returns, any remaining unread parent arc's values will
  194.  *  be discarded.
  195.  */
  196.  
  197. long
  198. GetArcValue(ToId)
  199. {
  200.  
  201. }
  202.  
  203. /*
  204.  *  This function may ONLY be called by a node function, and sets the
  205.  *  result value to one of its child arcs (arcs going out).  When the
  206.  *  node function returns, any remaining unset child arc's values will
  207.  *  be SKIPd.
  208.  *
  209.  *  NOTE!  This function will block on child nodes which have yet to
  210.  *  read the previous value with GetArcValue() or are still running.
  211.  */
  212.  
  213. SetArcValue(gnode, FromId, flags)
  214. GNODE *gnode;
  215. {
  216. }
  217.  
  218. /*
  219.  *  This function may be called by anybody, and forces a value into an
  220.  *  arc.  This function is usually used to 'prime' a graph.
  221.  */
  222.  
  223. PrimeArc(from, to, value)
  224. GNODE *from, *to;
  225. {
  226. }
  227.  
  228. /*
  229.  *  GetGraph()
  230.  *
  231.  *  Load the two buffers with entries corrosponding to the graph.  arcen
  232.  *  and nodeen initially contain the number of ARC and NODE structure
  233.  *  entries that have been allocated.  These variables will hold the
  234.  *  actual number of ARC and NODE entries in the graph regardless of
  235.  *  whether the operation succeeds.
  236.  *
  237.  *  0 is returned if the operation does not succeed, 1 if it does.
  238.  *  The size of the node structure depends on the size of attached
  239.  *  user information.
  240.  *
  241.  *  ARC structure:  two words / entry, representing an arc (from, to),
  242.  *            where each word is an index (by entry #) into nodebuf.
  243.  *            i.e. 0, 1, 2 ... even if usrdatalen is 0.
  244.  *
  245.  *  NODE structure: any user data that has been applied to the node, as
  246.  *            specified by AllocGraphNode().
  247.  */
  248.  
  249. GetArcs(graph, arcbuf, &arcen, nodebuf, &nodeen)
  250. GRAPH *graph;
  251. {
  252.  
  253.  
  254. }
  255.  
  256.