WDL/ptrlist.h

   1 /*
   2     WDL - ptrlist.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 a simple templated class for a list of pointers. By default this list
  26   doesn't free any of the pointers, but you can call Empty(true) or Delete(x,true) to delete the pointer,
  27   or you can use Empty(true,free) etc to call free (or any other function).
  28
  29   Note: on certain compilers, instantiating with WDL_PtrList<void> bla; will give a warning, since
  30   the template will create code for "delete (void *)x;" which isn't technically valid. Oh well.
  31
  32 */
  33
  34 #ifndef _WDL_PTRLIST_H_
  35 #define _WDL_PTRLIST_H_
  36
  37 #include "heapbuf.h"
  38
  39 template<class PTRTYPE> class WDL_PtrList
  40 {
  41   public:
  42     explicit WDL_PtrList(int defgran=4096, int prealloc=0) : m_buf(defgran)
  43     {
  44       if (prealloc>0) m_buf.Prealloc(prealloc);
  45     }
  46
  47     ~WDL_PtrList()
  48     {
  49     }
  50
  51     void Prealloc(int sz) { m_buf.Prealloc(sz); }
  52     void ResizeToCurrent() { m_buf.ResizeToCurrent(); }
  53
  54     PTRTYPE **GetList() const { return m_buf.Get(); }
  55     PTRTYPE *Get(INT_PTR index) const
  56     {
  57       PTRTYPE **list = m_buf.Get();
  58       if (list && (UINT_PTR)index < (UINT_PTR)m_buf.GetSize()) return list[index];
  59       return NULL;
  60     }
  61
  62     int GetSize(void) const { return m_buf.GetSize(); }
  63
  64     PTRTYPE *Pop()
  65     {
  66       const int l = GetSize()-1;
  67       if (l<0) return NULL;
  68       PTRTYPE *ret = m_buf.Get()[l];
  69       m_buf.Resize(l,false);
  70       return ret;
  71     }
  72     PTRTYPE *GetLast() const { return Get(GetSize()-1); }
  73
  74     int Find(const PTRTYPE *p) const
  75     {
  76       if (p)
  77       {
  78         PTRTYPE **list=m_buf.Get();
  79         int x;
  80         const int n = GetSize();
  81         for (x = 0; x < n; x ++) if (list[x] == p) return x;
  82       }
  83       return -1;
  84     }
  85     int FindR(const PTRTYPE *p) const
  86     {
  87       if (p)
  88       {
  89         PTRTYPE **list=m_buf.Get();
  90         int x = GetSize();
  91         while (--x >= 0) if (list[x] == p) return x;
  92       }
  93       return -1;
  94     }
  95
  96     PTRTYPE *Add(PTRTYPE *item) { return m_buf.Add(item) ? item : NULL; }
  97     void Add(PTRTYPE **items, int numitems) { m_buf.Add(items, numitems); }
  98
  99     PTRTYPE *Set(int index, PTRTYPE *item)
 100     {
 101       PTRTYPE **list=m_buf.Get();
 102       if (list && index >= 0 && index < GetSize()) return list[index]=item;
 103       return NULL;
 104     }
 105
 106     PTRTYPE *Insert(int index, PTRTYPE *item)
 107     {
 108       const int s=GetSize();
 109       m_buf.Insert(item, wdl_clamp(index,0,s));
 110       return item;
 111
 112     }
 113     template<class SB, class SB2> int FindSorted(SB p, int (*compar)(SB2 a, const PTRTYPE *b)) const
 114     {
 115       bool m;
 116       int i = LowerBound(p,&m,compar);
 117       return m ? i : -1;
 118     }
 119     PTRTYPE *InsertSorted(PTRTYPE *item, int (*compar)(const PTRTYPE *a, const PTRTYPE *b))
 120     {
 121       bool m;
 122       return Insert(LowerBound(item,&m,compar),item);
 123     }
 124     template<class SB, class SB2> PTRTYPE *InsertSorted(PTRTYPE *item, SB ref, int (*compar)(SB2 a, const PTRTYPE *b))
 125     {
 126       bool m;
 127       return Insert(LowerBound(ref,&m,compar),item);
 128     }
 129
 130     void Delete(int index) { m_buf.Delete(index);  }
 131     void Delete(int index, bool wantDelete, void (*delfunc)(void *)=NULL)
 132     {
 133       PTRTYPE **list=GetList();
 134       int size=GetSize();
 135       if (list && index >= 0 && index < size)
 136       {
 137         if (wantDelete)
 138         {
 139           if (delfunc) delfunc(Get(index));
 140           else delete Get(index);
 141         }
 142         // if delfunc modified the list this could be unpredictable
 143         WDL_ASSERT(size == GetSize());
 144         if (index < --size) memmove(list+index,list+index+1,(unsigned int)sizeof(PTRTYPE *)*(size-index));
 145         m_buf.Resize(size,false);
 146       }
 147     }
 148     template<class PT> void Delete(int index, PT delfunc)
 149     {
 150       PTRTYPE **list=GetList();
 151       int size=GetSize();
 152       if (list && index >= 0 && index < size)
 153       {
 154         if (delfunc) delfunc(Get(index));
 155         // if delfunc modified the list this could be unpredictable
 156         WDL_ASSERT(size == GetSize());
 157
 158         if (index < --size) memmove(list+index,list+index+1,(unsigned int)sizeof(PTRTYPE *)*(size-index));
 159         m_buf.Resize(size,false);
 160       }
 161     }
 162     void DeletePtr(const PTRTYPE *p) { Delete(Find(p)); }
 163     void DeletePtr(const PTRTYPE *p, bool wantDelete, void (*delfunc)(void *)=NULL) { Delete(Find(p),wantDelete,delfunc); }
 164     template<class PT> void DeletePtr(const PTRTYPE *p, PT delfunc) { Delete(Find(p),delfunc); }
 165
 166     void DeleteRange(int index, int count) { m_buf.DeleteRange(index,count); }
 167
 168     void Empty()
 169     {
 170       m_buf.Resize(0,false);
 171     }
 172     void Empty(bool wantDelete, void (*delfunc)(void *)=NULL)
 173     {
 174       if (wantDelete)
 175       {
 176         int x;
 177         for (x = GetSize()-1; x >= 0; x --)
 178         {
 179           PTRTYPE* p = Get(x);
 180           if (p)
 181           {
 182             if (delfunc) delfunc(p);
 183             else delete p;
 184           }
 185           // if delfunc modified the list this could be unpredictable
 186           WDL_ASSERT(x == GetSize()-1);
 187           m_buf.Resize(x,false);
 188         }
 189       }
 190       m_buf.Resize(0,false);
 191     }
 192     template<class PT> void Empty(PT delfunc)
 193     {
 194       WDL_ASSERT(delfunc != NULL);
 195       for (int x = GetSize()-1; x >= 0; x --)
 196       {
 197         PTRTYPE* p = Get(x);
 198         if (delfunc && p) delfunc(p);
 199         // if delfunc modified the list this could be unpredictable
 200         WDL_ASSERT(x == GetSize()-1);
 201         m_buf.Resize(x,false);
 202       }
 203     }
 204
 205     template<class SB, class SB2> int LowerBound(SB key, bool* ismatch, int (*compar)(SB2 a, const PTRTYPE *b)) const
 206     {
 207       int a = 0;
 208       int c = GetSize();
 209       PTRTYPE **list=GetList();
 210       while (a != c)
 211       {
 212         int b = (a+c)/2;
 213         int cmp = compar(key, list[b]);
 214         if (cmp > 0) a = b+1;
 215         else if (cmp < 0) c = b;
 216         else
 217         {
 218           *ismatch = true;
 219           return b;
 220         }
 221       }
 222       *ismatch = false;
 223       return a;
 224     }
 225
 226     int DeleteBatch(bool (*proc)(PTRTYPE *p, void *ctx), void *ctx=NULL) // proc returns true to remove item. returns number removed
 227     {
 228       const int sz = GetSize();
 229       int cnt=0;
 230       PTRTYPE **rd = GetList(), **wr = rd;
 231       for (int x = 0; x < sz; x ++)
 232       {
 233         if (!proc(*rd,ctx))
 234         {
 235           if (rd != wr) *wr=*rd;
 236           wr++;
 237           cnt++;
 238         }
 239         rd++;
 240       }
 241       if (cnt < sz) m_buf.Resize(cnt,false);
 242       return sz - cnt;
 243     }
 244
 245     const PTRTYPE **begin() const { return GetList(); }
 246     const PTRTYPE **end() const { return GetList() + GetSize(); }
 247     PTRTYPE **begin() { return GetList(); }
 248     PTRTYPE **end() { return GetList() + GetSize(); }
 249
 250   private:
 251     WDL_TypedBuf<PTRTYPE *> m_buf;
 252
 253 };
 254
 255
 256 template<class PTRTYPE> class WDL_PtrList_DeleteOnDestroy : public WDL_PtrList<PTRTYPE>
 257 {
 258 public:
 259   explicit WDL_PtrList_DeleteOnDestroy(void (*delfunc)(void *)=NULL, int defgran=4096) : WDL_PtrList<PTRTYPE>(defgran), m_delfunc(delfunc) {  }
 260   ~WDL_PtrList_DeleteOnDestroy()
 261   {
 262     WDL_PtrList<PTRTYPE>::Empty(true,m_delfunc);
 263   }
 264 private:
 265   void (*m_delfunc)(void *);
 266 };
 267
 268 #endif
 269