Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Andres Noetzli, Morgan Deters, Tim King
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2024 by the authors listed in the file AUTHORS
       8                 :            :  * in the top-level source directory and their institutional affiliations.
       9                 :            :  * All rights reserved.  See the file COPYING in the top-level source
      10                 :            :  * directory for licensing information.
      11                 :            :  * ****************************************************************************
      12                 :            :  * Context-dependent list class (only supports append).
      13                 :            :  *
      14                 :            :  * This list only supports appending to the list; on backtrack, the list is
      15                 :            :  * simply shortened.
      16                 :            :  */
      17                 :            : 
      18                 :            : #include "cvc5parser_public.h"
      19                 :            : 
      20                 :            : #ifndef CVC5__CONTEXT__CDLIST_H
      21                 :            : #define CVC5__CONTEXT__CDLIST_H
      22                 :            : 
      23                 :            : #include <cstring>
      24                 :            : #include <iterator>
      25                 :            : #include <memory>
      26                 :            : #include <string>
      27                 :            : #include <vector>
      28                 :            : 
      29                 :            : #include "base/check.h"
      30                 :            : #include "context/cdlist_forward.h"
      31                 :            : #include "context/context.h"
      32                 :            : #include "context/context_mm.h"
      33                 :            : #include "context/default_clean_up.h"
      34                 :            : 
      35                 :            : namespace cvc5::context {
      36                 :            : 
      37                 :            : /**
      38                 :            :  * Generic context-dependent dynamic array.  Note that for efficiency, this
      39                 :            :  * implementation makes the following assumption: Over time, objects are only
      40                 :            :  * added to the list.  Objects are only removed when a pop restores the list to
      41                 :            :  * a previous state.
      42                 :            :  */
      43                 :            : template <class T, class CleanUpT, class Allocator>
      44                 :            : class CDList : public ContextObj
      45                 :            : {
      46                 :            :  public:
      47                 :            :   /** The value type with which this CDList<> was instantiated. */
      48                 :            :   using value_type = T;
      49                 :            : 
      50                 :            :   /** The cleanup type with which this CDList<> was instantiated. */
      51                 :            :   using CleanUp = CleanUpT;
      52                 :            : 
      53                 :            :   /**
      54                 :            :    * `std::vector<T>::operator[] const` returns an
      55                 :            :    * std::vector<T>::const_reference, which does not necessarily have to be a
      56                 :            :    * `const T&`. Specifically, in the case of `std::vector<bool>`, the type is
      57                 :            :    * specialized to be just a simple `bool`. For our `operator[] const`, we use
      58                 :            :    * the same type.
      59                 :            :    */
      60                 :            :   using ConstReference = typename std::vector<T>::const_reference;
      61                 :            : 
      62                 :            :   /**
      63                 :            :    * Instead of implementing our own iterators, we just use the iterators of
      64                 :            :    * the underlying `std::vector<T>`.
      65                 :            :    */
      66                 :            :   using const_iterator = typename std::vector<T>::const_iterator;
      67                 :            :   using iterator = typename std::vector<T>::const_iterator;
      68                 :            : 
      69                 :            :   /**
      70                 :            :    * Main constructor: d_list starts with size 0
      71                 :            :    *
      72                 :            :    * Optionally, a cleanup callback can be specified, which is called on every
      73                 :            :    * element that gets removed during a pop. The callback is only used when
      74                 :            :    * callCleanup is true. Note: the destructor of the elements in the list is
      75                 :            :    * called regardless of whether callCleanup is true or false.
      76                 :            :    */
      77                 :   15304008 :   CDList(Context* context,
      78                 :            :          bool callCleanup = true,
      79                 :            :          const CleanUp& cleanup = CleanUp())
      80                 :            :       : ContextObj(context),
      81                 :            :         d_list(),
      82                 :            :         d_size(0),
      83                 :            :         d_callCleanup(callCleanup),
      84                 :   15304008 :         d_cleanUp(cleanup)
      85                 :            :   {
      86                 :   15304008 :   }
      87                 :            : 
      88                 :            :   /**
      89                 :            :    * Destructor: delete the list
      90                 :            :    */
      91                 :   15250642 :   ~CDList() {
      92                 :   15250642 :     this->destroy();
      93                 :            : 
      94         [ +  + ]:   15250642 :     if (this->d_callCleanup)
      95                 :            :     {
      96                 :   15152603 :       truncateList(0);
      97                 :            :     }
      98                 :   30501284 :   }
      99                 :            : 
     100                 :            :   /**
     101                 :            :    * Return the current size of (i.e. valid number of objects in) the
     102                 :            :    * list.
     103                 :            :    */
     104                 :  492378868 :   size_t size() const { return d_list.size(); }
     105                 :            : 
     106                 :            :   /**
     107                 :            :    * Return true iff there are no valid objects in the list.
     108                 :            :    */
     109                 :   21499863 :   bool empty() const { return d_list.empty(); }
     110                 :            : 
     111                 :            :   /**
     112                 :            :    * Add an item to the end of the list. This method uses the copy constructor
     113                 :            :    * of T, so the type has to support it. As a result, this method cannot be
     114                 :            :    * used with types that do not have a copy constructor such as
     115                 :            :    * std::unique_ptr. Use CDList::emplace_back() instead of CDList::push_back()
     116                 :            :    * to avoid this issue.
     117                 :            :    */
     118                 :  232896745 :   void push_back(const T& data) {
     119         [ +  - ]:  232896745 :     Trace("cdlist") << "push_back " << this << " " << getContext()->getLevel()
     120                 :          0 :                     << ": make-current" << std::endl;
     121                 :  232896745 :     makeCurrent();
     122                 :  232896745 :     d_list.push_back(data);
     123                 :  232896745 :     ++d_size;
     124                 :  232896745 :   }
     125                 :            : 
     126                 :            :   /**
     127                 :            :    * Construct an item to the end of the list. This method constructs the item
     128                 :            :    * in-place (similar to std::vector::emplace_back()), so it can be used for
     129                 :            :    * types that do not have a copy constructor such as std::unique_ptr.
     130                 :            :    */
     131                 :            :   template <typename... Args>
     132                 :      27254 :   void emplace_back(Args&&... args)
     133                 :            :   {
     134         [ +  - ]:      54508 :     Trace("cdlist") << "emplace_back " << this << " "
     135                 :      27254 :                     << getContext()->getLevel() << ": make-current" << std::endl;
     136                 :      27254 :     makeCurrent();
     137                 :      27254 :     d_list.emplace_back(std::forward<Args>(args)...);
     138                 :      27254 :     ++d_size;
     139                 :      27254 :   }
     140                 :            : 
     141                 :            :   /**
     142                 :            :    * Access to the ith item in the list.
     143                 :            :    */
     144                 :  304124240 :   ConstReference operator[](size_t i) const
     145                 :            :   {
     146 [ -  + ][ -  + ]:  304124240 :     Assert(i < d_size) << "index out of bounds in CDList::operator[]";
                 [ -  - ]
     147                 :  304124240 :     return d_list[i];
     148                 :            :   }
     149                 :            : 
     150                 :            :   /**
     151                 :            :    * Returns the most recent item added to the list.
     152                 :            :    */
     153                 :      20786 :   ConstReference back() const
     154                 :            :   {
     155 [ -  + ][ -  + ]:      20786 :     Assert(d_size > 0) << "CDList::back() called on empty list";
                 [ -  - ]
     156                 :      20786 :     return d_list[d_size - 1];
     157                 :            :   }
     158                 :            : 
     159                 :            :   /**
     160                 :            :    * Returns an iterator pointing to the first item in the list.
     161                 :            :    */
     162                 :   26255338 :   const_iterator begin() const { return d_list.begin(); }
     163                 :            : 
     164                 :            :   /**
     165                 :            :    * Returns an iterator pointing one past the last item in the list.
     166                 :            :    */
     167                 :   30003353 :   const_iterator end() const { return d_list.end(); }
     168                 :            : 
     169                 :            :  protected:
     170                 :            :   /**
     171                 :            :    * Private copy constructor used only by save(). d_list is not copied: only
     172                 :            :    * the base class information and d_size are needed in restore.
     173                 :            :    */
     174                 :   42427445 :   CDList(const CDList& l)
     175                 :            :       : ContextObj(l),
     176                 :   42427445 :         d_size(l.d_size),
     177                 :            :         d_callCleanup(false),
     178                 :   42427445 :         d_cleanUp(l.d_cleanUp)
     179                 :            :   {
     180         [ +  - ]:   42427445 :     Trace("cdlist") << "copy ctor: " << this << " from " << &l << " size "
     181                 :          0 :                     << d_size << std::endl;
     182                 :   42427445 :   }
     183                 :            :   CDList& operator=(const CDList& l) = delete;
     184                 :            :   /**
     185                 :            :    * Implementation of mandatory ContextObj method restore: simply
     186                 :            :    * restores the previous size.  Note that the list pointer and the
     187                 :            :    * allocated size are not changed.
     188                 :            :    */
     189                 :            : 
     190                 :   42425391 :   void restore(ContextObj* data) override
     191                 :            :   {
     192                 :   42425391 :     truncateList(((CDList<T, CleanUp, Allocator>*)data)->d_size);
     193                 :   42425391 :   }
     194                 :            : 
     195                 :            :   /**
     196                 :            :    * Given a size parameter smaller than d_size, truncateList()
     197                 :            :    * removes the elements from the end of the list until d_size equals size.
     198                 :            :    *
     199                 :            :    * WARNING! You should only use this function when you know what you are
     200                 :            :    * doing. This is a primitive operation with strange context dependent
     201                 :            :    * behavior! It is up to the user of the function to ensure that the saved
     202                 :            :    * d_size values at lower context levels are less than or equal to size.
     203                 :            :    */
     204                 :   70778512 :   void truncateList(const size_t size)
     205                 :            :   {
     206 [ -  + ][ -  + ]:   70778512 :     Assert(size <= d_size);
                 [ -  - ]
     207         [ +  + ]:   70778512 :     if (d_callCleanup)
     208                 :            :     {
     209         [ +  + ]:  282196593 :       while (d_size != size)
     210                 :            :       {
     211                 :  213206637 :         --d_size;
     212                 :  213206637 :         typename std::vector<T>::reference elem = d_list[d_size];
     213                 :  213206637 :         d_cleanUp(elem);
     214                 :            :       }
     215                 :            :     }
     216                 :            :     else
     217                 :            :     {
     218                 :    1788633 :       d_size = size;
     219                 :            :     }
     220                 :            :     // Note that std::vector::resize() would require a default constructor for
     221                 :            :     // the elements in std::vector
     222                 :   70778512 :     d_list.erase(d_list.begin() + d_size, d_list.end());
     223                 :   70778512 :   }
     224                 :            : 
     225                 :            :   /**
     226                 :            :    * d_list is a vector of objects of type T.
     227                 :            :    */
     228                 :            :   std::vector<T> d_list;
     229                 :            : 
     230                 :            :   /**
     231                 :            :    * Number of objects in d_list
     232                 :            :    */
     233                 :            :   size_t d_size;
     234                 :            : 
     235                 :            :  private:
     236                 :            :   /**
     237                 :            :    * Whether to call the destructor when items are popped from the
     238                 :            :    * list.  True by default, but can be set to false by setting the
     239                 :            :    * second argument in the constructor to false.
     240                 :            :    */
     241                 :            :   bool d_callCleanup;
     242                 :            : 
     243                 :            :   /**
     244                 :            :    * The CleanUp functor.
     245                 :            :    */
     246                 :            :   CleanUp d_cleanUp;
     247                 :            : 
     248                 :            :   /**
     249                 :            :    * Implementation of mandatory ContextObj method save: simply copies
     250                 :            :    * the current size to a copy using the copy constructor (the
     251                 :            :    * pointer and the allocated size are *not* copied as they are not
     252                 :            :    * restored on a pop).  The saved information is allocated using the
     253                 :            :    * ContextMemoryManager.
     254                 :            :    */
     255                 :   28481525 :   ContextObj* save(ContextMemoryManager* pCMM) override
     256                 :            :   {
     257                 :   28481525 :     ContextObj* data = new(pCMM) CDList<T, CleanUp, Allocator>(*this);
     258                 :   28481525 :     return data;
     259                 :            :   }
     260                 :            : 
     261                 :            : }; /* class CDList<> */
     262                 :            : 
     263                 :            : }  // namespace cvc5::context
     264                 :            : 
     265                 :            : #endif /* CVC5__CONTEXT__CDLIST_H */