33 template<
typename T,
size_t BLOCK_ELEMENTS = 1000>
35 static int const headerCells = 1;
44 static size_t numCells(
size_t n) {
45 return (n +
sizeof(Cell) - 1) /
sizeof(Cell);
48 static Cell* setFlag(Cell* p) {
49 return reinterpret_cast<Cell*
>(
reinterpret_cast<size_t>(p) | 1);
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);
57 static bool flagged(Cell* p) {
58 return reinterpret_cast<size_t>(p) & 1;
61 static Cell*& blockStart(Cell* p) {
65 static T* dataStart(Cell* p) {
66 return reinterpret_cast<T*
>(p + 1);
71 : front_(0), size_(0) {
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!");
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!");
105 size_t size()
const {
114 assert((front_ == 0) == (size_ == 0));
126 while (!flagged(p)) {
130 delete[] blockStart(front_);
131 front_ = clearFlag(p);
141 return dataStart(front_);
148 T
const* front()
const {
149 return dataStart(front_);
159 T* alloc_front(
size_t numElements = 1) {
160 size_t const n = numCells(numElements *
sizeof(T)) + 1;
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_);
171 Cell* newFront = front_ - n;
172 blockStart(newFront) = blockStart(front_);
173 newFront->next = front_;
178 return dataStart(front_);
186 Cell* next = front_->next;
189 delete[] blockStart(front_);
190 front_ = clearFlag(next);
193 blockStart(next) = blockStart(front_);
203 iterator(Cell* front)
207 T* operator*()
const {
208 return dataStart(front);
211 T* operator->()
const {
212 return dataStart(front);
215 iterator& operator++() {
216 front = clearFlag(front->next);
220 bool operator==(iterator
const& o)
const {
221 return front == o.front;
224 bool operator!=(iterator
const& o)
const {
225 return front != o.front;
229 class const_iterator {
233 const_iterator(Cell
const* front)
237 T
const* operator*()
const {
238 return *dataStart(front);
241 T
const* operator->()
const {
242 return dataStart(front);
245 const_iterator& operator++() {
246 front = clearFlag(front->next);
250 bool operator==(iterator
const& o)
const {
251 return front == o.front;
254 bool operator!=(iterator
const& o)
const {
255 return front != o.front;
264 return iterator(front_);
271 const_iterator begin()
const {
272 return const_iterator(front_);
287 const_iterator end()
const {
288 return const_iterator(0);
322 friend std::ostream& operator<<(std::ostream& os, MyList
const& o) {
325 for (const_iterator t = o.begin(); t != o.end(); ++t) {
343 static size_t dataCells(
size_t n) {
344 return (n +
sizeof(Cell) - 1) /
sizeof(Cell);
347 static size_t workCells(
size_t n) {
348 return 1 + dataCells(n);
351 static T* dataStart(Cell* p) {
352 return reinterpret_cast<T*
>(p + 1);
355 static T
const* dataStart(Cell
const* p) {
356 return reinterpret_cast<T const*
>(p + 1);
361 : front_(0), size_(0) {
364 MyListOnPool(MyListOnPool
const& o) {
368 MyListOnPool& operator=(MyListOnPool
const& o) {
369 if (!o.empty())
throw std::runtime_error(
370 "MyListOnPool: Can't copy a nonempty object.");
389 virtual ~MyListOnPool() {
397 size_t size()
const {
406 assert((front_ == 0) == (size_ == 0));
424 return dataStart(front_);
431 T
const* front()
const {
432 return dataStart(front_);
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_;
451 return dataStart(front_);
458 front_ = front_->next;
466 iterator(Cell* front)
470 T* operator*()
const {
471 return dataStart(front);
474 iterator& operator++() {
479 bool operator==(iterator
const& o)
const {
480 return front == o.front;
483 bool operator!=(iterator
const& o)
const {
484 return front != o.front;
488 class const_iterator {
492 const_iterator(Cell
const* front)
496 T
const* operator*()
const {
497 return dataStart(front);
500 const_iterator& operator++() {
505 bool operator==(const_iterator
const& o)
const {
506 return front == o.front;
509 bool operator!=(const_iterator
const& o)
const {
510 return front != o.front;
519 return iterator(front_);
526 const_iterator begin()
const {
527 return const_iterator(front_);
542 const_iterator end()
const {
543 return const_iterator(0);
577 friend std::ostream& operator<<(std::ostream& os, MyListOnPool
const& o) {
580 for (const_iterator t = o.begin(); t != o.end(); ++t) {