list.c

AT91所有开发板的资料 AT91所有开发板的资料

/* -*-C-*-
 *
 * $Revision: 1.2 $
 *   $Author: rivimey $
 *     $Date: 1999/03/22 12:35:41 $
 *
 * Copyright (c) 1998 ARM Limited.
 * All Rights Reserved.
 *
 *   Project: ANGEL
 *
 *     Title: List management code
 */

#include <string.h>

#ifndef NULL
#define NULL 0
#endif

#ifndef INLINE_LIST_SM

#define INLINE_LIST_SM __inline
#define NEED_SM_FN_BODIES
#define INLINE_LIST_LG
#define NEED_LG_FN_BODIES

#endif 

#include "list.h"

/*
 *        Function:  Enqueue
 *
 *         Purpose:  Add a node to a list based on it's priority, placing
 *                   higher priority nodes earlier in the list. When nodes
 *                   with a priority equal to that of an existing node are
 *                   added, the new node will be added after all equal
 *                   priority nodes, thus implementing a 'round robin' scheme.
 *
 *       Arguments:  lp - the address of the list header
 *                   np - the address of the node to add.
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(enqueue_c)
void Enqueue(List *lp, Node *np)
{
    if (IsListEmpty(lp))
    {
        AddHead(lp, &np->n);
    }
    else
    {
	Node *fp = (Node*)FirstNode(lp);
	Node *bp = (Node*)LastNode(lp);
	short pri = np->n_pri;

	if (pri > fp->n_pri)
	{
	    AddHead(lp, (MinNode*)np);
	}
	else if (pri <= bp->n_pri)
	{
	    AddTail(lp, (MinNode*)np);
	}
	else
	{
	    /* we've checked start & end of list; it must be in the middle! */
	    while(pri <= fp->n_pri)
	    {
		fp = (Node*)Succ((MinNode*)fp);
	    }
	    InsertBefore((MinNode*)fp, (MinNode*)np);
	}
    }
}
#endif


/*
 *        Function:  FindNodeByName
 *
 *         Purpose:  Find a node whose name matches the name given.
 *                   The search starts at the start of the list, if
 *                   'lp' is the list header, or at the node after
 *                   a data node passed in place of lp. That is:
 *                   
 *                     np1 = FindNodeByName(lp, "task1")
 *                     np2 = FindNodeByName(np1, "task2")
 *                   
 *                   will set np1 to the address of the (first) node
 *                   named "task1" and set np2 to the address of the
 *                   first node after 'np1' node named "task2".
 *
 *       Arguments:  lp - the address of the list header, or the
 *                        address of the node to before the one to
 *                        resume searching.
 *
 *          Return:  Node* - the address of the matching node or NULL.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(findnodebyname_c)
Node* FindNodeByName(List *lp, char *name)
{
    Node *np = (Node*)FirstNode(lp);
    while(!AtEndOfList((MinNode*)np) && strcmp(np->n_name, name) != 0 )
    {
        np = (Node*)Succ(&np->n);
    }
    if (AtEndOfList((MinNode*)np))
        return NULL;
    else
        return np;
}
#endif

/*
 *        Function:  FindNodeByPri
 *
 *         Purpose:  Find a node whose priority matches the priority given.
 *                   The search starts at the start of the list, if
 *                   'lp' is the list header, or at the node after
 *                   a data node passed in place of lp. That is:
 *                   
 *                     np1 = FindNodeByPri(lp, 2)
 *                     np2 = FindNodeByPri(np1, 4)
 *                   
 *                   will set np1 to the address of the (first) node
 *                   with n_pri = 2 and set np2 to the address of the
 *                   first node after 'np1' node with n_pri = 4.
 *
 *       Arguments:  lp - the address of the list header, or the
 *                        address of the node to before the one to
 *                        resume searching.
 *
 *          Return:  Node* - the address of the matching node or NULL.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(findnodebypri_c)
Node* FindNodeByPri(List *lp, short pri)
{
    Node *np = (Node*)FirstNode(lp);
    while(!AtEndOfList((MinNode*)np) && np->n_pri != pri)
    {
        np = (Node*)Succ(&np->n);
    }
    if (AtEndOfList((MinNode*)np))
        return NULL;
    else
        return np;
}
#endif

/*
 *        Function:  FindNodeByType
 *
 *         Purpose:  Find a node whose priority matches the priority given.
 *                   The search starts at the start of the list, if
 *                   'lp' is the list header, or at the node after
 *                   a data node passed in place of lp. That is:
 *                   
 *                     np1 = FindNodeByType(lp, 2)
 *                     np2 = FindNodeByType(np1, 4)
 *                   
 *                   will set np1 to the address of the (first) node
 *                   with n_type = 2 and set np2 to the address of the
 *                   first node after 'np1' node with n_type = 4.
 *
 *       Arguments:  lp - the address of the list header, or the
 *                        address of the node to before the one to
 *                        resume searching.
 *                   type - the type number to search for
 *
 *          Return:  Node* - the address of the matching node or NULL.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(STATIC_LIBRARY) || defined(findnodebytype_c)
Node* FindNodeByType(List *lp, short type)
{
    Node *np = (Node*)FirstNode(lp);
    while(!AtEndOfList((MinNode*)np) && np->n_type != type)
    {
        np = (Node*)Succ(&np->n);
    }
    if (AtEndOfList((MinNode*)np))
        return NULL;
    else
        return np;
}
#endif

#ifdef TEST

#ifndef NULL
#define NULL 0
#endif

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int verbose = 0;

#define TRUE  (1)
#define FALSE (0)

void PrintNode(MinNode *p)
{
    if (verbose)
        printf("  Node: %0p <- prev [ %0p ] next -> %0p\n", p->mn_prev, p, p->mn_next);
}

void PrintLH(List *l)
{
    if (verbose)
    {
        printf("  List: %0p\n", l);
        printf("    lp_next = %0p\n", l->lp_next);
        printf("    lp_prev = %0p\n", l->lp_prev);
        printf("    lp_tailprev = %0p\n", l->lp_tailprev);
    }
}

void CheckEmptyList(List *l)
{
    PrintLH(l);
    
    assert(l->lp_next == (MinNode*)&(l->lp_prev));
    assert(l->lp_prev == NULL);
    assert(l->lp_tailprev == (MinNode*)&(l->lp_next));

    assert(IsListEmpty(l) == TRUE);
}

void CheckList(List *l)
{
    MinNode *p, *last;

    PrintLH(l);
    
    assert(l->lp_next != 0);
    assert(l->lp_prev == 0);
    assert(l->lp_tailprev != 0);
    
    p = l->lp_next;
    last = 0;
    while (!AtEndOfList(p))
    {
        PrintNode(p);
        
	if (last)
	{
	    assert (last->mn_next == p);
	    assert (p->mn_prev == last);
	}

	last = p;
	p = Succ(p);
    }
    assert(l->lp_tailprev == last);
}


void PrintList(List *l)
{
    Node *p;

    for(p = (Node*)l->lp_next; p->n.mn_next; p = (Node*)Succ(&p->n))
    {
    	printf("  Node: %p = %d\n", p, p->n_pri);
    }
}

int main(int argc, char *argv[])
{
    List l;
    int i;
    Node *p, *p2;
    Node *insrem[4];

    if (argc == 2 && !strcmp(argv[1], "-v"))
        verbose = 1;
    
    printf("NewList\n");
    NewList(&l);

    CheckEmptyList(&l);

    printf("----------------------------------\n");
    printf("AddHead 6 times\n");
    for (i = 0; i < 6; i++)
    {
	p2 = (Node*)l.lp_next;

	p = (Node*)malloc(sizeof(Node));
	p->n_pri = i;
	AddHead(&l, (MinNode*)p);

	assert(l.lp_next == (MinNode*)p);
	/* assert(p->n.mn_prev == (MinNode*)&(l.lp_next)); */
	assert(p->n.mn_next == (MinNode*)p2);
	assert(p2->n.mn_prev == (MinNode*)p);
    }

    CheckList(&l);

    printf("----------------------------------\n");
    printf("AddTail 4 times\n");
    for (i = 0; i < 4; i++)
    {
	p2 = (Node*)l.lp_tailprev;

	p = (Node*)malloc(sizeof(Node));
	p->n_pri = i+10;
        AddTail(&l, (MinNode*)p);

	assert(p->n.mn_next == (MinNode*)&(l.lp_prev));
	assert(l.lp_tailprev == (MinNode*)p);
	assert(p2->n.mn_next == (MinNode*)p);
	assert(p->n.mn_prev == (MinNode*)p2);
    }

    CheckList(&l);

    printf("----------------------------------\n");
    printf("RemHead all\n");
    PrintLH(&l);
    i = 0;
    do
    {
        p2 = (Node*)l.lp_next;
        /* printf("Node before remove:\n"); */
        /* PrintNode((MinNode*)p2); */
            
        p = (Node*)RemHead(&l);        
        if (p != 0)
        {
            i++;
            
            /* printf("Node after remove:\n"); */
            PrintNode((MinNode*)p);
            
            /* PrintLH(&l); */
            /* PrintNode((MinNode*)l.lp_next); */
            
            /* did we remove first in list? */
            assert(p == p2);
            /* is second node now first? */
            assert(l.lp_next == (MinNode*)p->n.mn_next);
            /* does second node now point at header? */
            assert(l.lp_next->mn_prev == (MinNode*)&(l.lp_next));
            
            free(p);
        }
    } while( p != NULL );
    
    assert(i == 10);
        
    CheckEmptyList(&l);
    
    printf("\n");

    printf("----------------------------------\n");
    printf("Insert ...\n");
    for (i = 0; i < 4; i++)
    {
	p = (Node*)malloc(sizeof(Node));
	p->n_pri = i+10;
	insrem[i] = p;
    }

    /* insert at front of list */
    printf(" front (empty) ...\n");
    Insert((MinNode*)&l, (MinNode*)insrem[0]);

	/* result node: 0 */

	assert(l.lp_next == (MinNode*)insrem[0]);
	assert(insrem[0]->n.mn_next == (MinNode*)&(l.lp_prev));
	assert(insrem[0]->n.mn_prev == (MinNode*)&(l.lp_next));
	assert(l.lp_tailprev == (MinNode*)insrem[0]);

    /* insert after node */
    printf(" after (last)...\n");
    Insert((MinNode*)insrem[0], (MinNode*)insrem[1]);

	/* result node: 0 -> 1 */
    
	assert(insrem[0]->n.mn_next == (MinNode*)insrem[1]);
	assert(insrem[1]->n.mn_prev == (MinNode*)insrem[0]);
	assert(insrem[1]->n.mn_next == (MinNode*)&(l.lp_prev));
	assert(l.lp_tailprev == (MinNode*)insrem[1]);

    /* insert after node, node not last */
    printf(" after (not last)...\n");
    Insert((MinNode*)insrem[0], (MinNode*)insrem[2]);

	/* result node: 0 -> 2 -> 1 */
    
	assert(insrem[0]->n.mn_next == (MinNode*)insrem[2]);
	assert(insrem[2]->n.mn_prev == (MinNode*)insrem[0]);
	assert(insrem[2]->n.mn_next == (MinNode*)insrem[1]);
	assert(insrem[1]->n.mn_prev == (MinNode*)insrem[2]);

    /* insert at front of list, list not empty */
    printf(" front (not empty) ...\n");
    Insert((MinNode*)&l, (MinNode*)insrem[3]);

	/* result node: 3 -> 0 -> 2 -> 1 */

	assert(insrem[3]->n.mn_next == (MinNode*)insrem[0]);
	assert(insrem[0]->n.mn_prev == (MinNode*)insrem[3]);
	assert(insrem[3]->n.mn_prev == (MinNode*)&(l.lp_next));
	assert(l.lp_next == (MinNode*)insrem[3]);

        assert(IsListEmpty(&l) == FALSE);
        
    CheckList(&l);

    printf("\n");
    
    /* remove first node */
    printf("----------------------------------\n");
    
	/* initial node: 3 -> 0 -> 2 -> 1 */

    printf("Remove (first)\n");
    Remove((MinNode*)insrem[3]);

	/* result node: 0 -> 2 -> 1 */

	assert(insrem[0]->n.mn_next == (MinNode*)insrem[2]);
	assert(insrem[0]->n.mn_prev == (MinNode*)&(l.lp_next));
	assert(l.lp_next == (MinNode*)insrem[0]);
	assert(l.lp_tailprev == (MinNode*)insrem[1]);

    /* remove middle node */
    printf("Remove (middle)\n");
    Remove((MinNode*)insrem[2]);

	/* result node: 0 -> 1 */

	assert(insrem[0]->n.mn_next == (MinNode*)insrem[1]);
	assert(insrem[0]->n.mn_prev == (MinNode*)&(l.lp_next));
        
	assert(insrem[1]->n.mn_next == (MinNode*)&(l.lp_prev));
	assert(insrem[1]->n.mn_prev == (MinNode*)insrem[0]);
        
	assert(l.lp_next == (MinNode*)insrem[0]);
        assert(l.lp_prev == NULL);
	assert(l.lp_tailprev == (MinNode*)insrem[1]);

    /* remove first node */
    printf("Remove (end)\n");
    Remove((MinNode*)insrem[1]);

	/* result node: 0 */

	assert(insrem[0]->n.mn_next == (MinNode*)&(l.lp_prev));
	assert(insrem[0]->n.mn_prev == (MinNode*)&(l.lp_next));
        
	assert(l.lp_next == (MinNode*)insrem[0]);
        assert(l.lp_prev == NULL);
	assert(l.lp_tailprev == (MinNode*)insrem[0]);

    /* remove last node */
    printf("Remove (only)\n");
    Remove((MinNode*)insrem[0]);

    CheckEmptyList(&l);
    
    printf("----------------------------------\n");
    
    printf("Enqueue (ascending)\n");
    for (i = 0; i < 4; i++)
    {
	p = (Node*)malloc(sizeof(Node));
	p->n_pri = (i * 2) + 2;
        Enqueue(&l, p);

	printf("%d: ", p->n_pri);
    	PrintNode((MinNode*)p);

	    assert(l.lp_next == (MinNode*)p);
	    assert(l.lp_prev == NULL);
	    assert(p->n.mn_prev = (MinNode*)&(l.lp_next));
    }
    
    printf("Enqueue (descending)\n");
    for (i = 0; i < 4; i++)
    {
	p = (Node*)malloc(sizeof(Node));
	p->n_pri = 12 - (i * 2);
        Enqueue(&l, p);

	printf("%d: ", p->n_pri);
    	PrintNode((MinNode*)p);

	    assert(l.lp_prev == NULL);
    }

    p2 = (Node*)l.lp_next;
    
    printf("Enqueue (front, higher)\n");
    p = (Node*)malloc(sizeof(Node));
    p->n_pri = 100;
    Enqueue(&l, p);

    printf("%d: ", p->n_pri);
    PrintNode((MinNode*)p);
    
	assert(p->n.mn_next == (MinNode*)p2);
	assert(p->n.mn_prev == (MinNode*)&(l.lp_next));

    p2 = p;
    
    printf("Enqueue (front, equal)\n");
    p = (Node*)malloc(sizeof(Node));
    p->n_pri = 100;
    Enqueue(&l, p);

    printf("%d: ", p->n_pri);
    PrintNode((MinNode*)p);
    
	assert(p2->n.mn_next == (MinNode*)p);
	assert(p->n.mn_prev == (MinNode*)p2);

    printf("Enqueue (end, lower)\n");
    p = (Node*)malloc(sizeof(Node));
    p->n_pri = 0;
    Enqueue(&l, p);

    printf("%d: ", p->n_pri);
    PrintNode((MinNode*)p);

	assert(l.lp_tailprev == (MinNode*)p);
	assert(p->n.mn_next == (MinNode*)&(l.lp_prev));

    printf("Enqueue (end, equal)\n");
    p = (Node*)malloc(sizeof(Node));
    p->n_pri = 0;
    Enqueue(&l, p);

    printf("%d: ", p->n_pri);
    PrintNode((MinNode*)p);

	assert(l.lp_tailprev == (MinNode*)p);
	assert(p->n.mn_next == (MinNode*)&(l.lp_prev));

    CheckList(&l);

    printf("\n");

    printf("----------------------------------\n");
    printf("RemTail all\n");
    PrintLH(&l);
    i = 0;
    do
    {
        p2 = (Node*)l.lp_tailprev;
        /* printf("\nNode before remove:\n"); */
        PrintNode((MinNode*)p2);
            
        p = (Node*)RemTail(&l);
        
        if (p != 0)
        {
            i++;
            
            /* printf("Node after remove:\n"); */
            PrintNode((MinNode*)p);
            
            /* PrintLH(&l); */
            /* PrintNode((MinNode*)l.lp_tailprev); */
            
            /* did we remove first in list? */
            assert(p == p2);
            /* is second node now first? */
            assert(l.lp_tailprev == (MinNode*)p->n.mn_prev);
            /* does new last node now point at header? */
            assert(l.lp_tailprev->mn_next == (MinNode*)&(l.lp_prev));
            
            free(p);
        }
    } while( p != NULL );
    
    assert(i == 12);

    CheckEmptyList(&l);
    
    printf("\n");
    
}

#endif