stack_string.hpp

Go to the documentation of this file.

#ifndef LIBJMMCG_CORE_BASIC_STACK_STRING_HPP
#define LIBJMMCG_CORE_BASIC_STACK_STRING_HPP
 
/******************************************************************************
** 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
*/
 
#include "hash.hpp"
#include "max_min.hpp"
#include "memops.hpp"
#include "non_allocatable.hpp"
 
#include "boost/mpl/assert.hpp"
 
#include <algorithm>
#include <cstring>
#include <functional>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <limits>
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
/// A class to provide a representation for a null-terminated character string that utilises a small-string optimisation.
/**
   This class is a value-type.
   If the string to be stored is less than small_string_max_size it is not stored on the heap, but on the stack.
   It is not a drop-in replacement for std::string, as it does not implement all of the member functions of the latter (because I don't like the fat interface).
   The optimisations assume that this class will be used for small strings, get the static branch-predictions wrong, and one can get a 50% drop in performance!
 
   \see __gnuxx::__vstring, std::string
*/
template<
   unsigned int BuffN,  ///< The approximate number of charT characters to store in the stack-based buffer. The minimum actual size is given by small_string_max_size.
   class charT,
   class traits=std::char_traits<charT>
>
class basic_stack_string final : private non_newable {
   /**
      A type to express the machine's native memory-bus width for a word, i.e. what can be rapidly fetched from, copied in a single register operation & written back to memory. This is not the cache line width.
   */
   using native_databus_type=unsigned long;
 
public:
   typedef charT value_type;
   typedef traits traits_type;
   typedef std::iterator_traits<value_type const *> const_iterator_traits;
   typedef std::iterator_traits<value_type *> iterator_traits;
   typedef std::size_t size_type;
   typedef typename iterator_traits::pointer pointer;
   typedef typename const_iterator_traits::pointer const_pointer;
   typedef typename iterator_traits::pointer iterator;
   typedef typename const_iterator_traits::pointer const_iterator;
   typedef typename iterator_traits::reference reference;
   typedef typename const_iterator_traits::reference const_reference;
 
   static_assert(std::is_pod<value_type>::value, "The contained type must be a POD due to the implementation.");
 
   enum : std::size_t {
      small_string_max_size=max<
         std::size_t,
         sizeof(pointer),
         ((BuffN+sizeof(native_databus_type))/sizeof(native_databus_type))*sizeof(native_databus_type)
      >::value ///< Ensure that the internal, stack-based buffer is the minimum size of a pointer, or larger, in units of "native word"s. Also store the null termination char so that c_str() is fast too, trading off size for speed. In units of chars.
   };
   BOOST_MPL_ASSERT_RELATION(sizeof(pointer), <=, small_string_max_size);
 
   /**
      The type of the exception that we throw.
   */
   struct exception : std::runtime_error {
      typedef std::runtime_error base_t;
 
      explicit constexpr exception(char const *s) FORCE_INLINE : base_t(s) {}
   };
 
private:
   /**
      Try to ensure that the alignment of the input char ptr parameter is suitable for speedily copying into the internal buffer, otherwise we might get sub-optimal copying or at worst a bus error or alignment error in buffer_type::copy().
      Note that this is compiler-specific, and the attribute will need to change for different compilers.
 
      \see buffer_type::copy(), basic_stack_string()
   */
   typedef value_type __attribute__ ((aligned (sizeof(native_databus_type)))) const * ensure_char_ptr_argument_aligned;
 
public:
   /**
      Complexity: O(1)
   */
   constexpr basic_stack_string() noexcept(true) FORCE_INLINE;
   /// Convert a C-style string into a basic_stack_string.
   /**
      Note the use of the opaque parameter type ensure_char_ptr_argument_aligned: this allows the user to pass in a char const * pointer, but ensures that it is suitably aligned for our purposes, without the user having to worry about alignment issues.
      Complexity: O(sz) best case, O(new()+sz) worst-case.
      May throw: std::bad_alloc, exception if pointer is nullptr
 
      \param   src   A c-style null terminated string, that should have been suitably aligned, automatically, by the compiler.
      \param   sz The number of chars to copy.
 
      \see ensure_char_ptr_argument_aligned
   */
   explicit basic_stack_string(ensure_char_ptr_argument_aligned src, std::size_t sz) noexcept(false) FORCE_INLINE;
   /// Convert a C-style array of chars into a basic_stack_string.
   /**
      Complexity: O(1) best case, O(new()+SrcSz) worst-case.
      May throw: std::bad_alloc
 
      \param   src   A c-style null terminated char-array.
   */
   template<std::size_t SrcSz> explicit FORCE_INLINE
   basic_stack_string(value_type const (& src)[SrcSz]) noexcept(SrcSz<=small_string_max_size);
   /**
      Note that if the string contained in str can be optimised, this function will optimise the copy, i.e. place the copy on the stack from the heap.
      Complexity: O(1) best case, O(new()+str.size()) worst-case.
      May throw: std::bad_alloc
 
      \param   str   The basic_stack_string to be copied.
   */
   basic_stack_string(basic_stack_string const &str) noexcept(false) FORCE_INLINE;
   /**
      Complexity: O(1).
 
      \param   str   The string to be copied.
   */
   basic_stack_string(basic_stack_string&& str) noexcept(true) FORCE_INLINE;
   /**
      Complexity: O(1) best-case, O(delete()) worst-case.
   */
   ~basic_stack_string() noexcept(true) FORCE_INLINE;
 
   /// Copy the basic_stack_string.
   /**
      Complexity: O(1) best case, O(new()+str.size()) worst-case.
      May throw: std::bad_alloc
 
      \return An r-value to the copied basic_stack_string.
   */
   basic_stack_string &operator=(basic_stack_string const &str) noexcept(false) FORCE_INLINE;
   /// Move the basic_stack_string.
   /**
      Complexity: O(1)
 
      \return An r-value to the copied basic_stack_string.
   */
   basic_stack_string &operator=(basic_stack_string &&str) noexcept(true) FORCE_INLINE;
 
   constexpr bool operator==(basic_stack_string const &) const noexcept(true) FORCE_INLINE;
   constexpr bool operator!=(basic_stack_string const &) const noexcept(true) FORCE_INLINE;
 
   /// Return an iterator to the beginning of the contained string.
   /**
      Complexity: O(1)
 
      \return  iterator to the beginning of the contained string.
   */
   iterator begin() noexcept(true) FORCE_INLINE;
   /// Return a const_iterator to the beginning of the contained string.
   /**
      Complexity: O(1)
 
      \return  const_iterator to the beginning of the contained string.
   */
   const_iterator begin() const noexcept(true) FORCE_INLINE;
   /// Return an iterator to the end of the contained string.
   /**
      Complexity: O(1)
 
      \return  iterator to the end of the contained string.
   */
   iterator end() noexcept(true) FORCE_INLINE;
   /// Return a const_iterator to the end of the contained string.
   /**
      Complexity: O(1)
 
      \return  const_iterator to the end of the contained string.
   */
   const_iterator end() const noexcept(true) FORCE_INLINE;
 
   /// Return the size of the contained string, excluding any null termination.
   /**
      Complexity: O(1)
      Constraint: size()<=capacity() && empty==(size()==0).
 
      \return  Size of the contained string.
 
      \see capacity(), empty()
   */
   constexpr size_type size() const noexcept(true) FORCE_INLINE;
   /// Return the maximum size of any possible contained string, including any null termination.
   /**
      Complexity: O(1)
      Constraint: max_size()>=capacity().
 
      \return  Maximum possible size of a contained string.
 
      \see capacity()
   */
   static constexpr size_type max_size() noexcept(true) FORCE_INLINE {
      return std::numeric_limits<typename iterator_traits::difference_type>::max();
   }
   /// Uninitialised resize of the contained string to the requested size.
   /**
      Notes:
      - The elements in the internal buffer are not re-initialised, even if more memory has had to be allocated, for speed.
      - If capacity()>s then the internal buffer is reduced in size. Note that if the string has been moved to the heap it will not be moved back to the stack, for speed.
      - The null terminator is re-added to the end.
      - If the capacity() has to be increased, all iterators are invalidated but the contained string is maintained.
      Complexity: O(reserve())
      Constraint: size()==s.
      May throw: std::bad_alloc
 
      \param   s  Ensure that size() returns s. The internal buffer in which the contained string may be stored is adjusted to ensure that it has a capacity of at least s.
 
      \see empty(), reserve(), size()
   */
   void resize(size_type s) noexcept(false) FORCE_INLINE;
   /// Initialised resize of the contained string to the requested size.
   /**
      Notes:
      - If capacity()>s then the internal buffer is reduced in size. Note that if the string has been moved to the heap it will not be moved back to the stack, for speed.
      - The null terminator is re-added to the end.
      - If the capacity() has to be increased, all iterators are invalidated but the contained string is maintained.
      Complexity: O(reserve()+std::max(s-size(), 0))
      Constraint: size()==s && empty()==false.
      May throw: std::bad_alloc
 
      \param   s  Ensure that size() returns s. The internal buffer in which the contained string may be stored is adjusted to ensure that it has a capacity() of at least s.
      \param   i  The value to which the s elements within the contained string should be initialised.
 
      \see capacity(), empty(), size()
   */
   void resize(size_type s, value_type i) noexcept(false) FORCE_INLINE;
   /// Return the size of the internal buffer used to store the string, including the null termination.
   /**
      Complexity: O(1)
      Constraint: capacity()>=size() && capacity()<=max_size().
 
      \return  Return the size of internal buffer.
 
      \see max_size(), size()
   */
   constexpr size_type capacity() const noexcept(true) FORCE_INLINE {
      return capacity_;
   }
   /// Set the size of the internal buffer to at least the requested size, if the requested size is larger, then it will not be made smaller.
   /**
      Notes:
      - The elements in the internal buffer are not re-initialised, even if more memory has had to be allocated.
      - If the capacity() has to be increased, all iterators are invalidated, values returned from data() & c_str() are invalidated, but the contained string is maintained.
      - If capacity() has to be reduced, note that if the string has been moved to the heap it will not be moved back to the stack, for speed.
      - If an exception is thrown, then the object is unaffected.
      Complexity: O(1) best case, O(new()+delete()+std::max(s-size(), 0)) worst case.
      Constraint: capacity()==s && capacity()<=max_size().
      May throw: std::bad_alloc
 
      \param   s  Ensure that capacity() returns s, if less than max_size(), otherwise no effect. The internal buffer in which the contained string may be stored is adjusted to ensure that it has a capacity of s.
 
      \see capacity(), max_size()
   */
   void reserve(size_type s) noexcept(false) FORCE_INLINE;
 
   /// Clear the contained string.
   /**
      Complexity: O(1) best case, O(delete()) worst case.
      Postcondition: size()==0 && empty()==true.
 
      \see empty(), size()
   */
   void clear() noexcept(true) FORCE_INLINE;
   /// Return is the string is empty.
   /**
      Complexity: O(1)
      Condition: empty()==(size()==0).
 
      \return  true if size()==0, false otherwise.
 
      \see size()
   */
   constexpr bool empty() const noexcept(true) FORCE_INLINE;
 
   /// Return an l-value to the requested element in the contained string.
   /**
      Note that p must be less than size(), otherwise UB.
      Complexity: O(1)
 
      \param   p  The zero-based index into the contained string.
      \return  An l-value to the requested character in the contained string.
 
      \see at(), size()
   */
   reference operator[](size_type p) noexcept(true) FORCE_INLINE;
   /// Return an r-value to the requested element in the contained string.
   /**
      Note that p must be less than size(), otherwise UB.
      Complexity: O(1)
 
      \param   p  The zero-based index into the contained string.
      \return  An r-value to the requested character in the contained string.
 
      \see at(), size()
   */
   const_reference operator[](size_type p) const noexcept(true) FORCE_INLINE;
 
   /// Append a character to the end of the contained string.
   /**
      Note:
      - If the capacity() has to be increased, all iterators are invalidated, values returned from data() & c_str() are invalidated, but the contained basic_stack_string is maintained.
      Complexity: O(resize())
      May throw: std::bad_alloc
 
      \param   c  The character to append.
 
      \see resize()
   */
   void push_back(value_type c) noexcept(false) FORCE_INLINE;
   /// Insert the characters in the range [b, e) into the contained string from the specified position, growing the contained string as necessary.
   /**
      Note:
      - I'm not implementing the large number of overloads in std::basic_basic_stack_string, as that interface is unnecessarily fat.
      - The range inserted is [b, e).
      - If the capacity() has to be increased, all iterators are invalidated, values returned from data() & c_str() are invalidated, but the contained basic_stack_string is maintained.
      Complexity: O(resize())
      May throw: std::bad_alloc
 
      \param   p  The position immediately after the position into which the range is inserted, must be in the range [begin(), end()).
      \param   b  The beginning of the range.
      \param   e  The end of the range.
      \return  An iterator which refers to the copy of the first inserted character, or p if b==e.
   */
   iterator insert(iterator p, const_iterator b, const_iterator e) noexcept(false) FORCE_INLINE;
 
   /// Remove the characters in the range [b, e).
   /**
      Note that {b, e} must be within [begin(), end()).
      Complexity: O(std::distance(b, e))
 
      \param   b  The beginning of the range.
      \param   e  The end of the range.
      \return  An iterator which points to the element pointed to by e prior to the other elements being
erased. If no such element exists, end() is returned.
   */
   iterator erase(const_iterator b, const_iterator e) noexcept(true) FORCE_INLINE;
 
   /// Replace the characters in the range [b, e) with those in the range [src_b, src_e).
   /**
      Note that {b, e} must be within [begin(), end()).
      Complexity: O(resize()+std::max(std::distance(b, e), std::distance(src_b, src_e))
 
      \param   b  The beginning of the range.
      \param   e  The end of the range.
      \param   src_b The beginning of the source range.
      \param   src_e The end of the source range.
      \return  An l-value to the basic_stack_string.
   */
   basic_stack_string &replace(iterator b, iterator e, const_iterator src_b, const_iterator src_e) noexcept(false) FORCE_INLINE;
 
   /// Swap the current basic_stack_string with the argument.
   /**
      Complexity: O(1)
 
      \param   str   The basic_stack_string with which to swap.
   */
   void swap(basic_stack_string &str) noexcept(true) FORCE_INLINE;
 
private:
   /**
      Either have a pointer to the heap or a small string stored in the space for the pointer. By using this union and putting the pointer-type first this should guarantee that the string alignment is reasonable for the cache, i.e. not at char alignment, which could be very bad.
      If the small_string_max_size>capacity() then make sure that the small-string optimisation is engaged, i.e. this is the flag to know which member of the buffer_type union is valid.
   */
   union ALIGN_TO_L1_CACHE buffer_type {
      /**
         The copy of the small string can be sped up using this array to directly copy the chunks of chars words-at-a-time.
      */
      native_databus_type fast_copy_values[small_string_max_size/sizeof(native_databus_type)+1]={};
      pointer heap;
      value_type small_basic_stack_string[small_string_max_size/sizeof(value_type)];
 
      enum {
         num_fast_copy_values=sizeof(fast_copy_values)/sizeof(native_databus_type)
      };
      BOOST_MPL_ASSERT_RELATION(sizeof(pointer), <=, sizeof(fast_copy_values));
      BOOST_MPL_ASSERT_RELATION(sizeof(small_basic_stack_string), <=, sizeof(fast_copy_values));
      BOOST_MPL_ASSERT_RELATION(sizeof(small_basic_stack_string), ==, small_string_max_size);
      BOOST_MPL_ASSERT_RELATION(small_string_max_size, <=, num_fast_copy_values*sizeof(native_databus_type));
 
      using unrolled_op_t=private_::unroll<num_fast_copy_values>;
 
      void ctor(size_type cap, ensure_char_ptr_argument_aligned src) noexcept(false) FORCE_INLINE;
      template<std::size_t SrcSz>
      void ctor(value_type const (& src)[SrcSz]) noexcept(SrcSz<=small_string_max_size) FORCE_INLINE;
      void cctor(size_type cap, buffer_type const &b) noexcept(false) FORCE_INLINE;
 
      /**
         Copy the small string directly in chunks of chars words-at-a-time.
 
         \param   src   The source string.
      */
      constexpr void copy(native_databus_type const *src) noexcept(true) FORCE_INLINE;
      /**
         Copy the small string directly in chunks of chars words-at-a-time.
 
         \param   src   The source string.
      */
      constexpr void copy(ensure_char_ptr_argument_aligned src) noexcept(true) FORCE_INLINE;
      template<std::size_t SrcSz> constexpr void FORCE_INLINE
      copy(value_type const (& src)[SrcSz]) noexcept(true);
      void copy(size_type cap, const_pointer b, const_pointer e, size_type offset) noexcept(true) FORCE_INLINE;
      void fill_n(size_type cap, size_type offset, size_type n, value_type i) noexcept(true) FORCE_INLINE;
      void swap(buffer_type &buff) noexcept(true) FORCE_INLINE;
      void move(size_type cap, typename iterator_traits::difference_type f, typename iterator_traits::difference_type l, size_type n) noexcept(true) FORCE_INLINE;
   };
 
   /**
      We store the size to get at it rapidly, trading off the space required to store the size.
   */
   size_type size_;
   /**
      We store the capacity to get at it rapidly, trading off the space required to store the size.
   */
   size_type capacity_;
   // Larger objects come first to improve cache use of strings.
   buffer_type buffer;
};
 
template<unsigned int BuffN, class charT, class traits> std::basic_ostream<charT, traits> &
operator<<(std::basic_ostream<charT, traits> &os, basic_stack_string<BuffN, charT, traits> const &s) noexcept(false);
 
template<unsigned int BuffN, class charT, class traits> std::basic_istream<charT, traits> &
operator>>(std::basic_istream<charT, traits> &os, basic_stack_string<BuffN, charT, traits> &s) noexcept(false);
 
typedef basic_stack_string<1, char> stack_string;
typedef basic_stack_string<1, wchar_t> wstack_string;
 
} }
 
namespace std {
 
template<>
struct hash<libjmmcg::stack_string> : unary_function<libjmmcg::stack_string, std::size_t> {
   typedef unary_function<libjmmcg::stack_string, size_t>::result_type result_type;
   typedef unary_function<libjmmcg::stack_string, size_t>::argument_type argument_type;
 
   result_type operator()(argument_type const &s) const noexcept(true) FORCE_INLINE {
      using hasher_t=libjmmcg::hashers::murmur2<argument_type>;
      return s.capacity()<s.small_string_max_size ? *s.begin() : hasher_t().operator()(s);
   }
};
 
template<>
struct hash<libjmmcg::wstack_string> : unary_function<libjmmcg::wstack_string, std::size_t> {
   typedef unary_function<libjmmcg::wstack_string, size_t>::result_type result_type;
   typedef unary_function<libjmmcg::wstack_string, size_t>::argument_type argument_type;
 
   result_type operator()(argument_type const &s) const noexcept(true) FORCE_INLINE {
      using hasher_t=libjmmcg::hashers::murmur2<argument_type>;
      return s.capacity()<s.small_string_max_size ? *s.begin() : hasher_t().operator()(s);
   }
};
 
}
 
#include "stack_string_impl.hpp"
 
#endif