LCOV - code coverage report
Current view: top level - src - containers.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 64 64 100.0 %
Date: 2018-02-05 16:49:44 Functions: 36 36 100.0 %

          Line data    Source code
       1             : /*
       2             : # Copyright (C) 2014-2017 Fulvio Benini
       3             : 
       4             : * This file is part of Scid (Shane's Chess Information Database).
       5             : *
       6             : * Scid is free software: you can redistribute it and/or modify
       7             : * it under the terms of the GNU General Public License as published by
       8             : * the Free Software Foundation.
       9             : *
      10             : * Scid is distributed in the hope that it will be useful,
      11             : * but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      13             : * GNU General Public License for more details.
      14             : *
      15             : * You should have received a copy of the GNU General Public License
      16             : * along with Scid. If not, see <http://www.gnu.org/licenses/>.
      17             : */
      18             : 
      19             : #ifndef CONTAINERS_H
      20             : #define CONTAINERS_H
      21             : 
      22             : #include "common.h" // for ASSERT
      23             : #include <vector>
      24             : 
      25             : /**
      26             :  * A container useful for implementing a undo-redo behavior.
      27             :  * @e UNDOMAX: max number of copies to store.
      28             :  * Typical use:
      29             :  * store(obj_ptr); // (1)
      30             :  * modify obj;
      31             :  * obj_ptr = undo(obj_ptr); // obj_ptr now contains the copy of (1)
      32             :  */
      33          15 : template <class TElem, size_t UNDOMAX> class UndoRedo {
      34             :         std::vector<TElem*> undo_;
      35             :         std::vector<TElem*> redo_;
      36             : 
      37             : public:
      38          15 :         ~UndoRedo() { clear(); }
      39          16 :         void clear() {
      40          16 :                 clear(undo_);
      41          16 :                 clear(redo_);
      42          16 :         }
      43          19 :         size_t undoSize() const { return undo_.size(); }
      44           7 :         size_t redoSize() const { return redo_.size(); }
      45             : 
      46             :         /**
      47             :          * Stores a copy of an element into the undo queue.
      48             :          * Deletes all the objects of the redo queue.
      49             :          * @param current: the element to clone and store.
      50             :          */
      51          12 :         void store(TElem* current) {
      52          12 :                 clear(redo_);
      53          12 :                 undo_.push_back(current->clone());
      54          12 :                 if (undo_.size() > UNDOMAX) {
      55           1 :                         delete undo_.front();
      56           1 :                         undo_.erase(undo_.begin());
      57             :                 }
      58          12 :         }
      59             : 
      60             :         /**
      61             :          * Retrieve the last element from the undo queue.
      62             :          * @param current: pointer to the current element; it will be stored into
      63             :          *                 the redo queue.
      64             :          * @returns the pointer to the last element of the undo queue (the pointer
      65             :          * will be removed from the queue). If the queue is empty returns @e current
      66             :          */
      67          15 :         TElem* undo(TElem* current) { return doUndoRedo(undo_, redo_, current); }
      68             : 
      69             :         /**
      70             :          * Retrieve the last element from the redo queue.
      71             :          * @param current: pointer to the current element; it will be stored into
      72             :          *                 the undo queue.
      73             :          * @returns the pointer to the last element of the redo queue (the pointer
      74             :          * will be removed from the queue). If the queue is empty returns @e current
      75             :          */
      76           4 :         TElem* redo(TElem* current) { return doUndoRedo(redo_, undo_, current); }
      77             : 
      78             : private:
      79             :         // Store current into cont2; remove and return the last element of cont1
      80             :         template <typename TCont>
      81          19 :         TElem* doUndoRedo(TCont& cont1, TCont& cont2, TElem* current) {
      82          19 :                 if (cont1.empty())
      83           5 :                         return current;
      84             : 
      85          14 :                 if (cont2.empty() || cont2.back() != current)
      86          14 :                         cont2.push_back(current);
      87             : 
      88          14 :                 auto res = cont1.back();
      89          14 :                 cont1.pop_back();
      90          14 :                 return res;
      91             :         }
      92             : 
      93          44 :         template <typename TCont> void clear(TCont& cont) {
      94          55 :                 for (auto& e : cont)
      95          11 :                         delete e;
      96          44 :                 cont.clear();
      97          44 :         }
      98             : };
      99             : 
     100             : /**
     101             :  * A vector-like container. Not all the elements are stored contiguously like in
     102             :  * a normal vector, but are allocated in separate chunks so that:
     103             :  * - growing in size do not move the elements and old references remain valid;
     104             :  * - very large containers can be created.
     105             :  * @e CHUNKSHIFT: is the base-2 logarithm of the number of T entries per chunk.
     106             :  *                Total size of a chunk: (2^CHUNKSHIFT)*sizeof(T)
     107             :  */
     108             : template <class T, size_t CHUNKSHIFT> class VectorChunked {
     109             :         std::vector<T*> chunks_;
     110             :         size_t size_ = 0;
     111             : 
     112             :         static constexpr size_t low_mask = ((1ULL << CHUNKSHIFT) - 1);
     113             : 
     114             : public:
     115          85 :         VectorChunked() = default;
     116             :         VectorChunked(const VectorChunked&) = delete;
     117             :         VectorChunked& operator=(const VectorChunked&) = delete;
     118          85 :         ~VectorChunked() {
     119         113 :                 for (auto& chunk : chunks_)
     120          28 :                         delete[] chunk;
     121          85 :         }
     122             : 
     123      927458 :         const T& operator[](size_t idx) const {
     124      927458 :                 ASSERT(idx < size_);
     125      927458 :                 return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
     126             :         }
     127       31577 :         T& operator[](size_t idx) {
     128       31577 :                 ASSERT(idx < size_);
     129       31577 :                 return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
     130             :         }
     131             : 
     132        8086 :         size_t capacity() const { return chunks_.size() << CHUNKSHIFT; }
     133             : 
     134             :         /**
     135             :          * @returns
     136             :          * the count of contiguously allocated objects starting at @e pos (included)
     137             :          */
     138       15043 :         size_t contiguous(size_t pos) const {
     139       15043 :                 ASSERT(pos < size());
     140       15043 :                 return 1 + (~pos & low_mask);
     141             :         }
     142             : 
     143       10047 :         void push_back(const T& e) {
     144       10047 :                 size_t idx = size_;
     145       10047 :                 resize(size_ + 1);
     146       10047 :                 operator[](idx) = e;
     147       10047 :         }
     148             : 
     149       18204 :         void resize(size_t count) {
     150       18204 :                 size_ = count;
     151       18204 :                 size_t newSize = (count > 0) ? 1 + (count >> CHUNKSHIFT) : 0;
     152       18204 :                 size_t chunksSz = chunks_.size();
     153       18204 :                 if (newSize == chunksSz)
     154       18116 :                         return;
     155             : 
     156          88 :                 if (newSize > chunksSz) {
     157          59 :                         chunks_.resize(newSize);
     158         120 :                         for (auto i = chunksSz; i < newSize; ++i) {
     159          61 :                                 chunks_[i] = new T[1ULL << CHUNKSHIFT];
     160             :                         }
     161             :                 } else {
     162          62 :                         for (auto i = newSize; i < chunksSz; ++i) {
     163          33 :                                 delete[] chunks_[i];
     164             :                         }
     165          29 :                         chunks_.resize(newSize);
     166             :                 }
     167             :         }
     168             : 
     169       37142 :         size_t size() const { return size_; }
     170             : };
     171             : 
     172             : #endif

Generated by: LCOV version 1.13