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 #ifdef WDL_HEAPBUF_TRACE
  39 #include <windows.h>
  40 #define WDL_HEAPBUF_TRACEPARM(x) ,(x)
  41 #else
  42 #define WDL_HEAPBUF_TRACEPARM(x)
  43 #endif
  44
  45 #include "wdltypes.h"
  46
  47 class WDL_HeapBuf
  48 {
  49   public:
  50     // interface
  51 #ifdef WDL_HEAPBUF_INTF_ONLY
  52     void *Resize(int newsize, bool resizedown=true);
  53     void CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig=false);
  54 #endif
  55     void *Get() const { return m_size?m_buf:NULL; }
  56     int GetSize() const { return m_size; }
  57     void *GetAligned(int align) const {  return (void *)(((UINT_PTR)Get() + (align-1)) & ~(UINT_PTR)(align-1)); }
  58
  59     void SetGranul(int granul) { m_granul = granul; }
  60     int GetGranul() const { return m_granul; }
  61
  62     void SetMinAllocSize(int mas) { m_mas=mas; }
  63
  64
  65     WDL_HeapBuf(const WDL_HeapBuf &cp)
  66     {
  67       m_buf=0;
  68       CopyFrom(&cp,true);
  69     }
  70     WDL_HeapBuf &operator=(const WDL_HeapBuf &cp)
  71     {
  72       CopyFrom(&cp,false);
  73       return *this;
  74     }
  75
  76
  77
  78   #ifndef WDL_HEAPBUF_TRACE
  79     explicit WDL_HeapBuf(int granul=4096) : m_alloc(0), m_size(0), m_mas(0)
  80     {
  81       SetGranul(granul);
  82       m_buf=0;
  83     }
  84     ~WDL_HeapBuf()
  85     {
  86       free(m_buf);
  87     }
  88   #else
  89     explicit WDL_HeapBuf(int granul=4096, const char *tracetype="WDL_HeapBuf"
  90       ) : m_alloc(0), m_size(0), m_mas(0)
  91     {
  92       SetGranul(granul);
  93       m_buf=0;
  94
  95       m_tracetype = tracetype;
  96       char tmp[512];
  97       wsprintf(tmp,"WDL_HeapBuf: created type: %s granul=%d\n",tracetype,granul);
  98       OutputDebugString(tmp);
  99     }
 100     ~WDL_HeapBuf()
 101     {
 102       char tmp[512];
 103       wsprintf(tmp,"WDL_HeapBuf: destroying type: %s (alloc=%d, size=%d)\n",m_tracetype,m_alloc,m_size);
 104       OutputDebugString(tmp);
 105       free(m_buf);
 106     }
 107   #endif
 108
 109 #endif // !WDL_HEAPBUF_IMPL_ONLY
 110
 111     // implementation bits
 112 #ifndef WDL_HEAPBUF_INTF_ONLY
 113     #ifdef WDL_HEAPBUF_IMPL_ONLY
 114       void *WDL_HeapBuf::Resize(int newsize, bool resizedown)
 115     #else
 116       void *Resize(int newsize, bool resizedown=true)
 117     #endif
 118       {
 119         if (newsize<0) newsize=0;
 120         #ifdef DEBUG_TIGHT_ALLOC // horribly slow, do not use for release builds
 121           if (newsize == m_size) return m_buf;
 122
 123           int a = newsize;
 124           if (a > m_size) a=m_size;
 125           void *newbuf = newsize ? malloc(newsize) : 0;
 126           if (!newbuf && newsize)
 127           {
 128             #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 129                 WDL_HEAPBUF_ONMALLOCFAIL(newsize)
 130             #endif
 131             return m_buf;
 132           }
 133           if (newbuf&&m_buf) memcpy(newbuf,m_buf,a);
 134           m_size=m_alloc=newsize;
 135           free(m_buf);
 136           return m_buf=newbuf;
 137         #endif
 138
 139         //#define WDL_HEAPBUF_DYNAMIC
 140         #ifdef WDL_HEAPBUF_DYNAMIC
 141           // ignoring m_granul and m_mas
 142
 143           if (newsize!=m_size)
 144           {
 145             if ((newsize > m_size && newsize <= m_alloc) || (newsize < m_size && !resizedown))
 146             {
 147               m_size = newsize;
 148               return m_buf;
 149             }
 150
 151             // next highest power of 2
 152             int n = newsize;
 153             if (n)
 154             {
 155               if (n < 64)
 156               {
 157                 n = 64;
 158               }
 159               else
 160               {
 161                 --n;
 162                 n = (n>>1)|n;
 163                 n = (n>>2)|n;
 164                 n = (n>>4)|n;
 165                 n = (n>>8)|n;
 166                 n = (n>>16)|n;
 167                 ++n;
 168               }
 169             }
 170
 171             if (n == m_alloc)
 172             {
 173               m_size = newsize;
 174               return m_buf;
 175             }
 176
 177             void* newbuf = realloc(m_buf, n);  // realloc==free when size==0
 178             #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 179               if (!newbuf && n) { WDL_HEAPBUF_ONMALLOCFAIL(n) } ;
 180             #endif
 181             if (newbuf || !newsize)
 182             {
 183               m_alloc = n;
 184               m_buf = newbuf;
 185               m_size = newsize;
 186             }
 187           }
 188
 189           return (m_size ? m_buf : 0);
 190         #else // WDL_HEAPBUF_DYNAMIC
 191           if (newsize!=m_size)
 192           {
 193             int resizedown_under = 0;
 194             if (resizedown && newsize < m_size)
 195             {
 196               // shrinking buffer: only shrink if allocation decreases to min(alloc/2, alloc-granul*4) or 0
 197               resizedown_under = m_alloc - (m_granul<<2);
 198               if (resizedown_under > m_alloc/2) resizedown_under = m_alloc/2;
 199               if (resizedown_under < 1) resizedown_under=1;
 200             }
 201
 202             if (newsize > m_alloc || newsize < resizedown_under)
 203             {
 204               int granul=newsize/2;
 205               int newalloc;
 206               if (granul < m_granul) granul=m_granul;
 207
 208               if (newsize<1) newalloc=0;
 209               else if (m_granul<4096) newalloc=newsize+granul;
 210               else
 211               {
 212                 granul &= ~4095;
 213                 if (granul< 4096) granul=4096;
 214                 else if (granul>4*1024*1024) granul=4*1024*1024;
 215                 newalloc = ((newsize + granul + 96)&~4095)-96;
 216               }
 217
 218               if (newalloc < m_mas) newalloc=m_mas;
 219
 220               if (newalloc != m_alloc)
 221               {
 222
 223                 #ifdef WDL_HEAPBUF_TRACE
 224                   char tmp[512];
 225                   wsprintf(tmp,"WDL_HeapBuf: type %s realloc(%d) from %d\n",m_tracetype,newalloc,m_alloc);
 226                   OutputDebugString(tmp);
 227                 #endif
 228                 if (newalloc <= 0)
 229                 {
 230                   free(m_buf);
 231                   m_buf=0;
 232                   m_alloc=0;
 233                   m_size=0;
 234                   return 0;
 235                 }
 236                 void *nbuf=realloc(m_buf,newalloc);
 237                 if (!nbuf)
 238                 {
 239                   if (!(nbuf=malloc(newalloc)))
 240                   {
 241                     #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 242                       WDL_HEAPBUF_ONMALLOCFAIL(newalloc);
 243                     #endif
 244                     return m_size?m_buf:0; // failed, do not resize
 245                   }
 246
 247                   if (m_buf)
 248                   {
 249                     int sz=newsize<m_size?newsize:m_size;
 250                     if (sz>0) memcpy(nbuf,m_buf,sz);
 251                     free(m_buf);
 252                   }
 253                 }
 254
 255                 m_buf=nbuf;
 256                 m_alloc=newalloc;
 257               } // alloc size change
 258             } // need size up or down
 259             m_size=newsize;
 260           } // size change
 261           return m_size?m_buf:0;
 262         #endif // WDL_HEAPBUF_DYNAMIC
 263       }
 264
 265     #ifdef WDL_HEAPBUF_IMPL_ONLY
 266       void WDL_HeapBuf::CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig)
 267     #else
 268       void CopyFrom(const WDL_HeapBuf *hb, bool exactCopyOfConfig=false)
 269     #endif
 270       {
 271         if (exactCopyOfConfig) // copy all settings
 272         {
 273           free(m_buf);
 274
 275           #ifdef WDL_HEAPBUF_TRACE
 276             m_tracetype = hb->m_tracetype;
 277           #endif
 278           m_granul = hb->m_granul;
 279           m_mas = hb->m_mas;
 280
 281           m_size=m_alloc=0;
 282           m_buf=hb->m_buf && hb->m_alloc>0 ? malloc(m_alloc = hb->m_alloc) : NULL;
 283           #ifdef WDL_HEAPBUF_ONMALLOCFAIL
 284             if (!m_buf && m_alloc) { WDL_HEAPBUF_ONMALLOCFAIL(m_alloc) } ;
 285           #endif
 286           if (m_buf) memcpy(m_buf,hb->m_buf,m_size = hb->m_size);
 287           else m_alloc=0;
 288         }
 289         else // copy just the data + size
 290         {
 291           const int newsz=hb->GetSize();
 292           Resize(newsz,true);
 293           if (GetSize()!=newsz) Resize(0);
 294           else memcpy(Get(),hb->Get(),newsz);
 295         }
 296       }
 297
 298 #endif // ! WDL_HEAPBUF_INTF_ONLY
 299
 300 #ifndef WDL_HEAPBUF_IMPL_ONLY
 301
 302   private:
 303     void *m_buf;
 304   #if !defined(_WIN64) && !defined(__LP64__)
 305     int ___pad; // keep this 8 byte aligned on osx32
 306   #endif
 307     int m_granul;
 308     int m_alloc;
 309     int m_size;
 310     int m_mas;
 311
 312   #ifdef WDL_HEAPBUF_TRACE
 313     const char *m_tracetype;
 314   #endif
 315
 316 };
 317
 318 template<class PTRTYPE> class WDL_TypedBuf
 319 {
 320   public:
 321     PTRTYPE *Get() const { return (PTRTYPE *) m_hb.Get(); }
 322     int GetSize() const { return m_hb.GetSize()/(unsigned int)sizeof(PTRTYPE); }
 323
 324     PTRTYPE *Resize(int newsize, bool resizedown=true) { return (PTRTYPE *)m_hb.Resize(newsize*(unsigned int)sizeof(PTRTYPE),resizedown); }
 325
 326     PTRTYPE *GetAligned(int align) const  { return (PTRTYPE *) m_hb.GetAligned(align); }
 327
 328     PTRTYPE *Add(PTRTYPE val)
 329     {
 330       return Insert(val, GetSize());
 331     }
 332
 333     PTRTYPE* Insert(PTRTYPE val, int idx)
 334     {
 335       int sz=GetSize();
 336       if (idx >= 0 && idx <= sz)
 337       {
 338         PTRTYPE* p=Resize(sz+1);
 339         if (p && GetSize() == sz+1)
 340         {
 341           memmove(p+idx+1, p+idx, (sz-idx)*(unsigned int)sizeof(PTRTYPE));
 342           p[idx]=val;
 343           return p+idx;
 344         }
 345       }
 346       return 0;
 347     }
 348
 349     PTRTYPE* Delete(int idx)
 350     {
 351       PTRTYPE* p=Get();
 352       int sz=GetSize();
 353       if (idx >= 0 && idx < sz)
 354       {
 355         memmove(p+idx, p+idx+1, (sz-idx-1)*(unsigned int)sizeof(PTRTYPE));
 356         return Resize(sz-1,false);
 357       }
 358       return p;
 359     }
 360
 361     void SetGranul(int gran) { m_hb.SetGranul(gran); }
 362
 363     int Find(PTRTYPE val) const
 364     {
 365       PTRTYPE* p=Get();
 366       int i;
 367       for (i=0; i < GetSize(); ++i) if (p[i] == val) return i;
 368       return -1;
 369     }
 370
 371 #ifndef WDL_HEAPBUF_TRACE
 372     explicit WDL_TypedBuf(int granul=4096) : m_hb(granul) { }
 373 #else
 374     explicit WDL_TypedBuf(int granul=4096, const char *tracetype="WDL_TypedBuf") : m_hb(granul WDL_HEAPBUF_TRACEPARM(tracetype)) { }
 375 #endif
 376     ~WDL_TypedBuf()
 377     {
 378     }
 379
 380   private:
 381     WDL_HeapBuf m_hb;
 382 };
 383
 384 #endif // ! WDL_HEAPBUF_IMPL_ONLY
 385
 386 #endif // _WDL_HEAPBUF_H_