iOS/Pods/Realm/include/core/realm/util/buffer.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2016 Realm Inc.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  **************************************************************************/
  18
  19 #ifndef REALM_UTIL_BUFFER_HPP
  20 #define REALM_UTIL_BUFFER_HPP
  21
  22 #include <cstddef>
  23 #include <algorithm>
  24 #include <exception>
  25 #include <limits>
  26 #include <utility>
  27
  28 #include <realm/util/features.h>
  29 #include <realm/utilities.hpp>
  30 #include <realm/util/safe_int_ops.hpp>
  31 #include <memory>
  32
  33 namespace realm {
  34 namespace util {
  35
  36
  37 /// A simple buffer concept that owns a region of memory and knows its
  38 /// size.
  39 template <class T>
  40 class Buffer {
  41 public:
  42     Buffer() noexcept
  43         : m_size(0)
  44     {
  45     }
  46     explicit Buffer(size_t initial_size);
  47     Buffer(Buffer<T>&&) noexcept = default;
  48     ~Buffer() noexcept
  49     {
  50     }
  51
  52     Buffer<T>& operator=(Buffer<T>&&) noexcept = default;
  53
  54     T& operator[](size_t i) noexcept
  55     {
  56         return m_data[i];
  57     }
  58     const T& operator[](size_t i) const noexcept
  59     {
  60         return m_data[i];
  61     }
  62
  63     T* data() noexcept
  64     {
  65         return m_data.get();
  66     }
  67     const T* data() const noexcept
  68     {
  69         return m_data.get();
  70     }
  71     size_t size() const noexcept
  72     {
  73         return m_size;
  74     }
  75
  76     /// False iff the data() returns null.
  77     explicit operator bool() const noexcept
  78     {
  79         return bool(m_data);
  80     }
  81
  82     /// Discards the original contents.
  83     void set_size(size_t new_size);
  84
  85     /// \param new_size Specifies the new buffer size.
  86     /// \param copy_begin, copy_end Specifies a range of element
  87     /// values to be retained. \a copy_end must be less than, or equal
  88     /// to size().
  89     ///
  90     /// \param copy_to Specifies where the retained range should be
  91     /// copied to. `\a copy_to + \a copy_end - \a copy_begin` must be
  92     /// less than, or equal to \a new_size.
  93     void resize(size_t new_size, size_t copy_begin, size_t copy_end, size_t copy_to);
  94
  95     void reserve(size_t used_size, size_t min_capacity);
  96
  97     void reserve_extra(size_t used_size, size_t min_extra_capacity);
  98
  99     T* release() noexcept;
 100
 101     friend void swap(Buffer& a, Buffer& b) noexcept
 102     {
 103         using std::swap;
 104         swap(a.m_data, b.m_data);
 105         swap(a.m_size, b.m_size);
 106     }
 107
 108 private:
 109     std::unique_ptr<T[]> m_data;
 110     size_t m_size;
 111 };
 112
 113
 114 /// A buffer that can be efficiently resized. It acheives this by
 115 /// using an underlying buffer that may be larger than the logical
 116 /// size, and is automatically expanded in progressively larger steps.
 117 template <class T>
 118 class AppendBuffer {
 119 public:
 120     AppendBuffer() noexcept;
 121     ~AppendBuffer() noexcept
 122     {
 123     }
 124
 125     AppendBuffer(AppendBuffer&&) noexcept = default;
 126     AppendBuffer& operator=(AppendBuffer&&) noexcept = default;
 127
 128     /// Returns the current size of the buffer.
 129     size_t size() const noexcept;
 130
 131     /// Gives read and write access to the elements.
 132     T* data() noexcept;
 133
 134     /// Gives read access the elements.
 135     const T* data() const noexcept;
 136
 137     /// Append the specified elements. This increases the size of this
 138     /// buffer by \a append_data_size. If the caller has previously requested
 139     /// a minimum capacity that is greater than, or equal to the
 140     /// resulting size, this function is guaranteed to not throw.
 141     void append(const T* append_data, size_t append_data_size);
 142
 143     /// If the specified size is less than the current size, then the
 144     /// buffer contents is truncated accordingly. If the specified
 145     /// size is greater than the current size, then the extra elements
 146     /// will have undefined values. If the caller has previously
 147     /// requested a minimum capacity that is greater than, or equal to
 148     /// the specified size, this function is guaranteed to not throw.
 149     void resize(size_t new_size);
 150
 151     /// This operation does not change the size of the buffer as
 152     /// returned by size(). If the specified capacity is less than the
 153     /// current capacity, this operation has no effect.
 154     void reserve(size_t min_capacity);
 155
 156     /// Set the size to zero. The capacity remains unchanged.
 157     void clear() noexcept;
 158
 159     /// Release the underlying buffer and reset the size. Note: The returned
 160     /// buffer may be larger than the amount of data appended to this buffer.
 161     /// Callers should call `size()` prior to releasing the buffer to know the
 162     /// usable/logical size.
 163     Buffer<T> release() noexcept;
 164
 165 private:
 166     util::Buffer<T> m_buffer;
 167     size_t m_size;
 168 };
 169
 170
 171 // Implementation:
 172
 173 class BufferSizeOverflow : public std::exception {
 174 public:
 175     const char* what() const noexcept override
 176     {
 177         return "Buffer size overflow";
 178     }
 179 };
 180
 181 template <class T>
 182 inline Buffer<T>::Buffer(size_t initial_size)
 183     : m_data(new T[initial_size]) // Throws
 184     , m_size(initial_size)
 185 {
 186 }
 187
 188 template <class T>
 189 inline void Buffer<T>::set_size(size_t new_size)
 190 {
 191     m_data.reset(new T[new_size]); // Throws
 192     m_size = new_size;
 193 }
 194
 195 template <class T>
 196 inline void Buffer<T>::resize(size_t new_size, size_t copy_begin, size_t copy_end, size_t copy_to)
 197 {
 198     std::unique_ptr<T[]> new_data(new T[new_size]); // Throws
 199     realm::safe_copy_n(m_data.get() + copy_begin, copy_end - copy_begin, new_data.get() + copy_to);
 200     m_data.reset(new_data.release());
 201     m_size = new_size;
 202 }
 203
 204 template <class T>
 205 inline void Buffer<T>::reserve(size_t used_size, size_t min_capacity)
 206 {
 207     size_t current_capacity = m_size;
 208     if (REALM_LIKELY(current_capacity >= min_capacity))
 209         return;
 210     size_t new_capacity = current_capacity;
 211
 212     // Use growth factor 1.5.
 213     if (REALM_UNLIKELY(int_multiply_with_overflow_detect(new_capacity, 3)))
 214         new_capacity = std::numeric_limits<size_t>::max();
 215     new_capacity /= 2;
 216
 217     if (REALM_UNLIKELY(new_capacity < min_capacity))
 218         new_capacity = min_capacity;
 219     resize(new_capacity, 0, used_size, 0); // Throws
 220 }
 221
 222 template <class T>
 223 inline void Buffer<T>::reserve_extra(size_t used_size, size_t min_extra_capacity)
 224 {
 225     size_t min_capacity = used_size;
 226     if (REALM_UNLIKELY(int_add_with_overflow_detect(min_capacity, min_extra_capacity)))
 227         throw BufferSizeOverflow();
 228     reserve(used_size, min_capacity); // Throws
 229 }
 230
 231 template <class T>
 232 inline T* Buffer<T>::release() noexcept
 233 {
 234     m_size = 0;
 235     return m_data.release();
 236 }
 237
 238
 239 template <class T>
 240 inline AppendBuffer<T>::AppendBuffer() noexcept
 241     : m_size(0)
 242 {
 243 }
 244
 245 template <class T>
 246 inline size_t AppendBuffer<T>::size() const noexcept
 247 {
 248     return m_size;
 249 }
 250
 251 template <class T>
 252 inline T* AppendBuffer<T>::data() noexcept
 253 {
 254     return m_buffer.data();
 255 }
 256
 257 template <class T>
 258 inline const T* AppendBuffer<T>::data() const noexcept
 259 {
 260     return m_buffer.data();
 261 }
 262
 263 template <class T>
 264 inline void AppendBuffer<T>::append(const T* append_data, size_t append_data_size)
 265 {
 266     m_buffer.reserve_extra(m_size, append_data_size); // Throws
 267     realm::safe_copy_n(append_data, append_data_size, m_buffer.data() + m_size);
 268     m_size += append_data_size;
 269 }
 270
 271 template <class T>
 272 inline void AppendBuffer<T>::reserve(size_t min_capacity)
 273 {
 274     m_buffer.reserve(m_size, min_capacity);
 275 }
 276
 277 template <class T>
 278 inline void AppendBuffer<T>::resize(size_t new_size)
 279 {
 280     reserve(new_size);
 281     m_size = new_size;
 282 }
 283
 284 template <class T>
 285 inline void AppendBuffer<T>::clear() noexcept
 286 {
 287     m_size = 0;
 288 }
 289
 290 template <class T>
 291 inline Buffer<T> AppendBuffer<T>::release() noexcept
 292 {
 293     m_size = 0;
 294     return std::move(m_buffer);
 295 }
 296
 297
 298 } // namespace util
 299 } // namespace realm
 300
 301 #endif // REALM_UTIL_BUFFER_HPP