00001 /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */ 00002 /* 00003 * Copyright (c) 1993 Regents of the University of California. 00004 * All rights reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 1. Redistributions of source code must retain the above copyright 00010 * notice, this list of conditions and the following disclaimer. 00011 * 2. Redistributions in binary form must reproduce the above copyright 00012 * notice, this list of conditions and the following disclaimer in the 00013 * documentation and/or other materials provided with the distribution. 00014 * 3. All advertising materials mentioning features or use of this software 00015 * must display the following acknowledgement: 00016 * This product includes software developed by the Computer Systems 00017 * Engineering Group at Lawrence Berkeley Laboratory. 00018 * 4. Neither the name of the University nor of the Laboratory may be used 00019 * to endorse or promote products derived from this software without 00020 * specific prior written permission. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00023 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00024 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00025 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00026 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00027 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00028 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00029 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00030 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00031 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00032 * SUCH DAMAGE. 00033 * 00034 * Author: 00035 * Mohit Talwar (mohit@catarina.usc.edu) 00036 * 00037 * $Header: /cvsroot/nsnam/ns-2/rap/raplist.h,v 1.4 2005/09/18 23:33:34 tomh Exp $ 00038 * 00039 * This is taken from UCB Nachos project 00040 * 00041 * list.h 00042 * Data structures to manage LISP-like lists. 00043 * 00044 * As in LISP, a list can contain any type of data structure 00045 * as an item on the list: IP addresses, pending interrupts etc. 00046 * That is why each item is a "void *", or in other words, 00047 * a "pointers to anything". 00048 */ 00049 00050 #ifndef RAPLIST_H 00051 #define RAPLIST_H 00052 00053 typedef void (*VoidFunctionPtr)(long arg); 00054 typedef int (*CompareFunction)(void *item, void *key); 00055 00056 // The following class defines a "List element" -- which is 00057 // used to keep track of one item on a List. It is equivalent to a 00058 // LISP cell, with a "car" ("next") pointing to the next element on the List, 00059 // and a "cdr" ("item") pointing to the item on the List. 00060 00061 class ListElement 00062 { 00063 public: 00064 ListElement(void *itemPtr, float sortKey); // initialize a List element 00065 00066 ListElement *next; // next element on List, 00067 // NULL if this is the last 00068 float key; // priority (+ve), for a sorted List 00069 // identification, for some 00070 void *item; // pointer to item on the List 00071 }; 00072 00073 // The following class defines a "List" -- a singly linked List of 00074 // List elements, each of which points to a single item on the List. 00075 // 00076 // By using the "Sorted" functions, the List can be kept in sorted 00077 // in increasing order by "key" in ListElement. 00078 00079 class List 00080 { 00081 public: 00082 List(); // Initialize the List 00083 ~List(); // Deallocate the List 00084 00085 void Prepend(void *item); // Put item at the beginning of the List 00086 void Append(void *item); // Put item at the end of the List 00087 void *Remove(); // Take item off the front of the List 00088 00089 void Mapcar(VoidFunctionPtr func); // Apply "func" to every element 00090 // on the List 00091 int IsEmpty(); // Is the List empty? 00092 int Size() {return size;} // Return the number of elements 00093 00094 // Routines to put/get items on/off List in order (sorted by key) 00095 void SortedInsert(void *item, float sortKey); // Put item into List 00096 void *SortedRemove(float *keyPtr); // Remove first item from List 00097 float MinKey(); // sortKey of item at front 00098 00099 // Routines to put/get items on/off a Set 00100 int SetInsert(void *key, CompareFunction eq); // Put key into set 00101 void *SetRemove(void *key, CompareFunction eq); // Remove key from set 00102 void *IsPresent(void *key, CompareFunction eq); // Is key there in set 00103 void Purge(void *key, CompareFunction eq, VoidFunctionPtr destroy); 00104 00105 private: 00106 ListElement *first; // Head of the List, NULL if List is empty 00107 ListElement *last; // Last element of List 00108 int size; // Number of elements in the List 00109 }; 00110 00111 #endif // RAPLIST_H