TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
MyList.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <cstring>
29 #include <stdexcept>
30 
31 namespace tdzdd {
32 
33 template<typename T, size_t BLOCK_ELEMENTS = 1000>
34 class MyList {
35  static int const headerCells = 1;
36 
37  struct Cell {
38  Cell* next;
39  };
40 
41  Cell* front_;
42  size_t size_;
43 
44  static size_t numCells(size_t n) {
45  return (n + sizeof(Cell) - 1) / sizeof(Cell);
46  }
47 
48  static Cell* setFlag(Cell* p) {
49  return reinterpret_cast<Cell*>(reinterpret_cast<size_t>(p) | 1);
50  }
51 
52  static Cell* clearFlag(Cell* p) {
53  static size_t const mask = ~size_t(0) << 1;
54  return reinterpret_cast<Cell*>(reinterpret_cast<size_t>(p) & mask);
55  }
56 
57  static bool flagged(Cell* p) {
58  return reinterpret_cast<size_t>(p) & 1;
59  }
60 
61  static Cell*& blockStart(Cell* p) {
62  return p[-1].next;
63  }
64 
65  static T* dataStart(Cell* p) {
66  return reinterpret_cast<T*>(p + 1);
67  }
68 
69 public:
70  MyList()
71  : front_(0), size_(0) {
72  }
73 
74  MyList(MyList const& o)
75  : front_(0), size_(0) {
76  if (o.size_ != 0) throw std::runtime_error(
77  "MyList can't be copied unless it is empty!"); //FIXME
78  }
79 
80  MyList& operator=(MyList const& o) {
81  if (o.size_ != 0) throw std::runtime_error(
82  "MyList can't be copied unless it is empty!"); //FIXME
83  clear();
84  return *this;
85  }
86 
87 // MyList(MyList&& o) {
88 // *this = std::move(o);
89 // }
90 
91 // MyList& operator=(MyList&& o) {
92 // front_ = o.front_;
93 // o.front_ = 0;
94 // return *this;
95 // }
96 
97  virtual ~MyList() {
98  clear();
99  }
100 
105  size_t size() const {
106  return size_;
107  }
108 
113  bool empty() const {
114  assert((front_ == 0) == (size_ == 0));
115  return front_ == 0;
116  }
117 
122  void clear() {
123  while (front_) {
124  Cell* p = front_;
125 
126  while (!flagged(p)) {
127  p = p->next;
128  }
129 
130  delete[] blockStart(front_);
131  front_ = clearFlag(p);
132  }
133  size_ = 0;
134  }
135 
140  T* front() {
141  return dataStart(front_);
142  }
143 
148  T const* front() const {
149  return dataStart(front_);
150  }
151 
159  T* alloc_front(size_t numElements = 1) {
160  size_t const n = numCells(numElements * sizeof(T)) + 1;
161 
162  if (front_ == 0 || front_ < blockStart(front_) + headerCells + n) {
163  size_t const m = headerCells + n * BLOCK_ELEMENTS;
164  Cell* newBlock = new Cell[m];
165  Cell* newFront = newBlock + m - n;
166  blockStart(newFront) = newBlock;
167  newFront->next = setFlag(front_);
168  front_ = newFront;
169  }
170  else {
171  Cell* newFront = front_ - n;
172  blockStart(newFront) = blockStart(front_);
173  newFront->next = front_;
174  front_ = newFront;
175  }
176  ++size_;
177 
178  return dataStart(front_);
179  }
180 
184  void pop_front() {
185  //front().~T(); I don't care about destruction!
186  Cell* next = front_->next;
187 
188  if (flagged(next)) {
189  delete[] blockStart(front_);
190  front_ = clearFlag(next);
191  }
192  else {
193  blockStart(next) = blockStart(front_);
194  front_ = next;
195  }
196  --size_;
197  }
198 
199  class iterator {
200  Cell* front;
201 
202  public:
203  iterator(Cell* front)
204  : front(front) {
205  }
206 
207  T* operator*() const {
208  return dataStart(front);
209  }
210 
211  T* operator->() const {
212  return dataStart(front);
213  }
214 
215  iterator& operator++() {
216  front = clearFlag(front->next);
217  return *this;
218  }
219 
220  bool operator==(iterator const& o) const {
221  return front == o.front;
222  }
223 
224  bool operator!=(iterator const& o) const {
225  return front != o.front;
226  }
227  };
228 
229  class const_iterator {
230  Cell const* front;
231 
232  public:
233  const_iterator(Cell const* front)
234  : front(front) {
235  }
236 
237  T const* operator*() const {
238  return *dataStart(front);
239  }
240 
241  T const* operator->() const {
242  return dataStart(front);
243  }
244 
245  const_iterator& operator++() {
246  front = clearFlag(front->next);
247  return *this;
248  }
249 
250  bool operator==(iterator const& o) const {
251  return front == o.front;
252  }
253 
254  bool operator!=(iterator const& o) const {
255  return front != o.front;
256  }
257  };
258 
263  iterator begin() {
264  return iterator(front_);
265  }
266 
271  const_iterator begin() const {
272  return const_iterator(front_);
273  }
274 
279  iterator end() {
280  return iterator(0);
281  }
282 
287  const_iterator end() const {
288  return const_iterator(0);
289  }
290 
291 // /**
292 // * Get the hash code of this object.
293 // * @return the hash code.
294 // */
295 // size_t hash() const {
296 // size_t h = size_;
297 // for (size_t i = 0; i < size_; ++i) {
298 // h = h * 31 + array_[i].hash();
299 // }
300 // return h;
301 // }
302 //
303 // /**
304 // * Check equivalence between another object.
305 // * @param o another object.
306 // * @return true if equivalent.
307 // */
308 // bool operator==(MyList const& o) const {
309 // if (size_ != o.size_) return false;
310 // for (size_t i = 0; i < size_; ++i) {
311 // if (!(array_[i] == o.array_[i])) return false;
312 // }
313 // return true;
314 // }
315 
322  friend std::ostream& operator<<(std::ostream& os, MyList const& o) {
323  bool cont = false;
324  os << "(";
325  for (const_iterator t = o.begin(); t != o.end(); ++t) {
326  if (cont) os << ",";
327  os << **t;
328  cont = true;
329  }
330  return os << ")";
331  }
332 };
333 
334 template<typename T>
335 class MyListOnPool {
336  struct Cell {
337  Cell* next;
338  };
339 
340  Cell* front_;
341  size_t size_;
342 
343  static size_t dataCells(size_t n) {
344  return (n + sizeof(Cell) - 1) / sizeof(Cell);
345  }
346 
347  static size_t workCells(size_t n) {
348  return 1 + dataCells(n);
349  }
350 
351  static T* dataStart(Cell* p) {
352  return reinterpret_cast<T*>(p + 1);
353  }
354 
355  static T const* dataStart(Cell const* p) {
356  return reinterpret_cast<T const*>(p + 1);
357  }
358 
359 public:
360  MyListOnPool()
361  : front_(0), size_(0) {
362  }
363 
364  MyListOnPool(MyListOnPool const& o) {
365  *this = o;
366  }
367 
368  MyListOnPool& operator=(MyListOnPool const& o) {
369  if (!o.empty()) throw std::runtime_error(
370  "MyListOnPool: Can't copy a nonempty object.");
371 
372  front_ = 0;
373  size_ = 0;
374  return *this;
375  }
376 
377 // MyListOnPool(MyListOnPool&& o) {
378 // *this = std::move(o);
379 // }
380 //
381 // MyListOnPool& operator=(MyListOnPool&& o) {
382 // front_ = o.front_;
383 // size_ = o.size_;
384 // o.front_ = 0;
385 // o.size_ = 0;
386 // return *this;
387 // }
388 
389  virtual ~MyListOnPool() {
390  clear();
391  }
392 
397  size_t size() const {
398  return size_;
399  }
400 
405  bool empty() const {
406  assert((front_ == 0) == (size_ == 0));
407  return front_ == 0;
408  }
409 
414  void clear() {
415  front_ = 0;
416  size_ = 0;
417  }
418 
423  T* front() {
424  return dataStart(front_);
425  }
426 
431  T const* front() const {
432  return dataStart(front_);
433  }
434 
443  template<typename Pool>
444  T* alloc_front(Pool& pool, size_t numElements = 1) {
445  size_t const n = workCells(numElements * sizeof(T));
446  Cell* newFront = pool.template allocate<Cell>(n);
447  newFront->next = front_;
448  front_ = newFront;
449  ++size_;
450 
451  return dataStart(front_);
452  }
453 
457  void pop_front() {
458  front_ = front_->next;
459  --size_;
460  }
461 
462  class iterator {
463  Cell* front;
464 
465  public:
466  iterator(Cell* front)
467  : front(front) {
468  }
469 
470  T* operator*() const {
471  return dataStart(front);
472  }
473 
474  iterator& operator++() {
475  front = front->next;
476  return *this;
477  }
478 
479  bool operator==(iterator const& o) const {
480  return front == o.front;
481  }
482 
483  bool operator!=(iterator const& o) const {
484  return front != o.front;
485  }
486  };
487 
488  class const_iterator {
489  Cell const* front;
490 
491  public:
492  const_iterator(Cell const* front)
493  : front(front) {
494  }
495 
496  T const* operator*() const {
497  return dataStart(front);
498  }
499 
500  const_iterator& operator++() {
501  front = front->next;
502  return *this;
503  }
504 
505  bool operator==(const_iterator const& o) const {
506  return front == o.front;
507  }
508 
509  bool operator!=(const_iterator const& o) const {
510  return front != o.front;
511  }
512  };
513 
518  iterator begin() {
519  return iterator(front_);
520  }
521 
526  const_iterator begin() const {
527  return const_iterator(front_);
528  }
529 
534  iterator end() {
535  return iterator(0);
536  }
537 
542  const_iterator end() const {
543  return const_iterator(0);
544  }
545 
546 // /**
547 // * Get the hash code of this object.
548 // * @return the hash code.
549 // */
550 // size_t hash() const {
551 // size_t h = size_;
552 // for (size_t i = 0; i < size_; ++i) {
553 // h = h * 31 + array_[i].hash();
554 // }
555 // return h;
556 // }
557 //
558 // /**
559 // * Check equivalence between another object.
560 // * @param o another object.
561 // * @return true if equivalent.
562 // */
563 // bool operator==(MyListOnPool const& o) const {
564 // if (size_ != o.size_) return false;
565 // for (size_t i = 0; i < size_; ++i) {
566 // if (!(array_[i] == o.array_[i])) return false;
567 // }
568 // return true;
569 // }
570 
577  friend std::ostream& operator<<(std::ostream& os, MyListOnPool const& o) {
578  bool cont = false;
579  os << "(";
580  for (const_iterator t = o.begin(); t != o.end(); ++t) {
581  if (cont) os << ",";
582  os << **t;
583  cont = true;
584  }
585  return os << ")";
586  }
587 };
588 
589 } // namespace tdzdd