sam-t2/sam/devices/common/regdef/include/List.h

/*
* ========== 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 ============================================
*/
#ifndef __List_h
#define __List_h

#include <iostream>
#include <stdlib.h>
#include "Link.h"
using namespace std;

/** @file List.h
 *  List is a template class that allows instances of some class T
 *  to be held on a doubly-linked list.
 *
 *  @sa List_Module
 */

/** @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>;

public:
  /** Constructor for List<T>. */
  List();
  ~List();

  /** 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. */
  T *removeHead();

  /** Remove an item from the tail of the list.
   *  NULL is returned if the list is empty. */
  T *removeTail();

  /** 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);

private:
  Link<T> *head;
  Link<T> *tail;
  uint length;
};

/** ListIterator<T> is used to iterate through the items held on a List. */

template<class T> class ListIterator
{
public:
  /** 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
   *  are available.
   */
  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. */
  T *getNextItem();

  /** Get the previous item, and set the current position of the
   *  iterator to that item. */
  T *getPrevItem();

  /** 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. */
  Link<T> *getNextLink();

  /** Get the previous link, and set the current position of the
   *  iterator to that link. */
  Link<T> *getPrevLink();

private:
  List<T> *list;
  Link<T> *link;
};

/** @} */

#include "pList.h"

#endif