OpenTTD Source  1.11.0-beta2
blob.hpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD 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.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
10 #ifndef BLOB_HPP
11 #define BLOB_HPP
12 
13 #include "../core/alloc_func.hpp"
14 
45 class ByteBlob {
46 protected:
48  struct BlobHeader {
49  size_t items;
50  size_t capacity;
51  };
52 
54  union {
55  byte *data;
57  };
58 
59 private:
65  static BlobHeader hdrEmpty[];
66 
67 public:
68  static const size_t tail_reserve = 4;
69  static const size_t header_size = sizeof(BlobHeader);
70 
72  inline ByteBlob()
73  {
74  InitEmpty();
75  }
76 
78  inline ByteBlob(const ByteBlob &src)
79  {
80  InitEmpty();
81  AppendRaw(src);
82  }
83 
85  inline ByteBlob(BlobHeader * const & src)
86  {
87  assert(src != nullptr);
88  header = src;
89  *const_cast<BlobHeader**>(&src) = nullptr;
90  }
91 
93  inline ~ByteBlob()
94  {
95  Free();
96  }
97 
98 protected:
100  static inline BlobHeader *RawAlloc(size_t num_bytes)
101  {
102  return (BlobHeader*)MallocT<byte>(num_bytes);
103  }
104 
109  static inline BlobHeader *Zero()
110  {
111  return const_cast<BlobHeader *>(&ByteBlob::hdrEmpty[1]);
112  }
113 
115  static inline size_t AllocPolicy(size_t min_alloc)
116  {
117  if (min_alloc < (1 << 9)) {
118  if (min_alloc < (1 << 5)) return (1 << 5);
119  return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9);
120  }
121  if (min_alloc < (1 << 15)) {
122  if (min_alloc < (1 << 11)) return (1 << 11);
123  return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15);
124  }
125  if (min_alloc < (1 << 20)) {
126  if (min_alloc < (1 << 17)) return (1 << 17);
127  return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20);
128  }
129  min_alloc = (min_alloc | ((1 << 20) - 1)) + 1;
130  return min_alloc;
131  }
132 
134  static inline void RawFree(BlobHeader *p)
135  {
136  /* Just to silence an unsilencable GCC 4.4+ warning. */
137  assert(p != ByteBlob::hdrEmpty);
138 
139  /* In case GCC warns about the following, see GCC's PR38509 why it is bogus. */
140  free(p);
141  }
142 
144  inline void InitEmpty()
145  {
146  header = Zero();
147  }
148 
150  inline void Init(BlobHeader *src)
151  {
152  header = &src[1];
153  }
154 
156  inline BlobHeader& Hdr()
157  {
158  return *(header - 1);
159  }
160 
162  inline const BlobHeader& Hdr() const
163  {
164  return *(header - 1);
165  }
166 
168  inline size_t& LengthRef()
169  {
170  return Hdr().items;
171  }
172 
173 public:
175  inline bool IsEmpty() const
176  {
177  return Length() == 0;
178  }
179 
181  inline size_t Length() const
182  {
183  return Hdr().items;
184  }
185 
187  inline size_t Capacity() const
188  {
189  return Hdr().capacity;
190  }
191 
193  inline byte *Begin()
194  {
195  return data;
196  }
197 
199  inline const byte *Begin() const
200  {
201  return data;
202  }
203 
205  inline void Clear()
206  {
207  LengthRef() = 0;
208  }
209 
211  inline void Free()
212  {
213  if (Capacity() > 0) {
214  RawFree(&Hdr());
215  InitEmpty();
216  }
217  }
218 
220  inline void AppendRaw(const void *p, size_t num_bytes)
221  {
222  assert(p != nullptr);
223  if (num_bytes > 0) {
224  memcpy(Append(num_bytes), p, num_bytes);
225  }
226  }
227 
229  inline void AppendRaw(const ByteBlob& src)
230  {
231  if (!src.IsEmpty()) {
232  memcpy(Append(src.Length()), src.Begin(), src.Length());
233  }
234  }
235 
240  inline byte *Prepare(size_t num_bytes)
241  {
242  size_t new_size = Length() + num_bytes;
243  if (new_size > Capacity()) SmartAlloc(new_size);
244  return data + Length();
245  }
246 
251  inline byte *Append(size_t num_bytes)
252  {
253  byte *pNewData = Prepare(num_bytes);
254  LengthRef() += num_bytes;
255  return pNewData;
256  }
257 
259  void SmartAlloc(size_t new_size)
260  {
261  if (Capacity() >= new_size) return;
262  /* calculate minimum block size we need to allocate
263  * and ask allocation policy for some reasonable block size */
264  assert(new_size < SIZE_MAX - header_size - tail_reserve);
265  new_size = AllocPolicy(header_size + new_size + tail_reserve);
266 
267  /* allocate new block and setup header */
268  BlobHeader *tmp = RawAlloc(new_size);
269  tmp->items = Length();
270  tmp->capacity = new_size - (header_size + tail_reserve);
271 
272  /* copy existing data */
273  if (tmp->items != 0) {
274  memcpy(tmp + 1, data, tmp->items);
275  }
276 
277  /* replace our block with new one */
278  if (Capacity() > 0) {
279  RawFree(&Hdr());
280  }
281  Init(tmp);
282  }
283 
285  inline void FixTail() const
286  {
287  if (Capacity() > 0) {
288  byte *p = &data[Length()];
289  for (uint i = 0; i < tail_reserve; i++) {
290  p[i] = 0;
291  }
292  }
293  }
294 };
295 
305 template <typename T>
306 class CBlobT : public ByteBlob {
307  /* make template arguments public: */
308 public:
309  typedef ByteBlob base;
310 
311  static const size_t type_size = sizeof(T);
312 
313  struct OnTransfer {
314  typename base::BlobHeader *header;
315 
316  OnTransfer(const OnTransfer& src) : header(src.header)
317  {
318  assert(src.header != nullptr);
319  *const_cast<typename base::BlobHeader**>(&src.header) = nullptr;
320  }
321 
322  OnTransfer(CBlobT& src) : header(src.header)
323  {
324  src.InitEmpty();
325  }
326 
327  ~OnTransfer()
328  {
329  assert(header == nullptr);
330  }
331  };
332 
334  inline CBlobT()
335  : base()
336  {}
337 
339  inline CBlobT(const OnTransfer& ot)
340  : base(ot.header)
341  {}
342 
344  inline ~CBlobT()
345  {
346  Free();
347  }
348 
350  inline void CheckIdx(size_t index) const
351  {
352  assert(index < Size());
353  }
354 
356  inline T *Data()
357  {
358  return (T*)base::Begin();
359  }
360 
362  inline const T *Data() const
363  {
364  return (const T*)base::Begin();
365  }
366 
368  inline T *Data(size_t index)
369  {
370  CheckIdx(index);
371  return (Data() + index);
372  }
373 
375  inline const T *Data(size_t index) const
376  {
377  CheckIdx(index);
378  return (Data() + index);
379  }
380 
382  inline size_t Size() const
383  {
384  return (base::Length() / type_size);
385  }
386 
388  inline size_t MaxSize() const
389  {
390  return (base::Capacity() / type_size);
391  }
392 
394  inline size_t GetReserve() const
395  {
396  return ((base::Capacity() - base::Length()) / type_size);
397  }
398 
400  inline T *GrowSizeNC(size_t num_items)
401  {
402  return (T*)base::Append(num_items * type_size);
403  }
404 
409  inline T *MakeFreeSpace(size_t num_items)
410  {
411  return (T*)base::Prepare(num_items * type_size);
412  }
413 
414  inline OnTransfer Transfer()
415  {
416  return OnTransfer(*this);
417  }
418 };
419 
420 
421 #endif /* BLOB_HPP */
ByteBlob::Hdr
const BlobHeader & Hdr() const
blob header accessor - use it rather than using the pointer arithmetic directly - const version
Definition: blob.hpp:162
CBlobT::GetReserve
size_t GetReserve() const
Return number of additional items that can fit in the Blob without buffer reallocation.
Definition: blob.hpp:394
ByteBlob::IsEmpty
bool IsEmpty() const
return true if blob doesn't contain valid data
Definition: blob.hpp:175
ByteBlob::Hdr
BlobHeader & Hdr()
blob header accessor - use it rather than using the pointer arithmetic directly - non-const version
Definition: blob.hpp:156
ByteBlob::Append
byte * Append(size_t num_bytes)
Increase Length() by num_bytes.
Definition: blob.hpp:251
ByteBlob::Init
void Init(BlobHeader *src)
initialize blob by attaching it to the given header followed by data
Definition: blob.hpp:150
ByteBlob::tail_reserve
static const size_t tail_reserve
four extra bytes will be always allocated and zeroed at the end
Definition: blob.hpp:68
CBlobT
Blob - simple dynamic T array.
Definition: blob.hpp:306
ByteBlob::Free
void Free()
free the blob's memory
Definition: blob.hpp:211
ByteBlob::~ByteBlob
~ByteBlob()
destructor
Definition: blob.hpp:93
ByteBlob::RawAlloc
static BlobHeader * RawAlloc(size_t num_bytes)
all allocation should happen here
Definition: blob.hpp:100
ByteBlob::hdrEmpty
static BlobHeader hdrEmpty[]
Just to silence an unsilencable GCC 4.4+ warning Note: This cannot be 'const' as we do a lot of 'hdrE...
Definition: blob.hpp:65
ByteBlob::Capacity
size_t Capacity() const
return the current blob capacity in bytes
Definition: blob.hpp:187
CBlobT::GrowSizeNC
T * GrowSizeNC(size_t num_items)
Grow number of data items in Blob by given number - doesn't construct items.
Definition: blob.hpp:400
ByteBlob::Clear
void Clear()
invalidate blob's data - doesn't free buffer
Definition: blob.hpp:205
ByteBlob::Zero
static BlobHeader * Zero()
Return header pointer to the static BlobHeader with both items and capacity containing zero.
Definition: blob.hpp:109
ByteBlob::ByteBlob
ByteBlob()
default constructor - initializes empty blob
Definition: blob.hpp:72
ByteBlob::InitEmpty
void InitEmpty()
initialize the empty blob
Definition: blob.hpp:144
CBlobT::CBlobT
CBlobT()
Default constructor - makes new Blob ready to accept any data.
Definition: blob.hpp:334
ByteBlob::Prepare
byte * Prepare(size_t num_bytes)
Reallocate if there is no free space for num_bytes bytes.
Definition: blob.hpp:240
ByteBlob::Length
size_t Length() const
return the number of valid data bytes in the blob
Definition: blob.hpp:181
ByteBlob::AllocPolicy
static size_t AllocPolicy(size_t min_alloc)
simple allocation policy - can be optimized later
Definition: blob.hpp:115
ByteBlob::data
byte * data
ptr to the first byte of data
Definition: blob.hpp:55
ByteBlob::RawFree
static void RawFree(BlobHeader *p)
all deallocations should happen here
Definition: blob.hpp:134
CBlobT::Size
size_t Size() const
Return number of items in the Blob.
Definition: blob.hpp:382
CBlobT::~CBlobT
~CBlobT()
Destructor - ensures that allocated memory (if any) is freed.
Definition: blob.hpp:344
ByteBlob::BlobHeader::items
size_t items
actual blob size in bytes
Definition: blob.hpp:49
CBlobT::CheckIdx
void CheckIdx(size_t index) const
Check the validity of item index (only in debug mode)
Definition: blob.hpp:350
ByteBlob::Begin
const byte * Begin() const
return pointer to the first byte of data - const version
Definition: blob.hpp:199
ByteBlob::header
BlobHeader * header
ptr just after the BlobHeader holding items and capacity
Definition: blob.hpp:56
CBlobT::CBlobT
CBlobT(const OnTransfer &ot)
Take ownership constructor.
Definition: blob.hpp:339
ByteBlob
Base class for simple binary blobs.
Definition: blob.hpp:45
CBlobT::OnTransfer
Definition: blob.hpp:313
ByteBlob::FixTail
void FixTail() const
fixing the four bytes at the end of blob data - useful when blob is used to hold string
Definition: blob.hpp:285
ByteBlob::Begin
byte * Begin()
return pointer to the first byte of data - non-const version
Definition: blob.hpp:193
CBlobT::MaxSize
size_t MaxSize() const
Return total number of items that can fit in the Blob without buffer reallocation.
Definition: blob.hpp:388
ByteBlob::AppendRaw
void AppendRaw(const void *p, size_t num_bytes)
append new bytes at the end of existing data bytes - reallocates if necessary
Definition: blob.hpp:220
ByteBlob::AppendRaw
void AppendRaw(const ByteBlob &src)
append bytes from given source blob to the end of existing data bytes - reallocates if necessary
Definition: blob.hpp:229
CBlobT::MakeFreeSpace
T * MakeFreeSpace(size_t num_items)
Ensures that given number of items can be added to the end of Blob.
Definition: blob.hpp:409
ByteBlob::ByteBlob
ByteBlob(const ByteBlob &src)
copy constructor
Definition: blob.hpp:78
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:454
ByteBlob::BlobHeader
header of the allocated memory block
Definition: blob.hpp:48
ByteBlob::SmartAlloc
void SmartAlloc(size_t new_size)
reallocate blob data if needed
Definition: blob.hpp:259
CBlobT::Data
T * Data()
Return pointer to the first data item - non-const version.
Definition: blob.hpp:356
ByteBlob::LengthRef
size_t & LengthRef()
return reference to the actual blob size - used when the size needs to be modified
Definition: blob.hpp:168
ByteBlob::BlobHeader::capacity
size_t capacity
maximum (allocated) size in bytes
Definition: blob.hpp:50
ByteBlob::ByteBlob
ByteBlob(BlobHeader *const &src)
move constructor - take ownership of blob data
Definition: blob.hpp:85