1

/* $Id$ */

     2

     4

     5

#ifndef BLOB_HPP

     6

#define BLOB_HPP

     7

     8

#include "../core/alloc_func.hpp"

     9

    10

/** Type-safe version of memcpy().

    11

 * @param d destination buffer

    12

 * @param s source buffer

    13

 * @param num_items number of items to be copied (!not number of bytes!) */

    14

template <class Titem_>

    15

FORCEINLINE void MemCpyT(Titem_* d, const Titem_* s, int num_items = 1)

    16

{

    17

	memcpy(d, s, num_items * sizeof(Titem_));

    18

}

    19

    20

/** Base class for simple binary blobs.

    21

*  Item is byte.

    22

*  The word 'simple' means:

    23

*    - no configurable allocator type (always made from heap)

    24

*    - no smart deallocation - deallocation must be called from the same

    25

*        module (DLL) where the blob was allocated

    26

*    - no configurable allocation policy (how big blocks should be allocated)

    27

*    - no extra ownership policy (i.e. 'copy on write') when blob is copied

    28

*    - no thread synchronization at all

    29

*

    30

*  Internal member layout:

    31

*  1. The only class member is pointer to the first item (see union ptr_u).

    32

*  2. Allocated block contains the blob header (see CHdr) followed by the raw byte data.

    33

*     Always, when it allocates memory the allocated size is:

    34

*                                                      sizeof(CHdr) + <data capacity>

    35

*  3. Two 'virtual' members (m_size and m_max_size) are stored in the CHdr at beginning

    36

*     of the alloated block.

    37

*  4. The pointter (in ptr_u) pobsize_ts behind the header (to the first data byte).

    38

*     When memory block is allocated, the sizeof(CHdr) it added to it.

    39

*  5. Benefits of this layout:

    40

*     - items are accessed in the simplest possible way - just dereferencing the pointer,

    41

*       which is good for performance (assuming that data are accessed most often).

    42

*     - sizeof(blob) is the same as the size of any other pointer

    43

*  6. Drawbacks of this layout:

    44

*     - the fact, that pointer to the alocated block is adjusted by sizeof(CHdr) before

    45

*       it is stored can lead to several confusions:

    46

*         - it is not common pattern so the implementation code is bit harder to read

    47

*         - valgrind can generate warning that allocated block is lost (not accessible)

    48

* */

    49

class CBlobBaseSimple {

    50

public:

    51

	typedef ::ptrdiff_t bsize_t;

    52

	typedef ::byte      bitem_t;

    53

    54

protected:

    55

	/** header of the allocated memory block */

    56

	struct CHdr {

    57

		bsize_t    m_size;      ///< actual blob size in bytes

    58

		bsize_t    m_max_size;  ///< maximum (allocated) size in bytes

    59

	};

    60

    61

	/** type used as class member */

    62

	union {

    63

		bitem_t    *m_pData;    ///< ptr to the first byte of data

    64

#if defined(HAS_WCHAR)

    65

		wchar_t    *m_pwData;   ///< ptr to the first byte of data

    66

#endif /* HAS_WCHAR */

    67

		CHdr       *m_pHdr_1;   ///< ptr just after the CHdr holding m_size and m_max_size

    68

	} ptr_u;

    69

    70

public:

    71

	static const bsize_t Ttail_reserve = 4; ///< four extra bytes will be always allocated and zeroed at the end

    72

    73

	/** default constructor - initializes empty blob */

    74

	FORCEINLINE CBlobBaseSimple() { InitEmpty(); }

    75

	/** constructor - create blob with data */

    76

	FORCEINLINE CBlobBaseSimple(const bitem_t *p, bsize_t num_bytes)

    77

	{

    78

		InitEmpty();

    79

		AppendRaw(p, num_bytes);

    80

	}

    81

    82

	/** copy constructor */

    83

	FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src)

    84

	{

    85

		InitEmpty();

    86

		AppendRaw(src);

    87

	}

    88

    89

	/** move constructor - take ownership of blob data */

    90

	FORCEINLINE CBlobBaseSimple(CHdr * const & pHdr_1)

    91

	{

    92

		assert(pHdr_1 != NULL);

    93

		ptr_u.m_pHdr_1 = pHdr_1;

    94

		*(CHdr**)&pHdr_1 = NULL;

    95

	}

    96

    97

	/** destructor */

    98

	FORCEINLINE ~CBlobBaseSimple()

    99

	{

   100

		Free();

   101

	}

   102

   103

protected:

   104

	/** initialize the empty blob by setting the ptr_u.m_pHdr_1 pointer to the static CHdr with

   105

	*  both m_size and m_max_size containing zero */

   106

	FORCEINLINE void InitEmpty()

   107

	{

   108

		static CHdr hdrEmpty[] = {{0, 0}, {0, 0}};

   109

		ptr_u.m_pHdr_1 = &hdrEmpty[1];

   110

	}

   111

   112

	/** initialize blob by attaching it to the given header followed by data */

   113

	FORCEINLINE void Init(CHdr* hdr)

   114

	{

   115

		ptr_u.m_pHdr_1 = &hdr[1];

   116

	}

   117

   118

	/** blob header accessor - use it rather than using the pointer arithmetics directly - non-const version */

   119

	FORCEINLINE CHdr& Hdr()

   120

	{

   121

		return ptr_u.m_pHdr_1[-1];

   122

	}

   123

   124

	/** blob header accessor - use it rather than using the pointer arithmetics directly - const version */

   125

	FORCEINLINE const CHdr& Hdr() const

   126

	{

   127

		return ptr_u.m_pHdr_1[-1];

   128

	}

   129

   130

	/** return reference to the actual blob size - used when the size needs to be modified */

   131

	FORCEINLINE bsize_t& RawSizeRef()

   132

	{

   133

		return Hdr().m_size;

   134

	};

   135

   136

public:

   137

	/** return true if blob doesn't contain valid data */

   138

	FORCEINLINE bool IsEmpty() const

   139

	{

   140

		return RawSize() == 0;

   141

	}

   142

   143

	/** return the number of valid data bytes in the blob */

   144

	FORCEINLINE bsize_t RawSize() const

   145

	{

   146

		return Hdr().m_size;

   147

	};

   148

   149

	/** return the current blob capacity in bytes */

   150

	FORCEINLINE bsize_t MaxRawSize() const

   151

	{

   152

		return Hdr().m_max_size;

   153

	};

   154

   155

	/** return pointer to the first byte of data - non-const version */

   156

	FORCEINLINE bitem_t* RawData()

   157

	{

   158

		return ptr_u.m_pData;

   159

	}

   160

   161

	/** return pointer to the first byte of data - const version */

   162

	FORCEINLINE const bitem_t* RawData() const

   163

	{

   164

		return ptr_u.m_pData;

   165

	}

   166

   167

	/** return the 32 bit CRC of valid data in the blob */

   168

	//FORCEINLINE bsize_t Crc32() const

   169

	//{

   170

	//	return CCrc32::Calc(RawData(), RawSize());

   171

	//}

   172

   173

	/** invalidate blob's data - doesn't free buffer */

   174

	FORCEINLINE void Clear()

   175

	{

   176

		RawSizeRef() = 0;

   177

	}

   178

   179

	/** free the blob's memory */

   180

	FORCEINLINE void Free()

   181

	{

   182

		if (MaxRawSize() > 0) {

   183

			RawFree(&Hdr());

   184

			InitEmpty();

   185

		}

   186

	}

   187

   188

	/** copy data from another blob - replaces any existing blob's data */

   189

	FORCEINLINE void CopyFrom(const CBlobBaseSimple& src)

   190

	{

   191

		Clear();

   192

		AppendRaw(src);

   193

	}

   194

   195

	/** overtake ownership of data buffer from the source blob - source blob will become empty */

   196

	FORCEINLINE void MoveFrom(CBlobBaseSimple& src)

   197

	{

   198

		Free();

   199

		ptr_u.m_pData = src.ptr_u.m_pData;

   200

		src.InitEmpty();

   201

	}

   202

   203

	/** swap buffers (with data) between two blobs (this and source blob) */

   204

	FORCEINLINE void Swap(CBlobBaseSimple& src)

   205

	{

   206

		bitem_t *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData;

   207

		src.ptr_u.m_pData = tmp;

   208

	}

   209

   210

	/** append new bytes at the end of existing data bytes - reallocates if necessary */

   211

	FORCEINLINE void AppendRaw(const void *p, bsize_t num_bytes)

   212

	{

   213

		assert(p != NULL);

   214

		if (num_bytes > 0) {

   215

			memcpy(GrowRawSize(num_bytes), p, num_bytes);

   216

		} else {

   217

			assert(num_bytes >= 0);

   218

		}

   219

	}

   220

   221

	/** append bytes from given source blob to the end of existing data bytes - reallocates if necessary */

   222

	FORCEINLINE void AppendRaw(const CBlobBaseSimple& src)

   223

	{

   224

		if (!src.IsEmpty())

   225

			memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize());

   226

	}

   227

   228

	/** Reallocate if there is no free space for num_bytes bytes.

   229

	*  @return pointer to the new data to be added */

   230

	FORCEINLINE bitem_t* MakeRawFreeSpace(bsize_t num_bytes)

   231

	{

   232

		assert(num_bytes >= 0);

   233

		bsize_t new_size = RawSize() + num_bytes;

   234

		if (new_size > MaxRawSize()) SmartAlloc(new_size);

   235

		return ptr_u.m_pData + RawSize();

   236

	}

   237

   238

	/** Increase RawSize() by num_bytes.

   239

	*  @return pointer to the new data added */

   240

	FORCEINLINE bitem_t* GrowRawSize(bsize_t num_bytes)

   241

	{

   242

		bitem_t* pNewData = MakeRawFreeSpace(num_bytes);

   243

		RawSizeRef() += num_bytes;

   244

		return pNewData;

   245

	}

   246

   247

	/** Decrease RawSize() by num_bytes. */

   248

	FORCEINLINE void ReduceRawSize(bsize_t num_bytes)

   249

	{

   250

		if (MaxRawSize() > 0 && num_bytes > 0) {

   251

			assert(num_bytes <= RawSize());

   252

			if (num_bytes < RawSize()) RawSizeRef() -= num_bytes;

   253

			else RawSizeRef() = 0;

   254

		}

   255

	}

   256

   257

	/** reallocate blob data if needed */

   258

	void SmartAlloc(bsize_t new_size)

   259

	{

   260

		bsize_t old_max_size = MaxRawSize();

   261

		if (old_max_size >= new_size) return;

   262

		// calculate minimum block size we need to allocate

   263

		bsize_t min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve;

   264

		// ask allocation policy for some reasonable block size

   265

		bsize_t alloc_size = AllocPolicy(min_alloc_size);

   266

		// allocate new block

   267

		CHdr* pNewHdr = RawAlloc(alloc_size);

   268

		// setup header

   269

		pNewHdr->m_size = RawSize();

   270

		pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve);

   271

		// copy existing data

   272

		if (RawSize() > 0)

   273

			memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size);

   274

		// replace our block with new one

   275

		CHdr* pOldHdr = &Hdr();

   276

		Init(pNewHdr);

   277

		if (old_max_size > 0)

   278

			RawFree(pOldHdr);

   279

	}

   280

   281

	/** simple allocation policy - can be optimized later */

   282

	FORCEINLINE static bsize_t AllocPolicy(bsize_t min_alloc)

   283

	{

   284

		if (min_alloc < (1 << 9)) {

   285

			if (min_alloc < (1 << 5)) return (1 << 5);

   286

			return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9);

   287

		}

   288

		if (min_alloc < (1 << 15)) {

   289

			if (min_alloc < (1 << 11)) return (1 << 11);

   290

			return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15);

   291

		}

   292

		if (min_alloc < (1 << 20)) {

   293

			if (min_alloc < (1 << 17)) return (1 << 17);

   294

			return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20);

   295

		}

   296

		min_alloc = (min_alloc | ((1 << 20) - 1)) + 1;

   297

		return min_alloc;

   298

	}

   299

   300

	/** all allocation should happen here */

   301

	static FORCEINLINE CHdr* RawAlloc(bsize_t num_bytes)

   302

	{

   303

		return (CHdr*)MallocT<byte>(num_bytes);

   304

	}

   305

   306

	/** all deallocations should happen here */

   307

	static FORCEINLINE void RawFree(CHdr* p)

   308

	{

   309

		free(p);

   310

	}

   311

	/** fixing the four bytes at the end of blob data - useful when blob is used to hold string */

   312

	FORCEINLINE void FixTail() const

   313

	{

   314

		if (MaxRawSize() > 0) {

   315

			bitem_t *p = &ptr_u.m_pData[RawSize()];

   316

			for (bsize_t i = 0; i < Ttail_reserve; i++) {

   317

				p[i] = 0;

   318

			}

   319

		}

   320

	}

   321

};

   322

   323

/** Blob - simple dynamic Titem_ array. Titem_ (template argument) is a placeholder for any type.

   324

*  Titem_ can be any integral type, pointer, or structure. Using Blob instead of just plain C array

   325

*  simplifies the resource management in several ways:

   326

*  1. When adding new item(s) it automatically grows capacity if needed.

   327

*  2. When variable of type Blob comes out of scope it automatically frees the data buffer.

   328

*  3. Takes care about the actual data size (number of used items).

   329

*  4. Dynamically constructs only used items (as opposite of static array which constructs all items) */

   330

template <class Titem_, class Tbase_ = CBlobBaseSimple>

   331

class CBlobT : public Tbase_ {

   332

	// make template arguments public:

   333

public:

   334

	typedef Titem_ Titem;

   335

	typedef Tbase_ Tbase;

   336

	typedef typename Tbase::bsize_t bsize_t;

   337

   338

	static const bsize_t Titem_size = sizeof(Titem);

   339

   340

	struct OnTransfer {

   341

		typename Tbase_::CHdr *m_pHdr_1;

   342

		OnTransfer(const OnTransfer& src) : m_pHdr_1(src.m_pHdr_1) {assert(src.m_pHdr_1 != NULL); *(typename Tbase_::CHdr**)&src.m_pHdr_1 = NULL;}

   343

		OnTransfer(CBlobT& src) : m_pHdr_1(src.ptr_u.m_pHdr_1) {src.InitEmpty();}

   344

		~OnTransfer() {assert(m_pHdr_1 == NULL);}

   345

	};

   346

   347

	/** Default constructor - makes new Blob ready to accept any data */

   348

	FORCEINLINE CBlobT()

   349

		: Tbase()

   350

	{}

   351

   352

	/** Constructor - makes new Blob with data */

   353

	FORCEINLINE CBlobT(const Titem_ *p, bsize_t num_items)

   354

		: Tbase((typename Tbase_::bitem_t*)p, num_items * Titem_size)

   355

	{}

   356

   357

	/** Copy constructor - make new blob to become copy of the original (source) blob */

   358

	FORCEINLINE CBlobT(const Tbase& src)

   359

		: Tbase(src)

   360

	{

   361

		assert((Tbase::RawSize() % Titem_size) == 0);

   362

	}

   363

   364

	/** Take ownership constructor */

   365

	FORCEINLINE CBlobT(const OnTransfer& ot)

   366

		: Tbase(ot.m_pHdr_1)

   367

	{}

   368

   369

	/** Destructor - ensures that allocated memory (if any) is freed */

   370

	FORCEINLINE ~CBlobT()

   371

	{

   372

		Free();

   373

	}

   374

   375

	/** Check the validity of item index (only in debug mode) */

   377

	{

   378

		assert(idx >= 0); assert(idx < Size());

   379

	}

   380

   381

	/** Return pointer to the first data item - non-const version */

   382

	FORCEINLINE Titem* Data()

   383

	{

   384

		return (Titem*)Tbase::RawData();

   385

	}

   386

   387

	/** Return pointer to the first data item - const version */

   388

	FORCEINLINE const Titem* Data() const

   389

	{

   390

		return (const Titem*)Tbase::RawData();

   391

	}

   392

   393

	/** Return pointer to the idx-th data item - non-const version */

   394

	FORCEINLINE Titem* Data(bsize_t idx)

   395

	{

   396

		CheckIdx(idx);

   397

		return (Data() + idx);

   398

	}

   399

   400

	/** Return pointer to the idx-th data item - const version */

   401

	FORCEINLINE const Titem* Data(bsize_t idx) const

   402

	{

   405

	}

   406

   407

	/** Return number of items in the Blob */

   408

	FORCEINLINE bsize_t Size() const

   409

	{

   410

		return (Tbase::RawSize() / Titem_size);

   411

	}

   412

   413

	/** Return total number of items that can fit in the Blob without buffer reallocation */

   414

	FORCEINLINE bsize_t MaxSize() const

   415

	{

   416

		return (Tbase::MaxRawSize() / Titem_size);

   417

	}

   418

	/** Return number of additional items that can fit in the Blob without buffer reallocation */

   419

	FORCEINLINE bsize_t GetReserve() const

   420

	{

   421

		return ((Tbase::MaxRawSize() - Tbase::RawSize()) / Titem_size);

   422

	}

   423

   424

	/** Free the memory occupied by Blob destroying all items */

   425

	FORCEINLINE void Free()

   426

	{

   427

		assert((Tbase::RawSize() % Titem_size) == 0);

   428

		bsize_t old_size = Size();

   429

		if (old_size > 0) {

   430

			// destroy removed items;

   431

			Titem* pI_last_to_destroy = Data(0);

   432

			for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_();

   433

		}

   434

		Tbase::Free();

   435

	}

   436

   437

	/** Grow number of data items in Blob by given number - doesn't construct items */

   438

	FORCEINLINE Titem* GrowSizeNC(bsize_t num_items)

   439

	{

   440

		return (Titem*)Tbase::GrowRawSize(num_items * Titem_size);

   441

	}

   442

   443

	/** Grow number of data items in Blob by given number - constructs new items (using Titem_'s default constructor) */

   444

	FORCEINLINE Titem* GrowSizeC(bsize_t num_items)

   445

	{

   446

		Titem* pI = GrowSizeNC(num_items);

   447

		for (bsize_t i = num_items; i > 0; i--, pI++) new (pI) Titem();

   448

	}

   449

   450

	/** Destroy given number of items and reduce the Blob's data size */

   451

	FORCEINLINE void ReduceSize(bsize_t num_items)

   452

	{

   453

		assert((Tbase::RawSize() % Titem_size) == 0);

   454

		bsize_t old_size = Size();

   455

		assert(num_items <= old_size);

   456

		bsize_t new_size = (num_items <= old_size) ? (old_size - num_items) : 0;

   457

		// destroy removed items;

   458

		Titem* pI_last_to_destroy = Data(new_size);

   459

		for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem();

   460

		// remove them

   461

		Tbase::ReduceRawSize(num_items * Titem_size);

   462

	}

   463

   464

	/** Append one data item at the end (calls Titem_'s default constructor) */

   465

	FORCEINLINE Titem* AppendNew()

   466

	{

   467

		Titem& dst = *GrowSizeNC(1); // Grow size by one item

   468

		Titem* pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator

   469

		return pNewItem;

   470

	}

   471

   472

	/** Append the copy of given item at the end of Blob (using copy constructor) */

   473

	FORCEINLINE Titem* Append(const Titem& src)

   474

	{

   475

		Titem& dst = *GrowSizeNC(1); // Grow size by one item

   476

		Titem* pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor()

   477

		return pNewItem;

   478

	}

   479

   480

	/** Add given items (ptr + number of items) at the end of blob */

   481

	FORCEINLINE Titem* Append(const Titem* pSrc, bsize_t num_items)

   482

	{

   483

		Titem* pDst = GrowSizeNC(num_items);

   484

		Titem* pDstOrg = pDst;

   485

		Titem* pDstEnd = pDst + num_items;

   486

		while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++));

   487

		return pDstOrg;

   488

	}

   489

   490

	/** Remove item with the given index by replacing it by the last item and reducing the size by one */

   491

	FORCEINLINE void RemoveBySwap(bsize_t idx)

   492

	{

   493

		CheckIdx(idx);

   494

		// destroy removed item

   495