NAMD
UniqueSetRaw.h
Go to the documentation of this file.
1 
7 /*
8  Uses simple hash table type unique elements set
9  layout allows for faster iteration due to clustering of data
10 */
11 
12 #ifndef USETRAW_H
13 #define USETRAW_H
14 
15 #include <new>
16 
17 template <class Elem> class EntryGlob;
18 template <class Elem> class UniqueSetRaw;
19 
20 // Utility class for UniqueSetRaw
21 // Each entry hold an Obj<Elem>, used flag and next pointer
22 
23 template <class Elem> class Entry {
24 
25  friend class UniqueSetRaw<Elem>;
26  friend class EntryGlob<Elem>;
27 
28  private:
29 
30  Entry<Elem> *_next;
31  long used;
32  Entry(void) { _next = 0; used = 0; }
33 
34  public:
35 
36  Elem obj;
37 
38  ~Entry(void) { clear(); }
39 
40  void clear(void) {
41  if (used) obj.~Elem();
42  used = 0;
43  }
44 
45  Entry<Elem> *next(void) const { return _next; }
46 
47  int isUsed(void) const { return used; }
48 
49  static void clearChain(Entry<Elem> *e) {
50  while(e) {
51  Entry<Elem> *tmp = e->next();
52  e->clear();
53  e = tmp;
54  }
55  }
56 
57  // remove this entry from link list
59  Entry<Elem> *e = this->next();
60  clear();
61  return (e);
62  }
63 
64  //
65  Entry<Elem> &operator=(const Elem &e) {
66  if (!used)
67  new(&obj) Elem;
68  obj = e;
69  used = 1;
70  return (*this);
71  }
72 
73  //
75  this->_next = e;
76  return this;
77  }
78 };
79 
80 template <class Elem> class UniqueSetRaw;
81 template <class Elem> class UniqueSetIter;
82 
83 // Utility class for UniqueSetRaw
84 template <class Elem> class EntryGlob {
85 
86  friend class UniqueSetIter<Elem>;
87  friend class UniqueSetRaw<Elem>;
88 
89  public:
90 
91  ~EntryGlob(void) { clear(); }
92 
93  void clear(void) { delete[] glob; }
94 
95  EntryGlob<Elem> *next(void) { return _next; }
96 
98  this->_next = e; return this;
99  }
100 
101  static void clearChain(EntryGlob<Elem> *e) {
102  while(e) { EntryGlob<Elem> *tmp = e->next(); delete e; e = tmp; }
103  }
104 
105  private:
106 
107  inline EntryGlob(int size);
108 
109  EntryGlob<Elem> *_next;
110  Entry<Elem> *glob;
111 };
112 
113 template<class Elem>
114 inline EntryGlob<Elem>::EntryGlob(int size) {
115  _next = 0;
116  Entry<Elem>* entry = glob = new Entry<Elem>[size];
117  for (; entry != glob+size-1; entry++) {
118  entry->setNext(entry+1);
119  }
120  entry->setNext(0);
121 }
122 
123 
124 //----------------------------------------------------------------------
125 // UniqueSetRaw container class definition
126 // Uses hash table type lookup
127 // main user methods: add(), del(), find()
128 //----------------------------------------------------------------------
129 
130 template <class Elem> class UniqueSet;
131 template <class Elem> class UniqueSetIter;
132 
133 template <class Elem> class UniqueSetRaw {
134 
135  friend class UniqueSet<Elem>;
136  friend class UniqueSetIter<Elem>;
137 
138  public:
139 
140  // Various Constructors
141  inline UniqueSetRaw(int size=101);
142 
143  // Hopefully, this is never used
144  UniqueSetRaw(const UniqueSetRaw<Elem> &us) { copy(us); }
145 
146  ~UniqueSetRaw(void) { cleanUp(); }
147 
149  copy(us);
150  return *this;
151  }
152 
153  void rehash(void) { rehash(numElem); }
154 
155  // make a new table of appropriate size
156  void rehash(int size) {
157  // Store away old pointers and Entry<Elem>(s)
158  int oldTableLength= tableLength;
159  Entry<Elem> **oldTable = table;
160 
161  // recreate the table
162  tableLength = findSize(numElem > size ? numElem : size);
163  if (tableLength == oldTableLength)
164  return;
165  numElem = 0;
166  table = new Entry<Elem>*[tableLength];
167  growSize = tableLength * 4;
168 
169  // 0 table
170  Entry<Elem> **t = table; Entry<Elem> **e = table+tableLength;
171  for (; t != e; *t++ = 0);
172 
173  // go thru old table and chains of Entry<Elem>(s)
174  for (int i=0; i<oldTableLength; i++) {
175  Entry<Elem> *e = oldTable[i];
176  while(e) {
177  Entry<Elem> *tmp = e->next();
178  remapEntry(e);
179  numElem++;
180  e = tmp;
181  }
182  }
183  delete[] oldTable;
184  }
185 
186 
187  void setSafeNoDestruction(int flag) { isSafeNoDestruction = flag; }
188 
189  // add element to our hash table!
190  int add(const Elem &elem) {
191  int tableSlot = elem.hash() % tableLength;
192  int doadd = 1;
193  for (Entry<Elem> *e = table[tableSlot]; e; e=e->next()) {
194  if (e->obj == elem) { doadd = 0; break; }
195  }
196  if (doadd) {
197  Entry<Elem> *entry = nextFree();
198  *entry = elem; // sets used flag
199  table[tableSlot] = entry->setNext(table[tableSlot]);
200  if ( ++numElem > growSize)
201  rehash();
202  }
203  return(doadd);
204  }
205 
206  int load(const Elem &elem) {
207  Entry<Elem> *entry = nextFree();
208  *entry = elem; // sets used flag
209  table[0] = entry->setNext(table[0]);
210  ++numElem;
211  return(1);
212  }
213 
214  // find element
215  Elem *find(const Elem &elem) {
216  register Entry<Elem> *e = table[elem.hash() % tableLength];
217  while(e) {
218  if (elem == e->obj ) {
219  return (&(e->obj));
220  }
221  e = e->next();
222  }
223  return (0);
224  }
225 
226  int del(const Elem &elem) {
227  int tableSlot = elem.hash() % tableLength;
228  int dodel = 0;
229 
230  Entry<Elem> *prev = 0;
231  Entry<Elem> *e = table[tableSlot];
232  while(e) {
233  if (e->obj == elem) {
234  if (0 == prev) {
235  table[tableSlot] = e->removeSelf();
236  } else {
237  prev->setNext(e->removeSelf());
238  }
239  addFree(e); dodel = 1; numElem--;
240  break;
241  }
242  prev = e;
243  e = e->next();
244  }
245  return dodel;
246  }
247 
248 
249  int size(void) const { return(numElem); }
250 
251  void clear(int n=0) {
252  if (!n) n = size();
253  cleanUp();
254  init(n); // have to have something currently for a table
255  }
256 
257 #ifdef DEBUG
258  void status(void) {
259  int count = 0;
260  for (int i=0; i < tableLength; i++) {
261  Entry<Elem> *e = table[i];
262  cout << "Table entry [" << i << "]" << std::endl;
263  while (e) {
264  if (e->isUsed()) {
265  count++;
266  e->obj.status();
267  } else {
268  cout << "Entry is not used" << std::endl;
269  }
270  e = e->next();
271  }
272  }
273  cout << "===== COUNT = " << count << std::endl;
274  }
275 #endif
276 
277  protected:
278 
279  int refCount;
280  // used by iterator and free list
282 
283  private:
284 
285  // basic hash table pointers
286  Entry<Elem> **table;
287  unsigned int tableLength;
288  unsigned int growSize;
289  // number of elements in table
290  unsigned int numElem;
291  // allocation parameters
292  int growable;
293  int globSize;
294  int isSafeNoDestruction;
295 
296  // Utilities
297 
298  int findSize(unsigned int size) {
299  size /= 2;
300  int rval;
301  if ( ( rval = 11 ) <= size )
302  if ( ( rval = 31 ) <= size )
303  if ( ( rval = 101 ) <= size )
304  if ( ( rval = 307 ) <= size )
305  if ( ( rval = 1009 ) <= size )
306  if ( ( rval = 3001 ) <= size )
307  if ( ( rval = 10007 ) <= size )
308  if ( ( rval = 30011 ) <= size )
309  if ( ( rval = 100003 ) <= size )
310  if ( ( rval = 300007 ) <= size )
311  if ( ( rval = 1000003 ) <= size )
312  if ( ( rval = 3000017 ) <= size )
313  if ( ( rval = 10000019 ) <= size )
314  if ( ( rval = 30000023 ) <= size )
315  if ( ( rval = 100000007 ) <= size )
316  if ( ( rval = 300000007 ) <= size )
317  rval = 1000000007;
318  return rval;
319  }
320 
321  void cleanUp(void) {
322  for (int i=0; i<tableLength; i++)
323  Entry<Elem>::clearChain(table[i]);
324  tableLength = 0;
325  growSize = 0;
326  delete[] table;
327  table = 0;
328  freeListClean();
329  numElem = 0;
330  }
331 
332  void copy(const UniqueSetRaw<Elem> &us) {
333  cleanUp();
334  isSafeNoDestruction = us.isSafeNoDestruction;
335  tableLength = findSize(us.numElem);
336  growSize = tableLength * 4;
337  table = new Entry<Elem>*[tableLength];
338 
339  for (int i=0; i<us.tableLength; i++) {
340  Entry<Elem> *e = us.table[i];
341  while (e) {
342  add(e->obj);
343  e = e->next();
344  }
345  }
346  }
347 
348  void init(int size) {
349  tableLength = findSize(size);
350  growSize = tableLength * 4;
351  table = new Entry<Elem>*[tableLength];
352 
353  Entry<Elem> **t = table; Entry<Elem> **e = table+tableLength;
354  for (; t != e; *t++ = 0);
355 
356  freeListInit();
357  }
358 
359  // Only to be used by rehash
360  void remapEntry(Entry<Elem> *e) {
361  int tableSlot = e->obj.hash() % tableLength;
362  table[tableSlot] = e->setNext(table[tableSlot]);
363  }
364 
365  // free list maintenance
366  Entry<Elem> *head;
367 
368  void freeListInit(void) {
369  head = 0; globHead = 0;
370  }
371 
372  void freeListClean(void) {
373  EntryGlob<Elem> *tmp = globHead;
374  while( (globHead = tmp) ) {
375  tmp = globHead->next();
376  delete globHead; // delete's glob
377  }
378  }
379 
380  Entry<Elem> *nextFree(void) {
381  if (!head) {
382  EntryGlob<Elem> *tmp = new EntryGlob<Elem>(globSize);
383  head = tmp->glob;
384  globHead = tmp->setNext(globHead);
385  }
386  Entry<Elem> *entry = head;
387  head = entry->next();
388  return(entry);
389  }
390 
391  void addFree(Entry<Elem> *e) {
392  head = e->setNext(head);
393  e->used = 0;
394  }
395 
396 };
397 
398 template <class Elem>
400  table(0), tableLength(0), numElem(0), growable(1) {
401  const int minGlobSize = 32;
402  isSafeNoDestruction = 1;
403  growSize = 0;
404  globSize = minGlobSize;
405  init(size);
406 }
407 
408 #endif
int size(void) const
Definition: UniqueSetRaw.h:249
EntryGlob< Elem > * globHead
Definition: UniqueSetRaw.h:281
~EntryGlob(void)
Definition: UniqueSetRaw.h:91
Entry< Elem > * next(void) const
Definition: UniqueSetRaw.h:45
UniqueSetRaw(int size=101)
Definition: UniqueSetRaw.h:399
void clear(void)
Definition: UniqueSetRaw.h:93
Entry< Elem > & operator=(const Elem &e)
Definition: UniqueSetRaw.h:65
int add(const Elem &elem)
Definition: UniqueSetRaw.h:190
void clear(void)
Definition: UniqueSetRaw.h:40
~Entry(void)
Definition: UniqueSetRaw.h:38
Elem obj
Definition: UniqueSetRaw.h:36
void setSafeNoDestruction(int flag)
Definition: UniqueSetRaw.h:187
Elem * find(const Elem &elem)
Definition: UniqueSetRaw.h:215
void status(void)
Definition: UniqueSetIter.h:98
static void clearChain(EntryGlob< Elem > *e)
Definition: UniqueSetRaw.h:101
int del(const Elem &elem)
Definition: UniqueSetRaw.h:226
void rehash(void)
Definition: UniqueSetRaw.h:153
~UniqueSetRaw(void)
Definition: UniqueSetRaw.h:146
EntryGlob< Elem > * next(void)
Definition: UniqueSetRaw.h:95
EntryGlob< Elem > * setNext(EntryGlob< Elem > *e)
Definition: UniqueSetRaw.h:97
void rehash(int size)
Definition: UniqueSetRaw.h:156
int isUsed(void) const
Definition: UniqueSetRaw.h:47
Entry< Elem > * setNext(Entry< Elem > *e)
Definition: UniqueSetRaw.h:74
int load(const Elem &elem)
Definition: UniqueSetRaw.h:206
void clear(int n=0)
Definition: UniqueSetRaw.h:251
Entry< Elem > * removeSelf(void)
Definition: UniqueSetRaw.h:58
static void clearChain(Entry< Elem > *e)
Definition: UniqueSetRaw.h:49
UniqueSetRaw(const UniqueSetRaw< Elem > &us)
Definition: UniqueSetRaw.h:144
UniqueSetRaw< Elem > & operator=(const UniqueSetRaw< Elem > &us)
Definition: UniqueSetRaw.h:148