--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/reference/ocr-new/list.cc Thu May 18 23:12:51 2006 +0200
@@ -0,0 +1,348 @@
+// list.cc
+//
+// Routines to manage a singly-linked list of "things".
+//
+// A "ListElement" is allocated for each item to be put on the
+// list; it is de-allocated when the item is removed. This means
+// we don't need to keep a "next" pointer in every object we
+// want to put on a list.
+//
+// NOTE: Mutual exclusion must be provided by the caller.
+// If you want a synchronized list, you must use the routines
+// in synchlist.cc.
+//
+// Copyright (c) 1992-1993 The Regents of the University of California.
+// All rights reserved. See copyright.h for copyright notice and limitation
+// of liability and disclaimer of warranty provisions.
+
+
+#include "list.h"
+
+//----------------------------------------------------------------------
+// ListElement::ListElement
+// Initialize a list element, so it can be added somewhere on a list.
+//
+// "itemPtr" is the item to be put on the list. It can be a pointer
+// to anything.
+// "sortKey" is the priority of the item, if any.
+//----------------------------------------------------------------------
+
+ListElement::ListElement(void *itemPtr, int sortKey)
+{
+ item = itemPtr;
+ key = sortKey;
+ next = NULL; // assume we'll put it at the end of the list
+ previous = NULL;
+}
+
+//----------------------------------------------------------------------
+// List::List
+// Initialize a list, empty to start with.
+// Elements can now be added to the list.
+//----------------------------------------------------------------------
+
+List::List()
+{
+ first = last = NULL;
+ length = 0;
+}
+
+//----------------------------------------------------------------------
+// List::~List
+// Prepare a list for deallocation. If the list still contains any
+// ListElements, de-allocate them. However, note that we do *not*
+// de-allocate the "items" on the list -- this module allocates
+// and de-allocates the ListElements to keep track of each item,
+// but a given item may be on multiple lists, so we can't
+// de-allocate them here.
+//----------------------------------------------------------------------
+
+List::~List()
+{
+ while (Remove() != NULL)
+ ; // delete all the list elements
+}
+
+//----------------------------------------------------------------------
+// List::Append
+// Append an "item" to the end of the list.
+//
+// Allocate a ListElement to keep track of the item.
+// If the list is empty, then this will be the only element.
+// Otherwise, put it at the end.
+//
+// "item" is the thing to put on the list, it can be a pointer to
+// anything.
+//----------------------------------------------------------------------
+
+void
+List::Append(void *item)
+{
+ ListElement *element = new ListElement(item, 0);
+
+ if (IsEmpty()) { // list is empty
+ first = element;
+ last = element;
+ } else { // else put it after last
+ last->next = element;
+ element->previous = last;
+ last = element;
+ }
+ length++;
+}
+
+//----------------------------------------------------------------------
+// List::Prepend
+// Put an "item" on the front of the list.
+//
+// Allocate a ListElement to keep track of the item.
+// If the list is empty, then this will be the only element.
+// Otherwise, put it at the beginning.
+//
+// "item" is the thing to put on the list, it can be a pointer to
+// anything.
+//----------------------------------------------------------------------
+
+void
+List::Prepend(void *item)
+{
+ ListElement *element = new ListElement(item, 0);
+
+ if (IsEmpty()) { // list is empty
+ first = element;
+ last = element;
+ } else { // else put it before first
+ element->next = first;
+ first->previous = element;
+ first = element;
+ }
+ length++;
+}
+
+//----------------------------------------------------------------------
+// List::Remove
+// Remove the first "item" from the front of the list.
+//
+// Returns:
+// Pointer to removed item, NULL if nothing on the list.
+//----------------------------------------------------------------------
+
+void *
+List::Remove()
+{
+ return SortedRemove(NULL); // Same as SortedRemove, but ignore the key
+ length--;
+}
+
+//----------------------------------------------------------------------
+// List::Mapcar
+// Apply a function to each item on the list, by walking through
+// the list, one element at a time.
+//
+// Unlike LISP, this mapcar does not return anything!
+//
+// "func" is the procedure to apply to each element of the list.
+//----------------------------------------------------------------------
+
+void
+List::Mapcar(VoidFunctionPtr func)
+{
+ for (ListElement *ptr = first; ptr != NULL; ptr = ptr->next) {
+ (*func)((int)ptr->item);
+ }
+}
+
+//----------------------------------------------------------------------
+// List::IsEmpty
+// Returns TRUE if the list is empty (has no items).
+//----------------------------------------------------------------------
+
+bool
+List::IsEmpty()
+{
+ if (first == NULL)
+ return TRUE;
+ else
+ return FALSE;
+}
+
+//----------------------------------------------------------------------
+// List::SortedInsert
+// Insert an "item" into a list, so that the list elements are
+// sorted in increasing order by "sortKey".
+//
+// Allocate a ListElement to keep track of the item.
+// If the list is empty, then this will be the only element.
+// Otherwise, walk through the list, one element at a time,
+// to find where the new item should be placed.
+//
+// "item" is the thing to put on the list, it can be a pointer to
+// anything.
+// "sortKey" is the priority of the item.
+//----------------------------------------------------------------------
+
+void
+List::SortedInsert(void *item, int sortKey)
+{
+ ListElement *element = new ListElement(item, sortKey);
+ ListElement *ptr; // keep track
+
+ if (IsEmpty()) { // if list is empty, put
+ first = element;
+ last = element;
+ } else if (sortKey < first->key) {
+ // item goes on front of list
+ element->next = first;
+ first->previous = element;
+ first = element;
+ } else { // look for first elt in list bigger than item
+ for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
+ if (sortKey < ptr->next->key) {
+ element->next = ptr->next;
+ element->previous = ptr;
+ ptr->next->previous = element;
+ ptr->next = element;
+ return;
+ }
+ }
+ last->next = element; // item goes at end of list
+ element->previous = last;
+ last = element;
+ }
+ length++;
+}
+
+//----------------------------------------------------------------------
+// List::SortedRemove
+// Remove the first "item" from the front of a sorted list.
+//
+// Returns:
+// Pointer to removed item, NULL if nothing on the list.
+// Sets *keyPtr to the priority value of the removed item
+// (this is needed by interrupt.cc, for instance).
+//
+// "keyPtr" is a pointer to the location in which to store the
+// priority of the removed item.
+//----------------------------------------------------------------------
+
+void *
+List::SortedRemove(int *keyPtr)
+{
+ ListElement *element = first;
+ void *thing;
+
+ if (IsEmpty())
+ return NULL;
+
+ thing = first->item;
+ if (first == last) { // list had one item, now has none
+ first = NULL;
+ last = NULL;
+ } else {
+ first = element->next;
+ if (first != NULL)
+ first->previous = NULL;
+ }
+ if (keyPtr != NULL)
+ *keyPtr = element->key;
+ delete element;
+ length--;
+ return thing;
+}
+
+
+void * List::removeElement(void * item)
+ // find this item in list and remove it
+ // return item pointer or NULL
+{
+ for (ListElement * ptr = first; ptr!=NULL; ptr= ptr->next)
+ {
+ if (ptr->item == item)
+ {
+ removeAt(ptr);
+ return item;
+ }
+ }
+ return NULL;
+
+}
+
+void List::insertAfter(ListElement * listEl, void *item)
+ // insert a new item after this one
+{
+ ListElement *newElement = new ListElement(item, 0);
+ newElement->next = listEl->next;
+ newElement->previous = listEl;
+ listEl->next = newElement;
+ if (last == listEl)
+ last = newElement;
+ length++;
+}
+
+
+void List::insertBefore(ListElement * listEl, void *item)
+ // insert a new item before this one
+{
+ ListElement *newElement = new ListElement(item, 0);
+ newElement->next = listEl;
+ newElement->previous = listEl->previous;
+ listEl->previous = newElement;
+ if (first == listEl)
+ first = newElement;
+ length++;
+}
+
+
+
+void List::removeAt(ListElement * listEl)
+ // removes listEl from the list. Do not delete it from memory
+{
+ if(first != listEl)
+ {
+ (listEl->previous)->next = listEl->next;
+ }
+ else
+ {
+ first = listEl->next;
+ }
+ if(last != listEl)
+ (listEl->next)->previous = listEl->previous;
+ else
+ last = listEl->previous;
+
+ if (first != NULL) first->previous = NULL;
+ if (last != NULL) last->next = NULL;
+
+
+ delete listEl;
+ length --;
+}
+
+
+
+void List::printList()
+{
+ int i=0;
+ printf("length= %d first = %u last = %u\n", length, first, last);
+ for(ListElement * ptr = first; ptr != NULL; ptr=ptr->next)
+ {
+ if ((i++%3) == 0) printf("\n");
+ printf(" ( %u, %u, %u ) ", ptr->previous, ptr, ptr->next);
+ }
+ printf("\n");
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+