stack_string_impl.hpp

Go to the documentation of this file.

/******************************************************************************
** Copyright © 2013 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr void
basic_stack_string<BuffN, charT, traits>::buffer_type::copy(native_databus_type const *src) noexcept(true) {
   assert(std::strlen(reinterpret_cast<value_type const *>(src))<small_string_max_size);
   // Unroll the copy in the hope that the compiler will notice the sequence of copies and optimize it.
// For comparative testing for my HFT series of talks.
   unrolled_op_t::result([src, this](std::size_t i) {fast_copy_values[i]=src[i];});
// std::memcpy(small_basic_stack_string, src, std::strlen(reinterpret_cast<value_type const *>(src)));
}
 
template<unsigned int BuffN, class charT, class traits>
template<std::size_t SrcSz>
inline constexpr void
basic_stack_string<BuffN, charT, traits>::buffer_type::copy(value_type const (& src)[SrcSz]) noexcept(true) {
   static_assert(SrcSz<=small_string_max_size, "Passed array must be smaller than the buffer size.");
// For comparative testing for my HFT series of talks.
   memcpy_opt(src, small_basic_stack_string);
// std::memcpy(small_basic_stack_string, src, SrcSz);
}
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr void
basic_stack_string<BuffN, charT, traits>::buffer_type::copy(ensure_char_ptr_argument_aligned src) noexcept(true) {
   assert(std::strlen(src)<small_string_max_size);
   native_databus_type const *punned_src=reinterpret_cast<native_databus_type const *>(src);
   copy(punned_src);
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::copy(size_type cap, const_pointer b, const_pointer e, size_type offset) noexcept(true) {
   if (LIKELY(cap<small_string_max_size)) {
      // TODO ideally unroll this.
      std::memcpy(small_basic_stack_string+offset, b, std::distance(b, e));
   } else {
      std::memcpy(heap+offset, b, std::distance(b, e));
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::fill_n(size_type cap, size_type offset, size_type n, value_type i) noexcept(true) {
   if (LIKELY(cap<small_string_max_size)) {
      // TODO ideally unroll this.
      memset(small_basic_stack_string+offset, i, n);
   } else {
      memset(heap+offset, i, n);
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::ctor(size_type cap, ensure_char_ptr_argument_aligned src) noexcept(false) {
   if (LIKELY(cap<small_string_max_size)) {
      std::memcpy(small_basic_stack_string, src, cap);
   } else {
      auto ptr=std::get_temporary_buffer<value_type>(cap);
      if (LIKELY(ptr.first)) {
         assert(static_cast<size_type>(ptr.second)>=cap);
         heap=ptr.first;
         std::memcpy(heap, src, cap);
      } else {
         throw std::bad_alloc();
      }
   }
}
 
template<unsigned int BuffN, class charT, class traits>
template<std::size_t SrcSz>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::ctor(value_type const (& src)[SrcSz]) noexcept(SrcSz<=small_string_max_size) {
   if constexpr (SrcSz<=small_string_max_size) {
      copy<SrcSz>(src);
   } else {
      auto ptr=std::get_temporary_buffer<value_type>(SrcSz);
      if (LIKELY(ptr.first)) {
         using dest_type=value_type [SrcSz];
         assert(static_cast<size_type>(ptr.second)>=SrcSz);
         heap=ptr.first;
// For comparative testing for my HFT series of talks.
         memcpy_opt(src, reinterpret_cast<dest_type &>(*heap));
//       std::memcpy(reinterpret_cast<dest_type &>(*heap), src, SrcSz);
      } else {
         throw std::bad_alloc();
      }
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::cctor(size_type cap, buffer_type const &b) noexcept(false) {
   if (LIKELY(cap<small_string_max_size)) {
      unrolled_op_t::result([&b, this](std::size_t i) {fast_copy_values[i]=b.fast_copy_values[i];});
   } else {
      auto ptr=std::get_temporary_buffer<value_type>(cap);
      if (LIKELY(ptr.first)) {
         assert(static_cast<size_type>(ptr.second)<=cap);
         heap=ptr.first;
         std::memcpy(heap, b.heap, cap);
      } else {
         throw std::bad_alloc();
      }
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::swap(buffer_type &buff) noexcept(true) {
   // Unroll the swap in the hope that the compiler will notice the sequence of copies and optimize it.
   unrolled_op_t::result([this, &buff](std::size_t i) {std::swap(fast_copy_values[i], buff.fast_copy_values[i]);});
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::buffer_type::move(size_type cap, typename iterator_traits::difference_type f, typename iterator_traits::difference_type l, size_type n) noexcept(true) {
   if (LIKELY(cap<small_string_max_size)) {
      // TODO ideally unroll this.
      memmove(small_basic_stack_string+f, small_basic_stack_string+l, n);
   } else {
      memmove(heap+f, heap+l, n);
   }
}
 
template<unsigned int BuffN, class charT, class traits>
constexpr inline
basic_stack_string<BuffN, charT, traits>::basic_stack_string() noexcept(true)
: size_(), capacity_(), buffer() {
}
 
template<unsigned int BuffN, class charT, class traits>
inline
basic_stack_string<BuffN, charT, traits>::basic_stack_string(ensure_char_ptr_argument_aligned src, std::size_t sz) noexcept(false) {
   if (LIKELY(src!=nullptr)) {
      size_=sz;
      capacity_=size_+1;
      buffer.ctor(capacity_, src);
   } else {
      throw exception("nullptr input.");
   }
   assert(size_<capacity_);
}
 
template<unsigned int BuffN, class charT, class traits>
template<std::size_t SrcSz>
inline
basic_stack_string<BuffN, charT, traits>::basic_stack_string(value_type const (& src)[SrcSz]) noexcept(SrcSz<=small_string_max_size)
: size_(SrcSz-1), capacity_(size_+1) {
   buffer.template ctor<SrcSz>(src);
   assert(size_<capacity_);
}
 
template<unsigned int BuffN, class charT, class traits>
inline
basic_stack_string<BuffN, charT, traits>::basic_stack_string(basic_stack_string const &str) noexcept(false)
: size_(str.size_), capacity_() {
   if (LIKELY(size_)) {
      capacity_=size_+1;
      buffer.cctor(capacity_, str.buffer);
      assert(size_<capacity_);
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline
basic_stack_string<BuffN, charT, traits>::basic_stack_string(basic_stack_string &&str) noexcept(true)
: size_(str.size_), capacity_(str.capacity_), buffer(str.buffer) {
   str.size_=0;
   str.capacity_=0;
   str.buffer.heap=nullptr;
}
 
template<unsigned int BuffN, class charT, class traits>
inline
basic_stack_string<BuffN, charT, traits>::~basic_stack_string() noexcept(true) {
// For comparative testing for my HFT series of talks.
   // Although this is UNLIKELY, DO NOT use UNLIKELY nor LIKELY here: it can give a 40% performance drop in some tests!!!
// if (LIKELY(capacity_>=small_string_max_size)) {
   if (capacity_>=small_string_max_size) {
      capacity_=size_type();
      std::return_temporary_buffer(buffer.heap);
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::swap(basic_stack_string &str) noexcept(true) {
   std::swap(size_, str.size_);
   std::swap(capacity_, str.capacity_);
   buffer.swap(str.buffer);
}
 
template<unsigned int BuffN, class charT, class traits>
inline basic_stack_string<BuffN, charT, traits> &
basic_stack_string<BuffN, charT, traits>::operator=(basic_stack_string const &str) noexcept(false) {
   basic_stack_string tmp(str);
   swap(tmp);
   return *this;
}
 
template<unsigned int BuffN, class charT, class traits>
inline basic_stack_string<BuffN, charT, traits> &
basic_stack_string<BuffN, charT, traits>::operator=(basic_stack_string &&str) noexcept(true) {
   swap(str);
   return *this;
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::iterator
basic_stack_string<BuffN, charT, traits>::begin() noexcept(true) {
   return iterator(capacity_<small_string_max_size ? buffer.small_basic_stack_string : buffer.heap);
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::const_iterator
basic_stack_string<BuffN, charT, traits>::begin() const noexcept(true) {
   return const_iterator(capacity_<small_string_max_size ? buffer.small_basic_stack_string : buffer.heap);
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::iterator
basic_stack_string<BuffN, charT, traits>::end() noexcept(true) {
   return iterator((capacity_<small_string_max_size ? buffer.small_basic_stack_string : buffer.heap)+size_);
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::const_iterator
basic_stack_string<BuffN, charT, traits>::end() const noexcept(true) {
   return const_iterator((capacity_<small_string_max_size ? buffer.small_basic_stack_string : buffer.heap)+size_);
}
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr bool
basic_stack_string<BuffN, charT, traits>::operator==(basic_stack_string const &s) const noexcept(true) {
   return size()==s.size() && memcmp(begin(), s.begin(), size());
}
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr bool
basic_stack_string<BuffN, charT, traits>::operator!=(basic_stack_string const &s) const noexcept(true) {
   return !(*this==s);
}
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr typename basic_stack_string<BuffN, charT, traits>::size_type
basic_stack_string<BuffN, charT, traits>::size() const noexcept(true) {
   return size_;
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::reserve(size_type s) noexcept(false) {
   if (LIKELY(s<max_size())) {
      // Do we need to grow?
      if (UNLIKELY(s>capacity_)) {
         // Are we a small basic_stack_string?
         if (LIKELY(capacity_<small_string_max_size)) {
            // Reserve within small basic_stack_string range?
            if (LIKELY(s<small_string_max_size)) {
               capacity_=s;
               return;
            }
            // Need to switch to big basic_stack_string mode.
            buffer_type tmp;
            tmp.copy(buffer.fast_copy_values);
            auto ptr=std::get_temporary_buffer<value_type>(s);
            if (LIKELY(ptr.first)) {
               assert(static_cast<size_type>(ptr.second)<=s);
               buffer.heap=ptr.first;
            } else {
               throw std::bad_alloc();
            }
            std::memcpy(buffer.heap, tmp.small_basic_stack_string, size_+1);
         } else {
            // Already a big basic_stack_string. Grow the buffer.
            // Throwing operations first.
            auto ptr=std::get_temporary_buffer<value_type>(s);
            if (LIKELY(ptr.first)) {
               assert(static_cast<size_type>(ptr.second)<=s);
            } else {
               throw std::bad_alloc();
            }
            std::memcpy(ptr.first, buffer.heap, size_+1);
            std::swap(buffer.heap, ptr.first);
            std::return_temporary_buffer(ptr.first);
         }
         capacity_=s;
      }
      assert(size_<capacity_);
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::resize(size_type s) noexcept(false) {
   reserve(s+1);
   size_=s;
   *end()=value_type();
   assert(size_<capacity_);
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::resize(size_type s, value_type i) noexcept(false) {
   reserve(s+1);
   if (UNLIKELY(s>size_)) {
      assert(s<=capacity_);
      buffer.fill_n(capacity_, size_, s-size_, i);
   }
   size_=s;
   *end()=value_type();
   assert(size_<capacity_);
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::clear() noexcept(true) {
   size_=size_type();
   *end()=value_type();
}
 
template<unsigned int BuffN, class charT, class traits>
inline constexpr bool
basic_stack_string<BuffN, charT, traits>::empty() const noexcept(true) {
   return size()==size_type();
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::reference
basic_stack_string<BuffN, charT, traits>::operator[](size_type p) noexcept(true) {
   return *std::next(begin(), p);
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::const_reference
basic_stack_string<BuffN, charT, traits>::operator[](size_type p) const noexcept(true) {
   return *std::next(begin(), p);
}
 
template<unsigned int BuffN, class charT, class traits>
inline void
basic_stack_string<BuffN, charT, traits>::push_back(value_type c) noexcept(false) {
   resize(size_+1, c);
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::iterator
basic_stack_string<BuffN, charT, traits>::insert(iterator p, const_iterator b, const_iterator e) noexcept(false) {
   if (LIKELY(b!=e)) {
      assert(static_cast<size_type>(std::distance(begin(), p))<=size_);
      assert(static_cast<size_type>(std::distance(p, end()))<=size_);
      // Iterators may be invalidated.
      const typename iterator_traits::difference_type size_str_ins=std::distance(b, e);
      const typename iterator_traits::difference_type dist_in_str=std::distance(begin(), p);
      reserve(size_+size_str_ins+1);
      if (LIKELY(capacity_<small_string_max_size)) {
         // TODO ideally unroll this.
         memmove(buffer.small_basic_stack_string+dist_in_str+size_str_ins, buffer.small_basic_stack_string+dist_in_str, size_-dist_in_str);
         std::memcpy(buffer.small_basic_stack_string+dist_in_str, b, size_str_ins);
         size_+=size_str_ins;
         *end()=value_type();
         assert(size_<=capacity_);
         return p;
      } else {
         memmove(buffer.heap+dist_in_str+size_str_ins, buffer.heap+dist_in_str, size_-dist_in_str);
         std::memcpy(buffer.heap+dist_in_str, b, size_str_ins);
         size_+=size_str_ins;
         *end()=value_type();
         assert(size_<=capacity_);
         return std::next(begin()+dist_in_str-1);
      }
   } else {
      return p;
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline typename basic_stack_string<BuffN, charT, traits>::iterator
basic_stack_string<BuffN, charT, traits>::erase(const_iterator b, const_iterator e) noexcept(true) {
   if (LIKELY(static_cast<size_type>(std::distance(b, e))<=size_)) {
      assert(static_cast<size_type>(std::distance(const_iterator(begin()), b))<=size_);
      assert(static_cast<size_type>(std::distance(b, const_iterator(end())))<=size_);
      assert(static_cast<size_type>(std::distance(const_iterator(begin()), e))<=size_);
      assert(static_cast<size_type>(std::distance(e, const_iterator(end())))<=size_);
      // Iterators may be invalidated.
      const typename iterator_traits::difference_type first=std::distance(const_iterator(begin()), b);
      const typename iterator_traits::difference_type last=std::distance(const_iterator(begin()), e);
      buffer.move(capacity_, first, last, size_-last);
      size_-=last-first;
      *end()=value_type();
      assert(size_<=capacity_);
      return begin()+first;
   } else {
      return end();
   }
}
 
template<unsigned int BuffN, class charT, class traits>
inline basic_stack_string<BuffN, charT, traits> &
basic_stack_string<BuffN, charT, traits>::replace(iterator b, iterator e, const_iterator src_b, const_iterator src_e) noexcept(false) {
   // The easy way to do this would be to erase(), then insert(), but it would have excessive copies.
   if (LIKELY(src_b!=src_e)) {
      if (UNLIKELY(b==e)) {
         // Equivalent to insert().
         insert(b, src_b, src_e);
      } else {
         assert(static_cast<size_type>(std::distance(begin(), b))<=size_);
         assert(static_cast<size_type>(std::distance(b, end()))<=size_);
         assert(static_cast<size_type>(std::distance(begin(), e))<=size_);
         assert(static_cast<size_type>(std::distance(e, end()))<=size_);
         // Iterators may be invalidated.
         const typename iterator_traits::difference_type first=std::distance(begin(), b);
         const typename iterator_traits::difference_type last=std::distance(begin(), e);
         const typename iterator_traits::difference_type replace_str_sz=std::distance(src_b, src_e);
         if (LIKELY((last-first)>=replace_str_sz)) {
            // We're shrinking, so no issues with copying the overlapping end range.
            if (LIKELY(capacity_<small_string_max_size)) {
               // TODO ideally unroll this.
               std::memcpy(buffer.small_basic_stack_string+first, src_b, replace_str_sz);
               memmove(buffer.small_basic_stack_string+first+replace_str_sz, buffer.small_basic_stack_string+last, size_-last);
            } else {
               std::memcpy(buffer.heap+first, src_b, replace_str_sz);
               memmove(buffer.heap+first+replace_str_sz, buffer.heap+last, size_-last);
            }
            size_-=(last-first)-replace_str_sz;
         } else {
            reserve(size_+(replace_str_sz-(last-first))+1);
            if (LIKELY(capacity_<small_string_max_size)) {
               // TODO ideally unroll this.
               std::copy_backward(buffer.small_basic_stack_string+last, buffer.small_basic_stack_string+size_, buffer.small_basic_stack_string+first+replace_str_sz+size_-last);
               std::memcpy(buffer.small_basic_stack_string+first, src_b, replace_str_sz);
            } else {
               std::copy_backward(buffer.heap+last, buffer.heap+size_, buffer.heap+first+replace_str_sz+size_-last);
               std::memcpy(buffer.heap+first, src_b, replace_str_sz);
            }
            size_+=replace_str_sz-(last-first);
         }
         *end()=value_type();
      }
   } else {
      // Equivalent to erase().
      erase(b, e);
   }
   assert(size_<=capacity_);
   return *this;
}
 
template<unsigned int BuffN, class charT, class traits> inline std::basic_ostream<charT, traits> &
operator<<(std::basic_ostream<charT, traits> &os, basic_stack_string<BuffN, charT, traits> const &s) noexcept(false) {
   os.write(s.begin(), s.size());
   return os;
}
 
template<unsigned int BuffN, class charT, class traits> inline std::basic_istream<charT, traits> &
operator>>(std::basic_istream<charT, traits> &is, basic_stack_string<BuffN, charT, traits> &s) noexcept(false) {
   typename std::basic_istream<charT, traits>::int_type ret;
   while ((ret=is.get())!=traits::eof()) {
      s.push_back(static_cast<typename basic_stack_string<BuffN, charT, traits>::value_type>(ret));
   }
   return is;
}
 
} }