dynArray.hh

Go to the documentation of this file.
1 
6 #ifndef dynarray_hh
7 #define dynarray_hh
8 
10 #include "basics/exceptions.hh"
11 #include "basics/typedefs.hh"
12 #include "basics/debug.hh"
13 
14 // debugging
15 #define DynArrayPageConstr_D 0
16 #define DynArrayDestr_D 0
17 #define DynArrayIndex_D 0
18 
19 namespace concepts {
20 
21  // ********************************************************** DynArrayBase **
22 
27  class DynArrayBase : public virtual OutputOperator {
28  public:
29  DynArrayBase(const uint htblsz, const uint htblmsk,
30  const uint pgsz, const uint pgmsk,
31  const bool init = false);
33  DynArrayBase(const DynArrayBase& base);
34  virtual ~DynArrayBase();
35 
37  uint max() const { return max_; }
38 
40  uint min() const { return min_; }
41  protected:
42  bool init_;
43  bool empty_;
44  uint max_;
45  uint min_;
46  uint npg_;
47 
49  const uint htblsz_;
50 
52  const uint htblmsk_;
53 
55  const uint pgsz_;
56  const uint pgmsk_;
57 
60  }
61 
62  virtual std::ostream& info(std::ostream& os) const;
63  };
64 
65  // ********************************************************** DynArrayPage **
66 
71  template <class T>
72  class DynArrayPage {
74  uint idx_;
75  uint sz_;
76  T* mem_;
77  public:
78  DynArrayPage(uint idx, uint sz, DynArrayPage* lnk = 0) :
79  lnk_(lnk), idx_(idx), sz_(sz), mem_(new T[sz]) {
80  DEBUGL(DynArrayPageConstr_D, "done.");
81  }
84  lnk_(0), idx_(pg.idx_), sz_(pg.sz_), mem_(new T[sz_]) {
85  std::memcpy(mem_, pg.mem_, sz_*sizeof(T));
86  if (pg.lnk_)
87  lnk_ = new DynArrayPage<T>(*pg.lnk_);
88  }
89  ~DynArrayPage() { delete[] mem_; }
90 
91  T& operator[](uint i) { return mem_[i]; }
92 
93  uint index() const { return idx_; }
94  DynArrayPage* link() const { return lnk_; }
95  };
96 
97  // ************************************************************** DynArray **
98 
104  template <class T>
105  class DynArray : public DynArrayBase {
106  public:
121  inline DynArray(uint htblsz = 2, uint pgsz = 2);
122  inline DynArray(uint htblsz, uint pgsz, const T& dflt);
124  inline DynArray(const DynArray& d);
125  inline ~DynArray();
126 
134  T& operator [](uint i);
135 
140  const T& operator [](uint i) const;
141 
145  bool isElm(uint i);
146  const bool isElm(uint i) const;
147 
149  inline float memory() const;
150 
152  void reset();
153  protected:
154  virtual std::ostream& info(std::ostream& os) const;
155  private:
158  T dflt_;
159  };
160 
161  template<class T>
162  DynArray<T>::DynArray(uint htblsz, uint pgsz) :
163  DynArrayBase(htblsz, (1 << htblsz) - 1, pgsz, (1 << pgsz) - 1, false),
164  htbl_(new DynArrayPage<T>*[htblmsk_ + 1]), lru_(0) {
165  for(uint i = htblmsk_ + 1; i--;)
166  htbl_[i] = 0;
167  }
168 
169  template<class T>
170  DynArray<T>::DynArray(uint htblsz, uint pgsz, const T& dflt) :
171  DynArrayBase(htblsz, (1 << htblsz) - 1, pgsz, (1 << pgsz) - 1, true),
172  htbl_(new DynArrayPage<T>*[htblmsk_ + 1]), lru_(0), dflt_(dflt) {
173  for(uint i = htblmsk_ + 1; i--;)
174  htbl_[i] = 0;
175  }
176 
177  template <class T>
179  : DynArrayBase(d), htbl_(new DynArrayPage<T>*[htblmsk_ + 1]),
180  lru_(0), dflt_(d.dflt_) {
181  for(uint i = d.htblmsk_ + 1; i--;)
182  if (d.htbl_[i])
183  htbl_[i] = new DynArrayPage<T>(*d.htbl_[i]);
184  }
185 
186  template <class T>
188  DEBUGL(DynArrayDestr_D, "start.");
189  for(uint i = htblmsk_ + 1; i--;) {
190  DynArrayPage<T>* pg = htbl_[i];
191  while (pg != NULL) {
192  DynArrayPage<T>* foo = pg; pg = pg->link();
193  delete foo;
194  }
195  }
196  delete[] htbl_;
197  DEBUGL(DynArrayDestr_D, "done.");
198  }
199 
200  template <class T>
202  DEBUGL(DynArrayIndex_D, "i = " << i);
203 
204  if (!(i < max_))
205  max_ = i + 1;
206  if (lru_ == NULL || i < min_)
207  min_ = i;
208 
209  uint pgidx = i >> pgsz_;
210 
211  if (lru_ != NULL && lru_->index() == pgidx)
212  return (*lru_)[i & pgmsk_];
213 
214  DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);
215 
216  DynArrayPage<T>* pg = *htbl;
217  while(pg != 0) {
218  if (pg->index() == pgidx)
219  return (*(lru_ = pg))[i & pgmsk_];
220  pg = pg->link();
221  }
222 
223  *htbl = pg = new DynArrayPage<T>(pgidx, pgmsk_ + 1, *htbl);
224  npg_++;
225  if (init_)
226  for(uint j = pgmsk_ + 1; j--;)
227  (*pg)[j] = dflt_;
228 
229  return (*(lru_ = pg))[i & pgmsk_];
230  }
231 
232  template <class T>
233  const T& DynArray<T>::operator[](uint i) const {
234 
235  if (!(i < max_)) {
236  DEBUGL(DynArrayIndex_D, *this);
237  DEBUGL(DynArrayIndex_D, "i = " << i);
239  }
240  if (lru_ == NULL || i < min_) {
241  DEBUGL(DynArrayIndex_D, *this);
242  DEBUGL(DynArrayIndex_D, "i = " << i);
244  }
245 
246  uint pgidx = i >> pgsz_;
247 
248  if (lru_ != NULL && lru_->index() == pgidx)
249  return (*lru_)[i & pgmsk_];
250 
251  DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);
252 
253  DynArrayPage<T>* pg = *htbl;
254  while(pg != 0) {
255  if (pg->index() == pgidx)
256  return (*pg)[i & pgmsk_];
257  pg = pg->link();
258  }
259  DEBUGL(DynArrayIndex_D, *this);
260  DEBUGL(DynArrayIndex_D, "i = " << i);
262  }
263 
264  template <class T>
265  bool DynArray<T>::isElm(uint i) {
266 
267  if (!(i < max_)) return 0;
268  if (lru_ == 0 || i < min_) return 0;
269 
270  uint pgidx = i >> pgsz_;
271 
272  if (lru_ != 0 && lru_->index() == pgidx)
273  return (init_) ? ((*lru_)[i & pgmsk_] != dflt_) : 1;
274 
275  DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);
276 
277  DynArrayPage<T>* pg = *htbl;
278  while(pg != 0) {
279  if (pg->index() == pgidx) {
280  lru_ = pg;
281  return (init_) ? ((*lru_)[i & pgmsk_] != dflt_) : 1;
282  }
283  pg = pg->link();
284  }
285  return 0;
286  }
287 
288  template <class T>
289  const bool DynArray<T>::isElm(uint i) const {
290 
291  if (!(i < max_)) return 0;
292  if (lru_ == 0 || i < min_) return 0;
293 
294  uint pgidx = i >> pgsz_;
295 
296  DynArrayPage<T>* lru = lru_;
297 
298  if (lru != 0 && lru->index() == pgidx)
299  return (init_) ? (&(*lru)[i & pgmsk_] != &dflt_) : 1;
300 
301  DynArrayPage<T>** htbl = htbl_ + (pgidx & htblmsk_);
302 
303  DynArrayPage<T>* pg = *htbl;
304  while(pg != 0) {
305  if (pg->index() == pgidx) {
306  lru = pg;
307  return (init_) ? ((*lru)[i & pgmsk_] != dflt_) : 1;
308  }
309  pg = pg->link();
310  }
311  return 0;
312  }
313 
314  template <class T>
315  inline float DynArray<T>::memory() const {
316  return sizeof(DynArray) + (float)(1 << htblsz_) *
317  sizeof(DynArrayPage<T>*) + (float)npg_ *
318  (sizeof(DynArrayPage<T>) + (float)(1 << pgsz_) * sizeof(T));
319  }
320 
321  template <class T>
323  for(uint i = htblmsk_ + 1; i--;) {
324  DynArrayPage<T>* pg = htbl_[i];
325  while (pg != NULL) {
326  DynArrayPage<T>* foo = pg;
327  pg = pg->link();
328  delete foo;
329  }
330  htbl_[i] = NULL;
331  }
332  lru_ = NULL; max_ = min_ = 0; npg_ = 0;
333  }
334 
335  template <class T>
336  std::ostream& DynArray<T>::info(std::ostream& os) const {
337  os << concepts::typeOf(*this)<<"(init = " << init_ << ", emtpy = " << empty_
338  << ", min = " << min_ << ", max = " << max_ << ", npg = "
339  << npg_ << ", htblsz = " << htblsz_ << ", htblmsk = "
340  << htblmsk_ << ", pgsz = " << pgsz_ << ", pgmsk = " << pgmsk_
341  << ", [" << std::endl;
342  for(uint i = htblmsk_ + 1; i--;) {
343  DynArrayPage<T>* pg = htbl_[i];
344  while (pg != NULL) {
345  uint pgidx = pg->index();
346  os << pgidx << " | ";
347  for (uint j = 0; j <= pgmsk_; ++j)
348  os << '(' << (pgidx << pgsz_) + j << ", " << (*pg)[j] << "), ";
349  pg = pg->link();
350  os << std::endl;
351  }
352  }
353  os << "])";
354  return os;
355  }
356 
357 } // namespace concepts
358 
359 #endif // dynarray_hh
#define DynArrayIndex_D
Definition: dynArray.hh:17
DynArrayPage(uint idx, uint sz, DynArrayPage *lnk=0)
Definition: dynArray.hh:78
void operator=(DynArrayBase &)
Definition: dynArray.hh:58
uint max() const
Maximal referenced index + 1.
Definition: dynArray.hh:37
void init()
Before using conceptspy make sure to call this routine.
#define conceptsException(exc)
Prepares an exception for throwing.
Definition: exceptions.hh:344
Base class for exceptions.
Definition: exceptions.hh:86
DynArrayPage(const DynArrayPage &pg)
Copy constructor of the whole queue.
Definition: dynArray.hh:83
Container class: a dynamic array.
Definition: mesh.hh:30
A page of a dynamic array.
Definition: dynArray.hh:72
DynArrayPage * lnk_
Definition: dynArray.hh:73
virtual std::ostream & info(std::ostream &os) const
Returns information in an output stream.
const uint pgsz_
Size of a page in number of entries.
Definition: dynArray.hh:55
T & operator[](uint i)
Index operator for the container.
Definition: dynArray.hh:201
DynArrayPage * link() const
Definition: dynArray.hh:94
DynArray(uint htblsz, uint pgsz, const T &dflt)
Definition: dynArray.hh:170
bool isElm(uint i)
Checks if the element is not equal to the default element.
Definition: dynArray.hh:265
#define DEBUGL(doit, msg)
virtual std::ostream & info(std::ostream &os) const
Definition: dynArray.hh:336
float memory() const
Approximate memory consumption in bytes.
Definition: dynArray.hh:315
uint index() const
Definition: dynArray.hh:93
DynArrayPage< T > * lru_
Definition: dynArray.hh:157
DynArrayBase(const DynArrayBase &base)
Copy constructor.
uint min() const
Minimal referenced index.
Definition: dynArray.hh:40
DynArray(uint htblsz=2, uint pgsz=2)
Constructor.
Definition: dynArray.hh:162
T & operator[](uint i)
Definition: dynArray.hh:91
#define DynArrayDestr_D
Definition: dynArray.hh:16
DynArrayBase(const uint htblsz, const uint htblmsk, const uint pgsz, const uint pgmsk, const bool init=false)
const uint htblmsk_
Hash table mask.
Definition: dynArray.hh:52
DynArray(const DynArray &d)
Copy constructor.
Definition: dynArray.hh:178
void reset()
Clears the array.
Definition: dynArray.hh:322
Exception class to express that an index in a dynamic array does not exist.
Definition: exceptions.hh:191
const bool isElm(uint i) const
Definition: dynArray.hh:289
Base class for DynArray for the non-template part.
Definition: dynArray.hh:27
std::string typeOf(const T &t)
Return the typeid name of a class object.
Definition: output.hh:43
DynArrayPage< T > ** htbl_
Definition: dynArray.hh:156
const uint htblsz_
Size of the hash table function (how many bits of the page number)
Definition: dynArray.hh:49
Class providing an output operator.
#define DynArrayPageConstr_D
Definition: dynArray.hh:15
Basic namespace for Concepts-2.
Definition: pml_formula.h:16
Page URL: http://wiki.math.ethz.ch/bin/view/Concepts/WebHome
21 August 2020
© 2020 Eidgenössische Technische Hochschule Zürich