EventSorter


1   /***************************************************************************/
2   /* COACH: Component Based Open Source Architecture for                     */
3   /*        Distributed Telecom Applications                                 */
4   /* See:   http://www.objectweb.org/                                        */
5   /*                                                                         */
6   /* Copyright (C) 2003 Lucent Technologies Nederland BV                     */
7   /*                    Bell Labs Advanced Technologies - EMEA               */
8   /*                                                                         */
9   /* Initial developer(s): Harold Batteram                                   */
10  /*                                                                         */
11  /* This library is free software; you can redistribute it and/or           */
12  /* modify it under the terms of the GNU Lesser General Public              */
13  /* License as published by the Free Software Foundation; either            */
14  /* version 2.1 of the License, or (at your option) any later version.      */
15  /*                                                                         */
16  /* This library is distributed in the hope that it will be useful,         */
17  /* but WITHOUT ANY WARRANTY; without even the implied warranty of          */
18  /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU        */
19  /* Lesser General Public License for more details.                         */
20  /*                                                                         */
21  /* You should have received a copy of the GNU Lesser General Public        */
22  /* License along with this library; if not, write to the Free Software     */
23  /* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
24  /***************************************************************************/
25  
26  package org.coach.tracing.server;
27  
28  import java.util.*;
29  
30  public class EventSorter
31  {
32      private Hashtable processTable = new Hashtable();
33      private EventDataBase eventDB;
34      private long eventCount;
35      private SortedEventList sortedEventList = new SortedEventList();
36      
37      public EventSorter(EventDataBase db)
38      {
39          eventDB = db;
40      }
41  
42      public synchronized void add(EventRecord eventRecord)
43      {
44          eventCount++;       
45          // Obtain the process list for this event
46          EventList eventList = (EventList)processTable.get(eventRecord.getProcessId());
47  
48          if (eventList == null)
49          {
50              eventList = new EventList();
51              processTable.put(eventRecord.getProcessId(), eventList);
52          }
53          
54          // Create an ordered event
55          OrderedEvent orderedEvent = new OrderedEvent(eventRecord.getIndex());
56          orderedEvent.key = eventRecord.getKey();
57          orderedEvent.isOutgoing = eventRecord.isOutgoingMessage();
58          if (eventRecord.getLink() != -1)
59          {
60              EventRecord link = eventDB.readEvent(eventRecord.getLink());
61              if (!link.getProcessId().equals(eventRecord.getProcessId()))
62              {
63                  // We are only concerned with messages between different processes, not within a process
64                  EventList linkList = (EventList)processTable.get(link.getProcessId());
65                  if (linkList == null)
66                  {        
67                      throw new RuntimeException  ("Unexpected empty list for process: " + link.getProcessId());
68                  }
69                  // link the two events
70                  OrderedEvent peer = linkList.getAbsoluteIndex(link.getIndex());
71                  orderedEvent.link = peer;
72                  peer.link = orderedEvent;
73              }
74          }
75          
76          eventList.add(orderedEvent);
77          sortedEventList.insert(orderedEvent);
78  
79  //        verify();
80      }
81  
82      public synchronized long getEventIndex(long key)
83      {
84          return sortedEventList.indexOf(key);
85      }
86                  
87      public synchronized EventRecord getEventAt(long index)
88      {
89          OrderedEvent e = sortedEventList.get(index);
90          EventRecord r = eventDB.readEvent(e.key);
91          r.currentIndex = index;
92          return r;
93      }        
94  
95      /**
96       * Returns the set of events from startIndex to startIndex + range plus
97       * all events linked to within that range.
98       */
99      public synchronized EventRecord[] getEvents(long startIndex, long endIndex)
100     {
101         TreeMap map = new TreeMap();
102         
103         if (endIndex >= sortedEventList.size())
104         {
105             endIndex = sortedEventList.size() - 1;
106         }
107         if (startIndex < 0 || startIndex >= sortedEventList.size())
108         {
109             return new EventRecord[0];
110         }
111         
112         for (long i = startIndex; i <= endIndex; i++)
113         {
114             OrderedEvent e = sortedEventList.get(i);
115             if (e == null)
116             {
117                 break;
118             }
119             map.put(new Long  (i), e);
120             if (e.link != null)
121             {
122                 map.put(new Long  (sortedEventList.indexOf(e.link)), e.link);
123             }
124         }
125         
126         EventRecord[] events = new EventRecord[map.size()];
127         Iterator it = map.keySet().iterator();
128         int i = 0;
129         while (it.hasNext())
130         {
131             Long   index = (Long  )it.next();
132             OrderedEvent e = (OrderedEvent)map.get(index);
133             EventRecord r = eventDB.readEvent(e.key);
134             r.currentIndex = index.longValue();
135             events[i++] = r;
136         }
137         return events;
138     }
139                 
140     /**
141      * For testing only.
142      * This method verifies the consistency of the event tables.
143      * Rule 1: all events in the same process list must have increasing relative and absolute indices
144      * Rule 2: all messages must have a larger relative index at the receiving event then the sending event.
145      */
146     private void verify()
147     {
148         Iterator it = processTable.keySet().iterator();
149         int checked = 0;
150         while(it.hasNext())
151         {
152             String   processId = (String  )it.next();
153             EventList eventList = (EventList)processTable.get(processId);
154             OrderedEvent e = eventList.getAbsoluteIndex(0);
155             int index = 0;
156             while(e != null)
157             {
158                 if (e.next != null)
159                 {
160                     if (e.next.prev != e)
161                     {
162                         dump();
163                         throw new RuntimeException  ("Event link inconsistency in process table: " + processId + " at index: " + index);                        
164                     }
165                     if (e.absoluteIndex >= e.next.absoluteIndex)
166                     {
167                         dump();
168                         throw new RuntimeException  ("Event order inconsistency in process table: " + processId + " at index: " + index + " " + e.absoluteIndex + " >= " + e.next.absoluteIndex);
169                     }
170                     if (e.relativeIndex >= e.next.relativeIndex)
171                     {
172                         dump();
173                         throw new RuntimeException  ("Event relative index inconsistency in process table: " + processId + " at index: " + index + " " + e.relativeIndex + " >= " + e.next.relativeIndex);
174                     }
175                 }
176                 if (e.link != null)
177                 {
178                     if (e.isOutgoing)
179                     {
180                         if (e.relativeIndex >= e.link.relativeIndex)
181                         {
182                             dump();
183                             throw new RuntimeException  ("Message inconsistency in process table: " + processId + " at index: " + index + " " + e.relativeIndex + " >= " + e.link.relativeIndex);
184                         }
185                     }
186                     else
187                     {
188                         if (e.relativeIndex <= e.link.relativeIndex)
189                         {
190                             dump();
191                             throw new RuntimeException  ("Message inconsistency in process table: " + processId + " at index: " + index + " " + e.relativeIndex + " <= " + e.link.relativeIndex);
192                         }
193                     }
194                 }
195                 if (e.key != -1) {
196                     checked++;
197                 }
198                 e = e.next;
199                 index++;
200             }            
201         }
202         if (checked != eventCount)
203         {
204             dump();
205             throw new RuntimeException  ("Event count (" + eventCount + ") and checked events (" + checked + ") don't match");
206         }            
207         if (sortedEventList.size() != eventCount)
208         {
209             dump();
210             throw new RuntimeException  ("Event count (" + eventCount + ") and sortedEventList size (" + sortedEventList.size() + ") don't match");
211         }
212     }
213 
214     private void dump()
215     {
216         Iterator it = processTable.keySet().iterator();
217         while(it.hasNext())
218         {
219             String   processId = (String  )it.next();
220             System.err.println("**** " + processId + " ****");
221             EventList eventList = (EventList)processTable.get(processId);
222             OrderedEvent e = eventList.getAbsoluteIndex(0);
223             int index = 0;
224             while(e != null)
225             {
226                 System.err.print(e.absoluteIndex + ": key: " + e.key + " relative index: " + e.relativeIndex);
227                 if (e.link != null)
228                 {
229                     if (e.isOutgoing)
230                     {
231                         System.err.println(" -> " + e.link.key);
232                     }
233                     else
234                     {
235                         System.err.println(" <- " + e.link.key);
236                     }                        
237                 }
238                 else
239                 {
240                     System.err.println();
241                 }
242                 e = e.next;
243                 index++;
244             }            
245         }
246     }
247 
248     class OrderedEvent implements Comparable  
249     {
250         public long key = -1;
251         public long absoluteIndex;
252         public long relativeIndex;
253         // pointers to the message counter part
254         public OrderedEvent link;
255         public boolean isOutgoing;
256 
257         public OrderedEvent prev;
258         public OrderedEvent next;
259         
260         public OrderedEvent(long index)
261         {
262             absoluteIndex = index;
263             relativeIndex = index;
264         }
265         
266         public int compareTo(Object   obj)
267         {
268             EventRecord e1 = eventDB.readEvent(key);
269             EventRecord e2 = eventDB.readEvent(((OrderedEvent)obj).key);
270             
271             if (e1.getTrailId().equals(e2.getTrailId()) || e1.getProcessId().equals(e2.getProcessId()))
272             {
273                 // compare relative index
274                 if (relativeIndex < ((OrderedEvent)obj).relativeIndex)
275                 {
276                     return -1;
277                 }
278                 if (relativeIndex > ((OrderedEvent)obj).relativeIndex)
279                 {
280                     return 1;
281                 }
282             }
283             
284             // compare physical clock
285     
286             // on fast machines the time resolution is not sufficient and identical physical clock values
287             // occur. When the physical clocks are identical the object hashcode is used to differentiate.
288             // The returned value cannot be 0 otherwise the event store will overwite a previous entry!
289             if (e1.getTime() == e2.getTime()) {
290                 // if they are still equal differentiate by hashcode
291                 if (e1.hashCode() == e2.hashCode()) {
292                     return 0;
293                 } else {
294                     return (e1.hashCode() > e2.hashCode()) ? 1 : -1;
295                 }
296             }
297             return (e1.getTime() > e2.getTime()) ? 1 : -1;
298         }        
299     }
300     
301     class EventList
302     {
303         public OrderedEvent head;
304         public OrderedEvent tail;
305         
306         public EventList() {
307         }   
308         
309         
310         /**
311          * Insert the event at the absolute index position in the list.
312          * If the event is out of order, placeholders will be inserted for missing events.
313          */
314         private void insert(OrderedEvent e)
315         {   
316             OrderedEvent prev = null;
317             if (e.absoluteIndex == 0)
318             {
319                 if (head != null && head.key == -1)
320                 {
321                     // The current head was a placeholder.
322                     e.next = head.next;
323                     if (e.next != null) {
324                         e.next.prev = e;
325                     }
326                 }                    
327                 head = e;
328             }
329             else
330             {
331                 prev = getAbsoluteIndex(e.absoluteIndex - 1);
332                 if (prev == null)
333                 {
334                     // The current event is ahead and the previous event is not yet inserted.
335                     // Insert a placeholder for the previous event.
336                     prev = new OrderedEvent(e.absoluteIndex - 1);
337                     // link the two events
338                     e.prev = prev;
339                     prev.next = e;
340                     insert(prev);
341                 }
342             }
343             
344             if (prev != null)
345             {
346                 if (prev.next != null && prev.next.key == -1)
347                 {
348                     // There was a placeholder for the current event.
349                     // Since the placeholder is replaced by the current event, link the event following
350                     // the placeholder to the current event.
351                     e.next = prev.next.next;
352                     if (e.next != null) {
353                         e.next.prev = e;
354                     }
355                 }
356                 // Now link the previous event with the current event.
357                 prev.next = e;
358                 e.prev = prev;
359                 // Now calculate the relativeIndex
360                 e.relativeIndex = e.prev.relativeIndex + 1;
361             }
362             
363             if (e.next == null)
364             {
365                 // The current event is at the end of the list.
366                 tail = e;
367             }                    
368         }
369         
370         public void add(OrderedEvent e)
371         {
372             // Insert the event in the list.
373             insert(e);
374             
375             if (e.link != null && e.link.isOutgoing)
376             {
377                 // This event is the receiving side of a message 
378                 if (e.link.relativeIndex >= e.relativeIndex)
379                 {
380                     // Advance the relative index to one more of the senders relativeIndex
381                     e.relativeIndex = e.link.relativeIndex + 1;
382                 }
383             }
384             if (e.next != null || (e.link != null && e.isOutgoing))
385             {
386                 // The event was inserted out of order.
387                 // All dependend relative indices must be recalculated.
388                 recalculate(e);               
389             }
390 //dump();
391         }        
392         
393         /**
394          * Searches the event list for the event with the given index.
395          */
396         public OrderedEvent getAbsoluteIndex(long index)
397         {
398             // search from the tail up
399             OrderedEvent e = tail;
400             while (e != null)
401             {
402                 if (e.absoluteIndex == index)
403                 {
404                     return e;
405                 }
406                 if (e.absoluteIndex < index)
407                 {
408                     return null;
409                 }
410                 else
411                 {
412                     e = e.prev;
413                 }
414             }
415             return null;
416         }
417     
418         public OrderedEvent getRelativeIndex(long index)
419         {
420             // search from the tail up
421             OrderedEvent e = tail;
422             while (e != null)
423             {
424                 if (e.relativeIndex <= index)
425                 {
426                     return e;
427                 }
428                 e = e.prev;
429             }
430             return null;
431         }
432         
433         /**
434          * The recalculation algoritm updates relative indices of all dependend events.
435          * The recalculation starts with an event from the vector list and then recalculates all indices in
436          * the process list for that event downward.
437          * If an event in the process list is the sending part of a message, the process list of the receiving event
438          * (and all its dependencies) must also be recalculated. Therefore, the receiving event is added to the end of the
439          * list.
440          */
441         private void recalculate(OrderedEvent e)
442         {
443 //System.err.println("************** recalculating ***********");
444             // The reorderList is used to keep track of events who's relative index values are changed.
445             // Since this also changes their order in the total ordering of events.
446             Vector reorderList = new Vector();
447             Vector v = new Vector();
448             v.add(e);
449             
450             // Don't use an iterator to process the vector elements because new elements may be
451             // added to the vector. An iterator will detect this and throws a ConcurrentModificationException
452             for (int i = 0; i < v.size(); i++)
453             {
454                 e = (OrderedEvent)(v.get(i));
455                 while (e != null)
456                 {
457                     if (e.prev != null)
458                     {
459                         // The relative index of the next event in the same list must be at least one higher then the
460                         // previous event.
461                         if (e.relativeIndex <= e.prev.relativeIndex)
462                         {
463                             // Update the relative index
464 //System.err.println("************** recalculating: update relative index: " + e.absoluteIndex + " key: " + e.key + " from: " + e.relativeIndex + " to: " + e.prev.relativeIndex + 1);
465                             e.relativeIndex = e.prev.relativeIndex + 1;
466                             if (e.key != -1)
467                             {
468                                 reorderList.add(e);
469                             }
470                         }
471                     }
472                     if (e.link != null)
473                     {
474                         if (e.isOutgoing)
475                         {
476                             if (e.relativeIndex >= e.link.relativeIndex)
477                             {
478                                 // This is a forward message with a relative index higer or equal to the event it links to.
479                                 // That means that the link and all subsequent events must also be recalculated.
480 //System.err.println("************** recalculating: add link for key: " + e.key);
481                                 v.add(e.link);
482                             }
483                         }
484                         else
485                         {
486                             // This event is the receiving side of a message 
487                             if (e.relativeIndex <= e.link.relativeIndex)
488                             {
489                                 // Update the relative index to one more of the senders relativeIndex
490 //System.err.println("************** recalculating: update relative index from link: " + e.absoluteIndex+ " key: " + e.key + " from: " + e.relativeIndex + " to: " + e.link.relativeIndex + 1);
491                                 e.relativeIndex = e.link.relativeIndex + 1;
492                                 if (e.key != -1)
493                                 {
494                                     reorderList.add(e);
495                                 }
496                             }
497                         }
498                     }
499                     // recalculate the next event in the process list
500                     e = e.next;
501                 }
502             }
503             
504             for (int i = 0; i < reorderList.size(); i++)
505             {
506                 // Reorder the events in the total ordering by removing and re-inserting them
507                 e = (OrderedEvent)reorderList.get(i);
508                 sortedEventList.remove(e);
509                 sortedEventList.insert(e);
510             }
511         }                
512     }
513     
514     /**
515      * This class maintains the total ordering of events.
516      * The current implementation is optimized to retrieve the EventRecord at a given index fast.
517      * The performance of insert and remove operations is very poor when the number of events grow.
518      * Eventualy, this should be replaced by a balanced tree with rank fields as described in
519      * The Art of Computer Programming, volume 3, page 471 - 473.
520      */
521     class SortedEventList
522     {
523         private ArrayList totalOrder = new ArrayList();
524         
525         public OrderedEvent get(long i)
526         {
527             return (OrderedEvent)totalOrder.get((int)i);
528         }
529         
530         public void insert(OrderedEvent e)
531         {
532             if (totalOrder.size() == 0)
533             {
534                 totalOrder.add(0, e);
535                 return;
536             }
537             // Since most events will be inserted at the end of the list, search bottom up
538             // for the first event earlier then the current event
539             for (int i = totalOrder.size() - 1; i >= 0; i--)
540             {
541                 if (((OrderedEvent)totalOrder.get(i)).compareTo(e) == -1)
542                 {
543                     totalOrder.add(i + 1, e);
544                     return;
545                 }
546             }
547             // No other entry was earlier. Hence, the current event is the earliest event.
548             // Insert it at the top of the list.
549             totalOrder.add(0, e); 
550         }
551         
552         public void remove(OrderedEvent e)
553         {
554             for (int i = totalOrder.size() - 1; i >= 0; i--)
555             {
556                 if (totalOrder.get(i) == e)
557                 {
558                     totalOrder.remove(i);
559                 }
560             }            
561         }
562 
563         public long indexOf(OrderedEvent e)
564         {
565             return (long)totalOrder.indexOf(e);
566         }
567                 
568         public long indexOf(long key)
569         {
570             for (int i = totalOrder.size() - 1; i >= 0; i--)
571             {
572                 if (((OrderedEvent)totalOrder.get(i)).key == key)
573                 {
574                     return (long)i;
575                 }
576             }
577             throw new RuntimeException  ("invalid record key! " + key);            
578         }
579         
580         public int size() {
581             return totalOrder.size();
582         }
583     }        
584 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags