vector.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 1,703 行 · 第 1/5 页

         #ifdef BOOST_INTERPROCESS_VECTOR_ALLOC_STATS
         ++this->num_expand_bwd;
         #endif
         this->priv_range_insert_expand_backwards
            ( detail::get_pointer(ret.first)
            , real_cap
            , detail::get_pointer(pos)
            , n
            , interf);
      }
      //New buffer
      else{
         #ifdef BOOST_INTERPROCESS_VECTOR_ALLOC_STATS
         ++this->num_alloc;
         #endif
         this->priv_range_insert_new_allocation
            ( detail::get_pointer(ret.first)
            , real_cap
            , detail::get_pointer(pos)
            , n
            , interf);
      }
   }

   void priv_range_insert_expand_forward(T* pos, size_type n, advanced_insert_aux_int_t &interf)
   {
      typedef typename value_traits::copy_move_it copy_move_it;
      typedef typename value_traits::assign_move_it assign_move_it;
      //There is enough memory
      T* old_finish = detail::get_pointer(this->members_.m_start) + this->members_.m_size;
      const size_type elems_after = old_finish - pos;

      if (elems_after > n){
         //New elements can be just copied.
         //Move to uninitialized memory last objects
         std::uninitialized_copy(copy_move_it(old_finish - n), copy_move_it(old_finish), old_finish);
         this->members_.m_size += n;
         //Copy previous to last objects to the initialized end
         std::copy_backward(assign_move_it(pos), assign_move_it(old_finish - n), old_finish);
         //Insert new objects in the pos
         interf.copy_all_to(pos);
      }
      else {
         //The new elements don't fit in the [pos, end()) range. Copy
         //to the beginning of the unallocated zone the last new elements.
         interf.uninitialized_copy_some_and_update(old_finish, elems_after, false);
         this->members_.m_size += n - elems_after;
         //Copy old [pos, end()) elements to the uninitialized memory
         std::uninitialized_copy
            ( copy_move_it(pos), copy_move_it(old_finish)
            , detail::get_pointer(this->members_.m_start) + this->members_.m_size);
         this->members_.m_size += elems_after;
         //Copy first new elements in pos
         interf.copy_all_to(pos);
      }
   }

   void priv_range_insert_new_allocation
      (T* new_start, size_type new_cap, T* pos, size_type n, advanced_insert_aux_int_t &interf)
   {
      typedef typename value_traits::copy_move_it copy_move_it;
      T* new_finish = new_start;
      T *old_finish;
      //Anti-exception rollbacks
      typename value_traits::UCopiedArrayDeallocator scoped_alloc(new_start, this->alloc(), new_cap);
      typename value_traits::UCopiedArrayDestructor constructed_values_destroyer(new_start, 0u);

      //Initialize with [begin(), pos) old buffer 
      //the start of the new buffer
      new_finish = std::uninitialized_copy
         ( copy_move_it(detail::get_pointer(this->members_.m_start))
         , copy_move_it(pos)
         , old_finish = new_finish);
      constructed_values_destroyer.increment_size(new_finish - old_finish);
      //Initialize new objects, starting from previous point
      interf.uninitialized_copy_all_to(old_finish = new_finish);
      new_finish += n;
      constructed_values_destroyer.increment_size(new_finish - old_finish);
      //Initialize from the rest of the old buffer, 
      //starting from previous point
      new_finish = std::uninitialized_copy
         ( copy_move_it(pos)
         , copy_move_it(detail::get_pointer(this->members_.m_start) + this->members_.m_size)
         , new_finish);

      //All construction successful, disable rollbacks
      constructed_values_destroyer.release();
      scoped_alloc.release();
      //Destroy and deallocate old elements
      //If there is allocated memory, destroy and deallocate
      if(this->members_.m_start != 0){
         if(!value_traits::trivial_dctr_after_move)
            this->destroy_n(detail::get_pointer(this->members_.m_start), this->members_.m_size); 
         this->alloc().deallocate(this->members_.m_start, this->members_.m_capacity);
      }
      this->members_.m_start     = new_start;
      this->members_.m_size      = new_finish - new_start;
      this->members_.m_capacity  = new_cap;
   }

   void priv_range_insert_expand_backwards
         (T* new_start, size_type new_capacity,
          T* pos, const size_type n, advanced_insert_aux_int_t &interf)
   {
      typedef typename value_traits::copy_move_it     copy_move_it;
      typedef typename value_traits::assign_move_it   assign_move_it;

      //Backup old data
      T* old_start  = detail::get_pointer(this->members_.m_start);
      T* old_finish = old_start + this->members_.m_size;
      size_type old_size = this->members_.m_size;

      //We can have 8 possibilities:
      const size_type elemsbefore   = (size_type)(pos - old_start);
      const size_type s_before      = (size_type)(old_start - new_start);

      //Update the vector buffer information to a safe state
      this->members_.m_start      = new_start;
      this->members_.m_capacity   = new_capacity;
      this->members_.m_size = 0;

      //If anything goes wrong, this object will destroy
      //all the old objects to fulfill previous vector state
      typename value_traits::OldArrayDestructor old_values_destroyer(old_start, old_size);
      //Check if s_before is big enough to hold the beginning of old data + new data
      if(difference_type(s_before) >= difference_type(elemsbefore + n)){
         //Copy first old values before pos, after that the new objects
         std::uninitialized_copy(copy_move_it(old_start), copy_move_it(pos), new_start);
         this->members_.m_size = elemsbefore;
         interf.uninitialized_copy_all_to(new_start + elemsbefore);
         this->members_.m_size += n;
         //Check if s_before is so big that even copying the old data + new data
         //there is a gap between the new data and the old data
         if(s_before >= (old_size + n)){
            //Old situation:
            // _________________________________________________________
            //|            raw_mem                | old_begin | old_end |
            //| __________________________________|___________|_________|
            //
            //New situation:
            // _________________________________________________________
            //| old_begin |    new   | old_end |         raw_mem        |
            //|___________|__________|_________|________________________|
            //
            //Now initialize the rest of memory with the last old values
            std::uninitialized_copy
               (copy_move_it(pos), copy_move_it(old_finish), new_start + elemsbefore + n);
            //All new elements correctly constructed, avoid new element destruction
            this->members_.m_size = old_size + n;
            //Old values destroyed automatically with "old_values_destroyer"
            //when "old_values_destroyer" goes out of scope unless the have trivial
            //destructor after move.
            if(value_traits::trivial_dctr_after_move)
               old_values_destroyer.release();
         }
         //s_before is so big that divides old_end
         else{
            //Old situation:
            // __________________________________________________
            //|            raw_mem         | old_begin | old_end |
            //| ___________________________|___________|_________|
            //
            //New situation:
            // __________________________________________________
            //| old_begin |   new    | old_end |  raw_mem        |
            //|___________|__________|_________|_________________|
            //
            //Now initialize the rest of memory with the last old values
            //All new elements correctly constructed, avoid new element destruction
            size_type raw_gap = s_before - (elemsbefore + n);
            //Now initialize the rest of s_before memory with the
            //first of elements after new values
            std::uninitialized_copy
               (copy_move_it(pos), copy_move_it(pos + raw_gap), new_start + elemsbefore + n);
            //Update size since we have a contiguous buffer
            this->members_.m_size = old_size + s_before;
            //All new elements correctly constructed, avoid old element destruction
            old_values_destroyer.release();
            //Now copy remaining last objects in the old buffer begin
            T *to_destroy = std::copy(assign_move_it(pos + raw_gap), assign_move_it(old_finish), old_start);
            //Now destroy redundant elements except if they were moved and
            //they have trivial destructor after move
            size_type n_destroy =  old_finish - to_destroy;
            if(!value_traits::trivial_dctr_after_move)
               this->destroy_n(to_destroy, n_destroy);
            this->members_.m_size -= n_destroy;
         }
      }
      else{
         //Check if we have to do the insertion in two phases
         //since maybe s_before is not big enough and
         //the buffer was expanded both sides
         //
         //Old situation:
         // _________________________________________________
         //| raw_mem | old_begin + old_end |  raw_mem        |
         //|_________|_____________________|_________________|
         //
         //New situation with do_after:
         // _________________________________________________
         //|     old_begin + new + old_end     |  raw_mem    |
         //|___________________________________|_____________|
         //
         //New without do_after:
         // _________________________________________________
         //| old_begin + new + old_end  |  raw_mem           |
         //|____________________________|____________________|
         //
         bool do_after    = n > s_before;

         //Now we can have two situations: the raw_mem of the
         //beginning divides the old_begin, or the new elements:
         if (s_before <= elemsbefore) {
            //The raw memory divides the old_begin group:
            //
            //If we need two phase construction (do_after)
            //new group is divided in new = new_beg + new_end groups
            //In this phase only new_beg will be inserted
            //
            //Old situation:
            // _________________________________________________
            //| raw_mem | old_begin | old_end |  raw_mem        |
            //|_________|___________|_________|_________________|
            //
            //New situation with do_after(1):
            //This is not definitive situation, the second phase
            //will include
            // _________________________________________________
            //| old_begin | new_beg | old_end |  raw_mem        |
            //|___________|_________|_________|_________________|
            //
            //New situation without do_after:
            // _________________________________________________
            //| old_begin | new | old_end |  raw_mem            |
            //|___________|_____|_________|_____________________|
            //
            //Copy the first part of old_begin to raw_mem
            T *start_n = old_start + difference_type(s_before); 
            std::uninitialized_copy(copy_move_it(old_start), copy_move_it(start_n), new_start);
            //The buffer is all constructed until old_end,
            //release destroyer and update size
            old_values_destroyer.release();
            this->members_.m_size = old_size + s_before;
            //Now copy the second part of old_begin overwriting himself
            T* next = std::copy(assign_move_it(start_n), assign_move_it(pos), old_start);
            if(do_after){
               //Now copy the new_beg elements
               interf.copy_some_and_update(next, s_before, true);
            }
            else{
               //Now copy the all the new elements
               interf.copy_all_to(next);
               T* move_start = next + n;
               //Now displace old_end elements
               T* move_end   = std::copy(assign_move_it(pos), assign_move_it(old_finish), move_start);
               //Destroy remaining moved elements from old_end except if
               //they have trivial destructor after being moved
               difference_type n_destroy = s_before - n;
               if(!value_traits::trivial_dctr_after_move)
                  this->destroy_n(move_end, n_destroy);
               this->members_.m_size -= n_destroy;
            }
         }
         else {
            //If we have to expand both sides,
            //we will play if the first new values so
            //calculate the upper bound of new values

            //The raw memory divides the new elements
            //
            //If we need two phase construction (do_after)
            //new group is divided in new = new_beg + new_end groups
            //In this phase only new_beg will be inserted
            //
            //Old situation:
            // _______________________________________________________
            //|   raw_mem     | old_begin | old_end |  raw_mem        |
            //|_______________|___________|_________|_________________|
            //
            //New situation with do_after():
            // ____________________________________________________
            //| old_begin |    new_beg    | old_end |  raw_mem     |
            //|___________|_______________|_________|______________|
            //
            //New situation without do_after:
            // ______________________________________________________
            //| old_begin | new | old_end |  raw_mem                 |
            //|___________|_____|_________|__________________________|
            //
            //First copy whole old_begin and part of new to raw_mem
            std::uninitialized_copy(copy_move_it(old_start), copy_move_it(pos), new_start);
            this->members_.m_size = elemsbefore;

            const size_type mid_n = difference_type(s_before) - elemsbefore;
            interf.uninitialized_copy_some_and_update(new_start + elemsbefore, mid_n, true);
            this->members_.m_size = old_size + s_before;
            //The buffer is all constructed until old_end,
            //release destroyer and update size
            old_values_destroyer.release();

            if(do_after){
               //Copy new_beg part
               interf.copy_some_and_update(old_start, s_before - mid_n, true);
            }
            else{
               //Copy all new elements
               interf.copy_all_to(old_start);
               T* move_start = old_start + (n-mid_n);
               //Displace old_end
               T* move_end   = std::copy(copy_move_it(pos), copy_move_it(old_finish), move_start);
               //Destroy remaining moved elements from old_end except if they
               //have trivial destructor after being moved
               difference_type n_destroy = s_before - n;
               if(!value_traits::trivial_dctr_after_move)
                  this->destroy_n(move_end, n_destroy);
               this->members_.m_size -= n_destroy;
            }
         }

         //This is only executed if two phase construction is needed
         //This can be executed without exception handling since we
         //have to just copy and append in raw memory and
         //old_values_destroyer has been released in phase 1.
         if(do_after){
            //The raw memory divides the new elements
            //
            //Old situation:
            // ______________________________________________________
            //|   raw_mem    | old_begin |  old_end   |  raw_mem     |
            //|______________|___________|____________|______________|
            //
            //New situation with do_after(1):
            // _______________________________________________________
            //| old_begin   +   new_beg  | new_end |old_end | raw_mem |
            //|__________________________|_________|________|_________|
            //
            //New situation with do_after(2):
            // ______________________________________________________
            //| old_begin      +       new