qdictbase.h

Go to the documentation of this file.
00001 /********************************************************************************
00002 *                                                                               *
00003 *                   G e n e r i c   Q D i c t   T h u n k                       *
00004 *                                                                               *
00005 *********************************************************************************
00006 *        Copyright (C) 2003 by Niall Douglas.   All Rights Reserved.            *
00007 *       NOTE THAT I DO NOT PERMIT ANY OF MY CODE TO BE PROMOTED TO THE GPL      *
00008 *********************************************************************************
00009 * This code is free software; you can redistribute it and/or modify it under    *
00010 * the terms of the GNU Library General Public License v2.1 as published by the  *
00011 * Free Software Foundation EXCEPT that clause 3 does not apply ie; you may not  *
00012 * "upgrade" this code to the GPL without my prior written permission.           *
00013 * Please consult the file "License_Addendum2.txt" accompanying this file.       *
00014 *                                                                               *
00015 * This code is distributed in the hope that it will be useful,                  *
00016 * but WITHOUT ANY WARRANTY; without even the implied warranty of                *
00017 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                          *
00018 *********************************************************************************
00019 * $Id:                                                                          *
00020 ********************************************************************************/
00021 
00022 #ifndef QDICTBASE_H
00023 #define QDICTBASE_H
00024 
00025 #include "FXException.h"
00026 #include "FXStream.h"
00027 #include "FXProcess.h"
00028 #include <utility>
00029 #include <vector>
00030 #include <map>
00031 
00032 namespace FX {
00033 
00038 typedef FXuint uint;
00039 
00040 /* ned 19th Oct 2003: Looked through hash_multimap but was not convinced at
00041 all - seems to be hard to get the last element of a group of elements
00042 attached to a key. I may be missing something, but this class is /the/ most
00043 important performance-wise to Tn which uses it very heavily indeed, so I'm
00044 going to opt for my own implementation after all. In the end, right now
00045 (2003) hash_multimap is not part of the C++ STL and it's likely to get
00046 replaced with something similar but different.
00047 */
00048 template<typename keytype, class type> class QDictBaseIterator;
00049 
00070 template<class keytype, class type> class QDictBase
00071 {
00072     friend class QDictBaseIterator<keytype, type>;
00073 private:
00074     typedef std::vector<type *> itemlist; // Simple array of pointers to items
00075     typedef std::pair<FXuint, itemlist> hashitemlist; // Tuple of (key hash, item list)
00076 protected:
00077     typedef std::map<keytype, hashitemlist> keyitemlist; // Map of key values to item list
00078     typedef typename keyitemlist::value_type keyitem;
00079 private:
00080     typedef std::vector<keyitemlist> dictionary; // Hash-indexed slots
00081     bool autodel;
00082     dictionary dict;
00083     FXuint items, mysize;
00084     mutable FXuint inserts, lookups;
00085     typedef std::vector<QDictBaseIterator<keytype, type> *> iteratorlist;
00086     iteratorlist iterators;
00087     inline FXuint mkIdx(FXuint hash, FXuint size) const
00088     {   // 0x9E3779B9 being the fibonacci constant (excellent spread)
00089         return ((hash*0x9E3779B9)>>8) % size;
00090     }
00091     inline FXuint mkSize(FXuint size) const
00092     {
00093         //FXuint ret=1;
00094         //while(ret<size) ret<<=1;
00095         //return ret;
00096         if(size<1) size=1;
00097         return size;
00098     }
00099 public:
00100     enum { HasSlowKeyCompare=false };
00102     typedef keytype KeyType;
00104     typedef type ItemType;
00105     QDictBase(uint _size, bool wantAutoDel=false) : autodel(wantAutoDel), dict(mkSize(_size)), items(0), mysize(mkSize(_size)), inserts(0), lookups(0) { }
00106     inline ~QDictBase();
00107     QDictBase(const QDictBase<keytype, type> &o) : autodel(o.autodel), dict(o.dict), items(o.items), mysize(o.mysize), inserts(o.inserts), lookups(o.lookups) { }
00108     QDictBase<keytype, type> &operator=(const QDictBase<keytype, type> &o)
00109     {
00110         clear();
00111         autodel=o.autodel; dict=o.dict; items=o.items; mysize=o.mysize; inserts=o.inserts; lookups=o.lookups;
00112         return (*this);
00113     }
00114 #ifdef HAVE_CPP0XRVALUEREFS
00115     QDictBase(const QDictBase<keytype, type> &&o) : autodel(std::move(o.autodel)), dict(std::move(o.dict)), items(std::move(o.items)), mysize(std::move(o.mysize)), inserts(std::move(o.inserts)), lookups(std::move(o.lookups)) { }
00116     QDictBase<keytype, type> &&operator=(const QDictBase<keytype, type> &&o)
00117     {
00118         autodel=std::move(o.autodel); dict=std::move(o.dict); items=std::move(o.items); mysize=std::move(o.mysize); inserts=std::move(o.inserts); lookups=std::move(o.lookups);
00119         return (*this);
00120     }
00121 #endif
00123     bool autoDelete() const { return autodel; }
00125     void setAutoDelete(bool a) { autodel=a; }
00126 
00128     uint count() const { return items; }
00130     bool isEmpty() const { return !items; }
00132     uint size() const { return mysize; }
00133 protected:
00134     keyitem *findKey(FXuint h, const keytype &k)
00135     {
00136         keyitemlist &kil=dict[mkIdx(h, mysize)];
00137         typename keyitemlist::iterator it=kil.find(k);
00138         if(it==kil.end()) return 0;
00139         else return &(*it);
00140     }
00141     const keyitem *findKey(FXuint h, const keytype &k) const
00142     {
00143         const keyitemlist &kil=dict[mkIdx(h, mysize)];
00144         typename keyitemlist::const_iterator it=kil.find(k);
00145         if(it==kil.end()) return 0;
00146         else return &(*it);
00147     }
00148     void insert(FXuint h, const keytype &k, type *d)
00149     {
00150         keyitemlist &kil=dict[mkIdx(h, mysize)];
00151         typename keyitemlist::iterator it=kil.find(k);
00152         FXEXCEPTION_STL1 {
00153             if(it==kil.end())
00154             {
00155                 std::pair<typename keyitemlist::iterator, bool> point=kil.insert(keyitem(k, hashitemlist(h, itemlist())));
00156                 it=point.first;
00157             }
00158             keyitem &ki=*it;
00159             itemlist &il=ki.second.second;
00160             il.push_back(d);
00161         } FXEXCEPTION_STL2;
00162         items++;
00163         inserts++;
00164     }
00165     void replace(FXuint h, const keytype &k, type *d)
00166     {
00167         remove(h, k);
00168         insert(h, k, d);
00169     }
00170     inline bool remove(FXuint h, const keytype &k);
00171     type *take(FXuint h, const keytype &k)
00172     {
00173         keyitem *ki=findKey(h, k);
00174         if(!ki) return 0;
00175         itemlist &il=ki->second.second;
00176         if(il.empty()) return 0;
00177         type *ret=il.back();
00178         il.pop_back();
00179         items--;
00180         inserts++;
00181         return ret;
00182     }
00183     type *find(FXuint h, const keytype &k) const
00184     {
00185         lookups++;
00186         const keyitem *ki=findKey(h, k);
00187         if(!ki) return 0;
00188         const itemlist &il=ki->second.second;
00189         if(il.empty()) return 0;
00190         return il.back();
00191     }
00192 public:
00194     void clear()
00195     {
00196         for(typename dictionary::iterator itdict=dict.begin(); itdict!=dict.end(); ++itdict)
00197         {
00198             keyitemlist &kil=*itdict;
00199             for(typename keyitemlist::iterator itkil=kil.begin(); itkil!=kil.end(); ++itkil)
00200             {
00201                 keyitem &ki=*itkil;
00202                 itemlist &il=ki.second.second;
00203                 for(typename itemlist::iterator itlist=il.begin(); itlist!=il.end(); ++itlist)
00204                 {
00205                     deleteItem(*itlist);
00206                 }
00207                 il.clear();
00208             }
00209             kil.clear();
00210         }
00211         items=0;
00212     }
00214     void append(const QDictBase<keytype, type> &o);
00216     QDictBase<keytype, type> &operator+=(const QDictBase<keytype, type> &o) { append(o); return *this; }
00217 private:
00218     void resizeI(uint newsize);
00219 public:
00221     void resize(uint newsize)
00222     {
00223         newsize=mkSize(newsize);
00224         if(mysize!=newsize)
00225         {
00226             FXEXCEPTION_STL1 {
00227                 resizeI(newsize);
00228             } FXEXCEPTION_STL2;
00229         }
00230     }
00232     void safeResize(uint newsize) throw()
00233     {
00234         newsize=mkSize(newsize);
00235         if(mysize!=newsize)
00236         {
00237             try
00238             {
00239                 resizeI(newsize);
00240             }
00241             catch(...)
00242             {
00243             }
00244         }
00245     }
00255     void spread(float *full, float *slotsspread, float *avrgkeysperslot, float *spread) const
00256     {
00257         if(full) *full=(float) 100.0*items/mysize;
00258         if(slotsspread || avrgkeysperslot || spread)
00259         {
00260             FXuint slotsused=0, keys=0;
00261             for(typename dictionary::const_iterator itdict=dict.begin(); itdict!=dict.end(); ++itdict)
00262             {
00263                 const keyitemlist &kil=(*itdict);
00264                 if(!kil.empty())
00265                 {
00266                     slotsused++;
00267                     keys+=(FXuint) kil.size();
00268                 }
00269             }
00270             if(slotsspread) *slotsspread=(float) 100.0*slotsused/FXMIN(mysize, items);
00271             if(avrgkeysperslot) *avrgkeysperslot=(float) keys/slotsused;
00272             if(spread) *spread=((float) 100.0*slotsused/FXMIN(mysize, items))/((float) keys/slotsused);
00273         }
00274     }
00276     void statistics() const
00277     {
00278 #ifdef DEBUG
00279         float full, slotsspread, avrgkeysperslot, _spread;
00280         spread(&full, &slotsspread, &avrgkeysperslot, &_spread);
00281         fxmessage("Dictionary size=%d, items=%d, full=%f%%, slot spread=%f%%, avrg keys per slot=%f, overall spread=%f%%\n", mysize, items, full, slotsspread, avrgkeysperslot, _spread);
00282 #endif
00283     }
00287     FXint dictionaryBias() const throw() { return (FXint)(lookups-inserts); }
00288 protected:
00289     virtual void deleteItem(type *d)=0;
00290 };
00291 
00292 
00296 template<typename keytype, class type> class QDictBaseIterator
00297 {
00298     friend class QDictBase<keytype, type>;
00299     QDictBase<keytype, type> *mydict;
00300     typename QDictBase<keytype, type>::dictionary::iterator itdict;
00301     typename QDictBase<keytype, type>::keyitemlist::iterator itkil;
00302     typename QDictBase<keytype, type>::itemlist::iterator itil;
00303     void int_next(int j=1)
00304     {
00305         bool firstiter=true;
00306         typename QDictBase<keytype, type>::dictionary::iterator itdictend=mydict->dict.end();
00307         while(itdict!=itdictend)
00308         {
00309             typename QDictBase<keytype, type>::keyitemlist::iterator itkilend=(*itdict).end();
00310             if(!firstiter) itkil=(*itdict).begin();
00311             while(itkil!=itkilend)
00312             {
00313                 typename QDictBase<keytype, type>::itemlist::iterator itilend=(*itkil).second.second.end();
00314                 if(!firstiter) itil=(*itkil).second.second.begin();
00315                 while(itil!=itilend)
00316                 {
00317                     if(!j) return;
00318                     if(firstiter) ++itil;
00319                     j--;
00320                 }
00321                 ++itkil;
00322                 firstiter=false;
00323             }
00324             ++itdict;
00325             firstiter=false;
00326         }
00327     }
00328     void int_removeFromDict() const
00329     {
00330         for(typename QDictBase<keytype, type>::iteratorlist::iterator it=mydict->iterators.begin(); it!=mydict->iterators.end(); ++it)
00331         {
00332             if(this==*it)
00333             {
00334                 mydict->iterators.erase(it);
00335                 break;
00336             }
00337         }
00338     }
00339 protected:
00340     type *retptr() const
00341     {
00342         if(!mydict || mydict->dict.end()==itdict) return 0;
00343         if((*itdict).end()==itkil) return 0;
00344         if((*itkil).second.second.end()==itil) return 0;
00345         return *itil;
00346     }
00347 public:
00348     QDictBaseIterator() : mydict(0) { }
00349     QDictBaseIterator(const QDictBase<keytype, type> &d)
00350         : mydict(const_cast<QDictBase<keytype, type> *>(&d))
00351     {
00352         toFirst();
00353         mydict->iterators.push_back(this);
00354     }
00355     QDictBaseIterator(const QDictBaseIterator &o) : mydict(o.mydict), itdict(o.itdict), itkil(o.itkil), itil(o.itil)
00356     {
00357         if(mydict)
00358             mydict->iterators.push_back(this);
00359     }
00360     ~QDictBaseIterator()
00361     {
00362         if(mydict)
00363             int_removeFromDict();
00364     }
00366     const keytype &currentKey() const
00367     {
00368         if(mydict)
00369         {
00370             typename QDictBase<keytype, type>::keyitem &ki=*itkil;
00371             return ki.first;
00372         }
00373         // Hopefully this will cause an exception
00374         return *((const keytype *) 0);
00375     }
00376     QDictBaseIterator &operator=(const QDictBaseIterator &it)
00377     {
00378         if(mydict)
00379             int_removeFromDict();
00380         mydict=it.mydict;
00381         itdict=it.itdict;
00382         itkil=it.itkil;
00383         itil=it.itil;
00384         if(mydict)
00385             mydict->iterators.push_back(this);
00386         return *this;
00387     }
00389     uint count() const   { return mydict ? mydict->count() : 0; }
00391     bool isEmpty() const { return mydict ? mydict.isEmpty() : true; }
00393     type *toFirst()
00394     {
00395         if(!mydict) return 0;
00396         itdict=mydict->dict.begin();
00397         itkil=(*itdict).begin();
00398         if((*itdict).end()!=itkil)
00399             itil=(*itkil).second.second.begin();
00400         else int_next();
00401         return retptr();
00402     }
00404     operator type *() const { return retptr(); }
00406     type *operator*() { return retptr(); }
00408     type *current() const { return retptr(); }
00410     type *operator()() { return retptr(); }
00412     type *operator++()
00413     {
00414         return this->operator+=(1);
00415     }
00417     type *operator+=(uint j)
00418     {
00419         if(!retptr()) return 0;
00420         int_next(j);
00421         return retptr();
00422     }
00423 };
00424 
00425 template<class keytype, class type> inline QDictBase<keytype, type>::~QDictBase()
00426 {
00427     clear();    // Should trigger a terminate() if not cleared
00428     for(typename iteratorlist::iterator it=iterators.begin(); it!=iterators.end(); ++it)
00429     {
00430         (*it)->mydict=0;
00431     }
00432 }
00433 
00434 template<class keytype, class type> inline bool QDictBase<keytype, type>::remove(FXuint h, const keytype &k)
00435 {
00436     keyitemlist &kil=dict[mkIdx(h, mysize)];
00437     typename keyitemlist::iterator it=kil.find(k);
00438     if(it==kil.end()) return false;
00439     itemlist &il=(*it).second.second;
00440     if(il.empty()) return false;
00441     typename itemlist::iterator ilend=il.end(); --ilend;
00442     for(typename iteratorlist::iterator it2=iterators.begin(); it2!=iterators.end(); ++it2)
00443     {
00444         QDictBaseIterator<keytype, type> *dictit=*it2;
00445         if(dictit->itil==ilend)
00446         {   // Advance the iterator
00447             ++(*dictit);
00448         }
00449     }
00450     deleteItem(il.back());
00451     il.pop_back();
00452     items--;
00453     inserts++;
00454     if(il.empty())
00455     {   // Delete the key entry
00456         kil.erase(it);
00457     }
00458     return true;
00459 }
00460 
00461 template<class keytype, class type> void QDictBase<keytype, type>::append(const QDictBase<keytype, type> &o)
00462 {
00463     type *a;
00464     for(QDictBaseIterator<keytype, type> it(o); (a=it.current()); ++it)
00465     {
00466         typename QDictBase<keytype, type>::keyitem &ki=*it.itkil;
00467         insert(ki.second.first, ki.first, a);
00468     }
00469 }
00470 
00471 template<class keytype, class type> void QDictBase<keytype, type>::resizeI(uint newsize)
00472 {
00473     dictionary newdict(newsize);
00474     for(typename dictionary::iterator itdict=dict.begin(); itdict!=dict.end(); ++itdict)
00475     {
00476         keyitemlist &kil=*itdict;
00477         for(typename keyitemlist::iterator itkil=kil.begin(); itkil!=kil.end(); ++itkil)
00478         {
00479             keyitem &ki=*itkil;
00480             hashitemlist &hil=ki.second;
00481             FXuint h=hil.first;
00482             itemlist &il=hil.second;
00483 
00484             keyitemlist &nkil=newdict[mkIdx(h, newsize)];
00485             // Really could do with move semantics here :(
00486             nkil.insert(keyitem(ki.first, hashitemlist(h, il)));
00487         }
00488     }
00489     dict.swap(newdict); // Save copying the whole tree. Even better if we had move semantics :(
00490     mysize=newsize;
00491     // Kill all iterators
00492     for(typename iteratorlist::iterator it2=iterators.begin(); it2!=iterators.end(); ++it2)
00493     {
00494         QDictBaseIterator<keytype, type> *dictit=*it2;
00495         dictit->mydict=0;
00496 #ifdef DEBUG
00497         fxmessage("WARNING: QDictBaseIterator at %p made invalid by QDictBase::resize()\n", dictit);
00498 #endif
00499     }
00500 #if defined(DEBUG) && 0
00501     // Ensure every element in the old list also exists in the new list
00502     for(typename dictionary::iterator itdict=dict.begin(); itdict!=dict.end(); ++itdict)
00503     {
00504         keyitemlist &kil=*itdict;
00505         for(typename keyitemlist::iterator itkil=kil.begin(); itkil!=kil.end(); ++itkil)
00506         {
00507             keyitem &ki=*itkil;
00508             hashitemlist &hil=ki.second;
00509             FXuint h=hil.first;
00510             itemlist &il=hil.second;
00511             assert(find(h, ki.first)==il.back());
00512         }
00513     }
00514 #endif
00515 }
00516 
00517 
00530 #ifdef DEBUG
00531 #define QDICTDYNRESIZE(dict) FX::QDictByMemLoadResize(dict, __FILE__, __LINE__)
00532 #else
00533 #define QDICTDYNRESIZE(dict) FX::QDictByMemLoadResize(dict)
00534 #endif
00535 
00536 template<class dicttype> inline bool QDictByMemLoadResize(dicttype &dict, const char *file=0, int lineno=0)
00537 {
00538     FXuint memload=FXProcess::memoryFull(), dictcount=dict.count(), dictsize=dict.size();
00539     FXuint newsize=dictsize;
00540     if(dictcount<=16+48*dicttype::HasSlowKeyCompare
00541 #ifndef FXDISABLE_QDICTSLOWINSERTSOPT
00542         || dict.dictionaryBias()<16 /* slush factor */)
00543 #else
00544         )
00545 #endif
00546     {   // Better performance if we leave it purely to std::map
00547         newsize=1;
00548     }
00549     else if(memload || dictcount>=dictsize/2 || (dictsize>=15 && dictcount<=dictsize/4))
00550     {   // 15*(4+4+12+4)=15*24=360 bytes
00551         const FXuint *primes=fx2powerprimes(dictcount*2);
00552         newsize=primes[memload];
00553     }
00554     if(newsize!=dictsize)
00555     {
00556 #ifdef DEBUG
00557         fxmessage("QDICTDYNRESIZE at %s:%d resizing %p from %u to %u (load %d)\n", file, lineno, &(dict), dictsize, newsize, memload);
00558 #endif
00559         dict.safeResize(newsize);
00560         return true;
00561     }
00562     return false;
00563 }
00564 
00571 #ifdef DEBUG
00572 #define QDICTDYNRESIZEAGGR(dict) FX::QDictByMemLoadResizeAggr(dict, __FILE__, __LINE__)
00573 #else
00574 #define QDICTDYNRESIZEAGGR(dict) FX::QDictByMemLoadResizeAggr(dict)
00575 #endif
00576 
00577 template<class dicttype> inline bool QDictByMemLoadResizeAggr(dicttype &dict, const char *file=0, int lineno=0)
00578 {
00579     FXuint memload=FXProcess::memoryFull(), dictcount=dict.count(), dictsize=dict.size();
00580     FXuint newsize=dictsize;
00581     if(dictcount<=16+48*dicttype::HasSlowKeyCompare
00582 #ifndef FXDISABLE_QDICTSLOWINSERTSOPT
00583         || dict.dictionaryBias()<16 /* slush factor */)
00584 #else
00585         )
00586 #endif
00587     {   // Better performance if we leave it purely to std::map
00588         newsize=1;
00589     }
00590     else if(dictcount>=dictsize/2 || (memload && dictsize>=31 && dictcount<=dictsize/8))
00591     {   // 31*(4+4+12+4)=31*24=744 bytes
00592         const FXuint *primes=fx2powerprimes(dictcount*2);
00593         newsize=primes[0];
00594     }
00595     if(newsize!=dictsize)
00596     {
00597 #ifdef DEBUG
00598         fxmessage("QDICTDYNRESIZEAGGR at %s:%d resizing %p from %u to %u (load %d)\n", file, lineno, &(dict), dictsize, newsize, memload);
00599 #endif
00600         dict.safeResize(newsize);
00601         return true;
00602     }
00603     return false;
00604 }
00605 
00606 } // namespace
00607 
00608 #endif

(C) 2002-2009 Niall Douglas. Some parts (C) to assorted authors.
Generated on Fri Nov 20 18:31:25 2009 for TnFOX by doxygen v1.4.7