00001 /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */ 00002 00003 /* 00004 * Copyright (C) 1997 by the University of Southern California 00005 * $Id: heap.h,v 1.9 2005/08/25 18:58:02 johnh Exp $ 00006 * 00007 * This program is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU General Public License, 00009 * version 2, as published by the Free Software Foundation. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License along 00017 * with this program; if not, write to the Free Software Foundation, Inc., 00018 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA. 00019 * 00020 * 00021 * The copyright of this module includes the following 00022 * linking-with-specific-other-licenses addition: 00023 * 00024 * In addition, as a special exception, the copyright holders of 00025 * this module give you permission to combine (via static or 00026 * dynamic linking) this module with free software programs or 00027 * libraries that are released under the GNU LGPL and with code 00028 * included in the standard release of ns-2 under the Apache 2.0 00029 * license or under otherwise-compatible licenses with advertising 00030 * requirements (or modified versions of such code, with unchanged 00031 * license). You may copy and distribute such a system following the 00032 * terms of the GNU GPL for this module and the licenses of the 00033 * other code concerned, provided that you include the source code of 00034 * that other code when and as the GNU GPL requires distribution of 00035 * source code. 00036 * 00037 * Note that people who make modified versions of this module 00038 * are not obligated to grant this special exception for their 00039 * modified versions; it is their choice whether to do so. The GNU 00040 * General Public License gives permission to release a modified 00041 * version without this exception; this exception also makes it 00042 * possible to release a modified version which carries forward this 00043 * exception. 00044 * 00045 */ 00046 00047 /* 00048 * @(#) $Header: /cvsroot/nsnam/ns-2/common/heap.h,v 1.9 2005/08/25 18:58:02 johnh Exp $ (USC/ISI) 00049 */ 00050 00051 #ifndef ns_heap_h 00052 #define ns_heap_h 00053 00054 #define HEAP_DEFAULT_SIZE 32 00055 00056 // This code has a long and rich history. It was stolen from the MaRS-2.0 00057 // distribution, that had in its turn acquired it from the NetSim 00058 // distribution (or so I have been told). It has been customised for 00059 // event queue handling. I, Kannan, added prolific comments to it in order 00060 // to better understand the data structure for myself, and turned into 00061 // a standalone C++ class that you see in this version now. 00062 00063 typedef double heap_key_t; 00064 typedef unsigned long heap_secondary_key_t; 00065 00066 // This code has (atleast?) one flaw: It does not check for memory allocated, 00067 // especially in the constructor, and in heap_insert() when trying 00068 // to resize the h_elems[] array. 00069 00070 class Heap 00071 { 00072 struct Heap_elem { 00073 heap_key_t he_key; 00074 heap_secondary_key_t he_s_key; 00075 void* he_elem; 00076 } *h_elems; 00077 unsigned int h_s_key; 00078 unsigned int h_size; 00079 unsigned int h_maxsize; 00080 unsigned int h_iter; 00081 00082 unsigned int parent(unsigned int i) { return ((i - 1) / 2); } 00083 unsigned int left(unsigned int i) { return ((i * 2) + 1); } 00084 unsigned int right(unsigned int i) { return ((i + 1) * 2); } 00085 void swap(unsigned int i, unsigned int j) { 00086 // swap elems[i] with elems[j] in this 00087 Heap_elem __he = h_elems[i]; 00088 h_elems[i] = h_elems[j]; 00089 h_elems[j] = __he; 00090 return; 00091 }; 00092 unsigned int KEY_LESS_THAN(heap_key_t k1, heap_secondary_key_t ks1, 00093 heap_key_t k2, heap_secondary_key_t ks2) { 00094 return (k1 < k2) || ((k1==k2)&&(ks1<ks2)); 00095 }; 00096 unsigned int KEY_LESS_OR_EQUAL_THAN(heap_key_t k1, heap_key_t k2) { 00097 return (k1 <= k2); 00098 }; 00099 00100 public: 00101 Heap(int size=HEAP_DEFAULT_SIZE); 00102 ~Heap(); 00103 00104 /* 00105 * int heap_member(Heap *h, void *elem): O(n) algorithm. 00106 */ 00107 int heap_member(void* elem); 00108 00109 /* 00110 * int heap_delete(Heap *h, void *elem): O(n) algorithm 00111 * 00112 * Returns 1 for success, 0 otherwise. 00113 */ 00114 int heap_delete(void* elem); 00115 00116 /* 00117 * Couple of functions to support iterating through all things on the 00118 * heap without having to know what a heap looks like. To be used as 00119 * follows: 00120 * 00121 * for (elem = heap_iter_init(h); elem; elem = heap_iter(h)) 00122 * Do whatever to the elem. 00123 * 00124 * You cannot use heap_iter to do anything but inspect the heap. If 00125 * heap_insert(), heap_extract_min(), or heap_delete() are called 00126 * while iterating through the heap, all bets are off. 00127 * 00128 * Tue Nov 14 20:17:59 PST 1995 -- kva 00129 * Actually now, heap_create() initialises h_iter correctly, 00130 * and heap_iter() correctly resets h_iter 00131 * when the heap is traversed, So, we do not really need 00132 * heap_iter_init() anymore, except to break off a current 00133 * iteration and restart. 00134 */ 00135 void* heap_iter_init() { 00136 h_iter = 1; 00137 return heap_min(); 00138 }; 00139 void* heap_iter() { 00140 if (h_iter >= h_size) { 00141 h_iter = 0; 00142 return 0; 00143 } else { 00144 return h_elems[h_iter++].he_elem; 00145 } 00146 }; 00147 00148 /* 00149 * void heap_insert(Heap *h, heap_key_t *key, void *elem) 00150 * 00151 * Insert <key, elem> into heap h. 00152 * Adjust heap_size if we hit the limit. 00153 */ 00154 void heap_insert(heap_key_t key, void* elem); 00155 00156 /* 00157 * void *heap_min(Heap *h) 00158 * 00159 * Returns the smallest element in the heap, if it exists, 00160 * NULL otherwise. The element is still in the heap. 00161 */ 00162 void* heap_min() { 00163 return (h_size > 0 ? h_elems[0].he_elem : 0); 00164 }; 00165 00166 /* 00167 * void *heap_extract_min(Heap *h) 00168 * 00169 * Returns the smallest element in the heap, if it exists. 00170 * NULL otherwise. 00171 */ 00172 void* heap_extract_min(); 00173 }; 00174 00175 #endif /* ns_heap_h */ 00176 00177 00178 00179 00180 00181