contrib/psg/src/peersim/edsim/Heap.java

   1 /*
   2  * Copyright (c) 2001 The Anthill Team
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.edsim;
  20
  21 import peersim.core.Node;
  22 import peersim.core.CommonState;
  23 import peersim.config.Configuration;
  24 import peersim.config.IllegalParameterException;
  25
  26 /**
  27  *  The Heap data structure used to maintain events "sorted" by
  28  *  scheduled time and to obtain the next event to be executed.
  29  *
  30  *  @author Alberto Montresor
  31  *  @version $Revision: 1.10 $
  32  */
  33 public class Heap implements PriorityQ {
  34
  35 //--------------------------------------------------------------------------
  36 // Constants
  37 //--------------------------------------------------------------------------
  38
  39 /**
  40  * This parameter specifies how many
  41  * bits are used to order events that occur at the same time. Defaults
  42  * to 8. A value smaller than 8 causes an IllegalParameterException.
  43  * Higher values allow for a better discrimination, but reduce
  44  * the maximal time steps that can be simulated.
  45  * @config
  46  */
  47 private static final String PAR_PBITS = "pbits";
  48 private static final String PAR_PBITS_LEGACY = "simulation.timebits";
  49
  50 /**
  51  * Specifies the initial capacity of the heap. Defaults to 65536.
  52  * @config
  53  */
  54 private static final String PAR_SIZE = "size";
  55
  56
  57 //--------------------------------------------------------------------------
  58 // Fields
  59 //--------------------------------------------------------------------------
  60
  61 // The following arrays are four heaps ordered by time. The alternative
  62 // approach (i.e. to store event objects) requires much more memory,
  63 // and based on some tests that I've done is not really much faster.
  64
  65 /** Event component of the heap */
  66 private Object[] events;
  67
  68 /** Time component of the heap */
  69 private long[] times;
  70
  71 /** Node component of the heap */
  72 private Node[] nodes;
  73
  74 /** Pid component of the heap */
  75 private byte[] pids;
  76
  77 /** Number of elements */
  78 private int size;
  79
  80 /** Singleton event object used to return (event, time, node, pid) tuples */
  81 private final Event ev = new Event();
  82
  83 /** The number of bits reserved to order event with the same timestamp */
  84 private final int pbits;
  85
  86 /** The mask to test whether the time value fits into the range we can
  87 represent */
  88 private final long overflowMask;
  89
  90 //--------------------------------------------------------------------------
  91 // Contructor
  92 //--------------------------------------------------------------------------
  93
  94 /**
  95  * Initializes a new heap using defaults.
  96  */
  97 public Heap() {
  98         this(""); // "" is not a valid prefix for a component
  99 }
 100
 101 //--------------------------------------------------------------------------
 102
 103 /**
 104  * Initializes a new heap using the configuration.
 105  */
 106 public Heap(String prefix) {
 107
 108         int size = Configuration.getInt(prefix+"."+PAR_SIZE,65536);
 109
 110         // some complex stuff to deal with legacy parameter names...
 111         if( !Configuration.contains(PAR_PBITS_LEGACY) )
 112                 pbits = Configuration.getInt(prefix+"."+PAR_PBITS,8);
 113         else
 114         {
 115                 pbits = Configuration.getInt(PAR_PBITS_LEGACY);
 116                 if( Configuration.contains(prefix+"."+PAR_PBITS) )
 117                         throw new IllegalParameterException(PAR_PBITS_LEGACY,
 118                                 "Your configuration file contains both "+
 119                                 prefix+"."+PAR_PBITS+ " and "+
 120                                 PAR_PBITS_LEGACY+"; please remove "+
 121                                 PAR_PBITS_LEGACY);
 122         }
 123
 124         if (pbits < 8 || pbits >= 31) {
 125                 throw new IllegalParameterException(prefix+"."+PAR_PBITS,
 126                 "This parameter should be >= 8 or < 31");
 127         }
 128         overflowMask = ~maxTime();
 129         events = new Object[size];
 130         times = new long[size];
 131         nodes = new Node[size];
 132         pids = new byte[size];
 133 }
 134
 135 //--------------------------------------------------------------------------
 136 // Methods
 137 //--------------------------------------------------------------------------
 138
 139 /**
 140  * Returns the current number of events in the system.
 141  */
 142 public int size()
 143 {
 144         return size;
 145 }
 146
 147 //--------------------------------------------------------------------------
 148
 149 /**
 150  * Add a new event, to be scheduled at the specified time.
 151  *
 152  * @param time the time at which this event should be scheduled
 153  * @param event the object describing the event
 154  * @param node the node at which the event has to be delivered
 155  * @param pid the protocol that handles the event
 156  */
 157 public void add(long time, Object event, Node node, byte pid)
 158 {
 159         add(time,event,node,pid,CommonState.r.nextInt(1 << pbits));
 160 }
 161
 162 //--------------------------------------------------------------------------
 163
 164 /**
 165  * Add a new event, to be scheduled at the specified time.
 166  *
 167  * @param time the time at which this event should be scheduled
 168  * @param event the object describing the event
 169  * @param node the node at which the event has to be delivered
 170  * @param pid the protocol that handles the event
 171  */
 172 public void add(long time, Object event, Node node, byte pid, long priority)
 173 {
 174         if( (time&overflowMask) != 0 ) throw new
 175                 IllegalArgumentException("Time overflow: time="+time);
 176 //XXX should we test priority overflow? How much does it cost?
 177
 178         time = (time << pbits) | priority;
 179
 180         size++;
 181         int pos = size;
 182         put(pos, time, event, node, pid);
 183         while (pos > 1 && getTime(pos / 2) > time) {
 184                 swap(pos, pos / 2);
 185                 pos = pos / 2;
 186         }
 187 }
 188
 189 //--------------------------------------------------------------------------
 190
 191 /**
 192  * Removes the first event in the heap and returns it.
 193  * Note that, to avoid garbage collection, a singleton instance of
 194  * the Event class is used. This means that data contained in the
 195  * returned event are overwritten when a new invocation of this
 196  * method is performed.
 197  * @return first event or null if size is zero
 198  */
 199 public Event removeFirst() {
 200
 201         if(size==0) return null;
 202
 203         ev.time = times[0] >> pbits;
 204         ev.event = events[0];
 205         ev.node = nodes[0];
 206         ev.pid = pids[0];
 207         swap(1, size);
 208         size--;
 209         minHeapify(1);
 210         return ev;
 211 }
 212
 213 //--------------------------------------------------------------------------
 214
 215 public long maxTime() { return Long.MAX_VALUE >> pbits; }
 216
 217 //--------------------------------------------------------------------------
 218
 219 public long maxPriority() { return (1L << pbits)-1; }
 220
 221 //--------------------------------------------------------------------------
 222
 223 /**
 224  *  Prints the time values contained in the heap.
 225  */
 226 public String toString()
 227 {
 228         StringBuffer buffer = new StringBuffer();
 229         buffer.append("[Size: " + size + " Times: ");
 230         for (int i=1; i <= size; i++) {
 231                 buffer.append(getTime(i)+",");
 232         }
 233         buffer.append("]");
 234         return buffer.toString();
 235 }
 236
 237
 238 //--------------------------------------------------------------------------
 239 // Private methods
 240 //--------------------------------------------------------------------------
 241
 242 /**
 243  *
 244  */
 245 private void minHeapify(int index)
 246 {
 247         // The time to be placed of the current node
 248         long time = getTime(index);
 249         // Left, right children of the current index
 250         int l,r;
 251         // Their associated time
 252         long lt, rt;
 253         // The minimum time between val, lt, rt
 254         long mintime;
 255         // The index of the mininum time
 256         int minindex = index;
 257         do {
 258                 index = minindex;
 259                 mintime = time;
 260                 l = index << 1;
 261                 r = l + 1;
 262                 if (l <= size && (lt = getTime(l)) < mintime) {
 263                         minindex = l;
 264                         mintime = lt;
 265                 }
 266                 if (r <= size && (rt = getTime(r)) < mintime) {
 267                         minindex = r;
 268                         mintime = rt;
 269                 }
 270                 if (minindex != index) {
 271                         swap(minindex, index);
 272                 }
 273         } while (minindex != index);
 274 }
 275
 276 //--------------------------------------------------------------------------
 277
 278 /**
 279  *
 280  */
 281 private void swap(int i1, int i2) {
 282
 283         i1--;
 284         i2--;
 285
 286         Object te = events[i1];
 287         events[i1] = events[i2];
 288         events[i2] = te;
 289
 290         long tt = times[i1];
 291         times[i1] = times[i2];
 292         times[i2] = tt;
 293
 294         Node tn = nodes[i1];
 295         nodes[i1] = nodes[i2];
 296         nodes[i2] = tn;
 297
 298         byte tp = pids[i1];
 299         pids[i1] = pids[i2];
 300         pids[i2] = tp;
 301 }
 302
 303 //--------------------------------------------------------------------------
 304
 305 /**
 306  *
 307  */
 308 private long getTime(int index) {
 309         /* Compute first and second index, and return the value */
 310         index--;
 311         return times[index];
 312 }
 313
 314 //--------------------------------------------------------------------------
 315
 316 /**
 317  *
 318  */
 319 private void put(int index, long time, Object event, Node node, byte pid) {
 320
 321         index--;
 322         if (index >= events.length) {
 323                 doubleCapacity();
 324         }
 325         events[index] = event;
 326         times[index] = time;
 327         nodes[index] = node;
 328         pids[index] = pid;
 329 }
 330
 331 //--------------------------------------------------------------------------
 332
 333 /**
 334  *
 335  */
 336 private void doubleCapacity() {
 337         int oldsize = events.length;
 338         int newsize = oldsize*2;
 339         Object[] te = new Object[newsize];
 340         System.arraycopy(events, 0, te, 0, oldsize);
 341         events = te;
 342         long[] tt = new long[newsize];
 343         System.arraycopy(times, 0, tt, 0, oldsize);
 344         times = tt;
 345         Node[] tn = new Node[newsize];
 346         System.arraycopy(nodes, 0, tn, 0, oldsize);
 347         nodes = tn;
 348         byte[] tp = new byte[newsize];
 349         System.arraycopy(pids, 0, tp, 0, oldsize);
 350         pids = tp;
 351 }
 352
 353 //--------------------------------------------------------------------------
 354 // Testing
 355 //--------------------------------------------------------------------------
 356
 357 /*
 358 public static void main(String[] args) {
 359         Random random = new Random();
 360         Heap heap = new Heap();
 361         int rep = 1000000;
 362         if( args.length > 0 ) rep = Integer.parseInt(args[0]);
 363         int[] values1 = new int[rep];
 364         long[] values2 = new long[rep];
 365         for (int i = 0; i < rep; i++) {
 366                 values1[i] = random.nextInt(1000000000);
 367         }
 368
 369         long time1 = System.currentTimeMillis();
 370         for (int i = 0; i < rep; i++) {
 371                 heap.add(values1[i], null, null, (byte) 1);
 372         }
 373         long time2 = System.currentTimeMillis();
 374         System.out.println("Inserting: " + (time2-time1));
 375
 376         time1 = System.currentTimeMillis();
 377         for (int i = 0; i < rep; i++) {
 378                 values2[i] = heap.removeFirst().time;
 379         }
 380         time2 = System.currentTimeMillis();
 381         System.out.println("Removing: " + (time2-time1));
 382
 383         Arrays.sort(values1);
 384         for (int i=0; i<rep; i++) {
 385                 if (values1[i] != values2[i])
 386                         System.out.print("+");
 387         }
 388 }
 389 */
 390
 391 } // END Heap