/******************************************************************************
* Module    :   List --- List building and maintenance module.
*
* Author    :   John Stevens.
******************************************************************************/

#include    "compiler.h"

#include    "unpost.h"
#include    "list.h"
#include    "utils.h"

#define INIT_SIZE   2
#define INCREASE    5

/*-----------------------------------------------------------------------------
| Routine   :   AddList() --- Add an element to a list.
|
| Inputs    :   Head    - Pointer to begining of list.
|               Elem    - New element to add to list.
|               InsPt   - List ordinal for add.
|
| Returns   :   Pointer to list head.
-----------------------------------------------------------------------------*/

void    *AddList(LIST   *Head,
                 void   *Elem,
                 int    InsPt)
{
    auto        char    *List;
    extern      FILE    *ErrFile;

    /*  Create or add to list.  */
    if (Head->NoElems >= Head->TotElems)
    {
        auto    int     NewSize;

        /*  Reallocate the list header. */
        NewSize = (Head->TotElems + INCREASE) * Head->ElemSz + sizeof( LIST );
        if ((Head = (LIST *) realloc(Head, NewSize)) == NULL)
        {
            fprintf(ErrFile,
                    "%s %d : Error - Out of memory.\n",
                    __FILE__,
                    __LINE__);
            exit( 1 );
        }

        /*  Update list size.   */
        Head->TotElems += INCREASE;
    }

    /*  Move list elements up to make room. */
    List = Head->List + Head->ElemSz * InsPt;
    if (InsPt < Head->NoElems)
    {
        MemMv(List +  Head->ElemSz,
              List,
              Head->ElemSz * (Head->NoElems - InsPt));
    }

    /*  Copy new element to it's proper location.   */
    MemCopy(List, Elem, Head->ElemSz);
    Head->NoElems++;
    return( Head );
}

/*-----------------------------------------------------------------------------
| Routine   :   CrtList() --- Create a new (empty) list.
|
| Inputs    :   ElemSz  - Size of element in bytes.
|
| Returns   :   Pointer to list head.
-----------------------------------------------------------------------------*/

void    *CrtList(int    ElemSz)
{
    auto    LIST    *Head;
    auto    int     Size;
    extern  FILE    *ErrFile;

    /*  Calculate the size of the new list and allocate it. */
    Size = INIT_SIZE * ElemSz + sizeof( LIST );
    if ((Head = (LIST *) calloc(1, Size)) == NULL)
    {
        fprintf(ErrFile,
                "%s %d : Error - Out of memory.\n",
                __FILE__,
                __LINE__);
        exit( 1 );
    }

    /*  Return the pointer to the list. */
    Head->ElemSz = ElemSz;
    Head->TotElems = INIT_SIZE;
    return( Head );
}

/*-----------------------------------------------------------------------------
| Routine   :   SrchList() --- Search the list.
|
| Inputs    :   Head    - Pointer to begining of list.
|               Elem    - Element to search list for.
|               CmpFn   - Function to compare in search.
| Outputs   :   InsPt   - List pointer for insert/found.
|
| Returns   :   TRUE for found, FALSE for not found.
-----------------------------------------------------------------------------*/

int     SrchList(LIST   *Head,
                 void   *Elem,
                 int    (*CmpFn)(void *, void *),
                 int    *InsPt)
{
    /*  Search the list for an element.
    *
    *   Do binary search.
    */
    if (Head->NoElems > 0)
    {
        auto    char    *List;
        auto    int     hi;
        auto    int     lo;
        auto    int     ret;
        auto    int     mid;

        lo = 0;
        hi = Head->NoElems - 1;
        do
        {
            /*  Get midpoint of list.   */
            mid = (hi + lo) >> 1;
            List = Head->List + Head->ElemSz * mid;

            /*  Do string compare.  */
            ret = CmpFn(Elem, List);

            /*  Adjust array pointers.  */
            if (ret <= 0)
                hi = mid - 1;
            if (ret >= 0)
                lo = mid + 1;
        } while (hi >= lo);

        /*  Did we find it? */
        if (ret == 0)
        {
            /*  We found it.    */
            *InsPt = mid;
            return( TRUE );
        }

        /*  We did not find it. */
        *InsPt = lo;
        return( FALSE );
    }

    /*  Return that we did not find it, and the point at
    *   which it should be inserted.
    */
    *InsPt = 0;
    return( FALSE );
}

/*-----------------------------------------------------------------------------
| Routine   :   ListIdx() --- Get pointer to a list element.
|
| Inputs    :   Head    - Pointer to begining of list.
|               Index   - Index of element to return pointer for.
|
| Returns   :   NULL for index outside of list limits, Pointer to list
|               element otherwise.
-----------------------------------------------------------------------------*/

void    *ListIdx(LIST   *Head,
                 int    Index)
{
    /*  Determine if index is inside list limits.   */
    if (Index < 0 || Index >= Head->NoElems)
        return( NULL );
    return( Head->List + Index * Head->ElemSz );
}

/*-----------------------------------------------------------------------------
| Routine   :   AppList() --- Append an element to a list.
|
| Inputs    :   Head    - Pointer to begining of list.
|               Elem    - New element to add to list.
|
| Returns   :   Pointer to list head.
-----------------------------------------------------------------------------*/

void    *AppList(LIST   *Head,
                 void   *Elem)
{
    auto        char    *List;
    extern      FILE    *ErrFile;

    /*  Create or add to list.  */
    if (Head->NoElems >= Head->TotElems)
    {
        auto    int     NewSize;

        /*  Reallocate the list header. */
        NewSize = (Head->TotElems + INCREASE) * Head->ElemSz + sizeof( LIST );
        if ((Head = (LIST *) realloc(Head, NewSize)) == NULL)
        {
            fprintf(ErrFile,
                    "%s %d : Error - Out of memory.\n",
                    __FILE__,
                    __LINE__);
            exit( 1 );
        }

        /*  Update list size.   */
        Head->TotElems += INCREASE;
    }

    /*  Copy new element to it's proper location.   */
    List = Head->List + Head->ElemSz * Head->NoElems;
    MemCopy(List, Elem, Head->ElemSz);
    Head->NoElems++;
    return( Head );
}