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) : m_hb(defgran WDL_HEAPBUF_TRACEPARM("WDL_PtrList"))
  43     {
  44     }
  45
  46     ~WDL_PtrList()
  47     {
  48     }
  49
  50     PTRTYPE **GetList() const { return (PTRTYPE**)m_hb.Get(); }
  51     PTRTYPE *Get(INT_PTR index) const
  52     {
  53       PTRTYPE **list = (PTRTYPE**)m_hb.Get();
  54       if (list && index >= 0 && index < (INT_PTR)(m_hb.GetSize()/sizeof(PTRTYPE *))) return list[index];
  55       return NULL;
  56     }
  57
  58     int GetSize(void) const { return m_hb.GetSize()/(unsigned int)sizeof(PTRTYPE *); }
  59
  60     int Find(const PTRTYPE *p) const
  61     {
  62       if (p)
  63       {
  64         PTRTYPE **list=(PTRTYPE **)m_hb.Get();
  65         int x;
  66         const int n = GetSize();
  67         for (x = 0; x < n; x ++) if (list[x] == p) return x;
  68       }
  69       return -1;
  70     }
  71     int FindR(const PTRTYPE *p) const
  72     {
  73       if (p)
  74       {
  75         PTRTYPE **list=(PTRTYPE **)m_hb.Get();
  76         int x = GetSize();
  77         while (--x >= 0) if (list[x] == p) return x;
  78       }
  79       return -1;
  80     }
  81
  82     PTRTYPE *Add(PTRTYPE *item)
  83     {
  84       const int s=GetSize();
  85       PTRTYPE **list=(PTRTYPE **)m_hb.ResizeOK((s+1)*(unsigned int)sizeof(PTRTYPE*),false);
  86       if (list)
  87       {
  88         list[s]=item;
  89         return item;
  90       }
  91       return NULL;
  92     }
  93
  94     PTRTYPE *Set(int index, PTRTYPE *item)
  95     {
  96       PTRTYPE **list=(PTRTYPE **)m_hb.Get();
  97       if (list && index >= 0 && index < GetSize()) return list[index]=item;
  98       return NULL;
  99     }
 100
 101     PTRTYPE *Insert(int index, PTRTYPE *item)
 102     {
 103       int s=GetSize();
 104       PTRTYPE **list = (PTRTYPE **)m_hb.ResizeOK((s+1)*(unsigned int)sizeof(PTRTYPE*),false);
 105
 106       if (!list) return item;
 107
 108       if (index<0) index=0;
 109
 110       int x;
 111       for (x = s; x > index; x --) list[x]=list[x-1];
 112       return (list[x] = item);
 113     }
 114     int FindSorted(const PTRTYPE *p, int (*compar)(const PTRTYPE **a, const PTRTYPE **b)) const
 115     {
 116       bool m;
 117       int i = LowerBound(p,&m,compar);
 118       return m ? i : -1;
 119     }
 120     PTRTYPE *InsertSorted(PTRTYPE *item, int (*compar)(const PTRTYPE **a, const PTRTYPE **b))
 121     {
 122       bool m;
 123       return Insert(LowerBound(item,&m,compar),item);
 124     }
 125
 126     void Delete(int index)
 127     {
 128       PTRTYPE **list=GetList();
 129       int size=GetSize();
 130       if (list && index >= 0 && index < size)
 131       {
 132         if (index < --size) memmove(list+index,list+index+1,(unsigned int)sizeof(PTRTYPE *)*(size-index));
 133         m_hb.Resize(size * (unsigned int)sizeof(PTRTYPE*),false);
 134       }
 135     }
 136     void Delete(int index, bool wantDelete, void (*delfunc)(void *)=NULL)
 137     {
 138       PTRTYPE **list=GetList();
 139       int size=GetSize();
 140       if (list && index >= 0 && index < size)
 141       {
 142         if (wantDelete)
 143         {
 144           if (delfunc) delfunc(Get(index));
 145           else delete Get(index);
 146         }
 147         if (index < --size) memmove(list+index,list+index+1,(unsigned int)sizeof(PTRTYPE *)*(size-index));
 148         m_hb.Resize(size * (unsigned int)sizeof(PTRTYPE*),false);
 149       }
 150     }
 151     void Delete(int index, void (*delfunc)(PTRTYPE *))
 152     {
 153       PTRTYPE **list=GetList();
 154       int size=GetSize();
 155       if (list && index >= 0 && index < size)
 156       {
 157         if (delfunc) delfunc(Get(index));
 158         if (index < --size) memmove(list+index,list+index+1,(unsigned int)sizeof(PTRTYPE *)*(size-index));
 159         m_hb.Resize(size * (unsigned int)sizeof(PTRTYPE*),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     void DeletePtr(const PTRTYPE *p, void (*delfunc)(PTRTYPE *)) { Delete(Find(p),delfunc); }
 165
 166     void Empty()
 167     {
 168       m_hb.Resize(0,false);
 169     }
 170     void Empty(bool wantDelete, void (*delfunc)(void *)=NULL)
 171     {
 172       if (wantDelete)
 173       {
 174         int x;
 175         for (x = GetSize()-1; x >= 0; x --)
 176         {
 177           PTRTYPE* p = Get(x);
 178           if (p)
 179           {
 180             if (delfunc) delfunc(p);
 181             else delete p;
 182           }
 183           m_hb.Resize(x*(unsigned int)sizeof(PTRTYPE *),false);
 184         }
 185       }
 186       m_hb.Resize(0,false);
 187     }
 188     void Empty(void (*delfunc)(PTRTYPE *))
 189     {
 190       int x;
 191       for (x = GetSize()-1; x >= 0; x --)
 192       {
 193         PTRTYPE* p = Get(x);
 194         if (delfunc && p) delfunc(p);
 195         m_hb.Resize(x*(unsigned int)sizeof(PTRTYPE *),false);
 196       }
 197     }
 198     void EmptySafe(bool wantDelete=false,void (*delfunc)(void *)=NULL)
 199     {
 200       if (!wantDelete) Empty();
 201       else
 202       {
 203         WDL_PtrList<PTRTYPE> tmp;
 204         int x;
 205         for(x=0;x<GetSize();x++)tmp.Add(Get(x));
 206         Empty();
 207         tmp.Empty(true,delfunc);
 208       }
 209     }
 210
 211     int LowerBound(const PTRTYPE *key, bool* ismatch, int (*compar)(const PTRTYPE **a, const PTRTYPE **b)) const
 212     {
 213       int a = 0;
 214       int c = GetSize();
 215       PTRTYPE **list=GetList();
 216       while (a != c)
 217       {
 218         int b = (a+c)/2;
 219         int cmp = compar((const PTRTYPE **)&key, (const PTRTYPE **)(list+b));
 220         if (cmp > 0) a = b+1;
 221         else if (cmp < 0) c = b;
 222         else
 223         {
 224           *ismatch = true;
 225           return b;
 226         }
 227       }
 228       *ismatch = false;
 229       return a;
 230     }
 231
 232     void Compact() { m_hb.Resize(m_hb.GetSize(),true); }
 233
 234   private:
 235     WDL_HeapBuf m_hb;
 236
 237 };
 238
 239
 240 template<class PTRTYPE> class WDL_PtrList_DeleteOnDestroy : public WDL_PtrList<PTRTYPE>
 241 {
 242 public:
 243   explicit WDL_PtrList_DeleteOnDestroy(void (*delfunc)(void *)=NULL, int defgran=4096) : WDL_PtrList<PTRTYPE>(defgran), m_delfunc(delfunc) {  }
 244   ~WDL_PtrList_DeleteOnDestroy()
 245   {
 246     WDL_PtrList<PTRTYPE>::EmptySafe(true,m_delfunc);
 247   }
 248 private:
 249   void (*m_delfunc)(void *);
 250 };
 251
 252 #endif
 253