# blob.hpp

Go to the documentation of this file.

    00001 /* $Id: blob.hpp 17461 2009-09-07 20:07:47Z rubidium $ */
    00002
    00003 /*
    00004  * This file is part of OpenTTD.
    00005  * 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.
    00006  * 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.
    00007  * 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/>.
    00008  */
    00009
    00012 #ifndef BLOB_HPP
    00013 #define BLOB_HPP
    00014
    00015 #include "../core/alloc_func.hpp"
    00016 #include "../core/mem_func.hpp"
    00017
    00047 class CBlobBaseSimple {
    00048 public:
    00049   typedef ::ptrdiff_t bsize_t;
    00050   typedef ::byte      bitem_t;
    00051
    00052 protected:
    00054   struct CHdr {
    00055     bsize_t    m_size;
    00056     bsize_t    m_max_size;
    00057   };
    00058
    00060   union {
    00061     bitem_t    *m_pData;
    00062     CHdr       *m_pHdr_1;
    00063   } ptr_u;
    00064
    00065 private:
    00067   static const CHdr hdrEmpty[];
    00068
    00069 public:
    00070   static const bsize_t Ttail_reserve = 4;
    00071
    00073   FORCEINLINE CBlobBaseSimple() { InitEmpty(); }
    00075   FORCEINLINE CBlobBaseSimple(const bitem_t *p, bsize_t num_bytes)
    00076   {
    00077     InitEmpty();
    00078     AppendRaw(p, num_bytes);
    00079   }
    00080
    00082   FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src)
    00083   {
    00084     InitEmpty();
    00085     AppendRaw(src);
    00086   }
    00087
    00089   FORCEINLINE CBlobBaseSimple(CHdr * const & pHdr_1)
    00090   {
    00091     assert(pHdr_1 != NULL);
    00092     ptr_u.m_pHdr_1 = pHdr_1;
    00093     *const_cast<CHdr**>(&pHdr_1) = NULL;
    00094   }
    00095
    00097   FORCEINLINE ~CBlobBaseSimple()
    00098   {
    00099     Free();
    00100   }
    00101
    00102 protected:
    00105   FORCEINLINE void InitEmpty()
    00106   {
    00107     ptr_u.m_pHdr_1 = const_cast<CHdr *>(&CBlobBaseSimple::hdrEmpty[1]);
    00108   }
    00109
    00111   FORCEINLINE void Init(CHdr *hdr)
    00112   {
    00113     ptr_u.m_pHdr_1 = &hdr[1];
    00114   }
    00115
    00117   FORCEINLINE CHdr& Hdr()
    00118   {
    00119     return ptr_u.m_pHdr_1[-1];
    00120   }
    00121
    00123   FORCEINLINE const CHdr& Hdr() const
    00124   {
    00125     return ptr_u.m_pHdr_1[-1];
    00126   }
    00127
    00129   FORCEINLINE bsize_t& RawSizeRef()
    00130   {
    00131     return Hdr().m_size;
    00132   };
    00133
    00134 public:
    00136   FORCEINLINE bool IsEmpty() const
    00137   {
    00138     return RawSize() == 0;
    00139   }
    00140
    00142   FORCEINLINE bsize_t RawSize() const
    00143   {
    00144     return Hdr().m_size;
    00145   };
    00146
    00148   FORCEINLINE bsize_t MaxRawSize() const
    00149   {
    00150     return Hdr().m_max_size;
    00151   };
    00152
    00154   FORCEINLINE bitem_t *RawData()
    00155   {
    00156     return ptr_u.m_pData;
    00157   }
    00158
    00160   FORCEINLINE const bitem_t *RawData() const
    00161   {
    00162     return ptr_u.m_pData;
    00163   }
    00164
    00166   //FORCEINLINE bsize_t Crc32() const
    00167   //{
    00168   //  return CCrc32::Calc(RawData(), RawSize());
    00169   //}
    00170
    00172   FORCEINLINE void Clear()
    00173   {
    00174     RawSizeRef() = 0;
    00175   }
    00176
    00178   FORCEINLINE void Free()
    00179   {
    00180     if (MaxRawSize() > 0) {
    00181       RawFree(&Hdr());
    00182       InitEmpty();
    00183     }
    00184   }
    00185
    00187   FORCEINLINE void CopyFrom(const CBlobBaseSimple& src)
    00188   {
    00189     Clear();
    00190     AppendRaw(src);
    00191   }
    00192
    00194   FORCEINLINE void MoveFrom(CBlobBaseSimple& src)
    00195   {
    00196     Free();
    00197     ptr_u.m_pData = src.ptr_u.m_pData;
    00198     src.InitEmpty();
    00199   }
    00200
    00202   FORCEINLINE void Swap(CBlobBaseSimple& src)
    00203   {
    00204     bitem_t *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData;
    00205     src.ptr_u.m_pData = tmp;
    00206   }
    00207
    00209   FORCEINLINE void AppendRaw(const void *p, bsize_t num_bytes)
    00210   {
    00211     assert(p != NULL);
    00212     if (num_bytes > 0) {
    00213       memcpy(GrowRawSize(num_bytes), p, num_bytes);
    00214     } else {
    00215       assert(num_bytes >= 0);
    00216     }
    00217   }
    00218
    00220   FORCEINLINE void AppendRaw(const CBlobBaseSimple& src)
    00221   {
    00222     if (!src.IsEmpty())
    00223       memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize());
    00224   }
    00225
    00228   FORCEINLINE bitem_t *MakeRawFreeSpace(bsize_t num_bytes)
    00229   {
    00230     assert(num_bytes >= 0);
    00231     bsize_t new_size = RawSize() + num_bytes;
    00232     if (new_size > MaxRawSize()) SmartAlloc(new_size);
    00233     return ptr_u.m_pData + RawSize();
    00234   }
    00235
    00238   FORCEINLINE bitem_t *GrowRawSize(bsize_t num_bytes)
    00239   {
    00240     bitem_t *pNewData = MakeRawFreeSpace(num_bytes);
    00241     RawSizeRef() += num_bytes;
    00242     return pNewData;
    00243   }
    00244
    00246   FORCEINLINE void ReduceRawSize(bsize_t num_bytes)
    00247   {
    00248     if (MaxRawSize() > 0 && num_bytes > 0) {
    00249       assert(num_bytes <= RawSize());
    00250       if (num_bytes < RawSize()) {
    00251         RawSizeRef() -= num_bytes;
    00252       } else {
    00253         RawSizeRef() = 0;
    00254       }
    00255     }
    00256   }
    00257
    00259   void SmartAlloc(bsize_t new_size)
    00260   {
    00261     bsize_t old_max_size = MaxRawSize();
    00262     if (old_max_size >= new_size) return;
    00263     /* calculate minimum block size we need to allocate */
    00264     bsize_t min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve;
    00265     /* ask allocation policy for some reasonable block size */
    00266     bsize_t alloc_size = AllocPolicy(min_alloc_size);
    00267     /* allocate new block */
    00268     CHdr *pNewHdr = RawAlloc(alloc_size);
    00269     /* setup header */
    00270     pNewHdr->m_size = RawSize();
    00271     pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve);
    00272     /* copy existing data */
    00273     if (RawSize() > 0)
    00274       memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size);
    00275     /* replace our block with new one */
    00276     CHdr *pOldHdr = &Hdr();
    00277     Init(pNewHdr);
    00278     if (old_max_size > 0)
    00279       RawFree(pOldHdr);
    00280   }
    00281
    00283   FORCEINLINE static bsize_t AllocPolicy(bsize_t min_alloc)
    00284   {
    00285     if (min_alloc < (1 << 9)) {
    00286       if (min_alloc < (1 << 5)) return (1 << 5);
    00287       return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9);
    00288     }
    00289     if (min_alloc < (1 << 15)) {
    00290       if (min_alloc < (1 << 11)) return (1 << 11);
    00291       return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15);
    00292     }
    00293     if (min_alloc < (1 << 20)) {
    00294       if (min_alloc < (1 << 17)) return (1 << 17);
    00295       return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20);
    00296     }
    00297     min_alloc = (min_alloc | ((1 << 20) - 1)) + 1;
    00298     return min_alloc;
    00299   }
    00300
    00302   static FORCEINLINE CHdr *RawAlloc(bsize_t num_bytes)
    00303   {
    00304     return (CHdr*)MallocT<byte>(num_bytes);
    00305   }
    00306
    00308   static FORCEINLINE void RawFree(CHdr *p)
    00309   {
    00310     /* Just to silence an unsilencable GCC 4.4+ warning. */
    00311     assert(p != CBlobBaseSimple::hdrEmpty);
    00312
    00313     /* In case GCC warns about the following, see GCC's PR38509 why it is bogus. */
    00314     free(p);
    00315   }
    00317   FORCEINLINE void FixTail() const
    00318   {
    00319     if (MaxRawSize() > 0) {
    00320       bitem_t *p = &ptr_u.m_pData[RawSize()];
    00321       for (bsize_t i = 0; i < Ttail_reserve; i++) {
    00322         p[i] = 0;
    00323       }
    00324     }
    00325   }
    00326 };
    00327
    00335 template <class Titem_, class Tbase_ = CBlobBaseSimple>
    00336 class CBlobT : public Tbase_ {
    00337   /* make template arguments public: */
    00338 public:
    00339   typedef Titem_ Titem;
    00340   typedef Tbase_ Tbase;
    00341   typedef typename Tbase::bsize_t bsize_t;
    00342
    00343   static const bsize_t Titem_size = sizeof(Titem);
    00344
    00345   struct OnTransfer {
    00346     typename Tbase_::CHdr *m_pHdr_1;
    00347     OnTransfer(const OnTransfer& src) : m_pHdr_1(src.m_pHdr_1) {assert(src.m_pHdr_1 != NULL); *const_cast<typename Tbase_::CHdr**>(&src.m_pHdr_1) = NULL;}
    00348     OnTransfer(CBlobT& src) : m_pHdr_1(src.ptr_u.m_pHdr_1) {src.InitEmpty();}
    00349     ~OnTransfer() {assert(m_pHdr_1 == NULL);}
    00350   };
    00351
    00353   FORCEINLINE CBlobT()
    00354     : Tbase()
    00355   {}
    00356
    00358   FORCEINLINE CBlobT(const Titem_ *p, bsize_t num_items)
    00359     : Tbase((typename Tbase_::bitem_t*)p, num_items * Titem_size)
    00360   {}
    00361
    00363   FORCEINLINE CBlobT(const Tbase& src)
    00364     : Tbase(src)
    00365   {
    00366     assert((Tbase::RawSize() % Titem_size) == 0);
    00367   }
    00368
    00370   FORCEINLINE CBlobT(const OnTransfer& ot)
    00371     : Tbase(ot.m_pHdr_1)
    00372   {}
    00373
    00375   FORCEINLINE ~CBlobT()
    00376   {
    00377     Free();
    00378   }
    00379
    00381   FORCEINLINE void CheckIdx(bsize_t idx) const
    00382   {
    00383     assert(idx >= 0); assert(idx < Size());
    00384   }
    00385
    00387   FORCEINLINE Titem *Data()
    00388   {
    00389     return (Titem*)Tbase::RawData();
    00390   }
    00391
    00393   FORCEINLINE const Titem *Data() const
    00394   {
    00395     return (const Titem*)Tbase::RawData();
    00396   }
    00397
    00399   FORCEINLINE Titem *Data(bsize_t idx)
    00400   {
    00401     CheckIdx(idx);
    00402     return (Data() + idx);
    00403   }
    00404
    00406   FORCEINLINE const Titem *Data(bsize_t idx) const
    00407   {
    00408     CheckIdx(idx);
    00409     return (Data() + idx);
    00410   }
    00411
    00413   FORCEINLINE bsize_t Size() const
    00414   {
    00415     return (Tbase::RawSize() / Titem_size);
    00416   }
    00417
    00419   FORCEINLINE bsize_t MaxSize() const
    00420   {
    00421     return (Tbase::MaxRawSize() / Titem_size);
    00422   }
    00424   FORCEINLINE bsize_t GetReserve() const
    00425   {
    00426     return ((Tbase::MaxRawSize() - Tbase::RawSize()) / Titem_size);
    00427   }
    00428
    00430   FORCEINLINE void Free()
    00431   {
    00432     assert((Tbase::RawSize() % Titem_size) == 0);
    00433     bsize_t old_size = Size();
    00434     if (old_size > 0) {
    00435       /* destroy removed items; */
    00436       Titem *pI_last_to_destroy = Data(0);
    00437       for (Titem *pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_();
    00438     }
    00439     Tbase::Free();
    00440   }
    00441
    00443   FORCEINLINE Titem *GrowSizeNC(bsize_t num_items)
    00444   {
    00445     return (Titem*)Tbase::GrowRawSize(num_items * Titem_size);
    00446   }
    00447
    00449   FORCEINLINE Titem *GrowSizeC(bsize_t num_items)
    00450   {
    00451     Titem *pI = GrowSizeNC(num_items);
    00452     for (bsize_t i = num_items; i > 0; i--, pI++) new (pI) Titem();
    00453   }
    00454
    00456   FORCEINLINE void ReduceSize(bsize_t num_items)
    00457   {
    00458     assert((Tbase::RawSize() % Titem_size) == 0);
    00459     bsize_t old_size = Size();
    00460     assert(num_items <= old_size);
    00461     bsize_t new_size = (num_items <= old_size) ? (old_size - num_items) : 0;
    00462     /* destroy removed items; */
    00463     Titem *pI_last_to_destroy = Data(new_size);
    00464     for (Titem *pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem();
    00465     /* remove them */
    00466     Tbase::ReduceRawSize(num_items * Titem_size);
    00467   }
    00468
    00470   FORCEINLINE Titem *AppendNew()
    00471   {
    00472     Titem& dst = *GrowSizeNC(1); // Grow size by one item
    00473     Titem *pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator
    00474     return pNewItem;
    00475   }
    00476
    00478   FORCEINLINE Titem *Append(const Titem& src)
    00479   {
    00480     Titem& dst = *GrowSizeNC(1); // Grow size by one item
    00481     Titem *pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor()
    00482     return pNewItem;
    00483   }
    00484
    00486   FORCEINLINE Titem *Append(const Titem *pSrc, bsize_t num_items)
    00487   {
    00488     Titem *pDst = GrowSizeNC(num_items);
    00489     Titem *pDstOrg = pDst;
    00490     Titem *pDstEnd = pDst + num_items;
    00491     while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++));
    00492     return pDstOrg;
    00493   }
    00494
    00496   FORCEINLINE void RemoveBySwap(bsize_t idx)
    00497   {
    00498     CheckIdx(idx);
    00499     /* destroy removed item */
    00500     Titem *pRemoved = Data(idx);
    00501     RemoveBySwap(pRemoved);
    00502   }
    00503
    00505   FORCEINLINE void RemoveBySwap(Titem *pItem)
    00506   {
    00507     Titem *pLast = Data(Size() - 1);
    00508     assert(pItem >= Data() && pItem <= pLast);
    00509     /* move last item to its new place */
    00510     if (pItem != pLast) {
    00511       pItem->~Titem_();
    00512       new (pItem) Titem_(*pLast);
    00513     }
    00514     /* destroy the last item */
    00515     pLast->~Titem_();
    00516     /* and reduce the raw blob size */
    00517     Tbase::ReduceRawSize(Titem_size);
    00518   }
    00519
    00522   FORCEINLINE Titem *MakeFreeSpace(bsize_t num_items)
    00523   {
    00524     return (Titem*)Tbase::MakeRawFreeSpace(num_items * Titem_size);
    00525   }
    00526
    00527   FORCEINLINE OnTransfer Transfer()
    00528   {
    00529     return OnTransfer(*this);
    00530   };
    00531 };
    00532
    00533
    00534 #endif /* BLOB_HPP */