UniqueSetRaw.h

Go to the documentation of this file.
00001 
00007 /*
00008    Uses simple hash table type unique elements set 
00009    layout allows for faster iteration due to clustering of data
00010 */
00011 
00012 #ifndef USETRAW_H
00013 #define USETRAW_H
00014 
00015 #include <new>
00016 
00017 template <class Elem> class EntryGlob;
00018 template <class Elem> class UniqueSetRaw;
00019 
00020 // Utility class for UniqueSetRaw
00021 // Each entry hold an Obj<Elem>, used flag and next pointer
00022 
00023 template <class Elem> class Entry {
00024 
00025   friend class UniqueSetRaw<Elem>;
00026   friend class EntryGlob<Elem>;
00027 
00028   private:
00029   
00030     Entry<Elem> *_next;
00031     long used;
00032     Entry(void) { _next = 0; used = 0; }
00033   
00034   public:
00035   
00036     Elem obj;
00037 
00038     ~Entry(void) { clear(); }
00039 
00040     void clear(void) { 
00041       if (used) obj.~Elem();
00042       used = 0;
00043     }
00044 
00045     Entry<Elem> *next(void) const { return _next; }
00046 
00047     int isUsed(void) const { return used; }
00048   
00049     static void clearChain(Entry<Elem> *e) {
00050       while(e) {
00051         Entry<Elem> *tmp = e->next();
00052         e->clear();
00053         e = tmp;
00054       }
00055     }
00056 
00057     // remove this entry from link list
00058     Entry<Elem> *removeSelf(void) {
00059       Entry<Elem> *e = this->next();
00060       clear();
00061       return (e);
00062     }
00063 
00064     //
00065     Entry<Elem> &operator=(const Elem &e) {
00066       if (!used)
00067         new(&obj) Elem;
00068       obj = e;
00069       used = 1;
00070       return (*this);
00071     }
00072 
00073     //
00074     Entry<Elem> *setNext(Entry<Elem> *e) {
00075       this->_next = e;
00076       return this;
00077     }
00078 };
00079 
00080 template <class Elem> class UniqueSetRaw;
00081 template <class Elem> class UniqueSetIter;
00082 
00083 // Utility class for UniqueSetRaw
00084 template <class Elem> class EntryGlob {
00085 
00086   friend class UniqueSetIter<Elem>;
00087   friend class UniqueSetRaw<Elem>;
00088 
00089   public:
00090   
00091     ~EntryGlob(void) { clear(); }
00092 
00093     void clear(void) { delete[] glob; }
00094 
00095     EntryGlob<Elem> *next(void) { return _next; }
00096 
00097     EntryGlob<Elem> *setNext(EntryGlob<Elem>* e) { 
00098       this->_next = e; return this; 
00099     }
00100 
00101     static void clearChain(EntryGlob<Elem> *e) {
00102       while(e) { EntryGlob<Elem> *tmp = e->next(); delete e; e = tmp; }
00103     }
00104 
00105   private:
00106 
00107     inline EntryGlob(int size);
00108   
00109     EntryGlob<Elem> *_next;
00110     Entry<Elem> *glob;
00111 };
00112   
00113 template<class Elem>
00114 inline EntryGlob<Elem>::EntryGlob(int size) {
00115   _next = 0;
00116   Entry<Elem>* entry = glob = new Entry<Elem>[size];
00117   for (; entry != glob+size-1; entry++) {
00118     entry->setNext(entry+1);
00119   }
00120   entry->setNext(0);
00121 }
00122 
00123 
00124 //----------------------------------------------------------------------
00125 // UniqueSetRaw container class definition
00126 // Uses hash table type lookup
00127 // main user methods: add(), del(), find()
00128 //----------------------------------------------------------------------
00129 
00130 template <class Elem> class UniqueSet;
00131 template <class Elem> class UniqueSetIter;
00132 
00133 template <class Elem> class UniqueSetRaw {
00134 
00135   friend class UniqueSet<Elem>;
00136   friend class UniqueSetIter<Elem>;
00137 
00138   public:
00139 
00140     // Various Constructors
00141     inline UniqueSetRaw(int size=101);
00142 
00143     // Hopefully, this is never used
00144     UniqueSetRaw(const UniqueSetRaw<Elem> &us) { copy(us); }
00145 
00146     ~UniqueSetRaw(void) { cleanUp(); }
00147 
00148     UniqueSetRaw<Elem> & operator=(const UniqueSetRaw<Elem> &us) {
00149       copy(us);
00150       return *this;
00151     }  
00152 
00153     void rehash(void) { rehash(numElem); }
00154 
00155     // make a new table of appropriate size
00156     void rehash(int size) {
00157       // Store away old pointers and Entry<Elem>(s)
00158       int oldTableLength= tableLength;
00159       Entry<Elem> **oldTable = table;
00160     
00161       // recreate the table
00162       tableLength = findSize(numElem > size ? numElem : size);
00163       if (tableLength == oldTableLength) 
00164         return;
00165       numElem = 0;
00166       table = new Entry<Elem>*[tableLength];
00167       growSize = tableLength * 4;
00168     
00169       // 0 table
00170       Entry<Elem> **t = table; Entry<Elem> **e = table+tableLength;
00171       for (; t != e; *t++ = 0);
00172     
00173       // go thru old table and chains of Entry<Elem>(s)
00174       for (int i=0; i<oldTableLength; i++) {
00175         Entry<Elem> *e = oldTable[i];
00176         while(e) {
00177           Entry<Elem> *tmp = e->next();
00178           remapEntry(e);
00179           numElem++;
00180           e = tmp;
00181         }
00182       }
00183       delete[] oldTable;
00184     } 
00185 
00186   
00187     void setSafeNoDestruction(int flag) { isSafeNoDestruction = flag; }
00188   
00189     // add element to our hash table!
00190     int add(const Elem &elem) {
00191       int tableSlot = elem.hash() % tableLength;
00192       int doadd = 1;
00193       for (Entry<Elem> *e = table[tableSlot]; e; e=e->next()) {
00194         if (e->obj == elem) { doadd = 0; break; }
00195       }
00196       if (doadd) {
00197         Entry<Elem> *entry = nextFree();
00198         *entry = elem; // sets used flag
00199         table[tableSlot] = entry->setNext(table[tableSlot]);
00200         if ( ++numElem > growSize)  
00201           rehash();
00202       }
00203       return(doadd);
00204     }
00205   
00206     int load(const Elem &elem) {
00207       Entry<Elem> *entry = nextFree();
00208       *entry = elem; // sets used flag
00209       table[0] = entry->setNext(table[0]);
00210       ++numElem;
00211       return(1);
00212     }
00213   
00214     // find element
00215     Elem *find(const Elem &elem) {
00216       register Entry<Elem> *e = table[elem.hash() % tableLength];
00217       while(e) {
00218         if (elem == e->obj ) {
00219           return (&(e->obj));
00220         }
00221         e = e->next();
00222       }
00223       return (0);
00224     }
00225   
00226     int del(const Elem &elem) {
00227       int tableSlot = elem.hash() % tableLength;
00228       int dodel = 0;
00229     
00230       Entry<Elem> *prev = 0;
00231       Entry<Elem> *e = table[tableSlot];
00232       while(e) {
00233         if (e->obj == elem) {
00234           if (0 == prev) {
00235             table[tableSlot] = e->removeSelf();
00236           } else {
00237             prev->setNext(e->removeSelf());
00238           } 
00239           addFree(e); dodel = 1; numElem--;
00240           break;
00241         }
00242         prev = e;
00243         e = e->next();
00244       }
00245       return dodel;
00246     }
00247 
00248   
00249     int size(void) const { return(numElem); }
00250 
00251     void clear(int n=0) {
00252       if (!n) n = size();
00253       cleanUp();
00254       init(n); // have to have something currently for a table
00255     }
00256 
00257 #ifdef DEBUG
00258     void status(void) {
00259       int count = 0;
00260       for (int i=0; i < tableLength; i++) {
00261         Entry<Elem> *e = table[i];
00262         cout << "Table entry [" << i << "]" << std::endl;
00263         while (e) {
00264           if (e->isUsed())  { 
00265               count++;
00266               e->obj.status();
00267           } else {
00268               cout << "Entry is not used" << std::endl;
00269           }
00270           e = e->next();
00271         }
00272       }
00273       cout << "===== COUNT = " << count << std::endl;
00274     }
00275 #endif
00276   
00277   protected:
00278 
00279     int refCount;
00280     // used by iterator and free list
00281     EntryGlob<Elem> *globHead;
00282   
00283   private:
00284 
00285     // basic hash table pointers
00286     Entry<Elem> **table;
00287     unsigned int tableLength;
00288     unsigned int growSize;
00289     // number of elements in table
00290     unsigned int numElem;
00291     // allocation parameters
00292     int growable;
00293     int globSize;
00294     int isSafeNoDestruction;
00295 
00296     // Utilities
00297 
00298     int findSize(unsigned int size) {
00299       size /= 2;
00300       int rval;
00301       if ( ( rval = 11 ) <= size )
00302        if ( ( rval = 31 ) <= size )
00303         if ( ( rval = 101 ) <= size )
00304          if ( ( rval = 307 ) <= size )
00305           if ( ( rval = 1009 ) <= size )
00306            if ( ( rval = 3001 ) <= size )
00307             if ( ( rval = 10007 ) <= size )
00308              if ( ( rval = 30011 ) <= size )
00309               if ( ( rval = 100003 ) <= size )
00310                if ( ( rval = 300007 ) <= size )
00311                 if ( ( rval = 1000003 ) <= size )
00312                  if ( ( rval = 3000017 ) <= size )
00313                   if ( ( rval = 10000019 ) <= size )
00314                    if ( ( rval = 30000023 ) <= size )
00315                     if ( ( rval = 100000007 ) <= size )
00316                      if ( ( rval = 300000007 ) <= size )
00317                       rval = 1000000007;
00318       return rval;
00319     }
00320 
00321     void cleanUp(void) {
00322       for (int i=0; i<tableLength; i++)
00323         Entry<Elem>::clearChain(table[i]);
00324       tableLength = 0;
00325       growSize = 0;
00326       delete[] table;
00327       table = 0;
00328       freeListClean();
00329       numElem = 0;
00330     }
00331 
00332     void copy(const UniqueSetRaw<Elem> &us) {
00333       cleanUp();
00334       isSafeNoDestruction = us.isSafeNoDestruction;
00335       tableLength = findSize(us.numElem);
00336       growSize = tableLength * 4;
00337       table = new Entry<Elem>*[tableLength];
00338     
00339       for (int i=0; i<us.tableLength; i++) {
00340         Entry<Elem> *e = us.table[i];
00341         while (e) {
00342           add(e->obj);
00343           e = e->next();
00344         }
00345       }
00346     }
00347 
00348     void init(int size) {
00349       tableLength = findSize(size);
00350       growSize = tableLength * 4;
00351       table = new Entry<Elem>*[tableLength];
00352     
00353       Entry<Elem> **t = table; Entry<Elem> **e = table+tableLength;
00354       for (; t != e; *t++ = 0);
00355     
00356       freeListInit();
00357     }
00358 
00359     // Only to be used by rehash
00360     void remapEntry(Entry<Elem> *e) {
00361       int tableSlot = e->obj.hash() % tableLength;
00362       table[tableSlot] = e->setNext(table[tableSlot]);
00363     }
00364   
00365     // free list maintenance
00366     Entry<Elem> *head;
00367 
00368     void freeListInit(void) {
00369       head = 0; globHead = 0;
00370     }
00371 
00372     void freeListClean(void) {
00373       EntryGlob<Elem> *tmp = globHead;
00374       while( (globHead = tmp) ) {
00375         tmp = globHead->next();
00376         delete globHead; // delete's glob
00377       } 
00378     }
00379 
00380     Entry<Elem> *nextFree(void) {
00381       if (!head) {
00382          EntryGlob<Elem> *tmp = new EntryGlob<Elem>(globSize);
00383          head = tmp->glob;
00384          globHead = tmp->setNext(globHead);
00385       }
00386       Entry<Elem> *entry = head;
00387       head = entry->next();
00388       return(entry);
00389     }
00390 
00391     void addFree(Entry<Elem> *e) {
00392       head = e->setNext(head);
00393       e->used = 0;
00394     }
00395   
00396 };
00397 
00398 template <class  Elem>
00399 inline UniqueSetRaw<Elem>::UniqueSetRaw(int size) : 
00400   table(0), tableLength(0), numElem(0), growable(1) {
00401   const int minGlobSize = 32;
00402   isSafeNoDestruction = 1;
00403   growSize = 0;
00404   globSize = minGlobSize;
00405   init(size);
00406 }
00407 
00408 #endif

Generated on Mon Nov 20 01:17:15 2017 for NAMD by  doxygen 1.4.7