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-2019 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_DB_PAGED_ARRAY_HH
22 #define OST_DB_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{ namespace db{
34 
35 template <typename T, uint64_t P>
36 class PagedArray {
37 private:
38  typedef std::vector<T> Page;
39 public:
40  typedef T value_type;
41 
43 
45  {
46  return pages_[this->GetPage(i)][this->GetOffset(i)];
47  }
48 
49  const T& operator[](uint64_t i) const
50  {
51  return pages_[this->GetPage(i)][this->GetOffset(i)];
52  }
53 
54  void push_back(const T& t)
55  {
56  if (pages_.empty()) {
57  pages_.push_back(Page());
58  pages_.back().reserve(P);
59  }
60  if (pages_.back().size()==P) {
61  pages_.push_back(Page());
62  pages_.back().reserve(P);
63  }
64  pages_.back().push_back(t);
65  }
66  uint64_t size() const
67  {
68  if (pages_.empty()) {
69  return 0;
70  } else {
71  return static_cast<uint64_t>((pages_.size()-1)*P+pages_.back().size());
72  }
73  }
74 
75  bool empty() const
76  {
77  return pages_.empty();
78  }
79 
80  void clear()
81  {
82  pages_.clear();
83  }
84 
85  // clears everything in [from, to[ and shifts every datapoint after the specified
86  // range at the location defined by from
87  void ClearRange(uint64_t from, uint64_t to)
88  {
89  if(to <= from) return; // invalid range
90  uint64_t current_size = this->size();
91  if(from >= current_size) return; // nothing to delete
92  if(to > current_size) to = current_size; // from is in the valid range, but
93  // to is too large. Let's just kill
94  // [from, this->size()[
95 
96  uint64_t num_elements_to_shift = current_size - to;
97  for(uint64_t i = 0; i < num_elements_to_shift; ++i) {
98  (*this)[from + i] = (*this)[to + i];
99  }
100 
101  uint64_t num_elements_deleted = to - from;
102  uint64_t new_size = current_size - num_elements_deleted;
103  uint64_t new_last_element_idx = new_size - 1;
104  uint64_t new_last_page_idx = this->GetPage(new_last_element_idx);
105  pages_.resize(new_last_page_idx + 1);
106  uint64_t offset = this->GetOffset(new_last_element_idx);
107  pages_.back().resize(offset + 1);
108  }
109 
110 
111  void Write(std::ofstream& out_stream, bool treat_as_pod=true) const
112  {
113  if (treat_as_pod) {
114  uint64_t s=this->size();
115  out_stream.write(reinterpret_cast<char*>(&s), sizeof(uint64_t));
116  for (typename std::vector<Page>::const_iterator i=pages_.begin(),
117  e=pages_.end(); i!=e; ++i) {
118  out_stream.write(reinterpret_cast<const char*>(&i->front()),
119  i->size()*sizeof(T));
120  }
121  } else {
122  throw ost::Error("Cannot write non POD paged array!");
123  }
124  }
125  void Read(std::ifstream& in_stream, bool treat_as_pod=true)
126  {
127  if (treat_as_pod) {
128  uint64_t s;
129  in_stream.read(reinterpret_cast<char*>(&s), sizeof(uint64_t));
130  uint64_t num_pages=s/P+1;
131  pages_.resize(num_pages);
132  for (uint64_t i=0; i<num_pages; ++i) {
133  uint64_t left=std::min(P, s-i*P);
134  Page& p=pages_[i];
135  p.reserve(P);
136  p.resize(left);
137  in_stream.read(reinterpret_cast<char*>(&p.front()),
138  p.size()*sizeof(T));
139  }
140  } else {
141  throw ost::Error("Cannot load non POD paged array!");
142  }
143  }
144 
145  // portable serialization
146  // (cleanly element by element with fixed-width base-types)
147  template <typename DS>
148  void Serialize(DS& ds) {
149  // assumes that T is not a fundamental type!
150  ds & pages_;
151  }
152 
153  bool operator==(const PagedArray& rhs) const {
154  return pages_ == rhs.pages_;
155  }
156  bool operator!=(const PagedArray& rhs) const {
157  return !this->operator==(rhs);
158  }
159 
160 private:
161  uint64_t GetPage(uint64_t i) const { return i/P; }
162  uint64_t GetOffset(uint64_t i) const { return i % P; }
163  std::vector<Page> pages_;
164 };
165 
166 }} // ns
167 
168 #endif
uint64_t size() const
Definition: paged_array.hh:66
void push_back(const T &t)
Definition: paged_array.hh:54
bool operator!=(const PagedArray &rhs) const
Definition: paged_array.hh:156
void Write(std::ofstream &out_stream, bool treat_as_pod=true) const
Definition: paged_array.hh:111
T & operator[](uint64_t i)
Definition: paged_array.hh:44
unsigned __int64 uint64_t
Definition: stdint_msc.hh:90
void Read(std::ifstream &in_stream, bool treat_as_pod=true)
Definition: paged_array.hh:125
bool empty() const
Definition: paged_array.hh:75
void ClearRange(uint64_t from, uint64_t to)
Definition: paged_array.hh:87
void Serialize(DS &ds)
Definition: paged_array.hh:148
bool operator==(const PagedArray &rhs) const
Definition: paged_array.hh:153
const T & operator[](uint64_t i) const
Definition: paged_array.hh:49