list.h

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

/* -*-C-*-
 *
 * $Revision: 1.1 $
 *   $Author: rivimey $
 *     $Date: 1999/03/11 19:25:38 $
 *
 * Copyright (c) 1998 ARM Limited.
 * All Rights Reserved.
 *
 *   Project: ANGEL
 *
 *     Title: List management code
 */

#ifndef list_h
#define list_h

/*
 * A MinNode structure, enough to link elements together, but not
 * adequate for the Enqueue function. Should normally be included
 * as the first element in another structure... e.g.
 *
 *  struct xx { MinNode node; int mydata, float myfloat };
 *
 */
typedef struct _minnode {

    struct _minnode *mn_next;
    struct _minnode *mn_prev;

} MinNode;

/*
 * A full Node... this includes a MinNode but extends it with
 * name, priority and type fields. The name is used by other code,
 * and by the FindNodeByName routine (which finds a node given its
 * name. The priority is used by Enqueue, which is used to create
 * priority sorted lists, and is also useful as a generic datum.
 */
typedef struct _node {
    MinNode n;
    char *n_name;
    short n_pri, n_type;
} Node;

/*
 * The list header. Unusually, there are three pointers here, one
 * of which is always NULL. While this *seems* stupid at first sight,
 * it is this fact which enables the code to ignore end conditions.
 * Lists are actually constructed with two extra nodes, one at each
 * end:
 *       A             B             C
 *   +======+      +======+      +======+
 *   |  FP  |  ->  | NEXT |  ->  |  nil |
 *   +------+      +------+      +------+
 *   |  nil |  <-  | PREV |  <-  |  BP  |
 *   +======+      +------+      +======+
 *                 | DATA |              
 *                 +======+
 *
 * Here, the central element 'B' is the only node which contains
 * data; nodes A and C are admin nodes and contain the pointers to
 * the start (FP) and end (BP) of the list. If you combine them:
 *
 *   +======+      
 *   |  FP  |      
 *   +------+      +------+
 *   |  nil |      |  nil |
 *   +======+      +------+
 *                 |  BP  |
 *                 +======+
 *
 * you end up with the structure below.
 */
typedef struct {

    MinNode *lp_next;  /* front of list */
    MinNode *lp_prev;  /* always NULL */
    MinNode *lp_tailprev; /* back of list */

} List;

/* PROTOTYPES */

/* possibly inlined */

extern void NewList(List *lp);
extern void AddHead(List *lp, MinNode *np);
extern void AddTail(List *lp, MinNode *np);
extern MinNode* RemHead(List *lp);
extern MinNode* RemTail(List *lp);
extern int IsListEmpty(List *lp);
extern int AtEndOfList(MinNode *np);
extern int AtStartOfList(MinNode *np);
extern MinNode* Succ(MinNode *np);
extern MinNode* Pred(MinNode *np);
extern MinNode* FirstNode(List *lp);
extern MinNode* LastNode(List *lp);
extern void InsertAfter(MinNode *np1, MinNode *np2);
extern void InsertBefore(MinNode *np1, MinNode *np2);
extern void Remove(MinNode *np);

/* non-inline functions */

extern void Enqueue(List *lp, Node *np);
extern Node* FindNodeByName(List *lp, char *name);
extern Node* FindNodeByPri(List *lp, short pri);
extern Node* FindNodeByType(List *lp, short type);

/*
 * inline control:
 * Define INLINE_LIST_FNS to get inline code. If
 * defined, use:
 *
 *   #define INLINE_LIST_SM __inline
 *   #define INLINE_LIST_LG 
 *
 * to have smaller functions inlined.
 * 
 *   #define INLINE_LIST_SM __inline
 *   #define INLINE_LIST_LG __inline
 *
 * to have all functions inlined.
 * ( this is the default )
 * 
 */
/* prevent __inline causing problems on other compilers */
#ifdef __ARMCC_VERSION

#if !defined( INLINE_LIST_SM ) && ! defined ( INLINE_LIST_LG )

/* make default to inline small but not large functions */
#define INLINE_LIST_SM __inline
#define NEED_SM_FN_BODIES
#define INLINE_LIST_LG

#endif

#else

#define INLINE_LIST_SM
#define INLINE_LIST_LG

#endif

/*
 *        Function:  NewList
 *
 *         Purpose:  Initialise the list header to the Empty state.
 *
 *       Arguments:  lp - pointer to the list header structure to be
 *                        initialised
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  None.
 *
 * Post-conditions:  Referenced list now empty.
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(newlist_c)
INLINE_LIST_LG
void NewList(List *lp)
{
    lp->lp_next = (MinNode*)(&lp->lp_prev);
    lp->lp_prev = NULL;
    lp->lp_tailprev = (MinNode*)(&lp->lp_next);
}
#endif


/*
 *        Function:  AddHead
 *
 *         Purpose:  Add the given node to the front (head) of the
 *                   indicated list.
 *
 *       Arguments:  lp - pointer to the list header of the list to add to
 *                   np - pointer to the node to add
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  list contains node as the first element.
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(addhead_c)
INLINE_LIST_LG
void AddHead(List *lp, MinNode *np)
{
    np->mn_next = lp->lp_next;
    np->mn_prev = (MinNode*)&lp->lp_next;
    lp->lp_next->mn_prev = np;
    lp->lp_next = np;
}
#endif

/*
 *        Function:  AddTail
 *
 *         Purpose:  Add the given node to the back (tail) of the
 *                   indicated list.
 *
 *       Arguments:  lp - pointer to the list header of the list to add to
 *                   np - pointer to the node to add
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  list contains node as the last element.
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(addtail_c)
INLINE_LIST_LG
void AddTail(List *lp, MinNode *np)
{
    np->mn_next = (MinNode*)&lp->lp_prev;
    np->mn_prev = lp->lp_tailprev;
    lp->lp_tailprev->mn_next = np;
    lp->lp_tailprev = np;
}
#endif

/*
 *        Function:  RemHead
 *
 *         Purpose:  Remove the first node from the indicated list, returning
 *                   a pointer to the removed node, or NULL if the list was empty
 *
 *       Arguments:  lp - pointer to the list header of the list
 *
 *          Return:  MinNode* - pointer to the removed node
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  list contains one less element.
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(remhead_c)
INLINE_LIST_LG
MinNode* RemHead(List *lp)
{
    MinNode *p = lp->lp_next; /* first node */
    if (p->mn_next != NULL)
    {
	p->mn_next->mn_prev = (MinNode*)&(lp->lp_next);
	lp->lp_next = lp->lp_next->mn_next;
	return p;
    }
    return NULL;
}
#endif

/*
 *        Function:  RemTail
 *
 *         Purpose:  Remove the last node from the indicated list, returning
 *                   a pointer to the removed node, or NULL if the list was empty
 *
 *       Arguments:  lp - pointer to the list header of the list
 *
 *          Return:  MinNode* - pointer to the removed node
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  list contains one less element.
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(remtail_c)
INLINE_LIST_LG
MinNode* RemTail(List *lp)
{
    MinNode *p = lp->lp_tailprev; /* last node */
    if (p != (MinNode*)&lp->lp_next)
    {
	p->mn_prev->mn_next = p->mn_next;
	lp->lp_tailprev = p->mn_prev;
	return p;
    }
    return NULL;
}
#endif

/*
 *        Function:  IsListEmpty
 *
 *         Purpose:  To return a boolean which is TRUE if the list
 *                   is empty, and FALSE otherwise.
 *
 *       Arguments:  lp - pointer to the list header of the list
 *
 *          Return:  int - TRUE if list contains nodes, FALSE otherwise
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(islistempty_c)
INLINE_LIST_SM int IsListEmpty(List *lp)
{
    return (lp->lp_next->mn_next == NULL);
}
#endif

/*
 *        Function:  AtEndOfList
 *
 *         Purpose:  To return a boolean which is TRUE if the referenced
 *                   node is at the end of the list, and FALSE otherwise.
 *                   If this routine returns TRUE, 'np' is pointing at
 *                   the admin node, and therefore contains no data.
 *
 *       Arguments:  np - pointer to a MinNode.
 *
 *          Return:  int - FALSE if node contains data, TRUE otherwise
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(atendoflist_c)
INLINE_LIST_SM int AtEndOfList(MinNode *np)
{
    return (np->mn_next == NULL);
}
#endif

/*
 *        Function:  AtStartOfList
 *
 *         Purpose:  To return a boolean which is TRUE if the referenced
 *                   node is the start of the list, and FALSE otherwise.
 *                   If this routine returns TRUE, 'np' is pointing at
 *                   the admin node, and therefore contains no data.
 *
 *       Arguments:  np - pointer to a MinNode.
 *
 *          Return:  int - FALSE if node contains data, TRUE otherwise
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(atstartoflist_c)
INLINE_LIST_SM int AtStartOfList(MinNode *np)
{
    return (np->mn_prev == NULL);
}
#endif

/*
 *        Function:  Succ
 *
 *         Purpose:  Return the next member of the list. Returns NULL
 *                   if on entry 'np' was pointing at the final admin node
 *
 *       Arguments:  np - pointer to a node in the list.
 *
 *          Return:  MinNode* - pointer to the following node in the list.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(succ_c)
INLINE_LIST_SM MinNode* Succ(MinNode *np)
{
    return np->mn_next;
}
#endif

/*
 *        Function:  Pred
 *
 *         Purpose:  Return the previous member of the list. Returns NULL
 *                   if on entry 'np' was pointing at the initial admin node
 *                   
 *       Arguments:  np - pointer to a node in the list.
 *
 *          Return:  MinNode* - pointer to the previous node in the list.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(pred_c)
INLINE_LIST_SM MinNode* Pred(MinNode *np)
{
    return np->mn_prev;
}
#endif

/*
 *        Function:  FirstNode
 *
 *         Purpose:  Returns the first data node in the list. If the list is
 *                   empty then AtEndOfList(FirstNode(&list)) will be TRUE.
 *
 *       Arguments:  lp - pointer to the list header of the list
 *
 *          Return:  MinNode* - pointer to first node in list.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(firstnode_c)
INLINE_LIST_SM MinNode* FirstNode(List *lp)
{
    return lp->lp_next;
}
#endif

/*
 *        Function:  LastNode
 *
 *         Purpose:  Returns the first data node in the list. If the list is
 *                   empty then AtStartOfList(LastNode(&list)) will be TRUE.
 *
 *       Arguments:  lp - pointer to the list header of the list
 *
 *          Return:  MinNode* - pointer to last node in list.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(lastnode_c)
INLINE_LIST_SM MinNode* LastNode(List *lp)
{
    return lp->lp_tailprev;
}
#endif

/*
 *        Function:  Insert
 *
 *         Purpose:  To insert a node np2 after an arbitrary node np1. If the address
 *                   of the list header is given as 'np1' then the node will be inserted
 *                   at the head of the list, equivalent to AddHead. Otherwise, 'np1'
 *                   should be a data node previously added to the list.
 *
 *       Arguments:  np1 - address of a data node in the list, or the address of the
 *                         list header.
 *                   np2 - address of a node to add to the list, after the np1.
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(insertafter_c)
INLINE_LIST_LG
void InsertAfter(MinNode *np1, MinNode *np2)
{
    np2->mn_next = np1->mn_next;
    np2->mn_prev = np1;
    np1->mn_next->mn_prev = np2;
    np1->mn_next = np2;
}
#endif

/*
 *        Function:  InsertBefore
 *
 *         Purpose:  To insert a node np2 before an arbitrary node np1, which
 *                   should be a data node previously added to the list.
 *
 *       Arguments:  np1 - address of a data node in the list
 *                   np2 - address of a node to add to the list, after the np1.
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_LG_FN_BODIES) || defined(insertbefore_c)
INLINE_LIST_LG
void InsertBefore(MinNode *np1, MinNode *np2)
{
    np2->mn_next = np1;
    np2->mn_prev = np1->mn_prev;
    np1->mn_prev->mn_next = np2;
    np1->mn_prev = np2;
}
#endif


/*
 *        Function:  Remove
 *
 *         Purpose:  Remove a data node from a list. 
 *
 *       Arguments:  np - the address of the node to remove.
 *
 *          Return:  none.
 *                   
 *  Pre-conditions:  list header initialised with NewList
 *
 * Post-conditions:  
 *
 */
#if defined(NEED_SM_FN_BODIES) || defined(remove_c)
INLINE_LIST_SM void Remove(MinNode *np)
{
    np->mn_next->mn_prev = np->mn_prev;
    np->mn_prev->mn_next = np->mn_next;
}
#endif

#endif /* list_h */