home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume36 / unpost / part06 / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-18  |  6.4 KB  |  225 lines
  1. /******************************************************************************
  2. * Module    :   List --- List building and maintenance module.
  3. *
  4. * Author    :   John Stevens.
  5. ******************************************************************************/
  6.  
  7. #include    "compiler.h"
  8.  
  9. #include    "unpost.h"
  10. #include    "list.h"
  11. #include    "utils.h"
  12.  
  13. #define INIT_SIZE   2
  14. #define INCREASE    5
  15.  
  16. /*-----------------------------------------------------------------------------
  17. | Routine   :   AddList() --- Add an element to a list.
  18. |
  19. | Inputs    :   Head    - Pointer to begining of list.
  20. |               Elem    - New element to add to list.
  21. |               InsPt   - List ordinal for add.
  22. |
  23. | Returns   :   Pointer to list head.
  24. -----------------------------------------------------------------------------*/
  25.  
  26. void    *AddList(LIST   *Head,
  27.                  void   *Elem,
  28.                  int    InsPt)
  29. {
  30.     auto        char    *List;
  31.     extern      FILE    *ErrFile;
  32.  
  33.     /*  Create or add to list.  */
  34.     if (Head->NoElems >= Head->TotElems)
  35.     {
  36.         auto    int     NewSize;
  37.  
  38.         /*  Reallocate the list header. */
  39.         NewSize = (Head->TotElems + INCREASE) * Head->ElemSz + sizeof( LIST );
  40.         if ((Head = (LIST *) realloc(Head, NewSize)) == NULL)
  41.         {
  42.             fprintf(ErrFile,
  43.                     "%s %d : Error - Out of memory.\n",
  44.                     __FILE__,
  45.                     __LINE__);
  46.             exit( 1 );
  47.         }
  48.  
  49.         /*  Update list size.   */
  50.         Head->TotElems += INCREASE;
  51.     }
  52.  
  53.     /*  Move list elements up to make room. */
  54.     List = Head->List + Head->ElemSz * InsPt;
  55.     if (InsPt < Head->NoElems)
  56.     {
  57.         MemMove(List +  Head->ElemSz,
  58.                 List,
  59.                 Head->ElemSz * (Head->NoElems - InsPt));
  60.     }
  61.  
  62.     /*  Copy new element to it's proper location.   */
  63.     MemCopy(List, Elem, Head->ElemSz);
  64.     Head->NoElems++;
  65.     return( Head );
  66. }
  67.  
  68. /*-----------------------------------------------------------------------------
  69. | Routine   :   CrtList() --- Create a new (empty) list.
  70. |
  71. | Inputs    :   ElemSz  - Size of element in bytes.
  72. |
  73. | Returns   :   Pointer to list head.
  74. -----------------------------------------------------------------------------*/
  75.  
  76. void    *CrtList(int    ElemSz)
  77. {
  78.     auto    LIST    *Head;
  79.     auto    int     Size;
  80.     extern  FILE    *ErrFile;
  81.  
  82.     /*  Calculate the size of the new list and allocate it. */
  83.     Size = INIT_SIZE * ElemSz + sizeof( LIST );
  84.     if ((Head = (LIST *) calloc(1, Size)) == NULL)
  85.     {
  86.         fprintf(ErrFile,
  87.                 "%s %d : Error - Out of memory.\n",
  88.                 __FILE__,
  89.                 __LINE__);
  90.         exit( 1 );
  91.     }
  92.  
  93.     /*  Return the pointer to the list. */
  94.     Head->ElemSz = ElemSz;
  95.     Head->TotElems = INIT_SIZE;
  96.     return( Head );
  97. }
  98.  
  99. /*-----------------------------------------------------------------------------
  100. | Routine   :   SrchList() --- Search the list.
  101. |
  102. | Inputs    :   Head    - Pointer to begining of list.
  103. |               Elem    - Element to search list for.
  104. |               CmpFn   - Function to compare in search.
  105. | Outputs   :   InsPt   - List pointer for insert/found.
  106. |
  107. | Returns   :   TRUE for found, FALSE for not found.
  108. -----------------------------------------------------------------------------*/
  109.  
  110. int     SrchList(LIST   *Head,
  111.                  void   *Elem,
  112.                  int    (*CmpFn)(void *, void *),
  113.                  int    *InsPt)
  114. {
  115.     /*  Search the list for an element.
  116.     *
  117.     *   Do binary search.
  118.     */
  119.     if (Head->NoElems > 0)
  120.     {
  121.         auto    char    *List;
  122.         auto    int     hi;
  123.         auto    int     lo;
  124.         auto    int     ret;
  125.         auto    int     mid;
  126.  
  127.         lo = 0;
  128.         hi = Head->NoElems - 1;
  129.         do
  130.         {
  131.             /*  Get midpoint of list.   */
  132.             mid = (hi + lo) >> 1;
  133.             List = Head->List + Head->ElemSz * mid;
  134.  
  135.             /*  Do string compare.  */
  136.             ret = CmpFn(Elem, List);
  137.  
  138.             /*  Adjust array pointers.  */
  139.             if (ret <= 0)
  140.                 hi = mid - 1;
  141.             if (ret >= 0)
  142.                 lo = mid + 1;
  143.         } while (hi >= lo);
  144.  
  145.         /*  Did we find it? */
  146.         if (ret == 0)
  147.         {
  148.             /*  We found it.    */
  149.             *InsPt = mid;
  150.             return( TRUE );
  151.         }
  152.  
  153.         /*  We did not find it. */
  154.         *InsPt = lo;
  155.         return( FALSE );
  156.     }
  157.  
  158.     /*  Return that we did not find it, and the point at
  159.     *   which it should be inserted.
  160.     */
  161.     *InsPt = 0;
  162.     return( FALSE );
  163. }
  164.  
  165. /*-----------------------------------------------------------------------------
  166. | Routine   :   ListIdx() --- Get pointer to a list element.
  167. |
  168. | Inputs    :   Head    - Pointer to begining of list.
  169. |               Index   - Index of element to return pointer for.
  170. |
  171. | Returns   :   NULL for index outside of list limits, Pointer to list
  172. |               element otherwise.
  173. -----------------------------------------------------------------------------*/
  174.  
  175. void    *ListIdx(LIST   *Head,
  176.                  int    Index)
  177. {
  178.     /*  Determine if index is inside list limits.   */
  179.     if (Index < 0 || Index >= Head->NoElems)
  180.         return( NULL );
  181.     return( Head->List + Index * Head->ElemSz );
  182. }
  183.  
  184. /*-----------------------------------------------------------------------------
  185. | Routine   :   AppList() --- Append an element to a list.
  186. |
  187. | Inputs    :   Head    - Pointer to begining of list.
  188. |               Elem    - New element to add to list.
  189. |
  190. | Returns   :   Pointer to list head.
  191. -----------------------------------------------------------------------------*/
  192.  
  193. void    *AppList(LIST   *Head,
  194.                  void   *Elem)
  195. {
  196.     auto        char    *List;
  197.     extern      FILE    *ErrFile;
  198.  
  199.     /*  Create or add to list.  */
  200.     if (Head->NoElems >= Head->TotElems)
  201.     {
  202.         auto    int     NewSize;
  203.  
  204.         /*  Reallocate the list header. */
  205.         NewSize = (Head->TotElems + INCREASE) * Head->ElemSz + sizeof( LIST );
  206.         if ((Head = (LIST *) realloc(Head, NewSize)) == NULL)
  207.         {
  208.             fprintf(ErrFile,
  209.                     "%s %d : Error - Out of memory.\n",
  210.                     __FILE__,
  211.                     __LINE__);
  212.             exit( 1 );
  213.         }
  214.  
  215.         /*  Update list size.   */
  216.         Head->TotElems += INCREASE;
  217.     }
  218.  
  219.     /*  Copy new element to it's proper location.   */
  220.     List = Head->List + Head->ElemSz * Head->NoElems;
  221.     MemCopy(List, Elem, Head->ElemSz);
  222.     Head->NoElems++;
  223.     return( Head );
  224. }
  225.