list.c

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

 * field in a Node.  The Enqueue() function is equivalent to Insert(),
 * except that it inserts nodes into a list sorting them according to
 * their priority.  It keeps the higher-priority nodes towards the head
 * of the list.  All nodes passed to this function must have their
 * priority and name assigned prior to the call.  Enqueue(header, mynode)
 * inserts ``mynode'' behind the lowest priority node with a priority
 * greater than or qual to ``mynode's''.  For Enqueue() to work properly,
 * the list ``mylist'' already be sorted according to priority.  Because the
 * highest priority node is at the head of the list, the RemHead() function
 * will remove the highest priority node.  Likewise, RemTail() will remove
 * the lowest priority node.
 *
 *      FIFO Is Used For The Same Priority.  If you add a node that has
 *      the same priority as another node in the queue, Enqueue() will
 *      use FIFO ordering.  The new node is inserted following the list
 *      node of equal priority.
 */

void Enqueue( struct List * list, struct Node * node )
{
    struct Node * curr;


    /* Try to get a pointer to the first node in the list.  If there
     * aren't any nodes in the list, GetHead() will return NULL.
     */

    curr = GetHead( list );


    /* If there aren't any nodes in the list, then we can't exactly
     * compare the priority of the supplied node to anything, so we'll
     * just make it the head of the list.
     */

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


    /* Now we will run through the list looking for a node that has a
     * priority that is less than the node the user supplied us with.
     * As soon as we find such a node, we'll put the user supplied node
     * in the list just before it.
     */

    do
    {
        /* Does the current node have a lower priority? */

        if ( curr->ln_Pri < node->ln_Pri )
        {
            /* Stuff ``node'' in the list right before ``curr'' and let's
             * get out of here!
             */

            preInsert( list, node, curr );
            return;
        }

        curr = SuccNode( curr );

    } while( curr != NULL );


    /* If the node did not go before any other node in the list, then
     * we'll just put it at the very end.
     */

    AddTail( list, node );
    return;
}




/******************************************************************************/
/* Name: FindName()
 *
 * Notes: The following passage is taken verbatim from _Amiga_ROM_Kernal
 *        _Reference_Manual:_Libraries_3rd_Edition_, page 493
 *
 * SEARCHING BY NAME
 *
 * Because many lists contain nodes with symbolic names attached (via
 * the ln_Name field), it is possible to find a node by its name.  This
 * naming technique is used throughout Exec for such nodes as tasks,
 * libraries, devices, and resources.
 *
 * The FindName() function searches a list for the first node with a
 * given name.  For example, FindName(header, "Furrbol") returns a pointer
 * the the first node named ``Furrbol''.  If no such node exists, a
 * NULL is returned.  The case of the name characters is significant;
 * ``foo'' is different from ``Foo''.
 */

#pragma intrinsic strcmp

struct Node * FindName( struct List * list, STRPTR name )
{
    struct Node  * curr;        /* pointer to the node being examined       */
    struct Node  * next;        /* pointer to the next node to be examined  */


#if 0
    for( curr = list->lh_Head ; curr->ln_Succ != NULL ; curr = curr->ln_Succ )
#else
    for( curr = list->lh_Head ; (next = curr->ln_Succ) != NULL ; curr = next )
#endif
    {
        /* If the names match, return a pointer to the current node. */

        if ( StrCmp( name, curr->ln_Name ) == 0 )
            return( curr );
    }


    /* If it gets this far, then there is no node with the given
     * name in this list. 
     */

    return( NULL );
}




/******************************************************************************/
/* Name : GetHead()
 *
 * Notes: This function is very similar in concept to RemHead(), with the
 *        exception that it doesn't modify the linked list.
 */

struct Node * GetHead( struct List * list )
{
    return( (list->lh_Head->ln_Succ == NULL) ? NULL : list->lh_Head );
}




/******************************************************************************/
/* Name : GetTail()
 *
 * Notes: This function is very similar in concept to RemTail(), with the
 *        exception that it doesn't modify the linked list.
 */

struct Node * GetTail( struct List * list )
{
    return( (list->lh_TailPred->ln_Pred == NULL) ? NULL : list->lh_TailPred );
}




/******************************************************************************/
/* Name : SuccNode()
 *
 * Notes: This function returns a pointer to the next node, if one exists.
 *
 */

struct Node * SuccNode( struct Node * node )
{
    return( (node->ln_Succ->ln_Succ == NULL) ? NULL : node->ln_Succ );
}




/******************************************************************************/
/* Name : PredNode()
 *
 * Notes: This function returns a pointer to the previous node, if one exists.
 *
 */

struct Node * PredNode( struct Node * node )
{
    return( (node->ln_Pred->ln_Pred == NULL) ? NULL : node->ln_Pred );
}




/******************************************************************************/
/* Name : MoveList()
 *
 * Notes: This function is used to take the nodes that are in one list and
 *        put them in another list.  It is important to note, that the
 *        source list is NOT VALID AFTER THIS CALL.  Also, any nodes that
 *        might already be in the destination list will be LOST.
 */

void MoveList( struct List * sList, struct List * dList )
{
    struct Node * node;


    /* First, make the destination list point to its new head and tail
     * nodes.  Also, init. the lh_Tail value.
     */

    dList->lh_Head     = sList->lh_Head;
    dList->lh_Tail     = NULL;
    dList->lh_TailPred = sList->lh_TailPred;


    /* Now, make the new tail node point to the list header. */

    node = dList->lh_TailPred;
    node->ln_Succ = (struct Node *) &(dList->lh_Tail);


    /* Now, make the new head node point back at the list header. */

    node = dList->lh_Head;
    node->ln_Pred = (struct Node *) &(dList->lh_Head);
}




/******************************************************************************/
/* Name : AppendList()
 *
 * Notes: This function takes pointer to two list header, preList and
 *        postList, and creates a list that is a combination of the
 *        two, with the nodes in preList appearing first, followed by
 *        the nodes of postList.  The resultant list is linked with the
 *        header specified by preList.
 */

void AppendList( struct List * preList, struct List * postList )
{
    struct Node * firstOfPost;      /* First node in the post list. */
    struct Node * lastOfPost;       /* Last node in the post list.  */
    struct Node * lastOfPre;        /* Last node in the pre list.   */


    firstOfPost = GetHead( postList );
    lastOfPre = GetTail( preList );


    /* If the list that we were going to append is empty, then we don't
     * really have a chore to do.  Let's return to the caller now.
     */

    if ( firstOfPost == NULL ) return;


    /* If the list that we were going to append to is empty, then the
     * resultant list is just the list that we were going to append.
     * The easy way to do this is to just copy the postList to the
     * preList header.
     */

    if ( lastOfPre == NULL )
    {
        MoveList( postList, preList );
        NewList( postList );
        return;
    }


    /* This is the point where this routine gets more than just a
     * little complex.  This would make a good assignment for 3rd term,
     * first year CS students.  It would weed the wimps out from the
     * big dogs. :)
     *
     * There are actually two steps to this process.  The first step is
     * to link the node at the end of the preList to the node at the
     * start of the postList.  The second step is to link the node at
     * the end of the postList to the tail part of the list header.
     */

    lastOfPre->ln_Succ   = firstOfPost;
    firstOfPost->ln_Pred = lastOfPre;

    lastOfPost           = postList->lh_TailPred;
    lastOfPost->ln_Succ  = (struct Node *) &(preList->lh_Tail);
    preList->lh_TailPred = lastOfPost;


    /* The last step is to make sure the user won't do something totally
     * retarded and use the postList.  We'll do that by clearing the
     * list out.
     */

    NewList( postList );
}




/******************************************************************************/
/* Name : PrependList()
 *
 * Notes: This function takes pointer to two list header, preList and
 *        postList, and creates a list that is a combination of the
 *        two, with the nodes in preList appearing first, followed by
 *        the nodes of postList.  The resultant list is linked with the
 *        header specified by postList.
 */

void PrependList( struct List * postList, struct List * preList )
{
    /* This is kind of a cheesy way to do this, but it works. :) The
     * main reason that I did this routine this way is that it is a
     * LOT less code, and I don't think that PrependList() will, in
     * general, be used as much as AppendList().
     */

    AppendList( preList, postList );
    MoveList( preList, postList );
    NewList( preList );
}




/******************************************************************************/
/* Name : SortList()
 *
 * Notes: This function is used to accomplish a slow and sleazy sorting of a
 *        list by copying the list into a temporary list and sorting each
 *        member as it gets copied.  Smaller Node Priorities get sorted to the
 *        bottom.
 */

#if 0
void SortList( struct List * d )
{
    struct MinList    t;    /* Temporary list header structure.     */
    struct Node     * n;    /* Temporary node pointer.              */


    /* Initialize our temporary list header structure. */

    NewList( (struct List *) & t );


    while( ! IsListEmpty( d ) )
    {
        /* Yank the next node out of the source list. */

        n = RemHead( d );


        /* Take the node that we just removed from the source list and
         * add it, in the proper position, to the temporary destination
         * list.
         */

        Enqueue( (struct List *) &t, n );
    }


    /* Now we copy the linkage information from our temporary list
     * into the caller's list header.
     */

    MoveList( (struct List *) &t, d );
}

#else

#define RADIX           4
#define RADIX_DIVIDE    (1<<7)
#define RADIX_OFFSET    (RADIX/2)

void SortList( struct List * list )
{
    struct MinList   bucket[RADIX]; /* Sorting buckets.             */
    struct Node    * node;          /* Temporary list node pointer. */
    int              lcv;           /* Local counter variable.      */


    /* First, initialize all of the buckets that we will be sorting the
     * nodes into.
     */

    for ( lcv = 0 ; lcv < RADIX ; lcv++ )
    {
        NewList( (struct List *) & bucket[ lcv ] );
    }


    /* Now, move every node out of the source list into the bucked that
     * it belongs in.
     */

    while ( (node = RemHead( list )) != NULL )
    {
        int     radix;


        radix = node->ln_Pri / RADIX_DIVIDE;
        Enqueue( (struct List *) & bucket[ radix + RADIX_OFFSET ], node );
    }


    /* Now merge all of the buckets together to form the final, sorted
     * linked list.
     */

    MoveList( (struct List *) &bucket[ RADIX - 1 ], list );
    for ( lcv = RADIX - 2 ; lcv > 0 ; lcv-- )
    {
        AppendList( (struct List *) &bucket[ lcv ], list );
    }


    return;
}
#endif