source: trunk/packages/vizservers/nanovis/Chain.cpp @ 1970

/*
 * Chain.cpp --
 *
 * The module implements a generic linked list package.
 *
 *      Copyright 1991-2004 George A Howlett.
 *
 *      Permission is hereby granted, free of charge, to any person obtaining
 *      a copy of this software and associated documentation files (the
 *      "Software"), to deal in the Software without restriction, including
 *      without limitation the rights to use, copy, modify, merge, publish,
 *      distribute, sublicense, and/or sell copies of the Software, and to
 *      permit persons to whom the Software is furnished to do so, subject to
 *      the following conditions:
 *
 *      The above copyright notice and this permission notice shall be
 *      included in all copies or substantial portions of the Software.
 *
 *      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *      EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *      MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *      NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *      LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *      OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *      WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include <stdlib.h>
#include <stdio.h>
#include "Chain.h"

typedef int (QSortCompareProc) (const void *, const void *);

/*
 *----------------------------------------------------------------------
 *
 * Reset --
 *
 *      Removes all the links from the chain, freeing the memory for each
 *      link.  Memory pointed to by the link (clientData) is not freed.  It's
 *      the caller's responsibility to deallocate it.
 *
 * Results:
 *      None.
 *
 *---------------------------------------------------------------------- 
 */
void
Chain::Reset() /* Chain to clear */
{
    ChainLink *oldPtr;
    ChainLink *linkPtr = _head;

    while (linkPtr != NULL) {
        oldPtr = linkPtr;
        linkPtr = linkPtr->Next();
        delete oldPtr;
    }
    Init();
}

/*
 *----------------------------------------------------------------------
 *
 * LinkAfter --
 *
 *      Inserts a link after another link.  If afterPtr is NULL, then the new
 *      link is prepended to the beginning of the chain.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
void
Chain::LinkAfter(ChainLink *linkPtr, ChainLink *afterPtr)
{
    if (_head == NULL) {
        _tail = _head = linkPtr;
    } else {
        if (afterPtr == NULL) {
            /* Prepend to the front of the chain */
            linkPtr->_next = _head;
            linkPtr->_prev = NULL;
            _head->_prev = linkPtr;
            _head = linkPtr;
        } else {
            linkPtr->_next = afterPtr->Next();
            linkPtr->_prev = afterPtr;
            if (afterPtr == _tail) {
                _tail = linkPtr;
            } else {
                afterPtr->Next()->_prev = linkPtr;
            }
            afterPtr->_next = linkPtr;
        }
    }
    _nLinks++;
}

/*
 *----------------------------------------------------------------------
 *
 * LinkBefore --
 *
 *      Inserts a new link preceding a given link in a chain.  If beforePtr is
 *      NULL, then the new link is placed at the beginning of the list.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
void
Chain::LinkBefore(
    ChainLink *linkPtr,         /* New entry to be inserted */
    ChainLink *beforePtr)       /* Entry to link before */
{
    if (_head == NULL) {
        _tail = _head = linkPtr;
    } else {
        if (beforePtr == NULL) {
            /* Append to the end of the chain. */
            linkPtr->_next = NULL;
            linkPtr->_prev = _tail;
            _tail->_next = linkPtr;
            _tail = linkPtr;
        } else {
            linkPtr->_prev = beforePtr->Prev();
            linkPtr->_next = beforePtr;
            if (beforePtr == _head) {
                _head = linkPtr;
            } else {
                beforePtr->Prev()->_next = linkPtr;
            }
            beforePtr->_prev = linkPtr;
        }
    }
    _nLinks++;
}

/*
 *----------------------------------------------------------------------
 *
 * Unlink --
 *
 *      Unlinks a link from the chain. The link is not deallocated, 
 *      but only removed from the chain.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
void
Chain::Unlink(ChainLink *linkPtr)
{
    bool unlinked;              /* Indicates if the link is actually removed
                                 * from the chain. */

    unlinked = false;
    if (_head == linkPtr) {
        _head = linkPtr->Next();
        unlinked = true;
    }
    if (_tail == linkPtr) {
        _tail = linkPtr->Prev();
        unlinked = true;
    }
    if (linkPtr->Next() != NULL) {
        linkPtr->Next()->_prev = linkPtr->Prev();
        unlinked = true;
    }
    if (linkPtr->Prev() != NULL) {
        linkPtr->Prev()->_next = linkPtr->Next();
        unlinked = true;
    }
    if (unlinked) {
        _nLinks--;
    }
    linkPtr->_prev = linkPtr->_next = NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * DeleteLink --
 *
 *      Unlinks and frees the given link from the chain.  It's assumed that
 *      the link belong to the chain. No error checking is performed to verify
 *      this.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
void
Chain::DeleteLink(ChainLink *linkPtr)
{
    Unlink(linkPtr);
    delete linkPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Append --
 *
 *      Creates and new link with the given data and appends it to the end of
 *      the chain.
 *
 * Results:
 *      Returns a pointer to the link created.
 *
 *----------------------------------------------------------------------
 */
ChainLink *
Chain::Append(void *clientData)
{
    ChainLink *linkPtr;

    linkPtr = new ChainLink(clientData);
    LinkBefore(linkPtr, (ChainLink *)NULL);
    return linkPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Prepend --
 *
 *      Creates and new link with the given data and prepends it to beginning
 *      of the chain.
 *
 * Results:
 *      Returns a pointer to the link created.
 *
 *----------------------------------------------------------------------
 */
ChainLink  *
Chain::Prepend(void *clientData)
{
    ChainLink *linkPtr;

    linkPtr = new ChainLink(clientData);
    LinkAfter(linkPtr, (ChainLink *)NULL);
    return linkPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * GetNthLink --
 *
 *      Find the link at the given position in the chain.
 *
 * Results:
 *      Returns the pointer to the link, if that numbered link
 *      exists. Otherwise NULL.
 *
 *----------------------------------------------------------------------
 */
ChainLink *
Chain::GetNthLink(long position) /* Index of link to select from front or back
                                  * of the chain. */
{
    ChainLink *linkPtr;

    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->Next()) {
        if (position == 0) {
            return linkPtr;
        }
        position--;
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Sort --
 *
 *      Sorts the chain according to the given comparison routine.  
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      The chain is reordered.
 *
 *----------------------------------------------------------------------
 */

void
Chain::Sort(ChainCompareProc *proc)
{
    ChainLink *linkPtr;
    long i;

    if (_nLinks < 2) {
        return;
    }
    ChainLink **linkArr = new ChainLink *[_nLinks + 1];
    if (linkArr == NULL) {
        return;                 /* Out of memory. */
    }
    i = 0;
    for (linkPtr = _head; linkPtr != NULL; linkPtr = linkPtr->Next()) { 
        linkArr[i++] = linkPtr;
    }
    qsort((char *)linkArr, _nLinks, sizeof(ChainLink *), 
          (QSortCompareProc *)proc);

    /* Rethread the chain. */
    linkPtr = linkArr[0];
    _head = linkPtr;
    linkPtr->_prev = NULL;
    for (i = 1; i < _nLinks; i++) {
        linkPtr->_next = linkArr[i];
        linkPtr->Next()->_prev = linkPtr;
        linkPtr = linkPtr->Next();
    }
    _tail = linkPtr;
    linkPtr->_next = NULL;
    delete [] linkArr;
}