home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / BM_STAR.ZIP / SOURCE.ZIP / LINKED.C < prev   
Encoding:
C/C++ Source or Header  |  1992-07-27  |  8.6 KB  |  306 lines
  1. /**************************************************************
  2. //      Linked.c
  3. //26jul92-bm
  4.  **************************************************************/
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <conio.h>
  9. #include "astar.h"
  10.  
  11. /******************
  12.    global functions   .. see astar.h
  13.    NPTR  DropLinked( NPTR Head )
  14.    NPTR   MakeLink( char *DataPtr, unsigned Info )
  15.    NPTR   PopLink( NPTR *Head )
  16.    NPTR  PushLink( NPTR Head, NPTR New )
  17.    void ReleaseNodes( void )
  18.  *******************************/
  19.  
  20. /* local functions */
  21. static int   AppendLink( NPTR head, NPTR New );
  22. static NPTR  DeleteLinkNum( NPTR *Head, unsigned Number );
  23. static NPTR  GetFreeLink( void );
  24. static NPTR  GetLastLink( NPTR First );
  25. static NPTR  GetLinkName( NPTR Tmp, char *Sp );
  26. static NPTR  GetLinkNum( NPTR Start, unsigned Number );
  27. static int   InsertLink( NPTR Head, NPTR Prev, NPTR New );
  28. static int   PutFreeLink( NPTR Spare );
  29. static int   ShowLinkedNames( NPTR Start );
  30. NPTR FreeHead; /* this is external to astar.c */
  31.  
  32. /**************************************************************
  33.    AppendLink()
  34. // Add a new node to the end of a non-empty linked list.
  35. // Return success flag
  36.  **************************************************************/
  37. static int  AppendLink( Head, New )  NPTR Head; NPTR New;
  38. {
  39.    int Success = NO;
  40.    NPTR Tmp = NULL;
  41.    if( New != NULL )
  42.      Tmp = Head;
  43.    while ( Tmp != NULL && Success == NO )
  44.    {
  45.       if ( Tmp->Next == NULL )  /* if at end of list */
  46.       {  /* append */
  47.          Tmp->Next = New;
  48.          New->Next = NULL;
  49.          Success = YES;
  50.       }
  51.       else
  52.          Tmp = Tmp->Next;
  53.    }
  54.    return( Success );
  55. }
  56. /**************************************************************
  57.  **************************************************************/
  58. static NPTR  DeleteLinkNum( Head, Number ) NPTR *Head; unsigned Number;
  59. {
  60.    NPTR Prev = *Head;
  61.    NPTR Tmp = Prev->Next;
  62.    NPTR NewFree = NULL;
  63.    if( (UINT)Prev->Num == Number )
  64.    {  /* delete first node */
  65.       NewFree = Prev;
  66.       Prev = Prev->Next;
  67.       *Head = Prev;             /* adjust head of list */
  68.       NewFree->Next = NULL;     /* terminate loose node */
  69.    }
  70.    while( Tmp != NULL && NewFree==NULL )
  71.    {
  72.       if ( (UINT)Tmp->Num == Number )
  73.       {
  74.        NewFree = Tmp;
  75.        Prev->Next = Tmp->Next;
  76.        NewFree->Next = NULL;
  77.       }
  78.       else
  79.       {
  80.        Prev = Tmp;
  81.        Tmp  = Tmp->Next;
  82.       }
  83.    }
  84.  
  85.    return( NewFree ); /* NULL indicates not found */
  86. }
  87. /**************************************************************
  88. // Delete entire linked list and return free nodes to
  89. // the global list of free nodes.
  90. // GLOBALS: FreeHead
  91.  **************************************************************/
  92. NPTR  DropLinked( Head ) NPTR  Head;
  93. {
  94.    if( Head != NULL )
  95.    {
  96.        NPTR Next = Head->Next;
  97.        PutFreeLink( Head );
  98.        while( Next != NULL )
  99.        {
  100.         Head = Next;
  101.         Next = Head->Next;
  102.         PutFreeLink( Head );
  103.        }
  104.    }
  105.    return( NULL );
  106. }
  107. /**************************************************************
  108. // To minimize memory fragmentation, new nodes are removed
  109. // from a list of free nodes if possible
  110. // GLOBALS: FreeHead
  111.  **************************************************************/
  112. static NPTR   GetFreeLink( void )
  113. {
  114.     NPTR Tmp = FreeHead ;
  115.     if ( Tmp != NULL )
  116.     {
  117.        FreeHead = Tmp->Next;    /* remove from head of list */
  118.        Tmp->Next = NULL;        /* terminate loose node */
  119.     }
  120.     return( Tmp );
  121. }
  122. /**************************************************************
  123.    GetLastLink()
  124. // Return pointer to last link in a linked list
  125.  **************************************************************/
  126. static NPTR  GetLastLink( First )  NPTR First;
  127. {
  128.    NPTR Last = NULL;
  129.    while( First != NULL )
  130.    {
  131.       Last = First;
  132.       First = First->Next;
  133.    }
  134.    return( Last );
  135. }
  136. /**************************************************************
  137. // Return a pointer to the node in a linked list which
  138. // contains the specified number.
  139. // GLOBALS: struct lnode
  140.  **************************************************************/
  141. static NPTR   GetLinkNum( Start, Number )  NPTR Start; unsigned Number;
  142. {
  143.     int Found = NO;
  144.     while ( Start != NULL && !Found )
  145.     {
  146.        if( (UINT)Start->Num == Number )
  147.        Found = YES;
  148.        else
  149.        Start = Start->Next;
  150.     }
  151.     return( Start );
  152. }
  153. /**************************************************************
  154. // Return a pointer to the node in a linked list which points
  155. // to the specified string.
  156. // GLOBALS: struct lnode
  157.  **************************************************************/
  158. static NPTR   GetLinkName( Tmp, Sp ) NPTR Tmp; char *Sp;
  159. {
  160.     int Found = NO;
  161.     while ( Tmp != NULL && !Found )
  162.     {
  163.        if( strcmp(Tmp->Dptr, Sp)==0 )
  164.        Found = YES;
  165.        else
  166.        Tmp = Tmp->Next;
  167.     }
  168.     return( Tmp );
  169. }
  170. /**************************************************************
  171. // Insert a new node within a linked list in front of node pointed
  172. // to by Prev.
  173. // Return success flag
  174.  **************************************************************/
  175. static int InsertLink( Head, Prev, New ) NPTR Head; NPTR Prev; NPTR New;
  176. {
  177.    int Success = NO;
  178.    if ( Prev != NULL && Head != NULL && New != NULL )
  179.    {
  180.       Success = YES;
  181.       if ( Head == Prev )
  182.       {
  183.      New->Next = Head;
  184.      Head = New;
  185.       }
  186.       else
  187.       {
  188.      New->Next = Prev->Next;
  189.      Prev->Next = New;
  190.       }
  191.    }
  192.    return( Success );
  193. }
  194. /**************************************************************
  195. // Take a node from the global pool of free nodes or
  196. // make a new list link & store a data pointer & node number
  197. // Return pointer to new link which is null terminated
  198. // GLOBALS: NodeNum;
  199.  **************************************************************/
  200. NPTR   MakeLink( DataPtr, Info ) char *DataPtr; unsigned Info;
  201. {
  202.     NPTR New = GetFreeLink();
  203.     if ( New == NULL )
  204.     {
  205.     New = (NPTR) malloc(sizeof(struct lnode) );
  206.     }
  207.     if ( New != NULL )
  208.     {
  209.        New->Num  = Info;        /* optional field */
  210.        New->Dptr = DataPtr;
  211.        New->Next = NULL;
  212.     }
  213.     else
  214.       puts("\n **no linked list space**");
  215.  
  216.     return( New );
  217. }
  218. /**************************************************************
  219. // Given pointer-pointer to a linked list, remove the first one
  220. // and return pointer to it:
  221. // GLOBALS: None
  222.  **************************************************************/
  223. NPTR   PopLink( Head ) NPTR *Head;
  224. {
  225.     NPTR Tmp = *Head;
  226.     if ( Tmp != NULL )
  227.     {
  228.        *Head = Tmp->Next;       /* remove from head of list */
  229.        Tmp->Next = NULL;        /* terminate loose node */
  230.     }
  231.     return( Tmp );
  232. }
  233. /**************************************************************
  234. // Add a node to the head of given list. Return pointer
  235. // to new head.
  236. // GLOBALS: None
  237.  **************************************************************/
  238. NPTR  PushLink( Head, New ) NPTR Head; NPTR New;
  239. {
  240.    NPTR Tmp = Head;
  241.    if( New != NULL )
  242.    {
  243.       if ( Head == NULL )
  244.       {
  245.       Head = New;           /* start a new list */
  246.       Head->Next = NULL;    /* ground 1st node  */
  247.       }
  248.       else
  249.       {
  250.      Head = New;            /* insert at front */
  251.      Head->Next = Tmp;      /* & connect old to tail */
  252.       }
  253.    }
  254.    return( Head );
  255. }
  256. /**************************************************************
  257. // To minimize memory fragmentation, dropped nodes are added to
  258. // a list of free nodes.
  259. // GLOBALS: FreeHead
  260.  **************************************************************/
  261. static int    PutFreeLink( Spare ) NPTR Spare;
  262. {
  263.     NPTR Tmp = FreeHead ;
  264.     if ( FreeHead == NULL )
  265.     {
  266.        FreeHead = Spare;
  267.        FreeHead->Next = NULL;
  268.     }
  269.     else
  270.     {
  271.        FreeHead = Spare;
  272.        FreeHead->Next = Tmp;
  273.     }
  274.     return( 1 );
  275. }
  276. /**************************************************************
  277. // de-allocate space used for free list of nodes
  278.  **************************************************************/
  279. void ReleaseNodes( void )
  280. {
  281.    NPTR Tmp = FreeHead;
  282.    while( Tmp != NULL )
  283.    {
  284.       FreeHead = FreeHead->Next;
  285.       free( Tmp );
  286.       Tmp = FreeHead;
  287.    }
  288. }
  289. /**************************************************************
  290. // display linked list headers (if pointing to strings)
  291. // and return count
  292.  **************************************************************/
  293. static int  ShowLinkedNames( Start ) NPTR Start;
  294. {
  295.    int q1 = 0;
  296.    while ( Start != NULL )
  297.    {
  298.       printf("\nNode: %d %s",Start->Num, Start->Dptr);
  299.       Start = Start->Next;
  300.       q1++;
  301.    }
  302.    printf("\n >>");getch();
  303.    return( q1 );
  304. }
  305.  
  306.