WDL/assocarray.h

   1 #ifndef _WDL_ASSOCARRAY_H_
   2 #define _WDL_ASSOCARRAY_H_
   3
   4 #include "heapbuf.h"
   5
   6
   7 // on all of these, if valdispose is set, the array will dispose of values as needed.
   8 // if keydup/keydispose are set, copies of (any) key data will be made/destroyed as necessary
   9
  10
  11 // WDL_AssocArrayImpl can be used on its own, and can contain structs for keys or values
  12 template <class KEY, class VAL> class WDL_AssocArrayImpl
  13 {
  14   WDL_AssocArrayImpl(const WDL_AssocArrayImpl &cp) { CopyContents(cp); }
  15
  16   WDL_AssocArrayImpl &operator=(const WDL_AssocArrayImpl &cp) { CopyContents(cp); return *this; }
  17
  18 public:
  19
  20   explicit WDL_AssocArrayImpl(int (*keycmp)(KEY *k1, KEY *k2), KEY (*keydup)(KEY)=0, void (*keydispose)(KEY)=0, void (*valdispose)(VAL)=0)
  21   {
  22     m_keycmp = keycmp;
  23     m_keydup = keydup;
  24     m_keydispose = keydispose;
  25     m_valdispose = valdispose;
  26   }
  27
  28   ~WDL_AssocArrayImpl()
  29   {
  30     DeleteAll();
  31   }
  32
  33   VAL* GetPtr(KEY key, KEY *keyPtrOut=NULL) const
  34   {
  35     bool ismatch = false;
  36     int i = LowerBound(key, &ismatch);
  37     if (ismatch)
  38     {
  39       KeyVal* kv = m_data.Get()+i;
  40       if (keyPtrOut) *keyPtrOut = kv->key;
  41       return &(kv->val);
  42     }
  43     return 0;
  44   }
  45
  46   bool Exists(KEY key) const
  47   {
  48     bool ismatch = false;
  49     LowerBound(key, &ismatch);
  50     return ismatch;
  51   }
  52
  53   int Insert(KEY key, VAL val)
  54   {
  55     bool ismatch = false;
  56     int i = LowerBound(key, &ismatch);
  57     if (ismatch)
  58     {
  59       KeyVal* kv = m_data.Get()+i;
  60       if (m_valdispose) m_valdispose(kv->val);
  61       kv->val = val;
  62     }
  63     else
  64     {
  65       KeyVal* kv = m_data.Resize(m_data.GetSize()+1)+i;
  66       memmove(kv+1, kv, (m_data.GetSize()-i-1)*(unsigned int)sizeof(KeyVal));
  67       if (m_keydup) key = m_keydup(key);
  68       kv->key = key;
  69       kv->val = val;
  70     }
  71     return i;
  72   }
  73
  74   void Delete(KEY key)
  75   {
  76     bool ismatch = false;
  77     int i = LowerBound(key, &ismatch);
  78     if (ismatch)
  79     {
  80       KeyVal* kv = m_data.Get()+i;
  81       if (m_keydispose) m_keydispose(kv->key);
  82       if (m_valdispose) m_valdispose(kv->val);
  83       m_data.Delete(i);
  84     }
  85   }
  86
  87   void DeleteByIndex(int idx)
  88   {
  89     if (idx >= 0 && idx < m_data.GetSize())
  90     {
  91       KeyVal* kv = m_data.Get()+idx;
  92       if (m_keydispose) m_keydispose(kv->key);
  93       if (m_valdispose) m_valdispose(kv->val);
  94       m_data.Delete(idx);
  95     }
  96   }
  97
  98   void DeleteAll(bool resizedown=false)
  99   {
 100     if (m_keydispose || m_valdispose)
 101     {
 102       int i;
 103       for (i = 0; i < m_data.GetSize(); ++i)
 104       {
 105         KeyVal* kv = m_data.Get()+i;
 106         if (m_keydispose) m_keydispose(kv->key);
 107         if (m_valdispose) m_valdispose(kv->val);
 108       }
 109     }
 110     m_data.Resize(0, resizedown);
 111   }
 112
 113   int GetSize() const
 114   {
 115     return m_data.GetSize();
 116   }
 117
 118   VAL* EnumeratePtr(int i, KEY* key=0) const
 119   {
 120     if (i >= 0 && i < m_data.GetSize())
 121     {
 122       KeyVal* kv = m_data.Get()+i;
 123       if (key) *key = kv->key;
 124       return &(kv->val);
 125     }
 126     return 0;
 127   }
 128
 129   KEY* ReverseLookupPtr(VAL val) const
 130   {
 131     int i;
 132     for (i = 0; i < m_data.GetSize(); ++i)
 133     {
 134       KeyVal* kv = m_data.Get()+i;
 135       if (kv->val == val) return &kv->key;
 136     }
 137     return 0;
 138   }
 139
 140   void ChangeKey(KEY oldkey, KEY newkey)
 141   {
 142     bool ismatch=false;
 143     int i = LowerBound(oldkey, &ismatch);
 144     if (ismatch)
 145     {
 146       KeyVal* kv = m_data.Get()+i;
 147       if (m_keydispose) m_keydispose(kv->key);
 148       if (m_keydup) newkey = m_keydup(newkey);
 149       kv->key = newkey;
 150       Resort();
 151     }
 152   }
 153
 154   void ChangeKeyByIndex(int idx, KEY newkey, bool needsort)
 155   {
 156     if (idx >= 0 && idx < m_data.GetSize())
 157     {
 158       KeyVal* kv = m_data.Get()+idx;
 159       if (m_keydispose) m_keydispose(kv->key);
 160       if (m_keydup) newkey = m_keydup(newkey);
 161       kv->key = newkey;
 162       if (needsort) Resort();
 163     }
 164   }
 165
 166   // fast add-block mode
 167   void AddUnsorted(KEY key, VAL val)
 168   {
 169     int i=m_data.GetSize();
 170     KeyVal* kv = m_data.Resize(i+1)+i;
 171     if (m_keydup) key = m_keydup(key);
 172     kv->key = key;
 173     kv->val = val;
 174   }
 175
 176   void Resort()
 177   {
 178     if (m_data.GetSize() > 1 && m_keycmp)
 179     {
 180       qsort(m_data.Get(),m_data.GetSize(),sizeof(KeyVal),(int(*)(const void *,const void *))m_keycmp);
 181
 182       // AddUnsorted can add duplicate keys
 183       // unfortunately qsort is not guaranteed to preserve order,
 184       // ideally this filter would always preserve the last-added key
 185       int i;
 186       for (i=0; i < m_data.GetSize()-1; ++i)
 187       {
 188         KeyVal* kv=m_data.Get()+i;
 189         KeyVal* nv=kv+1;
 190         if (!m_keycmp(&kv->key, &nv->key))
 191         {
 192           DeleteByIndex(i--);
 193         }
 194       }
 195     }
 196   }
 197
 198   int LowerBound(KEY key, bool* ismatch) const
 199   {
 200     int a = 0;
 201     int c = m_data.GetSize();
 202     while (a != c)
 203     {
 204       int b = (a+c)/2;
 205       KeyVal* kv=m_data.Get()+b;
 206       int cmp = m_keycmp(&key, &kv->key);
 207       if (cmp > 0) a = b+1;
 208       else if (cmp < 0) c = b;
 209       else
 210       {
 211         *ismatch = true;
 212         return b;
 213       }
 214     }
 215     *ismatch = false;
 216     return a;
 217   }
 218
 219   int GetIdx(KEY key) const
 220   {
 221     bool ismatch=false;
 222     int i = LowerBound(key, &ismatch);
 223     if (ismatch) return i;
 224     return -1;
 225   }
 226
 227   void SetGranul(int gran)
 228   {
 229     m_data.SetGranul(gran);
 230   }
 231
 232   void CopyContents(const WDL_AssocArrayImpl &cp)
 233   {
 234     m_data=cp.m_data;
 235     m_keycmp = cp.m_keycmp;
 236     m_keydup = cp.m_keydup;
 237     m_keydispose = m_keydup ? cp.m_keydispose : NULL;
 238     m_valdispose = NULL; // avoid disposing of values twice, since we don't have a valdup, we can't have a fully valid copy
 239     if (m_keydup)
 240     {
 241       int x;
 242       const int n=m_data.GetSize();
 243       for (x=0;x<n;x++)
 244       {
 245         KeyVal *kv=m_data.Get()+x;
 246         if (kv->key) kv->key = m_keydup(kv->key);
 247       }
 248     }
 249   }
 250
 251   void CopyContentsAsReference(const WDL_AssocArrayImpl &cp)
 252   {
 253     DeleteAll(true);
 254     m_keydup = NULL;  // this no longer can own any data
 255     m_keydispose = NULL;
 256     m_valdispose = NULL;
 257
 258     m_data=cp.m_data;
 259   }
 260
 261 protected:
 262
 263   struct KeyVal
 264   {
 265     KEY key;
 266     VAL val;
 267   };
 268   WDL_TypedBuf<KeyVal> m_data;
 269
 270   int (*m_keycmp)(KEY *k1, KEY *k2);
 271   KEY (*m_keydup)(KEY);
 272   void (*m_keydispose)(KEY);
 273   void (*m_valdispose)(VAL);
 274
 275 };
 276
 277
 278 // WDL_AssocArray adds useful functions but cannot contain structs for keys or values
 279 template <class KEY, class VAL> class WDL_AssocArray : public WDL_AssocArrayImpl<KEY, VAL>
 280 {
 281 public:
 282
 283   explicit WDL_AssocArray(int (*keycmp)(KEY *k1, KEY *k2), KEY (*keydup)(KEY)=0, void (*keydispose)(KEY)=0, void (*valdispose)(VAL)=0)
 284   : WDL_AssocArrayImpl<KEY, VAL>(keycmp, keydup, keydispose, valdispose)
 285   {
 286   }
 287
 288   VAL Get(KEY key, VAL notfound=0) const
 289   {
 290     VAL* p = this->GetPtr(key);
 291     if (p) return *p;
 292     return notfound;
 293   }
 294
 295   VAL Enumerate(int i, KEY* key=0, VAL notfound=0) const
 296   {
 297     VAL* p = this->EnumeratePtr(i, key);
 298     if (p) return *p;
 299     return notfound;
 300   }
 301
 302   KEY ReverseLookup(VAL val, KEY notfound=0) const
 303   {
 304     KEY* p=this->ReverseLookupPtr(val);
 305     if (p) return *p;
 306     return notfound;
 307   }
 308 };
 309
 310
 311 template <class VAL> class WDL_IntKeyedArray : public WDL_AssocArray<int, VAL>
 312 {
 313 public:
 314
 315   explicit WDL_IntKeyedArray(void (*valdispose)(VAL)=0) : WDL_AssocArray<int, VAL>(cmpint, NULL, NULL, valdispose) {}
 316   ~WDL_IntKeyedArray() {}
 317
 318 private:
 319
 320   static int cmpint(int *i1, int *i2) { return *i1-*i2; }
 321 };
 322
 323
 324 template <class VAL> class WDL_StringKeyedArray : public WDL_AssocArray<const char *, VAL>
 325 {
 326 public:
 327
 328   explicit WDL_StringKeyedArray(bool caseSensitive=true, void (*valdispose)(VAL)=0) : WDL_AssocArray<const char*, VAL>(caseSensitive?cmpstr:cmpistr, dupstr, freestr, valdispose) {}
 329
 330   ~WDL_StringKeyedArray() { }
 331
 332   static const char *dupstr(const char *s) { return strdup(s);  } // these might not be necessary but depending on the libc maybe...
 333   static int cmpstr(const char **s1, const char **s2) { return strcmp(*s1, *s2); }
 334   static int cmpistr(const char **a, const char **b) { return stricmp(*a,*b); }
 335   static void freestr(const char* s) { free((void*)s); }
 336   static void freecharptr(char *p) { free(p); }
 337 };
 338
 339
 340 template <class VAL> class WDL_StringKeyedArray2 : public WDL_AssocArrayImpl<const char *, VAL>
 341 {
 342 public:
 343
 344   explicit WDL_StringKeyedArray2(bool caseSensitive=true, void (*valdispose)(VAL)=0) : WDL_AssocArrayImpl<const char*, VAL>(caseSensitive?cmpstr:cmpistr, dupstr, freestr, valdispose) {}
 345
 346   ~WDL_StringKeyedArray2() { }
 347
 348   static const char *dupstr(const char *s) { return strdup(s);  } // these might not be necessary but depending on the libc maybe...
 349   static int cmpstr(const char **s1, const char **s2) { return strcmp(*s1, *s2); }
 350   static int cmpistr(const char **a, const char **b) { return stricmp(*a,*b); }
 351   static void freestr(const char* s) { free((void*)s); }
 352   static void freecharptr(char *p) { free(p); }
 353 };
 354
 355 // sorts text as text, sorts anything that looks like a number as a number
 356 template <class VAL> class WDL_LogicalSortStringKeyedArray : public WDL_StringKeyedArray<VAL>
 357 {
 358 public:
 359
 360   explicit WDL_LogicalSortStringKeyedArray(bool caseSensitive=true, void (*valdispose)(VAL)=0) : WDL_StringKeyedArray<VAL>(caseSensitive, valdispose)
 361   {
 362     WDL_StringKeyedArray<VAL>::m_keycmp = caseSensitive?cmpstr:cmpistr; // override
 363   }
 364
 365   ~WDL_LogicalSortStringKeyedArray() { }
 366
 367 private:
 368
 369   static int cmpstr(const char **a, const char **b) { return _cmpstr(*a, *b, true); }
 370   static int cmpistr(const char **a, const char **b) { return _cmpstr(*a, *b, false); }
 371
 372   static int _cmpstr(const char *s1, const char *s2, bool case_sensitive)
 373   {
 374     // this also exists as WDL_strcmp_logical in wdlcstring.h
 375     char lastNonZeroChar=0;
 376     // last matching character, updated if not 0. this allows us to track whether
 377     // we are inside of a number with the same leading digits
 378
 379     for (;;)
 380     {
 381       char c1=*s1++, c2=*s2++;
 382       if (!c1) return c1-c2;
 383
 384       if (c1!=c2)
 385       {
 386         if (c1 >= '0' && c1 <= '9' && c2 >= '0' && c2 <= '9')
 387         {
 388           int lzdiff=0, cnt=0;
 389           if (lastNonZeroChar < '1' || lastNonZeroChar > '9')
 390           {
 391             while (c1 == '0') { c1=*s1++; lzdiff--; }
 392             while (c2 == '0') { c2=*s2++; lzdiff++; } // lzdiff = lz2-lz1, more leading 0s = earlier in list
 393           }
 394
 395           for (;;)
 396           {
 397             if (c1 >= '0' && c1 <= '9')
 398             {
 399               if (c2 < '0' || c2 > '9') return 1;
 400
 401               c1=s1[cnt];
 402               c2=s2[cnt++];
 403             }
 404             else
 405             {
 406               if (c2 >= '0' && c2 <= '9') return -1;
 407               break;
 408             }
 409           }
 410
 411           s1--;
 412           s2--;
 413
 414           while (cnt--)
 415           {
 416             const int d = *s1++ - *s2++;
 417             if (d) return d;
 418           }
 419
 420           if (lzdiff) return lzdiff;
 421         }
 422         else
 423         {
 424           if (!case_sensitive)
 425           {
 426             if (c1>='a' && c1<='z') c1+='A'-'a';
 427             if (c2>='a' && c2<='z') c2+='A'-'a';
 428           }
 429           if (c1 != c2) return c1-c2;
 430         }
 431       }
 432       else if (c1 != '0') lastNonZeroChar=c1;
 433     }
 434   }
 435 };
 436
 437
 438 template <class VAL> class WDL_PtrKeyedArray : public WDL_AssocArray<INT_PTR, VAL>
 439 {
 440 public:
 441
 442   explicit WDL_PtrKeyedArray(void (*valdispose)(VAL)=0) : WDL_AssocArray<INT_PTR, VAL>(cmpptr, 0, 0, valdispose) {}
 443
 444   ~WDL_PtrKeyedArray() {}
 445
 446 private:
 447
 448   static int cmpptr(INT_PTR* a, INT_PTR* b) { const INT_PTR d = *a - *b; return d<0?-1:(d!=0); }
 449 };
 450
 451
 452 #endif
 453