
/*
 *@@sourcefile linklist.c:
 *      contains helper functions for maintaining linked lists.
 *      See explanations below.
 *
 *      This file is new with V0.81 and contains all the functions
 *      that were in helpers.c previously.
 *
 *      Function prefixes (new with V0.81):
 *      --  lst*    linked list helper functions
 *
 *      Changes for V0.84: All references to mutex semaphores have been
 *      removed. It is now the exclusive job of the caller to serialize
 *      access to these linked lists. It is not possible to implement
 *      proper exception handling otherwise.
 *
 *@@include #include "linklist.h"
 */

/*
 *      Copyright (C) 1997-99 Ulrich M”ller.
 *      This file is part of the XFolder source package.
 *      XFolder is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published
 *      by the Free Software Foundation, in version 2 as it comes in the
 *      "COPYING" file of the XFolder main distribution.
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 */

#include <stdlib.h>
// #include <string.h>
// #include <stdio.h>

#include "linklist.h"

/********************************************************************
 *                                                                  *
 *   Functions for maintaining linked pointer lists                 *
 *                                                                  *
 ********************************************************************/

/* The following functions are used commonly to maintain linked
   pointer lists: we have functions for appending, counting and
   removing list items, plus one for deleting a whole list.
   All these function names are introduced by "lst".

   Note that all these functions assume the passed pointers to
   be pointers to LISTITEM structures (linklist.h). You may, of course,
   use different structures, but the first items in your structure
   must be *pNext, *pPrevious, ulSize like in LISTITEM to make these
   functions work. You will then have to cast your structure pointers
   manually to PLISTITEM or PLISTITEM* before using these functions.

   All of the following functions work in two modes:
   -- "one-way" lists, i.e. list which can only be accessed through
      the first item on the list: this mode applies when *ppList
      is specified to be NULL;
   -- "two-way" lists, i.e. list which can be accessed both through
      the first item and the last item on the list; in this case,
      you must also specify *ppLast, the pointer of the last item,
      which will also be maintained by these functions. "Two-way"
      lists are much faster when appending many items, because we
      don't have to go through the whole list to find the last item.
*/

/*
 *@@ lstAppendItem:
 *      this will create an item for a linked list starting at
 *      *ppFirst; this must be a pointer to a pointer to the
 *      first list item; if *ppFirst is NULL (= list is empty),
 *      *ppFirst will be adjusted so that it points to the new
 *      item. If ppLast == NULL, the list is assumed to be
 *      a "one-way" list, otherwise it must point to a pointer
 *      for the last list item, which will be adjusted.
 *      This function returns the address of the new list item.
 */

PLISTITEM lstAppendItem(PLISTITEM *ppFirst, // first list item
            PLISTITEM *ppLast,              // last list item (or NULL)
            PLISTITEM pNewItem)             // item to insert
{
    if (pNewItem)
    {
        pNewItem->pNext = NULL;

        if (*ppFirst == NULL) {
            // list is empty: set first pointer to new list item
            *ppFirst = (void*)pNewItem;
            pNewItem->pPrevious = NULL;
        } else {
            BOOL    Search = TRUE;
            // list is not empty: find end of list and append the
            // new item

            if (ppLast)
                if (*ppLast) {
                    // last item given: use this
                    (*ppLast)->pNext = pNewItem;
                    pNewItem->pPrevious = *ppLast;
                    Search = FALSE;
                }

            if (Search)
            {
                // last item was not given: find last item
                PLISTITEM pItem = (PLISTITEM)*ppFirst;
                while (pItem->pNext)
                    pItem = pItem->pNext;
                pItem->pNext = pNewItem;
                pNewItem->pPrevious = pItem;
            }
        }
        if (ppLast)
            *ppLast = pNewItem;
    }

    return (pNewItem);
}

/*
 *@@ lstInsertItemAt:
 *      does just the same, but does not append the new item
 *      at the end of the list, but BEFORE the specified index
 *      lIndex. If lIndex is larger than the number of items
 *      on the list or == -1, the new item will be appended.
 */

PLISTITEM lstInsertItemAt(PLISTITEM *ppFirst, PLISTITEM *ppLast,
            PLISTITEM pNewItem, long lIndex)
{
    if (pNewItem)
    {
        if (lIndex == -1)
            lstAppendItem(ppFirst, ppLast, pNewItem);
        else
        {
            if (lIndex == 0) {
                // insert at beginning:
                pNewItem->pNext = (*ppFirst);
                pNewItem->pPrevious = NULL;
                (*ppFirst)->pPrevious = pNewItem;
                *ppFirst = pNewItem;
            } else {
                // insert at a later position:
                PLISTITEM pItemInsertAfter = lstItemFromIndex(
                                *ppFirst, (lIndex-1));

                if (pItemInsertAfter) {
                    pNewItem->pNext = pItemInsertAfter->pNext;
                    pItemInsertAfter->pNext = pNewItem;
                    pNewItem->pPrevious = pItemInsertAfter;
                    if (pNewItem->pNext)
                        pNewItem->pNext->pPrevious = pNewItem;
                } else {
                    // item index too large: append instead
                    lstAppendItem(ppFirst, ppLast, pNewItem);
                }
            }
        }
        return (pNewItem);
    } else
        return (NULL);
}

/*
 *@@ lstRemoveItem:
 *      reversely, this will remove a given pRemoveItem from
 *      the linked list beginning at *ppFirst. Returns TRUE if
 *      successful, FALSE if pRemoveItem was not found.
 */

BOOL lstRemoveItem(PLISTITEM *ppFirst, PLISTITEM *ppLast, PLISTITEM pRemoveItem)
{
    BOOL        Found = FALSE;

    if (ppFirst) {
        if ((*ppFirst) && (pRemoveItem))
        {
            if (*ppFirst == pRemoveItem) {
                // pRemoveItem is the first item on the list:
                // set *ppFirst to the second item on the list.
                // This also works if pRemoveItem is the only item */
                *ppFirst = pRemoveItem->pNext;
                if (*ppFirst)
                    (*ppFirst)->pPrevious = NULL;
                Found = TRUE;
            }
            else {
                // otherwise begin searching list:
                PLISTITEM pLastItem = *ppFirst;
                PLISTITEM pItem = pLastItem->pNext;

                while (pItem)
                {
                    if (pItem == pRemoveItem) {
                        // item found: set pNext of previous item to next item
                        // (i.e. leave out pRemoveItem) */
                        pLastItem->pNext = pRemoveItem->pNext;
                        if (pRemoveItem->pNext)
                            pRemoveItem->pNext->pPrevious = pLastItem;
                        Found = TRUE;
                        break;
                    }
                    else {
                        pLastItem = pItem;
                        pItem = pItem->pNext;
                    }
                }
            }
        }
        if (Found) {
            if (ppLast)
                /* if (*ppLast == pRemoveItem)
                    *ppLast = pRemoveItem->pPrevious;*/
                *ppLast = NULL;

            free(pRemoveItem);
        }
    }

    return (Found);
}

/*
 *@@ lstSwapItems:
 *      this will swap the items ppItem1 and ppItem2 in the linked
 *      list starting at *ppFirst; useful for sorting.
 *      Note that this function will not only adjust the pNext
 *      and pPrevious pointers of the LISTITEMs, but also
 *      swap the *ppItem1 and *ppItem2 pointers.
 */

BOOL lstSwapItems(PLISTITEM *ppFirst, PLISTITEM *ppLast,
            PLISTITEM *ppItem1, PLISTITEM *ppItem2)
{
    BOOL brc = FALSE;
    // PLISTITEM   pPrevious = NULL;

    if ( (ppFirst) && (ppItem1) && (ppItem2) )
        if ((*ppFirst) && ((*ppItem1)) && ((*ppItem2)))
            if (*ppItem1 != *ppItem2)
            {
                PLISTITEM pBefore1 = (*ppItem1)->pPrevious,
                          pAfter1 = (*ppItem1)->pNext,
                          pBefore2 = (*ppItem2)->pPrevious,
                          pAfter2 = (*ppItem2)->pNext,
                          pItemTemp;

                if ((*ppItem1)->pNext == (*ppItem2)) {
                    (*ppItem1)->pNext = pAfter2;
                    if (pAfter2)
                        pAfter2->pPrevious = (*ppItem1);

                    (*ppItem2)->pNext = (*ppItem1);
                    (*ppItem1)->pPrevious = (*ppItem2);

                    if (pBefore1) {
                        pBefore1->pNext = (*ppItem2);
                        (*ppItem2)->pPrevious = pBefore1;
                    } else {
                        *ppFirst = (*ppItem2);
                        (*ppItem2)->pPrevious = NULL;
                    }
                } else {
                    if (pBefore1) {
                        pBefore1->pNext = (*ppItem2);
                        (*ppItem2)->pPrevious = pBefore1;
                    } else {
                        *ppFirst = (*ppItem2);
                        (*ppItem2)->pPrevious = NULL;
                    }
                    (*ppItem2)->pNext = pAfter1;
                    if (pAfter1)
                        pAfter1->pPrevious = (*ppItem2);

                    if (pBefore2) {
                        pBefore2->pNext = (*ppItem1);
                        (*ppItem1)->pPrevious = pBefore2;
                    } else {
                        *ppFirst = (*ppItem1);
                        (*ppItem1)->pPrevious = NULL;
                    }
                    (*ppItem1)->pNext = pAfter2;
                    if (pAfter2)
                        pAfter2->pPrevious = (*ppItem1);
                }

                // now swap the pointers also
                pItemTemp = *ppItem1;
                *ppItem1 = *ppItem2;
                *ppItem2 = pItemTemp;

                if (ppLast)
                    *ppLast = NULL;
            }

    return (brc);
}

/*
 *@@ lstQuickSort2:
 *      helper routine for recursive quicksort (below)
 */

void lstQuickSort2(PLISTITEM *ppFirst, PLISTITEM *ppLast, PFNSORTLIST pfnSort, void* pStorage,
            long lLeft, long lRight)
{
    long ll = lLeft, lr = lRight-1,
         lPivot = lRight;

    if (lRight > lLeft) {
        PLISTITEM   pItemLeft = lstItemFromIndex(*ppFirst, ll),
                    pItemRight = lstItemFromIndex(*ppFirst, lr),
                    pItemPivot = lstItemFromIndex(*ppFirst, lPivot);

        while (TRUE) {
            // compare left item to pivot
            while ( (*pfnSort)(pItemLeft, pItemPivot, pStorage) < 0 )
            {
                ll++;
                pItemLeft = pItemLeft->pNext;
            }

            // compare right item to pivot
            while (     ( (*pfnSort)(pItemRight, pItemPivot, pStorage) >= 0 )
                    && (lr > ll)
                  )
            {
                lr--;
                pItemRight = pItemRight->pPrevious;
            }

            if (lr <= ll)
                break;

            // swap pItemLeft and pItemRight
            lstSwapItems(ppFirst, ppLast, &pItemLeft, &pItemRight);
        }

        // swap pItemLeft and pItemPivot
        lstSwapItems(ppFirst, ppLast, &pItemLeft, &pItemPivot);

        lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage, lLeft, ll-1);
        lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage, ll+1, lRight);
    }
}

/*
 *@@ lstQuickSort:
 *      this will sort the list starting at *ppFirst using the
 *      sort function pfnSort, which works similar to those of the
 *      container sorts, i.e. it must be declared as a
 *          SHORT fnSort(void* pItem1, void* pItem1, void* pStorage)
 *      These sort functions need to return the following:
 *          0   pItem1 == pItem2
 *         -1   pItem1 <  pItem2
 *         +1   pItem1 >  pItem2
 *      This function uses the "quick sort" algorithm, which is one of
 *      the fastest sort algorithms available. However, this is an
 *      "instable" sort algorithm, meaning that list items considered
 *      equal by pfnSort do _not_ retain their position, but might be
 *      changed. If you need these to remain where they are, use
 *      lstBubbleSort.
 */

BOOL lstQuickSort(PLISTITEM *ppFirst, PLISTITEM *ppLast,
            PFNSORTLIST pfnSort, void* pStorage)
{
    if ((pfnSort) && (ppFirst))
    {
        long lRight = lstCountItems(*ppFirst)-1;

        lstQuickSort2(ppFirst, ppLast, pfnSort, pStorage,
                    0,          // lLeft
                    lRight);
    }

    return (TRUE);
}

/*
 *@@ lstBubbleSort:
 *      this will sort the list starting at *ppFirst using the
 *      sort function pfnSort, which works similar to those of the
 *      container sorts, i.e. it must be declared as a
 *          SHORT EXPENTRY fnSort(void* pItem1, void* pItem1, void* pStorage)
 *      These sort functions need to return the following:
 *          0   pItem1 == pItem2
 *         -1   pItem1 <  pItem2
 *         +1   pItem1 >  pItem2
 *      This function uses the "bubble sort" algorithm, which will cause a
 *      lot of calls to pfnSort and which is really ineffective for lists
 *      with more than 100 items.
 */

BOOL lstBubbleSort(PLISTITEM *ppFirst, PLISTITEM *ppLast,
            PFNSORTLIST pfnSort, void* pStorage)
{
    if ((pfnSort) && (ppFirst))
    {
        long lRight = lstCountItems(*ppFirst),
             lSorted, x;

        do {
            lRight--;
            lSorted = 0;
            for (x = 0; x < lRight; x++) {
                // ulComp++;
                PLISTITEM pItem1 = lstItemFromIndex(*ppFirst, x),
                          pItem2 = pItem1->pNext;
                if ((pItem1) && (pItem2))
                    if ( (*pfnSort)(pItem1, pItem2, pStorage) > 0 )
                    {
                        lstSwapItems(ppFirst, ppLast, &pItem1, &pItem2);
                        lSorted++;
                    }
            }
        } while ( lSorted && (lRight > 1) );
    }

    return (TRUE);
}

/*
 *@@ lstCountItems:
 *      this will count the number of items from pFirst;
 *      returns 0 if error occured.
 */

unsigned long lstCountItems(PLISTITEM pFirst)
{
    unsigned long ulCount = 0;
    PLISTITEM pItem = pFirst;

    while (pItem)
    {
        ulCount++;
        pItem = pItem->pNext;
    }

    return (ulCount);
}

/*
 *@@ lstItemFromIndex:
 *      returns the list item with a given ulIndex
 *      (counting from 0), or NULL if ulIndex is too large
 */

PLISTITEM lstItemFromIndex(PLISTITEM pFirst, unsigned long ulIndex)
{
    unsigned long           ulCount = 0;
    PLISTITEM pItem = NULL;

    if (pFirst) {
        pItem = pFirst;
        for (ulCount = 0; ((pItem) && (ulCount < ulIndex)); ulCount++)
            if (pItem->pNext)
                pItem = pItem->pNext;
            else
                pItem = NULL;
    }

    return (pItem);
}

/*
 *@@ lstClear:
 *      this will free the whole list starting
 *      at *ppFirst and set *ppFirst/*ppLast to NULL
 */

void lstClear(PLISTITEM *ppFirst, PLISTITEM *ppLast)
{
    PLISTITEM  pItem, pItem2;

    pItem = (PLISTITEM)*ppFirst;
    while (pItem) {
        pItem2 = pItem->pNext;
        free(pItem);
        pItem = pItem2;
    }; // while (pItem);

    *ppFirst = NULL;
    if (ppLast)
        *ppLast = NULL;

}


