1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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 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 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 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 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 } 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 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 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 ![JavaDoc](../../../../../cmn/javadoc.gif) 249 { 250 public long key = -1; 251 public long absoluteIndex; 252 public long relativeIndex; 253 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 if (relativeIndex < ((OrderedEvent)obj).relativeIndex) 275 { 276 return -1; 277 } 278 if (relativeIndex > ((OrderedEvent)obj).relativeIndex) 279 { 280 return 1; 281 } 282 } 283 284 286 if (e1.getTime() == e2.getTime()) { 290 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 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 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 prev = new OrderedEvent(e.absoluteIndex - 1); 337 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 e.next = prev.next.next; 352 if (e.next != null) { 353 e.next.prev = e; 354 } 355 } 356 prev.next = e; 358 e.prev = prev; 359 e.relativeIndex = e.prev.relativeIndex + 1; 361 } 362 363 if (e.next == null) 364 { 365 tail = e; 367 } 368 } 369 370 public void add(OrderedEvent e) 371 { 372 insert(e); 374 375 if (e.link != null && e.link.isOutgoing) 376 { 377 if (e.link.relativeIndex >= e.relativeIndex) 379 { 380 e.relativeIndex = e.link.relativeIndex + 1; 382 } 383 } 384 if (e.next != null || (e.link != null && e.isOutgoing)) 385 { 386 recalculate(e); 389 } 390 } 392 393 396 public OrderedEvent getAbsoluteIndex(long index) 397 { 398 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 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 441 private void recalculate(OrderedEvent e) 442 { 443 Vector reorderList = new Vector(); 447 Vector v = new Vector(); 448 v.add(e); 449 450 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 if (e.relativeIndex <= e.prev.relativeIndex) 462 { 463 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 v.add(e.link); 482 } 483 } 484 else 485 { 486 if (e.relativeIndex <= e.link.relativeIndex) 488 { 489 e.relativeIndex = e.link.relativeIndex + 1; 492 if (e.key != -1) 493 { 494 reorderList.add(e); 495 } 496 } 497 } 498 } 499 e = e.next; 501 } 502 } 503 504 for (int i = 0; i < reorderList.size(); i++) 505 { 506 e = (OrderedEvent)reorderList.get(i); 508 sortedEventList.remove(e); 509 sortedEventList.insert(e); 510 } 511 } 512 } 513 514 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 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 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 }
| Popular Tags
|