Skip to content

Commit 5867985

Browse files
matthiasrichtersawenzel
matthiasrichter
authored and
sawenzel
committed
Adding table view abstraction for data sequences (AliceO2Group#581)
* Adding table view abstraction for data sequences Container class for multiple sequences of data wrapped by markers. This is a container for data sequences of multiple frames consisting of a header marker struct, a payload, and an optional trailer marker struct. Each sequence forms a row in the TableView, the columns are provided by the markers/frames. A parser is used to step through the data sequence and extract headers, trailers and payload positions. Factoring out the test frame allocator utility to a separate file to be used in multiple unit tests. Going to be made more general in the future. * Don't add the row desription for data sets without column structure
1 parent fb3247e commit 5867985

File tree

5 files changed

+584
-101
lines changed

5 files changed

+584
-101
lines changed

‎Algorithm/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ endif()
4040
set(TEST_SRCS
4141
test/headerstack.cxx
4242
test/parser.cxx
43+
test/tableview.cxx
4344
)
4445

4546
O2_GENERATE_TESTS(

‎Algorithm/include/Algorithm/TableView.h‎

Lines changed: 311 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,311 @@
1+
// Copyright CERN and copyright holders of ALICE O2. This software is
2+
// distributed under the terms of the GNU General Public License v3 (GPL
3+
// Version 3), copied verbatim in the file "COPYING".
4+
//
5+
// See http://alice-o2.web.cern.ch/license for full licensing information.
6+
//
7+
// In applying this license CERN does not waive the privileges and immunities
8+
// granted to it by virtue of its status as an Intergovernmental Organization
9+
// or submit itself to any jurisdiction.
10+
11+
#ifndef ALGORITHM_TABLEVIEW_H
12+
#define ALGORITHM_TABLEVIEW_H
13+
14+
/// @file TableView.h
15+
/// @author Matthias Richter
16+
/// @since 2017-09-21
17+
/// @brief Container class for multiple sequences of data wrapped by markers
18+
19+
namespace o2 {
20+
21+
namespace algorithm {
22+
23+
/**
24+
* @class TableView
25+
* Container class for multiple sequences of data wrapped by markers.
26+
*
27+
* This is a container for data sequences of multiple frames consisting
28+
* of a header marker struct, a payload, and an optional trailer marker
29+
* struct. Each sequence forms a row in the TableView, the columns
30+
* are provided by the markers/frames.
31+
*
32+
* A parser is used to step through the data sequence and extract
33+
* headers, trailers and payload positions.
34+
*
35+
* Requirements:
36+
* - both header and trailer type must provide an operator bool() method
37+
* to check validity
38+
* - the size of one frame needs to be extracted either from the header
39+
* marker or the trailer marker. The first requires forward, the latter
40+
* backward parsing. In the first case, the trailer is optional, while
41+
* in the latter required
42+
*
43+
*/
44+
template<typename RowDescT, // row description
45+
typename ColumnDescT, // column description
46+
typename ParserT // parser type (forward/backward)
47+
>
48+
class TableView {
49+
public:
50+
TableView() = default;
51+
~TableView() = default;
52+
53+
using RowDescType = RowDescT;
54+
using ColumnIndexType = ColumnDescT;
55+
using ParserType = ParserT;
56+
57+
/// FrameIndex is composed from column description and row number
58+
struct FrameIndex {
59+
ColumnIndexType columnIndex;
60+
unsigned row;
61+
62+
bool operator<(const FrameIndex& rh) const {
63+
if (rh.columnIndex < columnIndex) return false;
64+
if (columnIndex < rh.columnIndex) return true;
65+
return row < rh.row;
66+
}
67+
};
68+
69+
/// descriptor pointing to payload of one frame
70+
struct FrameData {
71+
const byte* buffer = nullptr;
72+
size_t size = 0;
73+
};
74+
75+
/**
76+
* Add a new data sequence, the set is traversed according to parser
77+
*
78+
* TODO: functors to check header and trailer validity as well as retrieving
79+
* the frame size could be passed as arguments.
80+
*
81+
* @param rowData Descriptive data struct for the sequence
82+
* @param seqData Pointer to sequence
83+
* @param seqSize Length of sequence
84+
* @return number of inserted elements
85+
*/
86+
size_t addRow(RowDescType rowData, byte* seqData, size_t seqSize) {
87+
unsigned nFrames = mFrames.size();
88+
unsigned currentRow = mRowData.size();
89+
ParserType p;
90+
p.parse(seqData, seqSize,
91+
[](const typename ParserT::HeaderType& h) {return (h);},
92+
[](const typename ParserT::TrailerType& t) {return (t);},
93+
[](const typename ParserT::TrailerType& t) {
94+
return t.dataLength + ParserT::totalOffset;
95+
},
96+
[this, currentRow](typename ParserT::FrameInfo entry) {
97+
// insert the header as column index in ascending order
98+
auto position = mColumns.begin();
99+
while (position != mColumns.end() && *position < *entry.header) {
100+
position++;
101+
}
102+
if (position == mColumns.end() || *entry.header < *position) {
103+
mColumns.emplace(position, *entry.header);
104+
}
105+
106+
// insert frame descriptor under key composed from header and row
107+
auto result = mFrames.emplace(FrameIndex{*entry.header, currentRow},
108+
FrameData{entry.payload, entry.length});
109+
return result.second;
110+
}
111+
);
112+
auto insertedFrames = mFrames.size() - nFrames;
113+
if (insertedFrames > 0) {
114+
mRowData.emplace_back(rowData);
115+
}
116+
return insertedFrames;
117+
}
118+
119+
/// clear the index, i.e. all internal lists
120+
void clear() {
121+
mFrames.clear();
122+
mColumns.clear();
123+
mRowData.clear();
124+
}
125+
126+
/// get number of columns in the created index
127+
size_t getNColumns() const {return mColumns.size();}
128+
129+
/// get number of rows, i.e. number rows in the created index
130+
size_t getNRows() const {return mRowData.size();}
131+
132+
/// get row data for a data set
133+
const RowDescType& getRowData(size_t row) const {
134+
if (row < mRowData.size()) return mRowData[row];
135+
// TODO: better to throw exception?
136+
static RowDescType dummy;
137+
return dummy;
138+
}
139+
140+
// TODO:
141+
// instead of a member with this pointer of parent class, the access
142+
// function was supposed to be specified as a lambda. This definition
143+
// was supposed to be the type of the function member.
144+
// passing the access function to the iterator did not work because
145+
// the typedef for the access function is without the capture, so there
146+
// is no matching conversion.
147+
// Solution would be to use std::function but that's probably slow and
148+
// the function is called often. Can be checked later.
149+
typedef FrameData (*AccessFct)(unsigned, unsigned);
150+
151+
/// Iterator class for configurable direction, i.e. either row or column
152+
class iterator { // TODO: derive from forward_iterator
153+
public:
154+
using self_type = iterator;
155+
using value_type = FrameData;
156+
157+
enum IteratorDirections {
158+
kAlongRow,
159+
kAlongColumn
160+
};
161+
162+
iterator() = delete;
163+
~iterator() = default;
164+
iterator(IteratorDirections direction, TableView* parent, unsigned row = 0, unsigned column = 0)
165+
: mDirection(direction)
166+
, mRow(row)
167+
, mColumn(column)
168+
, mEnd(direction==kAlongRow?parent->getNColumns():parent->getNRows())
169+
, mParent(parent)
170+
, mCache()
171+
, mIsCached(false)
172+
{
173+
while (!isValid() && !isEnd()) operator++();
174+
}
175+
176+
self_type& operator++() {
177+
mIsCached = false;
178+
if (mDirection==kAlongRow) {
179+
if (mColumn<mEnd) mColumn++;
180+
} else {
181+
if (mRow<mEnd) mRow++;
182+
}
183+
while (!isEnd() && !isValid()) operator++();
184+
return *this;
185+
}
186+
187+
value_type operator*() const {
188+
if (!mIsCached) {
189+
self_type* ncthis = const_cast<self_type*>(this);
190+
mParent->get(mRow, mColumn, ncthis->mCache);
191+
ncthis->mIsCached = true;
192+
}
193+
return mCache;
194+
}
195+
196+
bool operator==(const self_type& other) const {
197+
return mDirection==kAlongRow?(mColumn == other.mColumn):(mRow == other.mRow);
198+
}
199+
200+
bool operator!=(const self_type& other) const {
201+
return mDirection==kAlongRow?(mColumn != other.mColumn):(mRow != other.mRow);
202+
}
203+
204+
bool isEnd() const {
205+
return (mDirection==kAlongRow)?(mColumn>=mEnd):(mRow>=mEnd);
206+
}
207+
208+
bool isValid() const {
209+
if (!mIsCached) {
210+
self_type* ncthis = const_cast<self_type*>(this);
211+
ncthis->mIsCached = mParent->get(mRow, mColumn, ncthis->mCache);
212+
}
213+
return mIsCached;
214+
}
215+
216+
const RowDescType& getRowData() const {
217+
static RowDescType invalid;
218+
return invalid;
219+
}
220+
221+
protected:
222+
IteratorDirections mDirection;
223+
unsigned mRow;
224+
unsigned mColumn;
225+
unsigned mEnd;
226+
TableView* mParent;
227+
value_type mCache;
228+
bool mIsCached;
229+
};
230+
231+
/// iterator for the outer access of the index, either row or column direction
232+
template<unsigned Direction>
233+
class outerIterator : public iterator {
234+
public:
235+
using base = iterator;
236+
using value_type = typename base::value_type;
237+
using self_type = outerIterator;
238+
static const unsigned direction = Direction;
239+
240+
outerIterator() = delete;
241+
~outerIterator() = default;
242+
outerIterator(TableView* parent, unsigned index)
243+
: iterator(typename iterator::IteratorDirections(direction), parent, direction==iterator::kAlongColumn?index:0, direction==iterator::kAlongRow?index:0) {
244+
}
245+
246+
self_type& operator++() {
247+
if (base::mDirection==iterator::kAlongRow) {
248+
if (base::mColumn<base::mEnd) base::mColumn++;
249+
} else {
250+
if (base::mRow<base::mEnd) base::mRow++;
251+
}
252+
return *this;
253+
}
254+
255+
/// begin the inner iteration
256+
iterator begin() {
257+
return iterator((base::mDirection==iterator::kAlongColumn)?iterator::kAlongRow:iterator::kAlongColumn,
258+
base::mParent,
259+
(base::mDirection==iterator::kAlongColumn)?base::mRow:0,
260+
(base::mDirection==iterator::kAlongRow)?base::mColumn:0);
261+
}
262+
263+
/// end of the inner iteration
264+
iterator end() {
265+
return iterator((base::mDirection==iterator::kAlongColumn)?iterator::kAlongRow:iterator::kAlongColumn,
266+
base::mParent,
267+
(base::mDirection==iterator::kAlongRow)?base::mParent->getNRows():0,
268+
(base::mDirection==iterator::kAlongColumn)?base::mParent->getNColumns():0);
269+
}
270+
};
271+
272+
/// definition of the outer iterator over column
273+
using ColumnIterator = outerIterator<iterator::kAlongRow>;
274+
/// definition of the outer iterator over row
275+
using RowIterator = outerIterator<iterator::kAlongColumn>;
276+
277+
/// begin of the outer iteration
278+
ColumnIterator begin() {
279+
return ColumnIterator(this, 0);
280+
}
281+
282+
/// end of outer iteration
283+
ColumnIterator end() {
284+
return ColumnIterator(this, mColumns.size());
285+
}
286+
287+
private:
288+
/// private access function for the iterators
289+
bool get(unsigned row, unsigned column, FrameData& data) {
290+
if (this->mColumns.size() == 0) return false;
291+
auto element = this->mFrames.find(FrameIndex{this->mColumns[column], row});
292+
if (element != this->mFrames.end()) {
293+
data = element->second;
294+
return true;
295+
}
296+
return false;
297+
}
298+
299+
/// map of frame descriptors with key composed from header and row number
300+
std::map<FrameIndex, FrameData> mFrames;
301+
/// list of indices in row direction
302+
std::vector<ColumnIndexType> mColumns;
303+
/// data descriptor of each row forming the columns
304+
std::vector<RowDescType> mRowData;
305+
};
306+
307+
} // namespace algorithm
308+
309+
} // namespace o2
310+
311+
#endif // ALGORITHM_TABLEVIEW_H

0 commit comments

Comments
 (0)