list.c

Microsoft Visual C++ 6.0环境下的无损压缩测试工程

/* Name : list.c
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 490
 *
 * One subtlety here must be explained further.  The list header is
 * constructed in an efficient, but confusing manner.  This of the header
 * as a structure containg the head and tail nodes for the list.  The
 * head and tail nodes are placeholders, and never carry data.  The head
 * and tail portions of the header actually overlap in memory.  lh_Head and
 * lh_Tail form the head node; lh_Tail and lh_TailPred form the tail node.
 * This makes it easy to find the start or end of the list, and eliminates
 * any special cases for insertion or removal.
 *
 *   "Head Node"   "Tail Node"         "Merged Header"
 * +-------------+                     +-------------+
 * |   ln_Succ   |                     |   lh_Head   |
 * +-------------+-------------+       +-------------+
 * | ln_Pred = 0 | ln_Succ = 0 |  ---> | lh_Tail = 0 |
 * +-------------+-------------+       +-------------+
 *               |   ln_Pred   |       | ln_TailPred |
 *               +-------------+       +-------------+
 *
 *           Figure 23-2: List Header Overlap
 *
 * The lh_Head and lh_Tail fields of the list header act like the
 * ln_Succ and lh_Pred fields of a node.  The lh_Tail field is set
 * permanently to NULL, indicating that the head node is indeed the
 * first on the list -- that is, it has no predecessors.
 *
 * Likewise, the lh_Tail and lh_TailPred fields of the list header
 * act like the ln_Succ and ln_Pred fields of a node.  Here the NULL
 * lh_Tail indicates that the tail node is indeed the list on the
 * list -- that is, it has no successors.
 *
 *      $Log:	list.c,v $
 * Revision 1.4  95/10/26  16:17:42  idr
 * Changed FindName() to use a slightly more optimal loop condition.
 * Changed SortList() to use a radix sort rather than the yucky sort
 * that it was using before.  At this time, the old versions of both
 * functions still exist in the code.
 * 
 * Revision 1.3  95/10/20  15:03:47  idr
 * Fixed a bug in the Enqueue() function that caused nodes to be added to
 * the list in the wrong order.  I also cleaned that function and a couple
 * of others up a little bit so that they're a bit easier to read.
 * 
 * Revision 1.2  1995/09/05  02:38:01  idr
 * Move AddHead() and AddTail() so that I would not need to use any
 * bounus function prototypes to prevent compliation errors.
 *
 * Revision 1.1  1995/07/09  20:10:47  idr
 * Initial revision
 */

/******************************************************************************/

#include <stdio.h>
#include "stdtypes.h"

#undef HAVE_INLINE
#include "lists.h"

#ifdef AMIGA
#include <clib/utility_protos.h>
#else
#include <string.h>
#pragma intrinsic strcmp
#define StrCmp strcmp
#endif

/******************************************************************************/
/* Name : NewList()
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 490
 *
 * HEADER INITIALIZATION
 *
 * List headers must be properly initialized before use.  It is not
 * adequate to initialize the entire header to zero.  The head and tail
 * entries must have specific values.  The header must be initialized
 * as follows:
 *
 *  1. Set the lh_Head field to the address of lh_Tail.
 *  2. Clear the lh_Tail field.
 *  3. Set the lh_TailPred field to the address of lh_Head.
 *  4. Set lh_Type to the same data type as the nodes to be kept
 *     in the list. (Unless you are using a MinList).
 */

void NewList( struct List * list )
{
    list->lh_Head     = (struct Node *) &(list->lh_Tail);
    list->lh_Tail     = NULL;
    list->lh_TailPred = (struct Node *) &(list->lh_Head);
}




/******************************************************************************/
/* Name : AddHead()
 *
 * Notes: This function adds the specified node to the begining (head)
 *        of the specified list.
 */

void AddHead( struct List * list, struct Node * node )
{
    struct Node * tempNode;     /* temporary pointer to a node  */


    /* Save the pointer to the old head node. */

    tempNode = list->lh_Head;


    /* Make ``node'' the new head. */

    list->lh_Head = node;


    /* Link ``node'' to its new neighbors. */

    node->ln_Succ = tempNode;
    node->ln_Pred = (struct Node *)list;


    /* Link the old head to the new head. */

    tempNode->ln_Pred = node;

    return;
}




/******************************************************************************/
/* Name : AddTail()
 *
 * Notes: This function adds the specified node to the end (tail) of
 *        the given list.
 */

void AddTail( struct List * list, struct Node * node )
{
    struct Node  * tempNode;    /* temporary pointer to a node          */
    struct Node  * tailNode;    /* pointer to the tail part of the list */


    /* Get a pointer to the tail part of the list header so that
     * we can just treat it like a normal node. 
     */

    tailNode = (struct Node *)&(list->lh_Tail);


    /* Save a pointer to the old tail node. */

    tempNode = tailNode->ln_Pred;


    /* Set the new tail node pointer. */

    tailNode->ln_Pred = node;


    /* Link the new tail node to its new neighbors. */

    node->ln_Pred = tempNode;
    node->ln_Succ = tailNode;


    /* Line the old tail node to its new neighbors. */

    tempNode->ln_Succ = node;
    return;
}




/******************************************************************************/
/* Name : Insert()
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
 *
 * The Insert() function is used for inserting a new node into any
 * position in a list.  It always inserts the node following a
 * specified node that is already part of the list.  For example,
 * Insert(header, node, pred) inserts the node ``node'' after the node
 * ``pred'' in the specified list.  If the pred node points to the list
 * header or is NULL, the new node will be inserted at the head of the
 * list.  Similarly, if the pred node points to the lh_Tail of the
 * list, the new node will be inserted at the tail of the list.  However,
 * both of these actions can be better accomplished with the functions
 * mentioned in the "Special Case Insertion" section below.
 */

void Insert( struct List * list, struct Node * node, struct Node * pred )
{
    struct Node * tempNode;     /* temporary pointer to a node  */


    /* If the pointer to ``pred'' is NULL, then ``node'' will become
     * the head of the list. 
     */

    if ( pred == NULL )
    {
        AddHead( list, node );
        return;
    }


    /* Save the pointer to the node that comes after ``pred''. */

    tempNode = pred->ln_Succ;


    /* Link ``pred'' to its new successor. */

    pred->ln_Succ = node;


    /* Link ``node'' to its new neighbors. */

    node->ln_Pred = pred;
    node->ln_Succ = tempNode;


    /* Link pred's old successor back to its new predicessor. */

    tempNode->ln_Pred = node;


    return;
}




/******************************************************************************/
/* Name : preInsert()
 *
 * Notes: The preInsert() function is used for inserting a new node into any
 *        position in a list.  It always inserts the node preceding a
 *        specified node that is already part of the list.  For example,
 *        Insert(header, node, succ) inserts the node ``node'' before the node
 *        ``succ'' in the specified list.  If the succ node points to the list
 *        header or is NULL, the new node will be inserted at the head of the
 *        list.  Similarly, if the succ node points to the lh_Tail of the
 *        list, the new node will be inserted at the tail of the list.
 *        However, both of these actions can be better accomplished with the
 *        functions mentioned in the "Special Case Insertion" section below.
 */

void preInsert( struct List * list, struct Node * node, struct Node * succ )
{
    struct Node * tempNode;     /* temporary pointer to a node  */


    /* If the pointer to ``succ'' is NULL, then ``node'' will become
     * the head of the list. 
     */

    if( ( succ == NULL ) || (succ->ln_Pred == NULL) )
    {
        AddHead( list, node );
        return;
    }


    /* Save the pointer to the node that comes before ``succ''. */

    tempNode = succ->ln_Pred;


    /* Link ``pred'' to its new Predecessor */

    succ->ln_Pred = node;


    /* Link ``node'' to its new neighbors. */

    node->ln_Succ = succ;
    node->ln_Pred = tempNode;


    /* Link pred's old predecesor back to its new successor. */

    tempNode->ln_Succ = node;

    return;
}




/******************************************************************************/
/* Name : Remove()
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
 *
 * The Remove() function is used to remove a specified node from a list.
 * For example, Remove(node) will remove the specified node from whatever
 * list it is in.  To be removed, a node must actually be in a list.  If
 * you attempt to remove a node that is not in a list, you will cause
 * serious system problems.
 */

void Remove( struct Node * node )
{
    /* Line the node's neighbors to each other, rather than to node. */
    node->ln_Pred->ln_Succ = node->ln_Succ;
    node->ln_Succ->ln_Pred = node->ln_Pred;

    /* Unlink the node's neighbors from the node. */
    node->ln_Succ = node->ln_Pred = NULL;

    return;
}




/******************************************************************************/
/* Name : RemHead()
 *
 * Notes: This function unlinks and returns the head node in the
 *        given list.  If the list is empty, this function will
 *        return NULL.
 */

struct Node * RemHead( struct List * list )
{
    struct Node  * headNode;    /* pointer to the old head of the list  */
    struct Node  * tempNode;    /* pointer to temporary node            */


    /* Get a pointer to the old head of the list. */

    headNode = list->lh_Head;


    /* Get the node after the old head. */

    tempNode = headNode->ln_Succ;


    /* If the head node is the list node in the list, then
     * the list is really empty (see header comment for why
     * this is the case), so we need to return NULL. 
     */

    if ( tempNode == NULL )
        return( NULL );


    /* Link the header and the node after the old head node
     * to each other. 
     */

    list->lh_Head = tempNode;
    tempNode->ln_Pred = (struct Node *)list;


    /* Unlink the old head from the list. */

    headNode->ln_Succ = headNode->ln_Pred = NULL;


    /* Return the old head. */

    return( headNode );
}




/******************************************************************************/
/* Name : RemTail()
 *
 * Notes: This function unlinks and returns the tail node in the
 *        given list.  If the list is empty, this function will
 *        return NULL.
 */

struct Node * RemTail( struct List * list )
{
    struct Node  * tailNode;    /* pointer to the old tail of the list  */
    struct Node  * tempNode;    /* pointer to temporary node            */


    tailNode = list->lh_TailPred;
    tempNode = tailNode->ln_Pred;

    if ( tempNode == NULL )
        return( NULL );

    list->lh_TailPred = tempNode;
    tempNode->ln_Succ = (struct Node *)&(list->lh_Tail);

    return( tailNode );
}




/******************************************************************************/
/* Name : Enqueue()
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 492
 *
 * PRIORITIZED INSERTION
 *
 * The list functions discussed so far do not make use of the priority