WDL/heapbuf.h

   1 /*
   2     WDL - heapbuf.h
   3     Copyright (C) 2005 and later Cockos Incorporated
   4
   5     This software is provided 'as-is', without any express or implied
   6     warranty.  In no event will the authors be held liable for any damages
   7     arising from the use of this software.
   8
   9     Permission is granted to anyone to use this software for any purpose,
  10     including commercial applications, and to alter it and redistribute it
  11     freely, subject to the following restrictions:
  12
  13     1. The origin of this software must not be misrepresented; you must not
  14        claim that you wrote the original software. If you use this software
  15        in a product, an acknowledgment in the product documentation would be
  16        appreciated but is not required.
  17     2. Altered source versions must be plainly marked as such, and must not be
  18        misrepresented as being the original software.
  19     3. This notice may not be removed or altered from any source distribution.
  20
  21 */
  22
  23 /*
  24
  25   This file provides the interface and implementation for WDL_HeapBuf, a simple
  26   malloc() wrapper for resizeable blocks.
  27
  28   Also in this file is WDL_TypedBuf which is a templated version WDL_HeapBuf
  29   that manages type and type-size.
  30
  31 */
  32
  33 #ifndef _WDL_HEAPBUF_H_
  34 #define _WDL_HEAPBUF_H_
  35
  36 #ifndef WDL_HEAPBUF_IMPL_ONLY
  37
  38 #include "wdltypes.h"
  39
  40 class WDL_HeapBuf
  41 {
  42   public:
  43     // interface
  44 #ifdef WDL_HEAPBUF_INTF_ONLY
  45     void *Resize(int newsize, bool resizedown=true);
  46     void CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig=false);
  47 #endif
  48     void *Get() const { return m_size?m_buf:NULL; } // returns NULL if size is 0
  49     void *GetFast() const { return m_buf; } // returns last buffer if size is 0
  50     int GetSize() const { return m_size; }
  51     void *GetAligned(int align) const {  return (void *)(((UINT_PTR)Get() + (align-1)) & ~(UINT_PTR)(align-1)); }
  52
  53     void SetGranul(int granul) { m_granul = granul; }
  54     int GetGranul() const { return m_granul; }
  55     void Prealloc(int sz) { if (m_alloc < sz && WDL_NORMALLY(m_size < sz)) { const int oldsz = m_size; Resize(sz,false); m_size=oldsz; } }
  56     int GetAlloc() const { return m_alloc; }
  57
  58     void *ResizeOK(int newsize, bool resizedown = true) { void *p=Resize(newsize, resizedown); return GetSize() == newsize ? p : NULL; }
  59
  60     WDL_HeapBuf(const WDL_HeapBuf &cp)
  61     {
  62       m_buf=0;
  63       CopyFrom(&cp,true);
  64     }
  65     WDL_HeapBuf &operator=(const WDL_HeapBuf &cp)
  66     {
  67       CopyFrom(&cp,false);
  68       return *this;
  69     }
  70
  71     void ResizeToCurrent()
  72     {
  73       if (!m_buf || !m_size)
  74       {
  75         free(m_buf);
  76         m_buf = NULL;
  77         m_alloc = 0;
  78       }
  79       else if (m_alloc != m_size)
  80       {
  81         void *nb = realloc(m_buf,m_size);
  82         if (WDL_NORMALLY(nb!=NULL))
  83         {
  84           m_buf = nb;
  85           m_alloc = m_size;
  86         }
  87       }
  88     }
  89
  90     explicit WDL_HeapBuf(int granul=4096) : m_buf(NULL), m_alloc(0), m_size(0), m_granul(granul)
  91     {
  92     }
  93     ~WDL_HeapBuf()
  94     {
  95 #ifdef WDL_HEAPBUF__TRACE_ACTION
  96       if (m_buf) WDL_HEAPBUF__TRACE_ACTION(heapbuf_delete_free);
  97 #endif
  98       free(m_buf);
  99     }
 100
 101 #endif // !WDL_HEAPBUF_IMPL_ONLY
 102
 103     // implementation bits
 104 #ifndef WDL_HEAPBUF_INTF_ONLY
 105     #ifdef WDL_HEAPBUF_IMPL_ONLY
 106       void *WDL_HeapBuf::Resize(int newsize, bool resizedown)
 107     #else
 108       void *Resize(int newsize, bool resizedown=true)
 109     #endif
 110       {
 111         if (newsize<0) newsize=0;
 112         #ifdef DEBUG_TIGHT_ALLOC // horribly slow, do not use for release builds
 113           if (newsize == m_size) return m_buf;
 114
 115           int a = newsize;
 116           if (a > m_size) a=m_size;
 117           void *newbuf = newsize ? malloc(newsize) : 0;
 118           if (!newbuf && newsize)
 119           {
 120             #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 121                 WDL_HEAPBUF_ONMALLOCFAIL(newsize)
 122             #endif
 123             return m_buf;
 124           }
 125           if (newbuf&&m_buf) memcpy(newbuf,m_buf,a);
 126           m_size=m_alloc=newsize;
 127           free(m_buf);
 128           return m_buf=newbuf;
 129         #endif
 130
 131           if (newsize!=m_size || (resizedown && newsize < m_alloc/2))
 132           {
 133             int resizedown_under = 0;
 134             if (resizedown && newsize < m_size)
 135             {
 136               // shrinking buffer: only shrink if allocation decreases to min(alloc/2, alloc-granul*4) or 0
 137               resizedown_under = m_alloc - (m_granul<<2);
 138               if (resizedown_under > m_alloc/2) resizedown_under = m_alloc/2;
 139               if (resizedown_under < 1) resizedown_under=1;
 140             }
 141
 142             if (newsize > m_alloc || newsize < resizedown_under)
 143             {
 144               int granul=newsize/2;
 145               int newalloc;
 146               if (granul < m_granul) granul=m_granul;
 147
 148               if (newsize<1) newalloc=0;
 149               else if (m_granul<4096) newalloc=newsize+granul;
 150               else
 151               {
 152                 granul &= ~4095;
 153                 if (granul< 4096) granul=4096;
 154                 else if (granul>4*1024*1024) granul=4*1024*1024;
 155                 newalloc = ((newsize + granul + 96)&~4095)-96;
 156               }
 157
 158               if (newalloc != m_alloc)
 159               {
 160
 161                 if (newalloc <= 0)
 162                 {
 163 #ifdef WDL_HEAPBUF__TRACE_ACTION
 164                  if (m_buf) WDL_HEAPBUF__TRACE_ACTION(heapbuf_free);
 165 #endif
 166                   free(m_buf);
 167                   m_buf=0;
 168                   m_alloc=0;
 169                   m_size=0;
 170                   return 0;
 171                 }
 172 #ifdef WDL_HEAPBUF__TRACE_ACTION
 173                 if (m_buf) WDL_HEAPBUF__TRACE_ACTION(heapbuf_realloc);
 174                 else WDL_HEAPBUF__TRACE_ACTION(heapbuf_malloc);
 175 #endif
 176                 void *nbuf=realloc(m_buf,newalloc);
 177                 if (!nbuf)
 178                 {
 179 #ifdef WDL_HEAPBUF__TRACE_ACTION
 180                   WDL_HEAPBUF__TRACE_ACTION(heapbuf_mallocfree);
 181 #endif
 182                   if (!(nbuf=malloc(newalloc)))
 183                   {
 184                     #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 185                       WDL_HEAPBUF_ONMALLOCFAIL(newalloc);
 186                     #endif
 187                     return m_size?m_buf:0; // failed, do not resize
 188                   }
 189
 190                   if (m_buf)
 191                   {
 192                     int sz=newsize<m_size?newsize:m_size;
 193                     if (sz>0) memcpy(nbuf,m_buf,sz);
 194                     free(m_buf);
 195                   }
 196                 }
 197
 198                 m_buf=nbuf;
 199                 m_alloc=newalloc;
 200               } // alloc size change
 201             } // need size up or down
 202             m_size=newsize;
 203           } // size change
 204           return m_size?m_buf:0;
 205       }
 206
 207     #ifdef WDL_HEAPBUF_IMPL_ONLY
 208       void WDL_HeapBuf::CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig)
 209     #else
 210       void CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig=false)
 211     #endif
 212       {
 213         if (exactCopyOfConfig) // copy all settings
 214         {
 215           free(m_buf);
 216
 217           m_granul = hb->m_granul;
 218
 219           m_size=m_alloc=0;
 220           m_buf=hb->m_buf && hb->m_alloc>0 ? malloc(m_alloc = hb->m_alloc) : NULL;
 221           #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 222             if (!m_buf && m_alloc) { WDL_HEAPBUF_ONMALLOCFAIL(m_alloc) } ;
 223           #endif
 224           if (m_buf) memcpy(m_buf,hb->m_buf,m_size = hb->m_size);
 225           else m_alloc=0;
 226         }
 227         else // copy just the data + size
 228         {
 229           const int newsz=hb->GetSize();
 230           Resize(newsz,true);
 231           if (GetSize()!=newsz) Resize(0);
 232           else memcpy(Get(),hb->Get(),newsz);
 233         }
 234       }
 235
 236 #endif // ! WDL_HEAPBUF_INTF_ONLY
 237
 238 #ifndef WDL_HEAPBUF_IMPL_ONLY
 239
 240   private:
 241     void *m_buf;
 242     int m_alloc;
 243     int m_size;
 244     int m_granul;
 245
 246   #if defined(_WIN64) || defined(__LP64__)
 247   public:
 248     int ___pad; // keep size 8 byte aligned
 249   #endif
 250
 251 };
 252
 253 template<class PTRTYPE> class WDL_TypedBuf
 254 {
 255   public:
 256     PTRTYPE *Get() const { return (PTRTYPE *) m_hb.Get(); }
 257     PTRTYPE *GetFast() const { return (PTRTYPE *) m_hb.GetFast(); }
 258     int GetSize() const { return m_hb.GetSize()/(unsigned int)sizeof(PTRTYPE); }
 259     int GetSizeBytes() const { return m_hb.GetSize(); }
 260     int GetAlloc() const { return m_hb.GetAlloc()/(unsigned int)sizeof(PTRTYPE); }
 261
 262     PTRTYPE *Resize(int newsize, bool resizedown = true) { return (PTRTYPE *)m_hb.Resize(newsize*sizeof(PTRTYPE),resizedown); }
 263     PTRTYPE *ResizeOK(int newsize, bool resizedown = true) { return (PTRTYPE *)m_hb.ResizeOK(newsize*sizeof(PTRTYPE), resizedown);  }
 264
 265     void Prealloc(int sz) { return m_hb.Prealloc(sz*sizeof(PTRTYPE)); }
 266     void ResizeToCurrent() { m_hb.ResizeToCurrent(); }
 267
 268     void SetToZero() { memset(m_hb.Get(), 0, m_hb.GetSize()); }
 269
 270     PTRTYPE *GetAligned(int align) const  { return (PTRTYPE *) m_hb.GetAligned(align); }
 271
 272     PTRTYPE *Add(PTRTYPE val)
 273     {
 274       const int sz=GetSize();
 275       PTRTYPE* p=ResizeOK(sz+1,false);
 276       if (p)
 277       {
 278         p[sz]=val;
 279         return p+sz;
 280       }
 281       return NULL;
 282     }
 283     PTRTYPE *Add(const PTRTYPE *buf, int bufsz)
 284     {
 285       if (bufsz>0)
 286       {
 287         const int sz=GetSize();
 288         PTRTYPE* p=ResizeOK(sz+bufsz,false);
 289         if (p)
 290         {
 291           p+=sz;
 292           if (buf) memcpy(p,buf,bufsz*sizeof(PTRTYPE));
 293           else memset((char*)p,0,bufsz*sizeof(PTRTYPE));
 294           return p;
 295         }
 296       }
 297       return NULL;
 298     }
 299     PTRTYPE *Set(const PTRTYPE *buf, int bufsz)
 300     {
 301       if (bufsz>=0)
 302       {
 303         PTRTYPE* p=ResizeOK(bufsz,false);
 304         if (p)
 305         {
 306           if (buf) memcpy(p,buf,bufsz*sizeof(PTRTYPE));
 307           else memset((char*)p,0,bufsz*sizeof(PTRTYPE));
 308           return p;
 309         }
 310       }
 311       return NULL;
 312     }
 313     PTRTYPE* Insert(PTRTYPE val, int idx)
 314     {
 315       const int sz=GetSize();
 316       if (idx >= 0 && idx <= sz)
 317       {
 318         PTRTYPE* p=ResizeOK(sz+1,false);
 319         if (p)
 320         {
 321           memmove(p+idx+1, p+idx, (sz-idx)*sizeof(PTRTYPE));
 322           p[idx]=val;
 323           return p+idx;
 324         }
 325       }
 326       return NULL;
 327     }
 328
 329     void Delete(int idx)
 330     {
 331       PTRTYPE* p=Get();
 332       const int sz=GetSize();
 333       if (idx >= 0 && idx < sz)
 334       {
 335         memmove(p+idx, p+idx+1, (sz-idx-1)*sizeof(PTRTYPE));
 336         Resize(sz-1,false);
 337       }
 338     }
 339
 340     void DeleteRange(int index, int count)
 341     {
 342       PTRTYPE *list=Get();
 343       int size=GetSize();
 344       if (list && count > 0 && index >= 0 && index < size)
 345       {
 346         if (count > size - index) count = size - index;
 347         size -= count;
 348         if (index < size)
 349           memmove(list+index,list+index+count,(unsigned int)sizeof(PTRTYPE)*(size-index));
 350         Resize(size,false);
 351       }
 352     }
 353
 354     void SetGranul(int gran) { m_hb.SetGranul(gran); }
 355
 356     int Find(PTRTYPE val) const
 357     {
 358       const PTRTYPE* p=Get();
 359       const int sz=GetSize();
 360       int i;
 361       for (i=0; i < sz; ++i) if (p[i] == val) return i;
 362       return -1;
 363     }
 364
 365     explicit WDL_TypedBuf(int granul=4096) : m_hb(granul) { }
 366     ~WDL_TypedBuf() { }
 367
 368     WDL_HeapBuf *GetHeapBuf() { return &m_hb; }
 369     const WDL_HeapBuf *GetHeapBuf() const { return &m_hb; }
 370
 371     int DeleteBatch(bool (*proc)(PTRTYPE *p, void *ctx), void *ctx=NULL) // proc returns true to delete item. returns number deleted
 372     {
 373       const int sz = GetSize();
 374       int cnt=0;
 375       PTRTYPE *rd = Get(), *wr = rd;
 376       for (int x = 0; x < sz; x ++)
 377       {
 378         if (!proc(rd,ctx))
 379         {
 380           if (rd != wr) *wr=*rd;
 381           wr++;
 382           cnt++;
 383         }
 384         rd++;
 385       }
 386       if (cnt < sz) Resize(cnt,false);
 387       return sz - cnt;
 388     }
 389
 390     const PTRTYPE *begin() const { return Get(); }
 391     const PTRTYPE *end() const { return Get() + GetSize(); }
 392     PTRTYPE *begin() { return Get(); }
 393     PTRTYPE *end() { return Get() + GetSize(); }
 394
 395   private:
 396     WDL_HeapBuf m_hb;
 397 };
 398
 399 #endif // ! WDL_HEAPBUF_IMPL_ONLY
 400
 401 #endif // _WDL_HEAPBUF_H_