00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
00041
00042
00043
00044
00045
00046
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;
00075 typedef std::pair<FXuint, itemlist> hashitemlist;
00076 protected:
00077 typedef std::map<keytype, hashitemlist> keyitemlist;
00078 typedef typename keyitemlist::value_type keyitem;
00079 private:
00080 typedef std::vector<keyitemlist> dictionary;
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 {
00089 return ((hash*0x9E3779B9)>>8) % size;
00090 }
00091 inline FXuint mkSize(FXuint size) const
00092 {
00093
00094
00095
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 ¤tKey() const
00367 {
00368 if(mydict)
00369 {
00370 typename QDictBase<keytype, type>::keyitem &ki=*itkil;
00371 return ki.first;
00372 }
00373
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();
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 {
00447 ++(*dictit);
00448 }
00449 }
00450 deleteItem(il.back());
00451 il.pop_back();
00452 items--;
00453 inserts++;
00454 if(il.empty())
00455 {
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
00486 nkil.insert(keyitem(ki.first, hashitemlist(h, il)));
00487 }
00488 }
00489 dict.swap(newdict);
00490 mysize=newsize;
00491
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
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 )
00543 #else
00544 )
00545 #endif
00546 {
00547 newsize=1;
00548 }
00549 else if(memload || dictcount>=dictsize/2 || (dictsize>=15 && dictcount<=dictsize/4))
00550 {
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 )
00584 #else
00585 )
00586 #endif
00587 {
00588 newsize=1;
00589 }
00590 else if(dictcount>=dictsize/2 || (memload && dictsize>=31 && dictcount<=dictsize/8))
00591 {
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 }
00607
00608 #endif