* ========== Copyright Header Begin ==========================================
* OpenSPARC T2 Processor File: List.h
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
* The above named program is distributed in the hope that it will be
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
* You should have received a copy of the GNU General Public
* License along with this work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
* ========== Copyright Header End ============================================
* List is a template class that allows instances of some class T
* to be held on a doubly-linked list.
/** @defgroup List_Module The List Module
* List is a template class that allows instances of some class T
* to be held on a doubly-linked list. The design of the
* List class is closely related to that of the Link class. Further
* discussion can be found in the description for Link.h. The list
* uses the standard terminology of "head" and "tail" to refer to items
* at the ends of the list. The "next" pointers point towards the
* tail end, while the "previous" pointers point towards the head end.
* There are several key choices made here:
* - the use of template classes ensures that Link/List can be defined
* with no knowledge of the class that will be referenced by the
* Link/List. This is achieved without compromising type safety: there
* are no pointer casts involved.
* - instances of the Link are allocated using new/delete from the
* heap. The Link is not allocated in the state of the items that
* are being held on the linked list. This means the items do not
* need to derive from Link, nor contain Link instances. It also
* means that items can be held on multiple lists simultaneously,
* or even held in multiple places on one list at the same time.
* This is a significant reduction in complexity for the programmer.
* The use of new/delete creates a potential performance penalty.
* In general use, though, links and lists are used in the simulator
* infrastructure and this is not performance critical. Different
* structures with known bounded size (like a Buffer, Fifo, Queue
* or Stack) are more commonly used to model the system and are usually
* more critical for performance. However, if necessary the Link class
* can be extended to accelerate Link allocation and deallocation by
* overriding the new and delete operators for Link. This allows the
* Links to be allocated "en masse" and held in a freelist (using the
* Link state to hold itself on the freelist!) for efficient reallocation.
* - typically, there is no pointer from an item back to its link. This
* makes it more difficult to find an item's position in the list
* (e.g. to remove an item in the middle of a list). In some cases
* this operation is rare enough that a search through the list suffices.
* Alternatively, an item could provide and manage a suitable Link
* pointer in its own implementation. This approach is supported by the
* List::addHead() and List::addTail() methods by returning a pointer
* to the allocated link. Additionally, there is a List::removeLink()
* method that can remove any item in the list given its associated link
template<class T
> class ListIterator
; // forward reference
/** List<T> provides a doubly-linked list of items of
* type T. The link elements of the list are provided by Link<T>.
template<class T
> class List
friend class ListIterator
<T
>;
/** Constructor for List<T>. */
/** Add an item to the head of the list.
* @param newItem the item to be added to the list.
* @result a pointer to the link allocated to hold this item on the list.
* The link value should be retained by the caller if there is a need
* to remove arbitrary items from the list or insert at arbitrary points
* in the list (i.e. not just at the head or tail ends).
Link
<T
> *addHead(T
*newItem
);
/** Add an item to the tail of the list.
* @param newItem the item to be added to the list.
* @result a pointer to the link allocated to hold this item on the list.
* The link value should be retained by the caller if there is a need
* to remove arbitrary items from the list or insert at arbitrary points
* in the list (i.e. not just at the head or tail ends).
Link
<T
> *addTail(T
*newItem
);
/** Add an item before the specified link in the list.
* @param link the link before which the new item will be added.
* @param newItem the item to be added to the list.
* @result a pointer to the link allocated to hold this item on the list.
* The link value should be retained by the caller if there is a need
* to remove arbitrary items from the list or insert at arbitrary points
* in the list (i.e. not just at the head or tail ends).
Link
<T
> *addBefore(Link
<T
> *link
, T
*newItem
);
/** Add an item after the specified link in the list.
* @param link the link after which the new item will be added.
* @param newItem the item to be added to the list.
* @result a pointer to the link allocated to hold this item on the list.
* The link value should be retained by the caller if there is a need
* to remove arbitrary items from the list or insert at arbitrary points
* in the list (i.e. not just at the head or tail ends).
Link
<T
> *addAfter(Link
<T
> *link
, T
*newItem
);
/** Get an item from the head of the list, but do not remove it.
* NULL is returned if the list is empty. */
inline T
*getHead() { return (head
) ? head
->item
: NULL
; }
/** Get an item from the tail of the list, but do not remove it.
* NULL is returned if the list is empty. */
inline T
*getTail() { return (tail
) ? tail
->item
: NULL
; }
/** Get an arbitrary item from the list given its link pointer,
* but do not remove it. The return value is a pointer to the
* item corresponding to the link and is never NULL. */
inline T
*getItem(Link
<T
> *link
) { assert(link
!= NULL
); return link
->item
; }
/** Remove an item from the head of the list.
* NULL is returned if the list is empty. */
/** Remove an item from the tail of the list.
* NULL is returned if the list is empty. */
/** Remove an arbitrary item from the list given its link pointer. This
* method returns a pointer to the removed item (which is never NULL). */
T
*removeItem(Link
<T
> *link
);
/** Get the length of the list. */
inline uint
getLength() { return length
; }
/** Return true if the list is empty, otherwise false. */
inline bool isEmpty() { return (length
== 0); }
/** Return true if the list is not empty, otherwise false. */
inline bool isReady() { return (length
> 0); }
/** Print the list to the specified output stream. */
void printThis(ostream
&os
);
/** ListIterator<T> is used to iterate through the items held on a List. */
template<class T
> class ListIterator
/** Constructor for ListIterator<T>.
* @param l a pointer to the list to be iterated over.
* Initially the iterator is set to the head of the list,
* ready to walk the list from head to tail. A variety
* of methods are provided to move the current position
* and to return pointers to links and pointers to items.
* These methods return NULL when no more links or items
ListIterator(List
<T
> *l
) { list
= l
; link
= list
->head
; }
/** Get a pointer to the item at the head of the list, and
* set the current position of the iterator to that item. */
inline T
*getHeadItem() { link
= list
->head
; return getThisItem(); }
/** Get a pointer to the item at the tail of the list, and
* set the current position of the iterator to that item. */
inline T
*getTailItem() { link
= list
->tail
; return getThisItem(); }
/** Get a pointer to the item at the current position of the iterator. */
inline T
*getThisItem() { return (link
) ? link
->item
: NULL
; }
/** Get the next item, and set the current position of the
* iterator to that item. */
/** Get the previous item, and set the current position of the
* iterator to that item. */
/** Get a pointer to the link at the head of the list, and
* set the current position of the iterator to that link. */
inline Link
<T
> *getHeadLink() { link
= list
->head
; return link
; }
/** Get a pointer to the link at the tail of the list, and
* set the current position of the iterator to that link. */
inline Link
<T
> *getTailLink() { link
= list
->tail
; return link
; }
/** Get a pointer to the link at the current position of the iterator. */
inline Link
<T
> *getThisLink() { return link
; }
/** Get the next link, and set the current position of the
* iterator to that link. */
/** Get the previous link, and set the current position of the
* iterator to that link. */