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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
/*
* include/util/Cursor.h
*
* Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
* Dong Xie <dongx@psu.edu>
*
* All rights reserved. Published under the Modified BSD License.
*
*/
#pragma once
#include "util/base.h"
#include "util/Record.h"
#include "io/PagedFile.h"
namespace de {
template<typename K, typename V, typename W=void>
struct Cursor {
Record<K,V,W> *ptr;
const Record<K,V,W> *end;
size_t cur_rec_idx;
size_t rec_cnt;
friend bool operator==(const Cursor &a, const Cursor &b) {
return a.ptr == b.ptr && a.end == b.end;
}
};
/*
* Advance the cursor to the next record. If the cursor is backed by an
* iterator, will attempt to advance the iterator once the cursor reaches its
* end and reset the cursor to the beginning of the read page.
*
* If the advance succeeds, ptr will be updated to point to the new record
* and true will be returned. If the advance reaches the end, then ptr will
* be updated to be equal to end, and false will be returned. Iterators will
* not be closed.
*/
template<typename K, typename V, typename W>
inline static bool advance_cursor(Cursor<K,V,W> &cur, PagedFileIterator *iter = nullptr) {
cur.ptr++;
cur.cur_rec_idx++;
if (cur.cur_rec_idx >= cur.rec_cnt) return false;
if (cur.ptr >= cur.end) {
if (iter && iter->next()) {
cur.ptr = (Record<K,V,W>*)iter->get_item();
cur.end = cur.ptr + (PAGE_SIZE / sizeof(Record<K,V,W>));
return true;
}
return false;
}
return true;
}
/*
* Process the list of cursors to return the cursor containing the next
* largest element. Does not advance any of the cursors. If current is
* specified, then skip the current head of that cursor during checking.
* This allows for "peaking" at the next largest element after the current
* largest is processed.
*/
template <typename K, typename V, typename W>
inline static Cursor<K,V,W> *get_next(std::vector<Cursor<K,V,W>> &cursors, Cursor<K,V,W> *current=nullptr) {
const Record<K,V,W> *min_rec = nullptr;
Cursor<K,V,W> *result = nullptr;
for (size_t i=0; i< cursors.size(); i++) {
if (cursors[i] == (Cursor<K,V,W>) {0} ) continue;
const Record<K,V,W> *rec = (&cursors[i] == current) ? cursors[i].ptr + 1 : cursors[i].ptr;
if (rec >= cursors[i].end) continue;
if (min_rec == nullptr) {
result = &cursors[i];
min_rec = rec;
continue;
}
if (*rec < *min_rec) {
result = &cursors[i];
min_rec = rec;
}
}
return result;
}
}
|