#ifndef CYGONCE_INFRA_CLIST_HXX
|
#ifndef CYGONCE_INFRA_CLIST_HXX
|
#define CYGONCE_INFRA_CLIST_HXX
|
#define CYGONCE_INFRA_CLIST_HXX
|
|
|
//==========================================================================
|
//==========================================================================
|
//
|
//
|
// clist.hxx
|
// clist.hxx
|
//
|
//
|
// Standard types, and some useful coding macros.
|
// Standard types, and some useful coding macros.
|
//
|
//
|
//==========================================================================
|
//==========================================================================
|
//####ECOSGPLCOPYRIGHTBEGIN####
|
//####ECOSGPLCOPYRIGHTBEGIN####
|
// -------------------------------------------
|
// -------------------------------------------
|
// This file is part of eCos, the Embedded Configurable Operating System.
|
// This file is part of eCos, the Embedded Configurable Operating System.
|
// Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
|
// Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
|
//
|
//
|
// eCos is free software; you can redistribute it and/or modify it under
|
// eCos is free software; you can redistribute it and/or modify it under
|
// the terms of the GNU General Public License as published by the Free
|
// the terms of the GNU General Public License as published by the Free
|
// Software Foundation; either version 2 or (at your option) any later version.
|
// Software Foundation; either version 2 or (at your option) any later version.
|
//
|
//
|
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
|
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
|
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
// for more details.
|
// for more details.
|
//
|
//
|
// You should have received a copy of the GNU General Public License along
|
// You should have received a copy of the GNU General Public License along
|
// with eCos; if not, write to the Free Software Foundation, Inc.,
|
// with eCos; if not, write to the Free Software Foundation, Inc.,
|
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
|
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
|
//
|
//
|
// As a special exception, if other files instantiate templates or use macros
|
// As a special exception, if other files instantiate templates or use macros
|
// or inline functions from this file, or you compile this file and link it
|
// or inline functions from this file, or you compile this file and link it
|
// with other works to produce a work based on this file, this file does not
|
// with other works to produce a work based on this file, this file does not
|
// by itself cause the resulting work to be covered by the GNU General Public
|
// by itself cause the resulting work to be covered by the GNU General Public
|
// License. However the source code for this file must still be made available
|
// License. However the source code for this file must still be made available
|
// in accordance with section (3) of the GNU General Public License.
|
// in accordance with section (3) of the GNU General Public License.
|
//
|
//
|
// This exception does not invalidate any other reasons why a work based on
|
// This exception does not invalidate any other reasons why a work based on
|
// this file might be covered by the GNU General Public License.
|
// this file might be covered by the GNU General Public License.
|
//
|
//
|
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
|
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
|
// at http://sources.redhat.com/ecos/ecos-license/
|
// at http://sources.redhat.com/ecos/ecos-license/
|
// -------------------------------------------
|
// -------------------------------------------
|
//####ECOSGPLCOPYRIGHTEND####
|
//####ECOSGPLCOPYRIGHTEND####
|
//==========================================================================
|
//==========================================================================
|
//#####DESCRIPTIONBEGIN####
|
//#####DESCRIPTIONBEGIN####
|
//
|
//
|
// Author(s): nickg
|
// Author(s): nickg
|
// Contributors: nickg
|
// Contributors: nickg
|
// Date: 2000-11-08
|
// Date: 2000-11-08
|
// Purpose: Simple circular list implementation
|
// Purpose: Simple circular list implementation
|
// Description: A simple implementation of circular lists.
|
// Description: A simple implementation of circular lists.
|
// Usage: #include "cyg/infra/clist.hxx"
|
// Usage: #include "cyg/infra/clist.hxx"
|
// ...
|
// ...
|
//
|
//
|
//####DESCRIPTIONEND####
|
//####DESCRIPTIONEND####
|
//
|
//
|
//==========================================================================
|
//==========================================================================
|
|
|
#include
|
#include
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
// Class and structure conversion macros.
|
// Class and structure conversion macros.
|
// CYG_CLASSFROMFIELD translates a pointer to a field of a struct or
|
// CYG_CLASSFROMFIELD translates a pointer to a field of a struct or
|
// class into a pointer to the class.
|
// class into a pointer to the class.
|
// CYG_OFFSETOFBASE yields the offset of a base class of a derived
|
// CYG_OFFSETOFBASE yields the offset of a base class of a derived
|
// class.
|
// class.
|
// CYG_CLASSFROMBASE translates a pointer to a base class into a pointer
|
// CYG_CLASSFROMBASE translates a pointer to a base class into a pointer
|
// to a selected derived class. The base class object _must_ be part of
|
// to a selected derived class. The base class object _must_ be part of
|
// the specified derived class. This is essentially a poor mans version
|
// the specified derived class. This is essentially a poor mans version
|
// of the RTTI dynamic_cast operator.
|
// of the RTTI dynamic_cast operator.
|
// Caveat: These macros do not work for virtual base classes.
|
// Caveat: These macros do not work for virtual base classes.
|
|
|
// Note: These definitions are exact duplicates of definitions in
|
// Note: These definitions are exact duplicates of definitions in
|
// ktypes.h. If either definition is changed, the other should be too
|
// ktypes.h. If either definition is changed, the other should be too
|
// to avoid compiler messages.
|
// to avoid compiler messages.
|
|
|
#define CYG_CLASSFROMFIELD(_type_,_member_,_ptr_)\
|
#define CYG_CLASSFROMFIELD(_type_,_member_,_ptr_)\
|
((_type_ *)((char *)(_ptr_)-((char *)&(((_type_ *)0)->_member_))))
|
((_type_ *)((char *)(_ptr_)-((char *)&(((_type_ *)0)->_member_))))
|
|
|
#define CYG_OFFSETOFBASE(_type_,_base_)\
|
#define CYG_OFFSETOFBASE(_type_,_base_)\
|
((char *)((_base_ *)((_type_ *)4)) - (char *)4)
|
((char *)((_base_ *)((_type_ *)4)) - (char *)4)
|
|
|
# define CYG_CLASSFROMBASE(_class_,_base_,_ptr_)\
|
# define CYG_CLASSFROMBASE(_class_,_base_,_ptr_)\
|
((_class_ *)((char *)(_ptr_) - CYG_OFFSETOFBASE(_class_,_base_)))
|
((_class_ *)((char *)(_ptr_) - CYG_OFFSETOFBASE(_class_,_base_)))
|
|
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
// Cyg_DNode class.
|
// Cyg_DNode class.
|
// This simply represents a double linked node that is intended to
|
// This simply represents a double linked node that is intended to
|
// be a base member of the class that is being managed.
|
// be a base member of the class that is being managed.
|
|
|
class Cyg_DNode
|
class Cyg_DNode
|
{
|
{
|
friend class Cyg_CList;
|
friend class Cyg_CList;
|
|
|
Cyg_DNode *next;
|
Cyg_DNode *next;
|
Cyg_DNode *prev;
|
Cyg_DNode *prev;
|
|
|
public:
|
public:
|
|
|
Cyg_DNode()
|
Cyg_DNode()
|
{
|
{
|
// Initialize pointers to point here
|
// Initialize pointers to point here
|
next = prev = this;
|
next = prev = this;
|
};
|
};
|
|
|
// Accessor and test functions
|
// Accessor and test functions
|
Cyg_DNode *get_next() { return next; };
|
Cyg_DNode *get_next() { return next; };
|
Cyg_DNode *get_prev() { return prev; };
|
Cyg_DNode *get_prev() { return prev; };
|
cyg_bool in_list() { return next != this; };
|
cyg_bool in_list() { return next != this; };
|
|
|
// Insert a node into the list before this one,
|
// Insert a node into the list before this one,
|
// so that it becomes this nodes predecessor in
|
// so that it becomes this nodes predecessor in
|
// the list.
|
// the list.
|
void insert( Cyg_DNode *node )
|
void insert( Cyg_DNode *node )
|
{
|
{
|
node->next = this;
|
node->next = this;
|
node->prev = prev;
|
node->prev = prev;
|
prev->next = node;
|
prev->next = node;
|
prev = node;
|
prev = node;
|
};
|
};
|
|
|
// Append a node after this one so that it become
|
// Append a node after this one so that it become
|
// this nodes sucessor in the list.
|
// this nodes sucessor in the list.
|
void append( Cyg_DNode *node )
|
void append( Cyg_DNode *node )
|
{
|
{
|
node->prev = this;
|
node->prev = this;
|
node->next = next;
|
node->next = next;
|
next->prev = node;
|
next->prev = node;
|
next = node;
|
next = node;
|
};
|
};
|
|
|
// Unlink this node from it's list. It is safe to apply this to an
|
// Unlink this node from it's list. It is safe to apply this to an
|
// already unlinked node.
|
// already unlinked node.
|
void unlink()
|
void unlink()
|
{
|
{
|
next->prev = prev;
|
next->prev = prev;
|
prev->next = next;
|
prev->next = next;
|
next = prev = this;
|
next = prev = this;
|
};
|
};
|
|
|
~Cyg_DNode()
|
~Cyg_DNode()
|
{
|
{
|
// If this node is still linked, unlink it.
|
// If this node is still linked, unlink it.
|
if( next != this )
|
if( next != this )
|
unlink();
|
unlink();
|
};
|
};
|
|
|
};
|
};
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
// Cyg_CList class.
|
// Cyg_CList class.
|
|
|
// This is a simple class that manages a circular list of DNodes. This
|
// This is a simple class that manages a circular list of DNodes. This
|
// object points to the head of the list and provides functions to
|
// object points to the head of the list and provides functions to
|
// manipulate the head and tail of the list.
|
// manipulate the head and tail of the list.
|
|
|
class Cyg_CList
|
class Cyg_CList
|
{
|
{
|
Cyg_DNode *head; // list head pointer
|
Cyg_DNode *head; // list head pointer
|
|
|
public:
|
public:
|
|
|
Cyg_CList()
|
Cyg_CList()
|
{
|
{
|
head = NULL;
|
head = NULL;
|
};
|
};
|
|
|
// Accessor and test functions
|
// Accessor and test functions
|
Cyg_DNode *get_head() { return head; };
|
Cyg_DNode *get_head() { return head; };
|
Cyg_DNode *get_tail() { return head?head->prev:NULL; };
|
Cyg_DNode *get_tail() { return head?head->prev:NULL; };
|
cyg_bool empty() { return head == NULL; };
|
cyg_bool empty() { return head == NULL; };
|
|
|
// Add a node at the head of the list
|
// Add a node at the head of the list
|
void add_head( Cyg_DNode *node )
|
void add_head( Cyg_DNode *node )
|
{
|
{
|
if( head == NULL )
|
if( head == NULL )
|
head = node;
|
head = node;
|
else
|
else
|
{
|
{
|
head->insert( node );
|
head->insert( node );
|
head = node;
|
head = node;
|
}
|
}
|
};
|
};
|
|
|
// Remove the node at the head of the list
|
// Remove the node at the head of the list
|
Cyg_DNode *rem_head()
|
Cyg_DNode *rem_head()
|
{
|
{
|
Cyg_DNode *node = head;
|
Cyg_DNode *node = head;
|
if( node != NULL )
|
if( node != NULL )
|
{
|
{
|
// There is a node available
|
// There is a node available
|
Cyg_DNode *next = node->next;
|
Cyg_DNode *next = node->next;
|
if( next == node )
|
if( next == node )
|
{
|
{
|
// Only node on list
|
// Only node on list
|
head = NULL;
|
head = NULL;
|
}
|
}
|
else
|
else
|
{
|
{
|
// remove head node and move head to next.
|
// remove head node and move head to next.
|
node->unlink();
|
node->unlink();
|
head = next;
|
head = next;
|
}
|
}
|
}
|
}
|
return node;
|
return node;
|
};
|
};
|
|
|
|
|
// Add a node at the tail of the list
|
// Add a node at the tail of the list
|
void add_tail( Cyg_DNode *node )
|
void add_tail( Cyg_DNode *node )
|
{
|
{
|
if( head == NULL )
|
if( head == NULL )
|
head = node;
|
head = node;
|
else
|
else
|
head->insert( node );
|
head->insert( node );
|
};
|
};
|
|
|
// Remove the node at the tail of the list
|
// Remove the node at the tail of the list
|
Cyg_DNode *rem_tail()
|
Cyg_DNode *rem_tail()
|
{
|
{
|
if( head == NULL )
|
if( head == NULL )
|
return NULL;
|
return NULL;
|
|
|
Cyg_DNode *node = head->prev;
|
Cyg_DNode *node = head->prev;
|
|
|
if( node == head )
|
if( node == head )
|
head = NULL;
|
head = NULL;
|
else node->unlink();
|
else node->unlink();
|
|
|
return node;
|
return node;
|
};
|
};
|
|
|
// Merge the supplied list into this one, at the tail.
|
// Merge the supplied list into this one, at the tail.
|
void merge( Cyg_CList& list )
|
void merge( Cyg_CList& list )
|
{
|
{
|
if( list.head == NULL )
|
if( list.head == NULL )
|
return; // Nothing to do
|
return; // Nothing to do
|
else if( head == NULL )
|
else if( head == NULL )
|
head = list.head; // this is empty, just move it
|
head = list.head; // this is empty, just move it
|
else
|
else
|
{
|
{
|
// We have a real merge to do. Adjust the pointers
|
// We have a real merge to do. Adjust the pointers
|
// on the two lists so that they become one.
|
// on the two lists so that they become one.
|
|
|
Cyg_DNode *lh = list.head;
|
Cyg_DNode *lh = list.head;
|
Cyg_DNode *lt = lh->prev;
|
Cyg_DNode *lt = lh->prev;
|
Cyg_DNode *tail = head->prev;
|
Cyg_DNode *tail = head->prev;
|
|
|
head->prev = lt;
|
head->prev = lt;
|
lt->next = head;
|
lt->next = head;
|
tail->next = lh;
|
tail->next = lh;
|
lh->prev = tail;
|
lh->prev = tail;
|
}
|
}
|
list.head = NULL;
|
list.head = NULL;
|
};
|
};
|
|
|
// General removal. Deals with what happend if this is only
|
// General removal. Deals with what happend if this is only
|
// object on list, or is the head.
|
// object on list, or is the head.
|
void remove( Cyg_DNode *node )
|
void remove( Cyg_DNode *node )
|
{
|
{
|
if( node == head )
|
if( node == head )
|
rem_head();
|
rem_head();
|
else node->unlink();
|
else node->unlink();
|
};
|
};
|
|
|
// Rotation - move the head to the next node in the list.
|
// Rotation - move the head to the next node in the list.
|
void rotate()
|
void rotate()
|
{
|
{
|
if( head )
|
if( head )
|
head = head->next;
|
head = head->next;
|
};
|
};
|
|
|
// Move a node to the head of the list. Assumes that the
|
// Move a node to the head of the list. Assumes that the
|
// node is in this list.
|
// node is in this list.
|
void to_head( Cyg_DNode *node )
|
void to_head( Cyg_DNode *node )
|
{
|
{
|
head = node;
|
head = node;
|
};
|
};
|
|
|
// Insert a node before one in this list, and deal with what
|
// Insert a node before one in this list, and deal with what
|
// happens if the node happens to be at the head of the list.
|
// happens if the node happens to be at the head of the list.
|
void insert( Cyg_DNode *list_node, Cyg_DNode *node )
|
void insert( Cyg_DNode *list_node, Cyg_DNode *node )
|
{
|
{
|
if( list_node == head )
|
if( list_node == head )
|
{
|
{
|
head->insert( node );
|
head->insert( node );
|
head = node;
|
head = node;
|
}
|
}
|
else list_node->insert( node );
|
else list_node->insert( node );
|
};
|
};
|
|
|
~Cyg_CList()
|
~Cyg_CList()
|
{
|
{
|
while( head != NULL )
|
while( head != NULL )
|
rem_head();
|
rem_head();
|
};
|
};
|
|
|
};
|
};
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
// Cyg_CList_T
|
// Cyg_CList_T
|
// Template class that allows us to make use of the CList class in a
|
// Template class that allows us to make use of the CList class in a
|
// type-specific way.
|
// type-specific way.
|
|
|
template class Cyg_CList_T
|
template class Cyg_CList_T
|
: public Cyg_CList
|
: public Cyg_CList
|
{
|
{
|
public:
|
public:
|
|
|
Cyg_CList_T() {};
|
Cyg_CList_T() {};
|
~Cyg_CList_T() {};
|
~Cyg_CList_T() {};
|
|
|
T *get_head()
|
T *get_head()
|
{
|
{
|
Cyg_DNode *node = Cyg_CList::get_head();
|
Cyg_DNode *node = Cyg_CList::get_head();
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
return NULL;
|
return NULL;
|
};
|
};
|
T *get_tail()
|
T *get_tail()
|
{
|
{
|
Cyg_DNode *node = Cyg_CList::get_tail();
|
Cyg_DNode *node = Cyg_CList::get_tail();
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
return NULL;
|
return NULL;
|
};
|
};
|
|
|
T *rem_head()
|
T *rem_head()
|
{
|
{
|
Cyg_DNode *node = Cyg_CList::rem_head();
|
Cyg_DNode *node = Cyg_CList::rem_head();
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
return NULL;
|
return NULL;
|
};
|
};
|
|
|
T *rem_tail()
|
T *rem_tail()
|
{
|
{
|
Cyg_DNode *node = Cyg_CList::rem_tail();
|
Cyg_DNode *node = Cyg_CList::rem_tail();
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
if( node ) return CYG_CLASSFROMBASE( T, Cyg_DNode, node );
|
return NULL;
|
return NULL;
|
};
|
};
|
|
|
// The rest just default to the Cyg_CList class operations.
|
// The rest just default to the Cyg_CList class operations.
|
};
|
};
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
// Cyg_DNode_T
|
// Cyg_DNode_T
|
// Template class that allows us to make use of the DNode class in a
|
// Template class that allows us to make use of the DNode class in a
|
// type-specific way.
|
// type-specific way.
|
|
|
template class Cyg_DNode_T
|
template class Cyg_DNode_T
|
: public Cyg_DNode
|
: public Cyg_DNode
|
{
|
{
|
public:
|
public:
|
|
|
Cyg_DNode_T() {};
|
Cyg_DNode_T() {};
|
~Cyg_DNode_T() {};
|
~Cyg_DNode_T() {};
|
|
|
T *get_next() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_next() ); };
|
T *get_next() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_next() ); };
|
T *get_prev() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_prev() ); };
|
T *get_prev() { return CYG_CLASSFROMBASE( T, Cyg_DNode, Cyg_DNode::get_prev() ); };
|
|
|
// The rest just default to the Cyg_DNode class operations.
|
// The rest just default to the Cyg_DNode class operations.
|
};
|
};
|
|
|
// -------------------------------------------------------------------------
|
// -------------------------------------------------------------------------
|
#endif // CYGONCE_INFRA_CLIST_HXX multiple inclusion protection
|
#endif // CYGONCE_INFRA_CLIST_HXX multiple inclusion protection
|
// EOF clist.hxx
|
// EOF clist.hxx
|
|
|
|
|