OpenStructure
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
paged_array.hh
Go to the documentation of this file.
1 //------------------------------------------------------------------------------
2 // This file is part of the OpenStructure project <www.openstructure.org>
3 //
4 // Copyright (C) 2008-2020 by the OpenStructure authors
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License as published by the Free
8 // Software Foundation; either version 3.0 of the License, or (at your option)
9 // any later version.
10 // This library is distributed in the hope that it will be useful, but WITHOUT
11 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with this library; if not, write to the Free Software Foundation, Inc.,
17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 //------------------------------------------------------------------------------
19 
20 
21 #ifndef OST_PAGED_ARRAY_HH
22 #define OST_PAGED_ARRAY_HH
23 
24 /*
25  Author: Marco Biasini, Gabriel Studer
26  */
27 
28 #include <vector>
29 #include <fstream>
30 #include <ost/stdint.hh>
31 #include <ost/message.hh>
32 
33 namespace ost{
34 
35 
38 template <typename T, uint64_t P>
39 class PagedArray {
40 private:
41  typedef std::vector<T> Page;
42 public:
43  typedef T value_type;
44 
46 
48  {
49  return pages_[this->GetPage(i)][this->GetOffset(i)];
50  }
51 
52  const T& operator[](uint64_t i) const
53  {
54  return pages_[this->GetPage(i)][this->GetOffset(i)];
55  }
56 
57  void push_back(const T& t)
58  {
59  if (pages_.empty()) {
60  pages_.push_back(Page());
61  pages_.back().reserve(P);
62  }
63  if (pages_.back().size()==P) {
64  pages_.push_back(Page());
65  pages_.back().reserve(P);
66  }
67  pages_.back().push_back(t);
68  }
69  uint64_t size() const
70  {
71  if (pages_.empty()) {
72  return 0;
73  } else {
74  return static_cast<uint64_t>((pages_.size()-1)*P+pages_.back().size());
75  }
76  }
77 
78  bool empty() const
79  {
80  return pages_.empty();
81  }
82 
83  void clear()
84  {
85  pages_.clear();
86  }
87 
88  // clears everything in [from, to[ and shifts every datapoint after the specified
89  // range at the location defined by from
90  void ClearRange(uint64_t from, uint64_t to)
91  {
92  if(to <= from) return; // invalid range
93  uint64_t current_size = this->size();
94  if(from >= current_size) return; // nothing to delete
95  if(to > current_size) to = current_size; // from is in the valid range, but
96  // to is too large. Let's just kill
97  // [from, this->size()[
98 
99  uint64_t num_elements_to_shift = current_size - to;
100  for(uint64_t i = 0; i < num_elements_to_shift; ++i) {
101  (*this)[from + i] = (*this)[to + i];
102  }
103 
104  uint64_t num_elements_deleted = to - from;
105  uint64_t new_size = current_size - num_elements_deleted;
106  uint64_t new_last_element_idx = new_size - 1;
107  uint64_t new_last_page_idx = this->GetPage(new_last_element_idx);
108  pages_.resize(new_last_page_idx + 1);
109  uint64_t offset = this->GetOffset(new_last_element_idx);
110  pages_.back().resize(offset + 1);
111  }
112 
113 
114  void Write(std::ofstream& out_stream, bool treat_as_pod=true) const
115  {
116  if (treat_as_pod) {
117  uint64_t s=this->size();
118  out_stream.write(reinterpret_cast<char*>(&s), sizeof(uint64_t));
119  for (typename std::vector<Page>::const_iterator i=pages_.begin(),
120  e=pages_.end(); i!=e; ++i) {
121  out_stream.write(reinterpret_cast<const char*>(&i->front()),
122  i->size()*sizeof(T));
123  }
124  } else {
125  throw ost::Error("Cannot write non POD paged array!");
126  }
127  }
128  void Read(std::ifstream& in_stream, bool treat_as_pod=true)
129  {
130  if (treat_as_pod) {
131  uint64_t s;
132  in_stream.read(reinterpret_cast<char*>(&s), sizeof(uint64_t));
133  uint64_t num_pages=s/P+1;
134  pages_.resize(num_pages);
135  for (uint64_t i=0; i<num_pages; ++i) {
136  uint64_t left=std::min(P, s-i*P);
137  Page& p=pages_[i];
138  p.reserve(P);
139  p.resize(left);
140  in_stream.read(reinterpret_cast<char*>(&p.front()),
141  p.size()*sizeof(T));
142  if(!in_stream.good()) {
143  throw ost::Error("Failed to read data!");
144  }
145  }
146  } else {
147  throw ost::Error("Cannot load non POD paged array!");
148  }
149  }
150 
151  // portable serialization
152  // (cleanly element by element with fixed-width base-types)
153  template <typename DS>
154  void Serialize(DS& ds) {
155  // assumes that T is not a fundamental type!
156  ds & pages_;
157  }
158 
159  bool operator==(const PagedArray& rhs) const {
160  return pages_ == rhs.pages_;
161  }
162  bool operator!=(const PagedArray& rhs) const {
163  return !this->operator==(rhs);
164  }
165 
166 private:
167  uint64_t GetPage(uint64_t i) const { return i/P; }
168  uint64_t GetOffset(uint64_t i) const { return i % P; }
169  std::vector<Page> pages_;
170 };
171 
172 } // ns
173 
174 #endif
bool empty() const
Definition: paged_array.hh:78
const T & operator[](uint64_t i) const
Definition: paged_array.hh:52
unsigned __int64 uint64_t
Definition: stdint_msc.hh:90
void push_back(const T &t)
Definition: paged_array.hh:57
uint64_t size() const
Definition: paged_array.hh:69
void Write(std::ofstream &out_stream, bool treat_as_pod=true) const
Definition: paged_array.hh:114
bool operator==(const PagedArray &rhs) const
Definition: paged_array.hh:159
Vector style container that splits content in pages, suited for large amounts of data. Comes with serialization functionality.
Definition: paged_array.hh:39
bool operator!=(const PagedArray &rhs) const
Definition: paged_array.hh:162
void Read(std::ifstream &in_stream, bool treat_as_pod=true)
Definition: paged_array.hh:128
void ClearRange(uint64_t from, uint64_t to)
Definition: paged_array.hh:90
void Serialize(DS &ds)
Definition: paged_array.hh:154
T & operator[](uint64_t i)
Definition: paged_array.hh:47