1   
//
1   
//
2   
// Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
2   
// Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3   
//
3   
//
4   
// Distributed under the Boost Software License, Version 1.0. (See accompanying
4   
// Distributed under the Boost Software License, Version 1.0. (See accompanying
5   
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5   
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6   
//
6   
//
7   
// Official repository: https://github.com/boostorg/json
7   
// Official repository: https://github.com/boostorg/json
8   
//
8   
//
9  
9  
10   
#ifndef BOOST_JSON_DETAIL_IMPL_STACK_HPP
10   
#ifndef BOOST_JSON_DETAIL_IMPL_STACK_HPP
11   
#define BOOST_JSON_DETAIL_IMPL_STACK_HPP
11   
#define BOOST_JSON_DETAIL_IMPL_STACK_HPP
12  
12  
13   
#include <boost/core/detail/static_assert.hpp>
13   
#include <boost/core/detail/static_assert.hpp>
14   
#include <memory>
14   
#include <memory>
15  
15  
16   
namespace boost {
16   
namespace boost {
17   
namespace json {
17   
namespace json {
18   
namespace detail {
18   
namespace detail {
19  
19  
20   
template<>
20   
template<>
21   
struct stack::non_trivial<void>
21   
struct stack::non_trivial<void>
22   
{
22   
{
23   
    using relocate_t = non_trivial* (*) (non_trivial*, void*);
23   
    using relocate_t = non_trivial* (*) (non_trivial*, void*);
24  
24  
25   
    relocate_t rel;
25   
    relocate_t rel;
26   
    non_trivial* next;
26   
    non_trivial* next;
27   
    std::size_t offset;
27   
    std::size_t offset;
28  
28  
29   
    BOOST_JSON_DECL
29   
    BOOST_JSON_DECL
30   
    non_trivial<>*
30   
    non_trivial<>*
31   
    destroy() noexcept;
31   
    destroy() noexcept;
32  
32  
33   
    BOOST_JSON_DECL
33   
    BOOST_JSON_DECL
34   
    non_trivial*
34   
    non_trivial*
35   
    relocate(void* dst) noexcept;
35   
    relocate(void* dst) noexcept;
36  
36  
37   
protected:
37   
protected:
38   
    ~non_trivial() = default;
38   
    ~non_trivial() = default;
39   
};
39   
};
40  
40  
41   
template< class T >
41   
template< class T >
42   
struct stack::non_trivial
42   
struct stack::non_trivial
43   
    : stack::non_trivial<void>
43   
    : stack::non_trivial<void>
44   
{
44   
{
45   
    T obj;
45   
    T obj;
46  
46  
47   
    explicit
47   
    explicit
48   
    non_trivial(T t, non_trivial<>* next, std::size_t offset)
48   
    non_trivial(T t, non_trivial<>* next, std::size_t offset)
49   
        : non_trivial<void>{relocate, next, offset}, obj( std::move(t) )
49   
        : non_trivial<void>{relocate, next, offset}, obj( std::move(t) )
50   
    {}
50   
    {}
51  
51  
52   
    static
52   
    static
53   
    non_trivial<>*
53   
    non_trivial<>*
54   
    relocate(non_trivial<>* src, void* dest) noexcept
54   
    relocate(non_trivial<>* src, void* dest) noexcept
55   
    {
55   
    {
56   
        non_trivial* self = static_cast<non_trivial*>(src);
56   
        non_trivial* self = static_cast<non_trivial*>(src);
57   
        non_trivial<>* result = nullptr;
57   
        non_trivial<>* result = nullptr;
58   
        if( dest )
58   
        if( dest )
59   
            result = ::new(dest) non_trivial( std::move(*self) );
59   
            result = ::new(dest) non_trivial( std::move(*self) );
60   
        self->~non_trivial();
60   
        self->~non_trivial();
61   
        return result;
61   
        return result;
62   
    }
62   
    }
63   
};
63   
};
64  
64  
65   
template<class T>
65   
template<class T>
66   
void
66   
void
67   
stack::
67   
stack::
68   
push_unchecked(T const& t)
68   
push_unchecked(T const& t)
69   
{
69   
{
70   
    constexpr std::size_t n = sizeof(T);
70   
    constexpr std::size_t n = sizeof(T);
71   
    BOOST_CORE_STATIC_ASSERT( is_trivially_copy_assignable<T>::value );
71   
    BOOST_CORE_STATIC_ASSERT( is_trivially_copy_assignable<T>::value );
72   
    BOOST_ASSERT( n <= cap_ - size_ );
72   
    BOOST_ASSERT( n <= cap_ - size_ );
73   
    std::memcpy( base_ + size_, &t, n );
73   
    std::memcpy( base_ + size_, &t, n );
74   
    size_ += n;
74   
    size_ += n;
75   
}
75   
}
76  
76  
77   
template<class T>
77   
template<class T>
78   
void
78   
void
79   
stack::
79   
stack::
80   
peek(T& t)
80   
peek(T& t)
81   
{
81   
{
82   
    constexpr std::size_t n = sizeof(T);
82   
    constexpr std::size_t n = sizeof(T);
83   
    BOOST_CORE_STATIC_ASSERT( is_trivially_copy_assignable<T>::value );
83   
    BOOST_CORE_STATIC_ASSERT( is_trivially_copy_assignable<T>::value );
84   
    BOOST_ASSERT( size_ >= n );
84   
    BOOST_ASSERT( size_ >= n );
85   
    std::memcpy( &t, base_ + size_ - n, n );
85   
    std::memcpy( &t, base_ + size_ - n, n );
86   
}
86   
}
87  
87  
88   
//--------------------------------------
88   
//--------------------------------------
89  
89  
90   
// trivial
90   
// trivial
91   
template<class T>
91   
template<class T>
92   
void
92   
void
93   
stack::
93   
stack::
94   
push(T const& t, std::true_type)
94   
push(T const& t, std::true_type)
95   
{
95   
{
96   
    if( sizeof(T) > cap_ - size_ )
96   
    if( sizeof(T) > cap_ - size_ )
97   
        reserve_impl( sizeof(T) + size_ );
97   
        reserve_impl( sizeof(T) + size_ );
98   
    push_unchecked(t);
98   
    push_unchecked(t);
99   
}
99   
}
100  
100  
101   
// non-trivial
101   
// non-trivial
102   
template<class T>
102   
template<class T>
103   
void
103   
void
104   
stack::
104   
stack::
105   
push(T&& t, std::false_type)
105   
push(T&& t, std::false_type)
106   
{
106   
{
107   
    BOOST_CORE_STATIC_ASSERT( ! is_trivially_copy_assignable<T>::value );
107   
    BOOST_CORE_STATIC_ASSERT( ! is_trivially_copy_assignable<T>::value );
108  
108  
109   
    using Holder = non_trivial< remove_cvref<T> >;
109   
    using Holder = non_trivial< remove_cvref<T> >;
110   
    constexpr std::size_t size = sizeof(Holder);
110   
    constexpr std::size_t size = sizeof(Holder);
111   
    constexpr std::size_t alignment = alignof(Holder);
111   
    constexpr std::size_t alignment = alignof(Holder);
112  
112  
113   
    void* ptr;
113   
    void* ptr;
114   
    std::size_t offset;
114   
    std::size_t offset;
115   
    do
115   
    do
116   
    {
116   
    {
117   
        std::size_t space = cap_ - size_;
117   
        std::size_t space = cap_ - size_;
118   
        unsigned char* buf = base_ + size_;
118   
        unsigned char* buf = base_ + size_;
119   
        ptr = buf;
119   
        ptr = buf;
120   
        if( std::align(alignment, size, ptr, space) )
120   
        if( std::align(alignment, size, ptr, space) )
121   
        {
121   
        {
122   
            offset = (reinterpret_cast<unsigned char*>(ptr) - buf) + size;
122   
            offset = (reinterpret_cast<unsigned char*>(ptr) - buf) + size;
123   
            break;
123   
            break;
124   
        }
124   
        }
125  
125  
126   
        reserve_impl(size_ + size + alignment - 1);
126   
        reserve_impl(size_ + size + alignment - 1);
127   
    }
127   
    }
128   
    while(true);
128   
    while(true);
129   
    BOOST_ASSERT(
129   
    BOOST_ASSERT(
130   
        (reinterpret_cast<unsigned char*>(ptr) + size - offset) ==
130   
        (reinterpret_cast<unsigned char*>(ptr) + size - offset) ==
131   
        (base_ + size_) );
131   
        (base_ + size_) );
132  
132  
133   
    head_ = ::new(ptr) Holder( static_cast<T&&>(t), head_, offset );
133   
    head_ = ::new(ptr) Holder( static_cast<T&&>(t), head_, offset );
134   
    size_ += offset;
134   
    size_ += offset;
135   
}
135   
}
136  
136  
137   
// trivial
137   
// trivial
138   
template<class T>
138   
template<class T>
139   
void
139   
void
140   
stack::
140   
stack::
141   
pop(T& t, std::true_type)
141   
pop(T& t, std::true_type)
142   
{
142   
{
143   
    BOOST_ASSERT( size_ >= sizeof(T) );
143   
    BOOST_ASSERT( size_ >= sizeof(T) );
144   
    peek(t);
144   
    peek(t);
145   
    size_ -= sizeof(T);
145   
    size_ -= sizeof(T);
146   
}
146   
}
147  
147  
148   
// non-trivial
148   
// non-trivial
149   
template<class T>
149   
template<class T>
150   
void
150   
void
151   
stack::
151   
stack::
152   
pop(T& t, std::false_type)
152   
pop(T& t, std::false_type)
153   
{
153   
{
154   
    auto next = head_->next;
154   
    auto next = head_->next;
155   
    auto offset = head_->offset;
155   
    auto offset = head_->offset;
156  
156  
157   
    using U = remove_cvref<T>;
157   
    using U = remove_cvref<T>;
158   
    using Holder = non_trivial<U>;
158   
    using Holder = non_trivial<U>;
159   
    auto const head = static_cast<Holder*>(head_);
159   
    auto const head = static_cast<Holder*>(head_);
160  
160  
161   
    t = std::move( head->obj );
161   
    t = std::move( head->obj );
162   
    head->~Holder();
162   
    head->~Holder();
163  
163  
164   
    head_ = next;
164   
    head_ = next;
165   
    size_ -= offset;
165   
    size_ -= offset;
166   
}
166   
}
167  
167  
168   
} // detail
168   
} // detail
169   
} // json
169   
} // json
170   
} // boost
170   
} // boost
171  
171  
172   
#endif
172   
#endif