8
\$\begingroup\$

Here's an absolutely essential piece of C++ lore, a stack allocator, that will allow you to, say, allocate strings and vectors on the stack. There are 2 stack allocators I know of, here and here.

The trouble was, neither of them were working with gcc-4.8, and both needed fixing. Here's a fixed version of Hinant's allocator. Could there some improvement or fix to still be made?

#pragma once
#ifndef STACKALLOCATOR_HPP
# define STACKALLOCATOR_HPP

#include <cassert>

#include <cstddef>

#include <functional>

#include <new>

#include <utility>

template <std::size_t N>
class stack_store
{
public:
  stack_store() = default;

  stack_store(stack_store const&) = delete;

  stack_store& operator=(stack_store const&) = delete;

  char* allocate(std::size_t n)
  {
    assert(pointer_in_buffer(ptr_) &&
      "stack_allocator has outlived stack_store");

    n = align(n);

    if (buf_ + N >= ptr_ + n)
    {
      auto r(ptr_);

      ptr_ += n;

      return r;
    }
    else
    {
      return static_cast<char*>(::operator new(n));
    }
  }

  void deallocate(char* const p, std::size_t n) noexcept
  {
    assert(pointer_in_buffer(ptr_) &&
      "stack_allocator has outlived stack_store");

    if (pointer_in_buffer(p))
    {
      n = align(n);

      if (p + n == ptr_)
      {
        ptr_ = p;
      }
      // else do nothing
    }
    else
    {
      ::operator delete(p);
    }
  }

  void reset() noexcept { ptr_ = buf_; }

  static constexpr ::std::size_t size() noexcept { return N; }

  ::std::size_t used() const { return ::std::size_t(ptr_ - buf_); }

private:
  static constexpr ::std::size_t align(::std::size_t const n) noexcept
  {
    return (n + (alignment - 1)) & -alignment;
  }

  bool pointer_in_buffer(char* const p) noexcept
  {
    return (buf_ <= p) && (p <= buf_ + N);
  }

private:
  static constexpr auto const alignment = alignof(::max_align_t);

  char* ptr_{buf_};

  alignas(::max_align_t) char buf_[N];
};

template <class T, std::size_t N>
class stack_allocator
{
public:
  using store_type = stack_store<N>;

  using size_type = ::std::size_t;

  using difference_type = ::std::ptrdiff_t;

  using pointer = T*;
  using const_pointer = T const*;

  using reference = T&;
  using const_reference = T const&;

  using value_type = T;

  template <class U> struct rebind { using other = stack_allocator<U, N>; };

  stack_allocator() = default;

  stack_allocator(stack_store<N>& s) noexcept : store_(&s) { }

  template <class U>
  stack_allocator(stack_allocator<U, N> const& other) noexcept :
    store_(other.store_)
  {
  }

  stack_allocator& operator=(stack_allocator const&) = delete;

  T* allocate(::std::size_t const n)
  {
    return static_cast<T*>(static_cast<void*>(
      store_->allocate(n * sizeof(T))));
  }

  void deallocate(T* const p, ::std::size_t const n) noexcept
  {
    store_->deallocate(static_cast<char*>(static_cast<void*>(p)),
      n * sizeof(T));
  }

  template <class U, class ...A>
  void construct(U* const p, A&& ...args)
  {
    new (p) U(::std::forward<A>(args)...);
  }

  template <class U>
  void destroy(U* const p)
  {
    p->~U();
  }

  template <class U, std::size_t M>
  inline bool operator==(stack_allocator<U, M> const& rhs) const noexcept
  {
    return store_ == rhs.store_;
  }

  template <class U, std::size_t M>
  inline bool operator!=(stack_allocator<U, M> const& rhs) const noexcept
  {
    return !(*this == rhs);
  }

private:
  template <class U, std::size_t M> friend class stack_allocator;

  store_type* store_{};
};

namespace std
{
  // string
  template<class CharT> class char_traits;

  template<class CharT, class Traits, class Allocator> class basic_string;

  // unordered_map
  template<class Key, class T, class Hash, class Pred, class Alloc>
    class unordered_map;

  // vector
  template <class T, class Alloc> class vector;
}

using stack_string = ::std::basic_string<char, ::std::char_traits<char>,
  stack_allocator<char, 128> >;

template <class Key, class T, class Hash = ::std::hash<Key>,
  class Pred = ::std::equal_to<Key> >
using stack_unordered_map = ::std::unordered_map<Key, T, Hash, Pred,
  stack_allocator<::std::pair<Key const, T>, 256> >;

template <typename T>
using stack_vector = ::std::vector<T, stack_allocator<T, 256> >;

#endif // STACKALLOCATOR_HPP

Example usage:

#include <iostream>

#include "stackallocator.hpp"

int main()
{
  ::stack_string::allocator_type::store_type s;

  ::std::cout << ::stack_string("blabla", s).c_str() << std::endl;

  return 0;
}

After running the above example under valgrind, it will report:

==25600== HEAP SUMMARY:
==25600==     in use at exit: 0 bytes in 0 blocks
==25600==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==25600== 
==25600== All heap blocks were freed -- no leaks are possible
==25600== 
==25600== For counts of detected and suppressed errors, rerun with: -v
==25600== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
\$\endgroup\$
  • \$\begingroup\$ Why do you use global namespacing operator :: in example usage? \$\endgroup\$ – sasha.sochka Sep 19 '13 at 17:11
  • \$\begingroup\$ @sasha.sochka It's not really a global operator, it just means outside of the current namespace. \$\endgroup\$ – user1095108 Sep 19 '13 at 18:56
  • \$\begingroup\$ Ok, but why do you need it? \$\endgroup\$ – sasha.sochka Sep 19 '13 at 21:07
  • 1
    \$\begingroup\$ @sasha.sochka It's slightly more pedantic to use it than not. Programming is conveying meaning to the compiler. If you write ::stack_string, you mean exactly that, a ::stack_string type outside the current namespace. \$\endgroup\$ – user1095108 Sep 19 '13 at 21:30
  • 1
    \$\begingroup\$ @TemplateRex I think you mistook Code Review for SO. I wasn't asking for help in compiling Hinant's allocator, but for suggestions/fixes for my fix. We're commenting code here, not asking for help in making code work. \$\endgroup\$ – user1095108 Sep 20 '13 at 10:00
8
\$\begingroup\$

Fixes required for a conforming Standard Library

There is one big issue that will make custom allocators fragile to work with: incomplete C++11 library support. Since C++11, containers are required to go through std::allocator_traits<Allocator> to access construct() and destroy() allocator member functions, as well as to access nested typedefs such as pointer and reference. Furthermore, all containers have a constructor with a single allocator argument. Not every Standard Library implements this for every container.

With the Coliru online compiler, I can get Hinnant's stack allocator working with libstdc++ for a std::vector with only 2 minor modifications running

g++ -std=c++11 -O1 -pedantic -Wall -Wconversion -Wsign-conversion -Wsign-promo

The first is to put parenthesis around the n + (alignment - 1) operand in the align_up()

std::size_t 
    align_up(std::size_t n) noexcept
        {return (n + (alignment-1)) & ~(alignment-1);}
                ^                 ^

The second is to remove the exception specification from the overloaded operator new

void* operator new(std::size_t s) // throw(std::bad_alloc)

Live Example exactly reproducing Hinnant's first test case.

Note that these 2 warnings are rather innocent and do not affect correctness of the program.

Fixes required for a non-conforming Standard Library

Since libstdc++ works fine with all containers if a std::allocator is provided (even when the container implementation directly accesses the allocator, rather than through std::allocator_traits) the safest bet is to provide all the nested typedefs and member functions of std::allocator_traits in your own allocator as well. This includes the various pointer and reference types, as well as the rebind templates. You appear to have done so, and this should resolve at least of all those issues. I still would leave the original naming of Hinnant's version in tact, though.

That leaves the issues of constructors taking a single allocator argument. At least for libstdc++ for g++ 4.8.1, this constructor is missing for std:unordered_map. Apart from patching the standard library headers yourself (possible, but if you have an automatic package updater, that will require constant monitoring) or submit a bug report. Microsoft did have many such issues in Visual C++ 2012 November CTP, which have all been fixed in Visual C++ 2013.

\$\endgroup\$
  • \$\begingroup\$ Try making it work with an unordered_map. This was the source of major problems. Even so, it did not work out of the box. \$\endgroup\$ – user1095108 Sep 20 '13 at 8:43
  • \$\begingroup\$ @user1095108 It does work out-of-the-box without -Wall. Simply fixing the warnings as I showed above also works. What exactly does not work with std::unordered_map? And please indicate how I could improve this answer (if you were the one downvoting it). \$\endgroup\$ – TemplateRex Sep 20 '13 at 8:50
  • \$\begingroup\$ In my case it had a problem with the lack of a default constructor. Even if you added one, the compiler complained about a dangling reference. The problem, I think, had to do with libstdc++'s std::string implementation. Are you interested in seeing the error? In general you need to adapt the allocator to the situation at hand, sometimes, the STL container is odd itself (for example, does not make use of ::std::allocator_traits). I downvoted because you are not providing fixes/thoughts for improvement. \$\endgroup\$ – user1095108 Sep 20 '13 at 9:31
  • \$\begingroup\$ @user1095108 I think the problems you have with std::unordered_map and custom allocators are related to incomplete libstdc++ support for constructors taking a single allocator argument, and are unrelated to this specific allocator version. FYI, I posed a question on SO about it. \$\endgroup\$ – TemplateRex Sep 20 '13 at 9:38
  • 1
    \$\begingroup\$ @user1095108 I think your downvoting is rather harsh. I answered in detail how 2 minor fixes would eliminate the (innocent!) warnings from Hinnant's stack allocator. You then respond by making up 2 use cases that do not appear in your original question. How is one going to answer that without more detail? \$\endgroup\$ – TemplateRex Sep 20 '13 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.