source: vis_dev/vis-2.3/src/truesim/truesimMain.c @ 14

Last change on this file since 14 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 25.9 KB
RevLine 
[14]1/**CFile***********************************************************************
2
3  FileName    [truesimMain.c]
4
5  PackageName [truesim]
6
7  Synopsis    [Routines to perform full delay simulation.]
8
9  Descriptin [Routines to perform full delay simulation. The main routine
10  implements a levelized two-pass event driven simulator.]
11
12  Author      [Balakrishna Kumthekar]
13
14  Copyright   [This file was created at the University of Colorado at Boulder.
15  The University of Colorado at Boulder makes no warranty about the suitability
16  of this software for any purpose.  It is presented on an AS IS basis.]
17
18******************************************************************************/
19
20#include "truesimInt.h"
21
22/*---------------------------------------------------------------------------*/
23/* Constant declarations                                                     */
24/*---------------------------------------------------------------------------*/
25
26
27/*---------------------------------------------------------------------------*/
28/* Type declarations                                                         */
29/*---------------------------------------------------------------------------*/
30
31
32/*---------------------------------------------------------------------------*/
33/* Structure declarations                                                    */
34/*---------------------------------------------------------------------------*/
35
36
37/*---------------------------------------------------------------------------*/
38/* Variable declarations                                                     */
39/*---------------------------------------------------------------------------*/
40
41static long numEvents;
42
43extern int truesimVerbose;
44extern int truesimRptHeader;
45
46/*---------------------------------------------------------------------------*/
47/* Macro declarations                                                        */
48/*---------------------------------------------------------------------------*/
49
50/**AutomaticStart*************************************************************/
51
52/*---------------------------------------------------------------------------*/
53/* Static function prototypes                                                */
54/*---------------------------------------------------------------------------*/
55
56static void InsertInputEvents(st_table *nodeToSimTable, EventQueue *queue, array_t *inputArray, char *vector);
57static void SinglePatternSimulate(Ntk_Network_t *network, EventQueue *queue);
58static void HouseKeeping(EventQueue *queue, Event *threshevent);
59static void InsertFanouts(Ntk_Node_t *node, st_table *fanoutTable);
60static void PerformSecondPass(Ntk_Network_t *network, EventQueue *queue, st_table *fanoutTable);
61static void ScheduleEvent(EventQueue *queue, Ntk_Node_t *node, TrueSim_t *sim, char value);
62static void RescheduleEvent(EventQueue *queue, Ntk_Node_t *node, TrueSim_t *sim, char value);
63static void CancelEvent(EventQueue *queue, TrueSim_t *sim);
64static void InsertInBin(Event **wheel, Event *event);
65static EventQueue * InitQueue(void);
66static void NewPage(EventQueue *queue);
67static enum st_retval stTrueSimFree(char *key, char *value, char *arg);
68
69/**AutomaticEnd***************************************************************/
70
71
72/*---------------------------------------------------------------------------*/
73/* Definition of exported functions                                          */
74/*---------------------------------------------------------------------------*/
75
76/**Function********************************************************************
77
78  Synopsis [This routine performs real delay pattern simulation.]
79
80  Description [This routine performs real delay pattern simulation. inputArray
81  is an array of PI names. patternArray is a character array of pattern
82  vectors. Pattern vectors are 0-1 bit-vectors whose length is equal to the
83  number of primary inputs of the circuit. The length of inpuArray and
84  patternArray should be equal.
85 
86  Successive patterns are applied to the circuit after the changes due
87  to a previous pattern vector settle down. ]
88
89  SideEffects [Simulation data structure associated with each network node is
90  changed.]
91
92  SeeAlso [Truesim_ZeroDelayPatternSimulate]
93
94******************************************************************************/
95int
96Truesim_RealDelayPatternSimulate(
97  Ntk_Network_t *network,
98  array_t *inputArray,
99  array_t *patternArray)
100{
101  Ntk_Node_t *node;
102  int numVectors = array_n(patternArray);
103  int i;
104  EventQueue *queue;
105  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
106  lsGen gen;
107
108  if (nodeToSimTable == NIL(st_table)) {
109    (void) fprintf(vis_stderr,
110                   "** truesim error: Simulation structures not initialized\n");
111    (void) fprintf(vis_stderr,
112                   "** truesim error: Call Truesim_InitializeSimulation before ");
113    (void) fprintf(vis_stderr,"calling this function.\n");
114    return -1;
115  }
116
117  /* Initialize the converging list data structure */
118  queue = InitQueue();
119
120  /* Initialize node simulation data structures */
121  TruesimInitializeActivityFields(network,nodeToSimTable);
122
123  /* Warmup simulation. Simulate the first vector to initialize internal nodes
124     in the network. */
125  TruesimWarmUpPatternSimulate(network,inputArray,
126                               array_fetch(char *,patternArray,0));
127 
128  /* Performs simulation of all the vectors */
129  for (i = 1; i < numVectors; i++) {
130    char *stimulus;
131    stimulus = array_fetch(char *,patternArray,i);
132    InsertInputEvents(nodeToSimTable,queue,inputArray,stimulus);
133    SinglePatternSimulate(network,queue);
134
135    if (truesimVerbose) {
136      if (truesimRptHeader != -1) {
137        if (i % truesimRptHeader == 0) 
138          TruesimPrintNameHeader(network);
139      }
140      TruesimPrintNetworkNodeLogicState(network);
141    }
142  }
143
144  /* Free the queue */
145  if (queue != NIL(EventQueue)) {
146    while (queue->freeList != NIL(Event *)) {
147      Event **next;
148      next = (Event **) queue->freeList[0];
149      FREE(queue->freeList);
150      queue->freeList = next;
151    }
152    FREE(queue->wheel);
153    FREE(queue);
154  }
155 
156  /* Update the statistics for each node */
157  Ntk_NetworkForEachNode(network,gen,node) {
158    TrueSim_t *sim;
159    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
160      (void) fprintf(vis_stderr,
161                     "** truesim fatal:In Truesim_RealDelayPatternSimulate\n");
162      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
163                     Ntk_NodeReadName(node));
164     
165      assert(0);
166    }
167    /* Get the switching probability and the signal probability */
168    sim->switching /= ((float) array_n(patternArray));
169    sim->prob /= ((float) array_n(patternArray));
170  }
171
172  return 1;
173
174} /* End of Truesim_RealDelayPatternSimulate */
175
176
177/**Function********************************************************************
178
179  Synopsis [Initialize the info structure associated with truesim package.]
180
181  Description [Initialize the info structure associated with truesim
182  package. Every 'header' number of patterns simulated, a line
183  containing PI and PO names are output. In the absence of delay value
184  for a node (from nodeDelayTable or the delayFile), the fanout
185  count is used as the default delay value. Arrival times for PI are
186  assumed to be 0.
187
188  Simulation assumes that each node in the network has a local bdd associated
189  with it in the partition. This can be ensured by using 'total' as the
190  partition method.]
191
192  SideEffects [The info data structure is hooked to the network.]
193
194  SeeAlso [Truesim_QuitSimulation]
195
196******************************************************************************/
197void
198Truesim_InitializeSimulation(
199  Ntk_Network_t *network,
200  char *delayFile,
201  boolean truedelay,
202  int header,
203  int verbose,
204  st_table *nodeDelayTable)
205{
206  Truesim_Info_t *simInfo;
207  st_table *nodeToSimTable;
208  lsGen gen;
209  Ntk_Node_t *node;
210  TrueSim_t *sim;
211  float delay,load;
212  float *delayPtr;
213
214  delay = -1.0; /* To keep the compiler happy */
215  /* Allocate the Truesim_Info_t * structure */
216  simInfo = ALLOC(Truesim_Info_t,1);
217  Ntk_NetworkAddApplInfo(network,TRUESIM_NETWORK_APPL_KEY,
218                         (Ntk_ApplInfoFreeFn)TruesimEndSimulation,
219                         (void *)simInfo);
220  simInfo->depthArray = NIL(array_t);
221  simInfo->nodeToSimTable = NIL(st_table);
222
223  /* Allocate simulation structure for each node in the network and
224     put it in a table.*/
225  nodeToSimTable = st_init_table(st_ptrcmp,st_ptrhash);
226
227  if (delayFile) {
228    TruesimReadDelayFile(network,delayFile,nodeToSimTable);
229  } else { /* Read from nodeDelayTable */
230    Ntk_NetworkForEachNode(network,gen,node) {
231      sim = ALLOC(TrueSim_t,1);
232      /* I assume inputs to have zero delay. */
233      if (Ntk_NodeTestIsPrimaryInput(node)) {
234        delay = 0;
235      }
236      if (nodeDelayTable == NIL(st_table) ||
237          !st_lookup(nodeDelayTable,(char *)node,&delayPtr)) {
238        if (Ntk_NodeTestIsPrimaryInput(node)) {
239          load = (float) Ntk_NodeReadNumFanouts(node);
240        } else if (Ntk_NodeTestIsPrimaryOutput(node)){
241          /* Sometimes primary outputs can fanout to other internal nodes */
242          load = (float) Ntk_NodeReadNumFanouts(node);
243          load = load ? load : 1.0;
244          delay = load;
245        } else {
246          delay = load = (float) Ntk_NodeReadNumFanouts(node);
247        }
248      } else { /* if you do find it */
249        delay = load = *delayPtr;
250      }
251      sim->delay = delay;
252      sim->load = load;
253      st_insert(nodeToSimTable, (char *)node, (char *)sim);
254    }
255  }
256 
257  /* Set the global variables truesimRptHeader, truesimVerbose */
258  simInfo->trueDelay = truedelay;
259  simInfo->repeatHeader = truesimRptHeader = header;
260  simInfo->truesimVerbose = truesimVerbose = verbose;
261  simInfo->nodeToSimTable = nodeToSimTable;
262 
263  /* Fill in depth field for each node */
264  Truesim_NetworkUpdateNodeTopologicalDepth(network);
265
266  return;
267} /* End of Truesim_InitializeSimulation */
268
269
270/**Function********************************************************************
271
272  Synopsis [Free the truesim info data structure.]
273
274  SideEffects [The info data structure attached to the network is freed.]
275
276  SeeAlso [optional]
277
278******************************************************************************/
279void
280Truesim_QuitSimulation(Ntk_Network_t *network)
281{
282  Ntk_NetworkFreeApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
283 
284} /* End of Truesim_QuitSimulation */
285
286
287/*---------------------------------------------------------------------------*/
288/* Definition of internal functions                                          */
289/*---------------------------------------------------------------------------*/
290/**Function********************************************************************
291
292   Synopsis           [Free memory associated with Truesim_Info_t]
293   
294   SideEffects        [None]
295   
296   SeeAlso            [Truesim_QuitSimulation]
297
298******************************************************************************/
299void
300TruesimEndSimulation(void *data)
301{
302  st_table *nodeToSimTable;
303  array_t *depthArray,*tempArray;
304  Truesim_Info_t *dataBody;
305  int i;
306 
307  nodeToSimTable = ((Truesim_Info_t *)data)->nodeToSimTable;
308  depthArray = ((Truesim_Info_t *)data)->depthArray;
309 
310  if (nodeToSimTable) {
311    st_foreach(nodeToSimTable,stTrueSimFree,NIL(char));
312    st_free_table(nodeToSimTable);
313  }
314
315  arrayForEachItem(array_t *,depthArray,i,tempArray) {
316    array_free(tempArray);
317  }
318  array_free(depthArray);
319 
320  dataBody = (Truesim_Info_t *)data;
321  FREE(dataBody);
322 
323} /* End of TruesimEndSimulation */
324
325
326/*---------------------------------------------------------------------------*/
327/* Definition of static functions                                            */
328/*---------------------------------------------------------------------------*/
329/**Function********************************************************************
330
331   Synopsis [Insert input events, i.e., PI events.]
332
333   SideEffects [None]
334
335   SeeAlso []
336
337******************************************************************************/
338static void
339InsertInputEvents(
340  st_table *nodeToSimTable,
341  EventQueue *queue,             
342  array_t *inputArray,
343  char *vector)
344{
345  Ntk_Node_t *node;
346  TrueSim_t *sim;
347  int i;
348  char prev;
349
350  arrayForEachItem(Ntk_Node_t *,inputArray,i,node) {
351    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
352      (void) fprintf(vis_stderr,"** truesim fatal: In InsertInputEvents\n");
353      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
354                     Ntk_NodeReadName(node));
355      assert(0);
356    }
357    prev = sim->value;
358    if (prev != vector[i]) {
359      ScheduleEvent(queue,node,sim,vector[i]);
360    }
361  }
362 
363} /* End of InsertInputEvents */
364
365
366/**Function********************************************************************
367
368  Synopsis [Simulate all the events in the queue.]
369
370  Description [Simulate all the events in the queue.]
371
372  SideEffects [Events are freed when the events are executed.]
373
374  SeeAlso [optional]
375
376******************************************************************************/
377static void
378SinglePatternSimulate(
379  Ntk_Network_t *network,                     
380  EventQueue *queue)
381{
382  Event *currentEvent;
383  Event **wheel;
384  long currbin,halfPeriodBin;
385  Ntk_Node_t *gate;  /* Node being simulated/evaluated */
386  st_table *fanoutTable; /* Nodes in the fanout */
387  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
388  TrueSim_t *simInfo;
389  long eventType;
390
391  /* No events to start with */
392  if (numEvents == 0)
393    return;
394
395  wheel = queue->wheel;
396  halfPeriodBin = WHEEL_POS(HALF_PERIOD - 1);
397
398  currbin = 0;
399
400  /* Find the first sim, th2, th3 event */ 
401  /* Events th2 and th3 are control events. They help in housekeeping of the
402     event queue. When a th2 event is reached, the time ranges for each slot in
403     the wheel is increased. The threshold events are different from the
404     simulation events in that they are not related to simulation. They help in
405     the timely update of the wheel. */
406  do {
407    fanoutTable = st_init_table(st_ptrcmp,st_ptrhash);
408
409    do { /* examine each bin */
410      currentEvent = wheel[currbin];
411      eventType = TYPE(currentEvent);   
412
413      switch (eventType) {
414      case SIM_EVENT_C :
415        /* Simply cancel the event as this is a cancel event */
416        wheel[currbin] = NEXT_VER(currentEvent); 
417        /* free current event and obtain next */
418        EVENT_FREE(queue, currentEvent);
419        numEvents--;
420        break;
421      case SIM_EVENT_0 :       
422        wheel[currbin] = NEXT_VER(currentEvent); 
423        queue->time = TIME(currentEvent);
424        gate = GATE(currentEvent); 
425        if (!st_lookup(nodeToSimTable,(char *)gate,&simInfo)) {
426          (void) fprintf(vis_stderr,"** truesim fatal: In case SIM_EVENT_0\n");
427          (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
428                         Ntk_NodeReadName(gate));
429
430          assert(0);
431        }
432        (simInfo->switching)++;
433        simInfo->value = '0';
434        /* Collect the fanouts that may need to be scheduled. This is used for
435           the second pass */
436        InsertFanouts(gate,fanoutTable);
437        /* free current event and obtain next */
438        EVENT_FREE(queue, currentEvent);
439        simInfo->event = NIL(Event);
440        numEvents--;
441        break;
442      case SIM_EVENT_1 :       
443        wheel[currbin] = NEXT_VER(currentEvent); 
444        queue->time = TIME(currentEvent);
445        gate = GATE(currentEvent);
446        if (!st_lookup(nodeToSimTable,(char *)gate,&simInfo)) {
447          (void) fprintf(vis_stderr,"** truesim fatal: In case SIM_EVENT_1\n");
448          (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
449                         Ntk_NodeReadName(gate));
450          assert(0);
451        }
452        (simInfo->switching)++;
453        simInfo->value = '1';
454        (simInfo->prob)++;
455        /* Collect the fanouts that may need to be scheduled. This is used for
456           the second pass */
457        InsertFanouts(gate,fanoutTable);                               
458        /* free current event and obtain next */
459        EVENT_FREE(queue, currentEvent);
460        simInfo->event = NIL(Event);
461        numEvents--;
462        break;
463      case THRESHOLD_1 :       
464        currbin++; 
465        currbin &= ((1 << LOG_WHEEL_SIZE) - 1);
466        break;
467      case THRESHOLD_2 :       
468        HouseKeeping(queue, currentEvent);
469        currbin = halfPeriodBin + 1;
470        break;
471      case THRESHOLD_3 :       
472        HouseKeeping(queue, currentEvent);
473        currbin = 0;
474        break;
475      default:
476        (void) fprintf(vis_stderr,"** truesim fatal: Unknown event %ld\n",
477                       eventType);
478        assert(0);
479      } 
480    } while (NEXT_BOT(currentEvent) != currentEvent);
481
482    if (truesimVerbose > 2) {
483      (void) fprintf(vis_stdout,"Simulation time tick %ld",queue->time);
484      TruesimPrintNetworkNodeLogicState(network);
485    }
486   
487    /* We are finished processing a vertical list. A vertical list has events
488       scheduled for the same time. Now perform the second pass of the
489       simulation. */
490    PerformSecondPass(network,queue,fanoutTable);
491    st_free_table(fanoutTable);
492  } while (numEvents > 0);
493
494  /* End of simulation for one pattern */
495  /* Reset the queue */
496  queue->current = NIL(Event);
497  queue->time = 0;
498  TIME(queue->th1) = PERIOD - 1;
499  TIME(queue->th2) = PERIOD - 1;
500  TIME(queue->th3) = PERIOD - 1;
501
502} /* End of SinglePatternSimulate */
503
504
505/**Function********************************************************************
506
507  Synopsis [This function is called when control events (th1,th2 and th3) are
508  encountered. The time frame represented in the queue is increased by half and
509  the time stamps on the control events are updated to reflect the same. Events
510  earlier beyond th1 are bow brought into the wheel.]
511
512  SideEffects [None]
513
514  SeeAlso []
515
516******************************************************************************/
517static void
518HouseKeeping(
519  EventQueue *queue,
520  Event *threshevent)
521{
522  Event **wheel;
523  Event *event, *threshold1;
524  Event *temp;
525  long threshold1_time;
526
527  wheel = queue->wheel;
528
529  /* add T/2 to all threshold events */
530  threshold1 = queue->th1;
531  TIME(threshold1) += HALF_PERIOD;
532  TIME(queue->th2) += HALF_PERIOD;
533  TIME(queue->th3) += HALF_PERIOD;
534
535  threshold1_time = TIME(threshold1);
536  event = NEXT_HOR(threshold1);
537  while(TIME(event) <= threshold1_time) {
538    NEXT_HOR(threshold1) = NEXT_HOR(event);
539    temp = event;
540    while (NEXT_BOT(temp) != temp) {
541      InsertInBin(wheel,temp);
542      temp = NEXT_VER(temp);
543    }
544    InsertInBin(wheel,temp);
545    event = NEXT_HOR(threshold1);
546  }
547
548} /* End of HouseKeeping */
549
550
551/**Function********************************************************************
552
553  Synopsis [Insert fanouts of currently simulated node into a table.]
554
555  SideEffects [None]
556
557  SeeAlso []
558
559******************************************************************************/
560static void
561InsertFanouts(
562  Ntk_Node_t *node,
563  st_table *fanoutTable)
564{
565  int i;
566  Ntk_Node_t *fanout;
567 
568  Ntk_NodeForEachFanout(node,i,fanout) {
569    st_insert(fanoutTable,(char *)fanout,(char *)0);
570  }
571
572} /* End of InsertFanouts */
573
574
575/**Function********************************************************************
576
577  Synopsis [Fanouts of currently simulated events are scheduled to be simulated
578  at a later time.]
579
580  SideEffects [None]
581
582  SeeAlso []
583
584******************************************************************************/
585static void
586PerformSecondPass(
587  Ntk_Network_t *network,
588  EventQueue *queue,
589  st_table *fanoutTable)
590{
591  bdd_manager *ddManager = Ntk_NetworkReadMddManager(network);
592  graph_t *partition = Part_NetworkReadPartition(network);
593  st_table *nodeToSimTable = TruesimNetworkReadSimTable(network);
594  st_generator *stGen;
595  Ntk_Node_t *node,*dummy;
596  char next,prev;
597
598  st_foreach_item(fanoutTable,stGen,&node,&dummy) {
599    TrueSim_t *sim;
600
601    /* Lookup the simtable to extract the sim struct for the gate. */
602    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
603      (void) fprintf(vis_stderr,"** truesim fatal: In PerformSecondPass\n");
604      (void) fprintf(vis_stderr,"        Sim. structure missing for %s\n",
605                     Ntk_NodeReadName(node));
606      assert(0);
607    }
608
609    next = TruesimEvaluateNode(node,partition,ddManager,
610                               nodeToSimTable);
611    prev = sim->value;
612    if (prev != next) {
613      /* Check if an event already exists. If true, then reschedule the event */
614      if (sim->event) {
615        RescheduleEvent(queue,node,sim,next);
616      } else {
617        ScheduleEvent(queue,node,sim,next);
618      }
619    } else {
620      /* Check if an event already exists. If true, then cancel that event */
621      if (sim->event)
622        CancelEvent(queue,sim);
623    }
624  }
625
626} /* End of PerformSecondPass */
627
628
629/**Function********************************************************************
630
631  Synopsis [Schedule an event.]
632
633  SideEffects [None]
634
635  SeeAlso []
636
637******************************************************************************/
638static void
639ScheduleEvent(
640  EventQueue *queue,
641  Ntk_Node_t *node,
642  TrueSim_t *sim,
643  char value)
644{
645  Event *event;
646
647  EVENT_ALLOC(queue, event);
648  TIME(event) = queue->time + (long) sim->delay;
649  GATE(event) = node;
650  TYPE(event) = (value == '1') ? SIM_EVENT_1 : SIM_EVENT_0;
651  NEXT_HOR(event) = NIL(Event);
652  NEXT_VER(event) = NIL(Event);
653  NEXT_BOT(event) = NIL(Event);
654
655  InsertInBin(queue->wheel, event);
656
657  /* Cross pointer to the event, in case of cancellation or rescheduling */
658  sim->event = event;
659  numEvents++;
660
661} /* End of ScheduleEvent */
662
663
664/**Function********************************************************************
665
666  Synopsis [Reschedule an event.]
667
668  SideEffects [None]
669
670  SeeAlso []
671
672******************************************************************************/
673static void
674RescheduleEvent(
675  EventQueue *queue,
676  Ntk_Node_t *node,
677  TrueSim_t *sim,
678  char value)
679{
680  Event *event;
681
682  event = sim->event;
683  TYPE(event) = SIM_EVENT_C;
684
685  ScheduleEvent(queue,node,sim,value);
686
687} /* End of RescheduleEvent */
688
689
690/**Function********************************************************************
691
692  Synopsis [Cancel an event.]
693
694  SideEffects [None]
695
696  SeeAlso []
697
698******************************************************************************/
699static void
700CancelEvent(
701  EventQueue *queue,
702  TrueSim_t *sim)
703{
704  Event *event;
705
706  event = sim->event;
707  TYPE(event) = SIM_EVENT_C;
708
709  sim->event = NIL(Event);
710
711} /* End of CancelEvent */
712
713
714/**Function********************************************************************
715
716   Synopsis [Insert newly scheduled events to the event queue.]
717
718   Description [Insert newly scheduled events to the event queue. The time
719   stamp of the event is used to access the slot in the event table. If events
720   already exist at the event's time stamp, this event is inserted in a
721   vertical list.]
722
723   SideEffects [Event queue is updated]
724
725   SeeAlso [InsertInputEvents]
726
727******************************************************************************/
728static void
729InsertInBin(
730  Event **wheel,
731  Event *event)
732{
733  Event *prev,*curr;
734  long  pos;
735
736  pos = WHEEL_POS(TIME(event)); 
737
738  if (TIME(wheel[pos]) >= TIME(event)) { /* to insert as first element */
739    if (TIME(wheel[pos]) > TIME(event)) {
740      NEXT_BOT(event) = event;
741      NEXT_HOR(event) = wheel[pos];
742      NEXT_VER(event) = wheel[pos];
743      wheel[pos] = event;
744
745    } else {
746      NEXT_VER(event) = wheel[pos];
747      NEXT_BOT(event) = NEXT_BOT(NEXT_VER(event));
748      NEXT_HOR(event) = NEXT_HOR(wheel[pos]);
749      wheel[pos] = event;
750
751    }
752  } else {
753    prev = curr = wheel[pos];
754
755    /* Assumption : the last element in the converging list always has
756       a time greater than event. This is true by construction. */
757    while(TIME(curr) < TIME(event)) {
758      prev = curr;
759      curr = NEXT_HOR(curr);
760    }
761
762    if (TIME(curr) == TIME(event)) {
763      NEXT_VER(event) = curr;
764      NEXT_BOT(event) = NEXT_BOT(NEXT_VER(event));
765      NEXT_HOR(event) = NEXT_HOR(curr);
766      NEXT_HOR(prev) = event;
767      NEXT_VER(NEXT_BOT(prev)) = event;
768    } else {
769      NEXT_BOT(event) = event;
770      NEXT_HOR(event) = curr;
771      NEXT_VER(event) = curr;
772      NEXT_HOR(prev) = event;
773      NEXT_VER(NEXT_BOT(prev)) = event;
774    }
775  }     
776
777} /* End of InsertInBin */
778
779
780/**Function********************************************************************
781
782  Synopsis [Initialize the queue.]
783
784  SideEffects [None]
785
786  SeeAlso []
787
788******************************************************************************/
789static EventQueue *
790InitQueue(void)
791{
792  EventQueue *queue; 
793  Event **wheel,*threshold; 
794  int i;
795
796  queue = ALLOC(EventQueue, 1); 
797  queue->wheel = ALLOC(Event *, WHEEL_SIZE); 
798  queue->current = NIL(Event);
799  queue->time = 0;
800  queue->freeList = NIL(Event *);
801  queue->nextFree = NIL(Event);;
802
803  /* Allocate control events, th1, th2 and th3 and thi (infinity)*/
804  EVENT_ALLOC(queue, threshold);
805  queue->thi = threshold;
806  TYPE(threshold)  = THRESHOLD_I;
807  TIME(threshold) = MAX_TIME;
808  NEXT_HOR(threshold) = NIL(Event);
809  NEXT_VER(threshold) = NIL(Event);
810  NEXT_BOT(threshold) = threshold;
811
812  EVENT_ALLOC(queue, threshold);
813  queue->th1 = threshold;
814  TYPE(threshold)  = THRESHOLD_1;
815  TIME(threshold) = PERIOD -1;
816  NEXT_HOR(threshold) = queue->thi;
817  NEXT_VER(threshold) = queue->thi;
818  NEXT_BOT(threshold) = threshold;
819
820  EVENT_ALLOC(queue, threshold);
821  queue->th2 = threshold;
822  TYPE(threshold)  = THRESHOLD_2;
823  TIME(threshold) = PERIOD -1;
824  NEXT_HOR(threshold) = queue->th1;
825  NEXT_VER(threshold) = queue->th1;
826  NEXT_BOT(threshold) = threshold;
827
828  EVENT_ALLOC(queue, threshold);
829  queue->th3 = threshold;
830  TYPE(threshold)  = THRESHOLD_3;
831  TIME(threshold) = PERIOD-1;
832  NEXT_HOR(threshold) = queue->th1;
833  NEXT_VER(threshold) = queue->th1;
834  NEXT_BOT(threshold) = threshold;
835
836  wheel = queue->wheel;
837  threshold = queue->th1;
838  for (i = 0; i < WHEEL_SIZE; i++) {
839    wheel[i] = threshold;
840  }
841
842  wheel[WHEEL_POS(HALF_PERIOD - 1)] =  queue->th2;
843  wheel[WHEEL_POS(PERIOD - 1)] =  queue->th3;
844
845  return (queue);
846
847} /* End of InitQueue */
848
849
850/**Function********************************************************************
851
852  Synopsis [Increase memory for the freeList.]
853
854  SideEffects [None]
855
856  SeeAlso []
857
858******************************************************************************/
859static void
860NewPage(EventQueue *queue)
861{
862  Event **mem,*list;
863  int i;
864
865  mem = (Event **) ALLOC(char,MEM_CHUNK * sizeof(Event) + sizeof(Event *));
866
867  mem[0] = (Event *) queue->freeList;
868  queue->freeList = mem;
869
870  list = (Event *) &mem[1];
871
872  i = 0;
873  do {
874    list[i].horizontal = &list[i + 1];
875  } while (++i < MEM_CHUNK -1);
876
877  list[MEM_CHUNK - 1].horizontal = NIL(Event);
878
879  queue->nextFree = list;
880
881} /* End of NewPage */
882
883
884/**Function********************************************************************
885
886  Synopsis [Free Truesim_t data structure stored in an st_table.]
887
888  SideEffects [None]
889
890  SeeAlso [None]
891
892******************************************************************************/
893static enum st_retval
894stTrueSimFree(
895  char *key,
896  char *value,
897  char *arg)
898{
899  TrueSim_t *sim;
900  sim = (TrueSim_t *)value;
901
902  if (sim)
903    FREE(sim);
904
905  return (ST_CONTINUE);
906} /* End of stTrueSimFree */
907
Note: See TracBrowser for help on using the repository browser.