Project

General

Profile

Statistics
| Branch: | Revision:

root / src / eventlog / eventlogindex.cc @ 8aeaaccc

History | View | Annotate | Download (21.1 KB)

1 01873262 Georg Kunz
//=========================================================================
2
//  EVENTLOGINDEX.CC - part of
3
//                  OMNeT++/OMNEST
4
//           Discrete System Simulation in C++
5
//
6
//  Author: Levente Meszaros
7
//
8
//=========================================================================
9
10
/*--------------------------------------------------------------*
11
  Copyright (C) 2006-2008 OpenSim Ltd.
12

13
  This file is distributed WITHOUT ANY WARRANTY. See the file
14
  `license' for details on this and other legal matters.
15
*--------------------------------------------------------------*/
16
17
#include <stdio.h>
18
#include <algorithm>
19
#include "eventlogentry.h"
20
#include "eventlogindex.h"
21
#include "exception.h"
22
23
USING_NAMESPACE
24
25
#define LL INT64_PRINTF_FORMAT
26
27
static bool isEventNumber(eventnumber_t eventNumber)
28
{
29
    return true;
30
}
31
32
static bool isEventNumber(simtime_t simulationTime)
33
{
34
    return false;
35
}
36
37
static bool isSimulationTime(eventnumber_t eventNumber)
38
{
39
    return false;
40
}
41
42
static bool isSimulationTime(simtime_t simulationTime)
43
{
44
    return true;
45
}
46
47
static eventnumber_t getKey(eventnumber_t key, eventnumber_t eventNumber, simtime_t simulationTime)
48
{
49
    return eventNumber;
50
}
51
52
static simtime_t getKey(simtime_t key, eventnumber_t eventNumber, simtime_t simulationTime)
53
{
54
    return simulationTime;
55
}
56
57
EventLogIndex::CacheEntry::CacheEntry()
58
{
59
    this->simulationTime = -1;
60
    this->beginEventNumber = -1;
61
    this->endEventNumber = -1;
62
    this->beginOffset = -1;
63
    this->endEventBeginOffset = -1;
64
    this->endOffset = -1;
65
}
66
67
EventLogIndex::CacheEntry::CacheEntry(eventnumber_t eventNumber, simtime_t simulationTime, file_offset_t beginOffset, file_offset_t endOffset)
68
{
69
    this->simulationTime = simulationTime;
70
    this->beginEventNumber = eventNumber;
71
    this->endEventNumber = eventNumber;
72
    this->beginOffset = beginOffset;
73
    this->endEventBeginOffset = beginOffset;
74
    this->endOffset = endOffset;
75
}
76
77
void EventLogIndex::CacheEntry::include(eventnumber_t eventNumber, simtime_t simulationTime, file_offset_t beginOffset, file_offset_t endOffset)
78
{
79
    Assert(this->simulationTime == simulationTime);
80
    this->beginEventNumber = std::min(beginEventNumber, eventNumber);
81
    this->endEventNumber = std::max(endEventNumber, eventNumber);
82
    this->beginOffset = std::min(this->beginOffset, beginOffset);
83
    this->endEventBeginOffset = std::max(this->endEventBeginOffset, beginOffset);
84
    this->endOffset = std::max(this->endOffset, endOffset);
85
}
86
87
void EventLogIndex::CacheEntry::getBeginKey(eventnumber_t &key)
88
{
89
    key = beginEventNumber;
90
}
91
92
void EventLogIndex::CacheEntry::getBeginKey(simtime_t &key)
93
{
94
    key = simulationTime;
95
}
96
97
void EventLogIndex::CacheEntry::getEndKey(eventnumber_t &key)
98
{
99
    key = endEventNumber;
100
}
101
102
void EventLogIndex::CacheEntry::getEndKey(simtime_t &key)
103
{
104
    key = simulationTime;
105
}
106
107
//*************************************************************************************************
108
109
EventLogIndex::EventLogIndex(FileReader *reader)
110
{
111
    this->reader = reader;
112
113
    clearInternalState();
114
}
115
116
EventLogIndex::~EventLogIndex()
117
{
118
    delete reader;
119
}
120
121
void EventLogIndex::synchronize(FileReader::FileChangedState change)
122
{
123
    if (change != FileReader::UNCHANGED) {
124
        clearInternalState(change);
125
        reader->synchronize();
126
    }
127
}
128
129
void EventLogIndex::clearInternalState(FileReader::FileChangedState change)
130
{
131
    Assert(change != FileReader::UNCHANGED);
132
133
    if (change == FileReader::OVERWRITTEN) {
134
        eventNumberToCacheEntryMap.clear();
135
        simulationTimeToCacheEntryMap.clear();
136
137
        firstEventNumber = EVENT_NOT_YET_CALCULATED;
138
        firstSimulationTime = simtime_nil;
139
        firstEventOffset = -1;
140
    }
141
142
    lastEventNumber = EVENT_NOT_YET_CALCULATED;
143
    lastSimulationTime = simtime_nil;
144
    lastEventOffset = -1;
145
}
146
147
eventnumber_t EventLogIndex::getFirstEventNumber()
148
{
149
    if (firstEventNumber == EVENT_NOT_YET_CALCULATED)
150
    {
151
        file_offset_t lineEndOffset;
152
        readToEventLine(true, 0, firstEventNumber, firstSimulationTime, firstEventOffset, lineEndOffset);
153
    }
154
155
    return firstEventNumber;
156
}
157
158
eventnumber_t EventLogIndex::getLastEventNumber()
159
{
160
    if (lastEventNumber == EVENT_NOT_YET_CALCULATED)
161
    {
162
        file_offset_t lineEndOffset;
163
        readToEventLine(false, reader->getFileSize(), lastEventNumber, lastSimulationTime, lastEventOffset, lineEndOffset);
164
        cacheEntry(lastEventNumber, lastSimulationTime, lastEventOffset, reader->getFileSize());
165
    }
166
167
    return lastEventNumber;
168
}
169
170
file_offset_t EventLogIndex::getFirstEventOffset()
171
{
172
    getFirstEventNumber();
173
174
    return firstEventOffset;
175
}
176
177
file_offset_t EventLogIndex::getLastEventOffset()
178
{
179
    getLastEventNumber();
180
181
    return lastEventOffset;
182
}
183
184
simtime_t EventLogIndex::getFirstSimulationTime()
185
{
186
    getFirstEventNumber();
187
188
    return firstSimulationTime;
189
}
190
191
simtime_t EventLogIndex::getLastSimulationTime()
192
{
193
    getLastEventNumber();
194
195
    return lastSimulationTime;
196
}
197
198
file_offset_t EventLogIndex::getBeginOffsetForEndOffset(file_offset_t endOffset)
199
{
200
    Assert(endOffset >= 0);
201
202
    eventnumber_t eventNumber;
203
    simtime_t simulationTime;
204
    file_offset_t lineBeginOffset, lineEndOffset;
205
206
    if (readToEventLine(false, endOffset, eventNumber, simulationTime, lineBeginOffset, lineEndOffset))
207
        return lineBeginOffset;
208
    else
209
        return -1;
210
}
211
212
file_offset_t EventLogIndex::getEndOffsetForBeginOffset(file_offset_t beginOffset)
213
{
214
    Assert(beginOffset >= 0);
215
216
    eventnumber_t eventNumber;
217
    simtime_t simulationTime;
218
    file_offset_t lineBeginOffset, lineEndOffset;
219
220
    if (readToEventLine(true, beginOffset + 1, eventNumber, simulationTime, lineBeginOffset, lineEndOffset))
221
        return lineBeginOffset;
222
    else
223
        return reader->getFileSize();
224
}
225
226
bool EventLogIndex::isEventBeginOffset(file_offset_t offset)
227
{
228
    reader->seekTo(offset);
229
    char *line = reader->getNextLineBufferPointer();
230
231
    return line && *line == 'E';
232
}
233
234
file_offset_t EventLogIndex::getOffsetForEventNumber(eventnumber_t eventNumber, MatchKind matchKind)
235
{
236
    Assert(eventNumber >= 0);
237
    file_offset_t offset = searchForOffset(eventNumberToCacheEntryMap, eventNumber, matchKind);
238
239
    if (PRINT_DEBUG_MESSAGES) printf("Found event number: %"LL"d for match kind: %d at offset: %"LL"d\n", eventNumber, matchKind, offset);
240
241
    return offset;
242
}
243
244
file_offset_t EventLogIndex::getOffsetForSimulationTime(simtime_t simulationTime, MatchKind matchKind)
245
{
246
    Assert(simulationTime >= 0);
247
    file_offset_t offset = searchForOffset(simulationTimeToCacheEntryMap, simulationTime, matchKind);
248
249
    if (PRINT_DEBUG_MESSAGES) printf("Found simulation time: %.*g for match kind: %d at offset: %"LL"d\n", 12, simulationTime.dbl(), matchKind, offset);
250
251
    return offset;
252
}
253
254
template <typename T> file_offset_t EventLogIndex::searchForOffset(std::map<T, CacheEntry> &map, T key, MatchKind matchKind)
255
{
256
    T lowerKey;
257
    T upperKey;
258
    file_offset_t foundOffset;
259
    file_offset_t lowerOffset;
260
    file_offset_t upperOffset;
261
    // first try to look up it the cache, this may result in an exact offset or a range around the offset being searched
262
    bool found = cacheSearchForOffset(map, key, matchKind, lowerKey, upperKey, foundOffset, lowerOffset, upperOffset);
263
264
    // no events in cache (not even the first and last which is always cached)
265
    // so there are no events at all
266
    if (lowerKey == -1 && upperKey == -1)
267
        foundOffset = -1;
268
    else if (!found) {
269
        Assert(lowerKey <= key && key <= upperKey);
270
        Assert(foundOffset == -1 || (lowerOffset <= foundOffset && foundOffset <= upperOffset));
271
272
        // if we still have a key range then use a binary search to look up the closest match
273
        if (foundOffset == -1 || lowerKey != upperKey)
274
            foundOffset = binarySearchForOffset(key, matchKind, lowerKey, upperKey, lowerOffset, upperOffset);
275
276
        bool exactMatchFound = lowerKey == key && upperKey == key;
277
278
        // finally use linear search to find the requested offset
279
        if (matchKind == EXACT) {
280
            if (foundOffset != -1 && isSimulationTime(key)) {
281
                // check if there are multiple events with the same simulation time
282
                file_offset_t firstOffset = linearSearchForOffset(key, foundOffset, false, true);
283
                file_offset_t lastOffset = linearSearchForOffset(key, foundOffset, true, true);
284
285
                if (foundOffset != lastOffset || foundOffset != firstOffset)
286
                    throw opp_runtime_error("Found non unique simulation time when exact match is requested");
287
            }
288
        }
289
        else {
290
            bool forward;
291
            file_offset_t searchOffset;
292
293
            if (exactMatchFound) {
294
                forward = matchKind == LAST_OR_NEXT || matchKind == LAST_OR_PREVIOUS;
295
                searchOffset = foundOffset;
296
            }
297
            else {
298
                forward = matchKind == FIRST_OR_NEXT || matchKind == LAST_OR_NEXT;
299
                searchOffset = forward ? lowerOffset : (upperOffset + lowerOffset) / 2;
300
            }
301
302
            foundOffset = linearSearchForOffset(key, searchOffset, forward, exactMatchFound);
303
        }
304
    }
305
306
    Assert(foundOffset == -1 || isEventBeginOffset(foundOffset));
307
308
    return foundOffset;
309
}
310
311
template <typename T> bool EventLogIndex::cacheSearchForOffset(std::map<T, CacheEntry> &map, T key, MatchKind matchKind, T& lowerKey, T& upperKey, file_offset_t& foundOffset, file_offset_t& lowerOffset, file_offset_t& upperOffset)
312
{
313
    ensureFirstEventAndLastEventCached();
314
    T keyValue = (T)key;
315
    typename std::map<T, CacheEntry>::iterator it = map.lower_bound(keyValue); // greater or equal
316
317
    // if exact match found
318
    if (it != map.end() && it->first == keyValue) {
319
        CacheEntry &cacheEntry = it->second;
320
321
        // for event numbers there can be only one exact match so we can safely return it independently of matchKind
322
        if (isEventNumber(key)) {
323
            foundOffset = cacheEntry.beginOffset;
324
            return true;
325
        }
326
        else {
327
            // for simulation times we must consider whether the cache entry is complete or not by looking around it
328
            typename std::map<T, CacheEntry>::iterator itUpper = it;
329
            typename std::map<T, CacheEntry>::iterator itLower = it;
330
331
            ++itUpper;
332
            if (itLower != map.begin())
333
                --itLower;
334
            else
335
                itLower = map.end();
336
337
            bool completeBegin = itLower != map.end() && itLower->second.endOffset == cacheEntry.beginOffset;
338
            bool completeEnd = itUpper != map.end() && itUpper->second.beginOffset == cacheEntry.endOffset;
339
340
            // dispatching on match kind is required
341
            switch (matchKind) {
342
                case EXACT:
343
                    if (completeBegin && completeEnd) {
344
                        Assert(cacheEntry.beginEventNumber == cacheEntry.endEventNumber);
345
                        foundOffset = cacheEntry.beginOffset;
346
                        return true;
347
                    }
348
                    break;
349
                case FIRST_OR_PREVIOUS:
350
                case FIRST_OR_NEXT:
351
                    if (completeBegin) {
352
                        foundOffset = cacheEntry.beginOffset;
353
                        return true;
354
                    }
355
                    break;
356
                case LAST_OR_PREVIOUS:
357
                case LAST_OR_NEXT:
358
                    if (completeEnd) {
359
                        foundOffset = cacheEntry.endEventBeginOffset;
360
                        return true;
361
                    }
362
                    break;
363
            }
364
365
            // cannot exactly determine from cache
366
            lowerKey = key;
367
            lowerOffset = cacheEntry.beginOffset;
368
            upperKey = key;
369
            upperOffset = cacheEntry.endOffset;
370
            // an event's begin offset must be returned
371
            foundOffset = cacheEntry.beginOffset;
372
            return false;
373
        }
374
    }
375
    else {
376
        // upper iterator refers to the closest element after the key
377
        typename std::map<T, CacheEntry>::iterator itUpper = it;
378
        if (itUpper != map.end()) {
379
            CacheEntry &cacheEntry = itUpper->second;
380
            cacheEntry.getBeginKey(upperKey);
381
            upperOffset = cacheEntry.beginOffset;
382
        }
383
        else {
384
            upperKey = getKey(key, getLastEventNumber(), getLastSimulationTime());
385
            upperOffset = reader->getFileSize(); // this has to match last event's end offset
386
        }
387
388
        // lower iterator refers to the closest element before the key
389
        typename std::map<T, CacheEntry>::iterator itLower = it;
390
        if (!map.empty() && itLower != map.begin()) {
391
            --itLower;
392
            CacheEntry &cacheEntry = itLower->second;
393
            cacheEntry.getEndKey(lowerKey);
394
            lowerOffset = cacheEntry.endOffset;
395
        }
396
        else {
397
            lowerKey = getKey(key, getFirstEventNumber(), getFirstSimulationTime());
398
            lowerOffset = getFirstEventOffset();
399
        }
400
401
        // if the closest element before and after are subsequent elements
402
        // then the cache is complete around the key so the exact offset can be determined
403
        if (lowerOffset == upperOffset) {
404
            switch (matchKind) {
405
                case EXACT:
406
                    // we did not get an exact match in the first place (see above)
407
                    foundOffset = -1;
408
                    break;
409
                case FIRST_OR_PREVIOUS:
410
                case LAST_OR_PREVIOUS:
411
                    if (itLower == map.end())
412
                        foundOffset = -1;
413
                    else
414
                        foundOffset = itLower->second.endEventBeginOffset;
415
                    break;
416
                case FIRST_OR_NEXT:
417
                case LAST_OR_NEXT:
418
                    if (itUpper == map.end())
419
                        foundOffset = -1;
420
                    else
421
                        foundOffset = itUpper->second.beginOffset;
422
                    break;
423
            }
424
425
            return true;
426
        }
427
        else {
428
            // not possible to determine exact offset from cache
429
            foundOffset = -1;
430
            return false;
431
        }
432
    }
433
}
434
435
template <typename T> file_offset_t EventLogIndex::binarySearchForOffset(T key, MatchKind matchKind, T& lowerKey, T& upperKey, file_offset_t& lowerOffset, file_offset_t& upperOffset)
436
{
437
    Assert(key >= 0);
438
    file_offset_t foundOffset, middleEventBeginOffset, middleEventEndOffset;
439
    eventnumber_t middleEventNumber;
440
    simtime_t middleSimulationTime;
441
442
    /**
443
     * Binary search
444
     *
445
     * IMPORTANT NOTE: lowerOffset will always be exactly on an "E" line
446
     * (that of lowerKey), but upperOffset will NOT! This is necessary
447
     * for the distance between lowerOffset and upperOffset to shrink properly.
448
     */
449
    int stepCount = 0;
450
451
    while (true) {
452
        stepCount++;
453
        file_offset_t middleOffset = (upperOffset + lowerOffset) / 2;
454
        //printf("step %d: offsets: lo=%ld, up=%ld, middle=%ld \t\tkey#: lo=#%ld\n", stepCount, lowerOffset, upperOffset, middleOffset, lowerKey);
455
456
        if (readToEventLine(true, middleOffset, middleEventNumber, middleSimulationTime, middleEventBeginOffset, middleEventEndOffset)) {
457
            //printf("  found event #%ld at offset=%ld\n", middleEventNumber, middleEventBeginOffset);
458
            T middleKey = getKey(key, middleEventNumber, middleSimulationTime);
459
460
            // assign "middle" to "lower" or "upper"
461
            if (middleKey < key) {
462
                lowerKey = middleKey;
463
                lowerOffset = lowerOffset == middleEventBeginOffset ? middleEventBeginOffset + 1 : middleEventBeginOffset;
464
            }
465
            else if (middleKey > key) {
466
                upperKey = middleKey;
467
                upperOffset = upperOffset == middleOffset ? middleOffset - 1 : middleOffset;
468
            }
469
            // stopping condition
470
            else if (middleKey == key) {
471
                lowerKey = upperKey = key;
472
                foundOffset = lowerOffset = upperOffset = middleEventBeginOffset;
473
                break;
474
            }
475
        }
476
        else {
477
            //printf("  NOTHING found, decreasing upperOffset\n");
478
479
            // no key found -- we must be at the very end of the file.
480
            // try again finding an "E" line from a bit earlier point in the file.
481
            upperOffset = middleOffset;
482
        }
483
484
        if (lowerOffset >= upperOffset) {
485
            foundOffset = -1;
486
            break;
487
        }
488
    }
489
490
    if (PRINT_DEBUG_MESSAGES) printf("Binary search steps: %d\n", stepCount);
491
492
    return foundOffset;
493
}
494
495
template <typename T> file_offset_t EventLogIndex::linearSearchForOffset(T key, file_offset_t beginOffset, bool forward, bool exactMatchRequired)
496
{
497
    Assert(beginOffset >= 0);
498
499
    eventnumber_t eventNumber;
500
    simtime_t simulationTime;
501
    file_offset_t lineBeginOffset, lineEndOffset;
502
    file_offset_t previousOffset = beginOffset;
503
504
    while (beginOffset != -1)
505
    {
506
        bool readEventLine = readToEventLine(forward, beginOffset, eventNumber, simulationTime, lineBeginOffset, lineEndOffset);
507
508
        if (!readEventLine) {
509
            if (exactMatchRequired)
510
                return previousOffset;
511
            else
512
                return -1;
513
        }
514
515
        T readKey = getKey(key, eventNumber, simulationTime);
516
517
        if (!exactMatchRequired) {
518
            if (forward) {
519
                if (readKey > key)
520
                    return lineBeginOffset;
521
            }
522
            else {
523
                if (readKey < key)
524
                    return lineBeginOffset;
525
            }
526
        }
527
        else if (readKey != key)
528
            return previousOffset;
529
530
        previousOffset = lineBeginOffset;
531
532
        if (forward)
533
            beginOffset = lineEndOffset;
534
        else
535
            beginOffset = lineBeginOffset;
536
    }
537
538
    return -1;
539
}
540
541
bool EventLogIndex::readToEventLine(bool forward, file_offset_t readStartOffset, eventnumber_t& eventNumber, simtime_t& simulationTime, file_offset_t& lineStartOffset, file_offset_t& lineEndOffset)
542
{
543
    Assert(readStartOffset >= 0);
544
    eventNumber = -1;
545
    simulationTime = simtime_nil;
546
    reader->seekTo(readStartOffset);
547
548
    char *line;
549
550
    if (PRINT_DEBUG_MESSAGES) printf("Reading to first event line from offset: %"LL"d in direction: %s\n", readStartOffset, forward ? "forward" : "backward");
551
552
    // find first "E" line, return false if none found
553
    while (true)
554
    {
555
        if (forward)
556
            line = reader->getNextLineBufferPointer();
557
        else
558
            line = reader->getPreviousLineBufferPointer();
559
560
        if (!line)
561
            return false;
562
563
        if (line[0] == 'E' && line[1] == ' ')
564
            break;
565
    }
566
567
    // find event number and simulation time in line ("# 12345 t 1.2345")
568
    tokenizer.tokenize(line, reader->getCurrentLineLength());
569
    lineStartOffset = reader->getCurrentLineStartOffset();
570
    lineEndOffset = reader->getCurrentLineEndOffset();
571
572
    int numTokens = tokenizer.numTokens();
573
    char **tokens = tokenizer.tokens();
574
575
    for (int i = 1; i < numTokens - 1; i += 2)
576
    {
577
        const char *token = tokens[i];
578
579
        if (token[0] == '#' && token[1] == '\0')
580
            eventNumber = EventLogEntry::parseEventNumber(tokens[i+1]);
581
        else if (token[0] == 't' && token[1] == '\0')
582
            simulationTime = EventLogEntry::parseSimulationTime(tokens[i+1]);
583
    }
584
585
    if (eventNumber != -1) {
586
        Assert(simulationTime != simtime_nil);
587
        cacheEntry(eventNumber, simulationTime, lineStartOffset, lineEndOffset);
588
        return true;
589
    }
590
591
    // bad luck
592
    throw opp_runtime_error("Wrong file format: no event number in 'E' line, line %d", reader->getNumReadLines());
593
}
594
595
void EventLogIndex::cacheEntry(eventnumber_t eventNumber, simtime_t simulationTime, file_offset_t beginOffset, file_offset_t endOffset)
596
{
597
    EventNumberToCacheEntryMap::iterator itEventNumber = eventNumberToCacheEntryMap.lower_bound(eventNumber);
598
599
    if (itEventNumber != eventNumberToCacheEntryMap.end() && itEventNumber->first == eventNumber)
600
        itEventNumber->second.include(eventNumber, simulationTime, beginOffset, endOffset);
601
    else
602
        eventNumberToCacheEntryMap[eventNumber] = CacheEntry(eventNumber, simulationTime, beginOffset, endOffset);
603
604
    SimulationTimeToCacheEntryMap::iterator itSimulationTime = simulationTimeToCacheEntryMap.lower_bound(simulationTime);
605
606
    if (itSimulationTime != simulationTimeToCacheEntryMap.end() && itSimulationTime->first == simulationTime)
607
        itSimulationTime->second.include(eventNumber, simulationTime, beginOffset, endOffset);
608
    else
609
        simulationTimeToCacheEntryMap[simulationTime] = CacheEntry(eventNumber, simulationTime, beginOffset, endOffset);
610
}
611
612
void EventLogIndex::ensureFirstEventAndLastEventCached()
613
{
614
    getFirstEventNumber();
615
    getLastEventNumber();
616
}
617
618
void EventLogIndex::dump()
619
{
620
    printf("eventNumberToCacheEntryMap:\n");
621
622
    for (EventNumberToCacheEntryMap::iterator it = eventNumberToCacheEntryMap.begin(); it != eventNumberToCacheEntryMap.end(); ++it)
623
        printf("  #%"LL"d --> offset %"LL"d (0x%"LL"x)\n", it->first, it->second.beginOffset, it->second.beginOffset);
624
625
    printf("simulationTimeToCacheEntryMap:\n");
626
627
    for (SimulationTimeToCacheEntryMap::iterator it = simulationTimeToCacheEntryMap.begin(); it != simulationTimeToCacheEntryMap.end(); ++it)
628
        printf("  %.*g --> offset %"LL"d (0x%"LL"x)\n", 12, it->first.dbl(), it->second.beginOffset, it->second.beginOffset);
629
}
630