# blob.hpp

Go to the documentation of this file.

    00001 /* $Id: blob.hpp 14949 2009-01-10 00:31:47Z rubidium $ */
    00002
    00005 #ifndef BLOB_HPP
    00006 #define BLOB_HPP
    00007
    00008 #include "../core/alloc_func.hpp"
    00009 #include "../core/mem_func.hpp"
    00010
    00040 class CBlobBaseSimple {
    00041 public:
    00042   typedef ::ptrdiff_t bsize_t;
    00043   typedef ::byte      bitem_t;
    00044
    00045 protected:
    00047   struct CHdr {
    00048     bsize_t    m_size;
    00049     bsize_t    m_max_size;
    00050   };
    00051
    00053   union {
    00054     bitem_t    *m_pData;
    00055 #if defined(HAS_WCHAR)
    00056     wchar_t    *m_pwData;
    00057 #endif /* HAS_WCHAR */
    00058     CHdr       *m_pHdr_1;
    00059   } ptr_u;
    00060
    00061 public:
    00062   static const bsize_t Ttail_reserve = 4;
    00063
    00065   FORCEINLINE CBlobBaseSimple() { InitEmpty(); }
    00067   FORCEINLINE CBlobBaseSimple(const bitem_t *p, bsize_t num_bytes)
    00068   {
    00069     InitEmpty();
    00070     AppendRaw(p, num_bytes);
    00071   }
    00072
    00074   FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src)
    00075   {
    00076     InitEmpty();
    00077     AppendRaw(src);
    00078   }
    00079
    00081   FORCEINLINE CBlobBaseSimple(CHdr * const & pHdr_1)
    00082   {
    00083     assert(pHdr_1 != NULL);
    00084     ptr_u.m_pHdr_1 = pHdr_1;
    00085     *(CHdr**)&pHdr_1 = NULL;
    00086   }
    00087
    00089   FORCEINLINE ~CBlobBaseSimple()
    00090   {
    00091     Free();
    00092   }
    00093
    00094 protected:
    00097   FORCEINLINE void InitEmpty()
    00098   {
    00099     static CHdr hdrEmpty[] = {{0, 0}, {0, 0}};
    00100     ptr_u.m_pHdr_1 = &hdrEmpty[1];
    00101   }
    00102
    00104   FORCEINLINE void Init(CHdr *hdr)
    00105   {
    00106     ptr_u.m_pHdr_1 = &hdr[1];
    00107   }
    00108
    00110   FORCEINLINE CHdr& Hdr()
    00111   {
    00112     return ptr_u.m_pHdr_1[-1];
    00113   }
    00114
    00116   FORCEINLINE const CHdr& Hdr() const
    00117   {
    00118     return ptr_u.m_pHdr_1[-1];
    00119   }
    00120
    00122   FORCEINLINE bsize_t& RawSizeRef()
    00123   {
    00124     return Hdr().m_size;
    00125   };
    00126
    00127 public:
    00129   FORCEINLINE bool IsEmpty() const
    00130   {
    00131     return RawSize() == 0;
    00132   }
    00133
    00135   FORCEINLINE bsize_t RawSize() const
    00136   {
    00137     return Hdr().m_size;
    00138   };
    00139
    00141   FORCEINLINE bsize_t MaxRawSize() const
    00142   {
    00143     return Hdr().m_max_size;
    00144   };
    00145
    00147   FORCEINLINE bitem_t *RawData()
    00148   {
    00149     return ptr_u.m_pData;
    00150   }
    00151
    00153   FORCEINLINE const bitem_t *RawData() const
    00154   {
    00155     return ptr_u.m_pData;
    00156   }
    00157
    00159   //FORCEINLINE bsize_t Crc32() const
    00160   //{
    00161   //  return CCrc32::Calc(RawData(), RawSize());
    00162   //}
    00163
    00165   FORCEINLINE void Clear()
    00166   {
    00167     RawSizeRef() = 0;
    00168   }
    00169
    00171   FORCEINLINE void Free()
    00172   {
    00173     if (MaxRawSize() > 0) {
    00174       RawFree(&Hdr());
    00175       InitEmpty();
    00176     }
    00177   }
    00178
    00180   FORCEINLINE void CopyFrom(const CBlobBaseSimple& src)
    00181   {
    00182     Clear();
    00183     AppendRaw(src);
    00184   }
    00185
    00187   FORCEINLINE void MoveFrom(CBlobBaseSimple& src)
    00188   {
    00189     Free();
    00190     ptr_u.m_pData = src.ptr_u.m_pData;
    00191     src.InitEmpty();
    00192   }
    00193
    00195   FORCEINLINE void Swap(CBlobBaseSimple& src)
    00196   {
    00197     bitem_t *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData;
    00198     src.ptr_u.m_pData = tmp;
    00199   }
    00200
    00202   FORCEINLINE void AppendRaw(const void *p, bsize_t num_bytes)
    00203   {
    00204     assert(p != NULL);
    00205     if (num_bytes > 0) {
    00206       memcpy(GrowRawSize(num_bytes), p, num_bytes);
    00207     } else {
    00208       assert(num_bytes >= 0);
    00209     }
    00210   }
    00211
    00213   FORCEINLINE void AppendRaw(const CBlobBaseSimple& src)
    00214   {
    00215     if (!src.IsEmpty())
    00216       memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize());
    00217   }
    00218
    00221   FORCEINLINE bitem_t *MakeRawFreeSpace(bsize_t num_bytes)
    00222   {
    00223     assert(num_bytes >= 0);
    00224     bsize_t new_size = RawSize() + num_bytes;
    00225     if (new_size > MaxRawSize()) SmartAlloc(new_size);
    00226     return ptr_u.m_pData + RawSize();
    00227   }
    00228
    00231   FORCEINLINE bitem_t *GrowRawSize(bsize_t num_bytes)
    00232   {
    00233     bitem_t *pNewData = MakeRawFreeSpace(num_bytes);
    00234     RawSizeRef() += num_bytes;
    00235     return pNewData;
    00236   }
    00237
    00239   FORCEINLINE void ReduceRawSize(bsize_t num_bytes)
    00240   {
    00241     if (MaxRawSize() > 0 && num_bytes > 0) {
    00242       assert(num_bytes <= RawSize());
    00243       if (num_bytes < RawSize()) RawSizeRef() -= num_bytes;
    00244       else RawSizeRef() = 0;
    00245     }
    00246   }
    00247
    00249   void SmartAlloc(bsize_t new_size)
    00250   {
    00251     bsize_t old_max_size = MaxRawSize();
    00252     if (old_max_size >= new_size) return;
    00253     // calculate minimum block size we need to allocate
    00254     bsize_t min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve;
    00255     // ask allocation policy for some reasonable block size
    00256     bsize_t alloc_size = AllocPolicy(min_alloc_size);
    00257     // allocate new block
    00258     CHdr *pNewHdr = RawAlloc(alloc_size);
    00259     // setup header
    00260     pNewHdr->m_size = RawSize();
    00261     pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve);
    00262     // copy existing data
    00263     if (RawSize() > 0)
    00264       memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size);
    00265     // replace our block with new one
    00266     CHdr *pOldHdr = &Hdr();
    00267     Init(pNewHdr);
    00268     if (old_max_size > 0)
    00269       RawFree(pOldHdr);
    00270   }
    00271
    00273   FORCEINLINE static bsize_t AllocPolicy(bsize_t min_alloc)
    00274   {
    00275     if (min_alloc < (1 << 9)) {
    00276       if (min_alloc < (1 << 5)) return (1 << 5);
    00277       return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9);
    00278     }
    00279     if (min_alloc < (1 << 15)) {
    00280       if (min_alloc < (1 << 11)) return (1 << 11);
    00281       return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15);
    00282     }
    00283     if (min_alloc < (1 << 20)) {
    00284       if (min_alloc < (1 << 17)) return (1 << 17);
    00285       return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20);
    00286     }
    00287     min_alloc = (min_alloc | ((1 << 20) - 1)) + 1;
    00288     return min_alloc;
    00289   }
    00290
    00292   static FORCEINLINE CHdr *RawAlloc(bsize_t num_bytes)
    00293   {
    00294     return (CHdr*)MallocT<byte>(num_bytes);
    00295   }
    00296
    00298   static FORCEINLINE void RawFree(CHdr *p)
    00299   {
    00300     free(p);
    00301   }
    00303   FORCEINLINE void FixTail() const
    00304   {
    00305     if (MaxRawSize() > 0) {
    00306       bitem_t *p = &ptr_u.m_pData[RawSize()];
    00307       for (bsize_t i = 0; i < Ttail_reserve; i++) {
    00308         p[i] = 0;
    00309       }
    00310     }
    00311   }
    00312 };
    00313
    00321 template <class Titem_, class Tbase_ = CBlobBaseSimple>
    00322 class CBlobT : public Tbase_ {
    00323   // make template arguments public:
    00324 public:
    00325   typedef Titem_ Titem;
    00326   typedef Tbase_ Tbase;
    00327   typedef typename Tbase::bsize_t bsize_t;
    00328
    00329   static const bsize_t Titem_size = sizeof(Titem);
    00330
    00331   struct OnTransfer {
    00332     typename Tbase_::CHdr *m_pHdr_1;
    00333     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;}
    00334     OnTransfer(CBlobT& src) : m_pHdr_1(src.ptr_u.m_pHdr_1) {src.InitEmpty();}
    00335     ~OnTransfer() {assert(m_pHdr_1 == NULL);}
    00336   };
    00337
    00339   FORCEINLINE CBlobT()
    00340     : Tbase()
    00341   {}
    00342
    00344   FORCEINLINE CBlobT(const Titem_ *p, bsize_t num_items)
    00345     : Tbase((typename Tbase_::bitem_t*)p, num_items * Titem_size)
    00346   {}
    00347
    00349   FORCEINLINE CBlobT(const Tbase& src)
    00350     : Tbase(src)
    00351   {
    00352     assert((Tbase::RawSize() % Titem_size) == 0);
    00353   }
    00354
    00356   FORCEINLINE CBlobT(const OnTransfer& ot)
    00357     : Tbase(ot.m_pHdr_1)
    00358   {}
    00359
    00361   FORCEINLINE ~CBlobT()
    00362   {
    00363     Free();
    00364   }
    00365
    00367   FORCEINLINE void CheckIdx(bsize_t idx) const
    00368   {
    00369     assert(idx >= 0); assert(idx < Size());
    00370   }
    00371
    00373   FORCEINLINE Titem *Data()
    00374   {
    00375     return (Titem*)Tbase::RawData();
    00376   }
    00377
    00379   FORCEINLINE const Titem *Data() const
    00380   {
    00381     return (const Titem*)Tbase::RawData();
    00382   }
    00383
    00385   FORCEINLINE Titem *Data(bsize_t idx)
    00386   {
    00387     CheckIdx(idx);
    00388     return (Data() + idx);
    00389   }
    00390
    00392   FORCEINLINE const Titem *Data(bsize_t idx) const
    00393   {
    00394     CheckIdx(idx);
    00395     return (Data() + idx);
    00396   }
    00397
    00399   FORCEINLINE bsize_t Size() const
    00400   {
    00401     return (Tbase::RawSize() / Titem_size);
    00402   }
    00403
    00405   FORCEINLINE bsize_t MaxSize() const
    00406   {
    00407     return (Tbase::MaxRawSize() / Titem_size);
    00408   }
    00410   FORCEINLINE bsize_t GetReserve() const
    00411   {
    00412     return ((Tbase::MaxRawSize() - Tbase::RawSize()) / Titem_size);
    00413   }
    00414
    00416   FORCEINLINE void Free()
    00417   {
    00418     assert((Tbase::RawSize() % Titem_size) == 0);
    00419     bsize_t old_size = Size();
    00420     if (old_size > 0) {
    00421       // destroy removed items;
    00422       Titem *pI_last_to_destroy = Data(0);
    00423       for (Titem *pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_();
    00424     }
    00425     Tbase::Free();
    00426   }
    00427
    00429   FORCEINLINE Titem *GrowSizeNC(bsize_t num_items)
    00430   {
    00431     return (Titem*)Tbase::GrowRawSize(num_items * Titem_size);
    00432   }
    00433
    00435   FORCEINLINE Titem *GrowSizeC(bsize_t num_items)
    00436   {
    00437     Titem *pI = GrowSizeNC(num_items);
    00438     for (bsize_t i = num_items; i > 0; i--, pI++) new (pI) Titem();
    00439   }
    00440
    00442   FORCEINLINE void ReduceSize(bsize_t num_items)
    00443   {
    00444     assert((Tbase::RawSize() % Titem_size) == 0);
    00445     bsize_t old_size = Size();
    00446     assert(num_items <= old_size);
    00447     bsize_t new_size = (num_items <= old_size) ? (old_size - num_items) : 0;
    00448     // destroy removed items;
    00449     Titem *pI_last_to_destroy = Data(new_size);
    00450     for (Titem *pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem();
    00451     // remove them
    00452     Tbase::ReduceRawSize(num_items * Titem_size);
    00453   }
    00454
    00456   FORCEINLINE Titem *AppendNew()
    00457   {
    00458     Titem& dst = *GrowSizeNC(1); // Grow size by one item
    00459     Titem *pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator
    00460     return pNewItem;
    00461   }
    00462
    00464   FORCEINLINE Titem *Append(const Titem& src)
    00465   {
    00466     Titem& dst = *GrowSizeNC(1); // Grow size by one item
    00467     Titem *pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor()
    00468     return pNewItem;
    00469   }
    00470
    00472   FORCEINLINE Titem *Append(const Titem *pSrc, bsize_t num_items)
    00473   {
    00474     Titem *pDst = GrowSizeNC(num_items);
    00475     Titem *pDstOrg = pDst;
    00476     Titem *pDstEnd = pDst + num_items;
    00477     while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++));
    00478     return pDstOrg;
    00479   }
    00480
    00482   FORCEINLINE void RemoveBySwap(bsize_t idx)
    00483   {
    00484     CheckIdx(idx);
    00485     // destroy removed item
    00486     Titem *pRemoved = Data(idx);
    00487     RemoveBySwap(pRemoved);
    00488   }
    00489
    00491   FORCEINLINE void RemoveBySwap(Titem *pItem)
    00492   {
    00493     Titem *pLast = Data(Size() - 1);
    00494     assert(pItem >= Data() && pItem <= pLast);
    00495     // move last item to its new place
    00496     if (pItem != pLast) {
    00497       pItem->~Titem_();
    00498       new (pItem) Titem_(*pLast);
    00499     }
    00500     // destroy the last item
    00501     pLast->~Titem_();
    00502     // and reduce the raw blob size
    00503     Tbase::ReduceRawSize(Titem_size);
    00504   }
    00505
    00508   FORCEINLINE Titem *MakeFreeSpace(bsize_t num_items)
    00509   {
    00510     return (Titem*)Tbase::MakeRawFreeSpace(num_items * Titem_size);
    00511   }
    00512
    00513   FORCEINLINE OnTransfer Transfer()
    00514   {
    00515     return OnTransfer(*this);
    00516   };
    00517 };
    00518
    00519
    00520 #endif /* BLOB_HPP */