MFEM  v3.2
Finite element discretization library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
hash.hpp
Go to the documentation of this file.
1 // Copyright (c) 2010, Lawrence Livermore National Security, LLC. Produced at
2 // the Lawrence Livermore National Laboratory. LLNL-CODE-443211. All Rights
3 // reserved. See file COPYRIGHT for details.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability see http://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the GNU Lesser General Public License (as published by the Free
10 // Software Foundation) version 2.1 dated February 1999.
11 
12 #ifndef MFEM_HASH
13 #define MFEM_HASH
14 
15 #include "../config/config.hpp"
16 #include "array.hpp"
17 
18 namespace mfem
19 {
20 
26 {
27 public:
28  IdGenerator(int first_id = 0) : next(first_id) {}
29 
30  IdGenerator(const IdGenerator& other) : next(other.next)
31  { other.reusable.Copy(reusable); }
32 
34  int Get()
35  {
36  if (reusable.Size())
37  {
38  int id = reusable.Last();
39  reusable.DeleteLast();
40  return id;
41  }
42  return next++;
43  }
44 
46  void Reuse(int id)
47  {
48  reusable.Append(id);
49  }
50 
51 private:
52  int next;
53  Array<int> reusable;
54 };
55 
56 
63 template<typename Derived>
64 struct Hashed2
65 {
66  int id;
67  int p1, p2;
68  Derived* next;
69 
70  Hashed2() {}
71  Hashed2(int id) : id(id) {}
72 };
73 
77 template<typename Derived>
78 struct Hashed4
79 {
80  int id;
81  int p1, p2, p3; // NOTE: p4 is not hashed nor stored
82  Derived* next;
83 
84  Hashed4() {}
85  Hashed4(int id) : id(id) {}
86 };
87 
88 
116 template<typename ItemT>
118 {
119 public:
120  HashTable(int init_size = 32*1024);
121  HashTable(const HashTable& other); // deep copy
122  ~HashTable();
123 
125  ItemT* Get(int p1, int p2);
126  ItemT* Get(int p1, int p2, int p3, int p4);
127 
129  ItemT* Peek(int p1, int p2) const;
130  ItemT* Peek(int p1, int p2, int p3, int p4) const;
131 
132  // item pointer variants of the above for convenience
133  template<typename OtherT>
134  ItemT* Get(OtherT* i1, OtherT* i2)
135  { return Get(i1->id, i2->id); }
136 
137  template<typename OtherT>
138  ItemT* Get(OtherT* i1, OtherT* i2, OtherT* i3, OtherT* i4)
139  { return Get(i1->id, i2->id, i3->id, i4->id); }
140 
141  template<typename OtherT>
142  ItemT* Peek(OtherT* i1, OtherT* i2) const
143  { return Peek(i1->id, i2->id); }
144 
145  template<typename OtherT>
146  ItemT* Peek(OtherT* i1, OtherT* i2, OtherT* i3, OtherT* i4) const
147  { return Peek(i1->id, i2->id, i3->id, i4->id); }
148 
150  ItemT* Peek(int id) const { return id_to_item[id]; }
151 
153  void Delete(ItemT* item);
154 
156  void Reparent(ItemT* item, int new_p1, int new_p2);
157  void Reparent(ItemT* item, int new_p1, int new_p2, int new_p3, int new_p4);
158 
160  class Iterator
161  {
162  public:
164  : hash_table(table), cur_id(-1), cur_item(NULL) { next(); }
165 
166  operator ItemT*() const { return cur_item; }
167  ItemT& operator*() const { return *cur_item; }
168  ItemT* operator->() const { return cur_item; }
169 
170  Iterator &operator++() { next(); return *this; }
171 
172  protected:
174  int cur_id;
175  ItemT* cur_item;
176 
177  void next();
178  };
179 
181  long MemoryUsage() const;
182 
183  void PrintMemoryDetail() const;
184 
185 protected:
186 
187  ItemT** table;
188  int mask;
190 
191  // hash functions (NOTE: the constants are arbitrary)
192  inline int hash(int p1, int p2) const
193  { return (984120265*p1 + 125965121*p2) & mask; }
194 
195  inline int hash(int p1, int p2, int p3) const
196  { return (984120265*p1 + 125965121*p2 + 495698413*p3) & mask; }
197 
198  // Remove() uses one of the following two overloads:
199  inline int hash(const Hashed2<ItemT>* item) const
200  { return hash(item->p1, item->p2); }
201 
202  inline int hash(const Hashed4<ItemT>* item) const
203  { return hash(item->p1, item->p2, item->p3); }
204 
205  ItemT* SearchList(ItemT* item, int p1, int p2) const;
206  ItemT* SearchList(ItemT* item, int p1, int p2, int p3) const;
207 
208  void Insert(int idx, ItemT* item);
209  void Unlink(ItemT* item);
210 
212  void Rehash();
213 
216 };
217 
218 
219 // implementation
220 
221 template<typename ItemT>
223 {
224  mask = init_size-1;
225  if (init_size & mask)
226  {
227  MFEM_ABORT("HashTable(): init_size size must be a power of two.");
228  }
229 
230  table = new ItemT*[init_size];
231  std::memset(table, 0, init_size * sizeof(ItemT*));
232 
233  num_items = 0;
234 }
235 
236 template<typename ItemT>
238  : mask(other.mask), num_items(0), id_gen(other.id_gen)
239 {
240  int size = mask+1;
241  table = new ItemT*[size];
242  std::memset(table, 0, size * sizeof(ItemT*));
243 
245  id_to_item = NULL;
246 
247  for (Iterator it(other); it; ++it)
248  {
249  ItemT* item = new ItemT(*it);
250  Insert(hash(item), item);
251  id_to_item[item->id] = item;
252  }
253 }
254 
255 template<typename ItemT>
257 {
258  // delete all items
259  for (Iterator it(*this); it; ++it)
260  {
261  delete it;
262  }
263  delete [] table;
264 }
265 
266 namespace internal
267 {
268 
269 inline void sort3(int &a, int &b, int &c)
270 {
271  if (a > b) { std::swap(a, b); }
272  if (a > c) { std::swap(a, c); }
273  if (b > c) { std::swap(b, c); }
274 }
275 
276 inline void sort4(int &a, int &b, int &c, int &d)
277 {
278  if (a > b) { std::swap(a, b); }
279  if (a > c) { std::swap(a, c); }
280  if (a > d) { std::swap(a, d); }
281  sort3(b, c, d);
282 }
283 
284 } // internal
285 
286 template<typename ItemT>
287 ItemT* HashTable<ItemT>::Peek(int p1, int p2) const
288 {
289  if (p1 > p2) { std::swap(p1, p2); }
290  return SearchList(table[hash(p1, p2)], p1, p2);
291 }
292 
293 template<typename ItemT>
294 ItemT* HashTable<ItemT>::Peek(int p1, int p2, int p3, int p4) const
295 {
296  internal::sort4(p1, p2, p3, p4);
297  return SearchList(table[hash(p1, p2, p3)], p1, p2, p3);
298 }
299 
300 template<typename ItemT>
301 void HashTable<ItemT>::Insert(int idx, ItemT* item)
302 {
303  // insert into hashtable
304  item->next = table[idx];
305  table[idx] = item;
306  num_items++;
307 }
308 
309 template<typename ItemT>
310 ItemT* HashTable<ItemT>::Get(int p1, int p2)
311 {
312  // search for the item in the hashtable
313  if (p1 > p2) { std::swap(p1, p2); }
314  int idx = hash(p1, p2);
315  ItemT* node = SearchList(table[idx], p1, p2);
316  if (node) { return node; }
317 
318  // not found - create a new one
319  ItemT* newitem = new ItemT(id_gen.Get());
320  newitem->p1 = p1;
321  newitem->p2 = p2;
322 
323  // insert into hashtable
324  Insert(idx, newitem);
325 
326  // also, maintain the mapping ID -> item
327  if (id_to_item.Size() <= newitem->id)
328  {
329  id_to_item.SetSize(newitem->id + 1, NULL);
330  }
331  id_to_item[newitem->id] = newitem;
332 
333  Rehash();
334  return newitem;
335 }
336 
337 template<typename ItemT>
338 ItemT* HashTable<ItemT>::Get(int p1, int p2, int p3, int p4)
339 {
340  // search for the item in the hashtable
341  internal::sort4(p1, p2, p3, p4);
342  int idx = hash(p1, p2, p3);
343  ItemT* node = SearchList(table[idx], p1, p2, p3);
344  if (node) { return node; }
345 
346  // not found - create a new one
347  ItemT* newitem = new ItemT(id_gen.Get());
348  newitem->p1 = p1;
349  newitem->p2 = p2;
350  newitem->p3 = p3;
351 
352  // insert into hashtable
353  Insert(idx, newitem);
354 
355  // also, maintain the mapping ID -> item
356  if (id_to_item.Size() <= newitem->id)
357  {
358  id_to_item.SetSize(newitem->id + 1, NULL);
359  }
360  id_to_item[newitem->id] = newitem;
361 
362  Rehash();
363  return newitem;
364 }
365 
366 template<typename ItemT>
367 ItemT* HashTable<ItemT>::SearchList(ItemT* item, int p1, int p2) const
368 {
369  while (item != NULL)
370  {
371  if (item->p1 == p1 && item->p2 == p2) { return item; }
372  item = item->next;
373  }
374  return NULL;
375 }
376 
377 template<typename ItemT>
378 ItemT* HashTable<ItemT>::SearchList(ItemT* item, int p1, int p2, int p3) const
379 {
380  while (item != NULL)
381  {
382  if (item->p1 == p1 && item->p2 == p2 && item->p3 == p3) { return item; }
383  item = item->next;
384  }
385  return NULL;
386 }
387 
388 template<typename ItemT>
390 {
391  const int fill_factor = 2;
392  int old_size = mask+1;
393 
394  // is the table overfull?
395  if (num_items > old_size * fill_factor)
396  {
397  delete [] table;
398 
399  // double the table size
400  int new_size = 2*old_size;
401  table = new ItemT*[new_size];
402  memset(table, 0, new_size * sizeof(ItemT*));
403  mask = new_size-1;
404 
405 #ifdef MFEM_DEBUG
406  std::cout << _MFEM_FUNC_NAME << ": rehashing to size " << new_size
407  << std::endl;
408 #endif
409 
410  // reinsert all items
411  num_items = 0;
412  for (Iterator it(*this); it; ++it)
413  {
414  Insert(hash(it), it);
415  }
416  }
417 }
418 
419 template<typename ItemT>
420 void HashTable<ItemT>::Unlink(ItemT* item)
421 {
422  // remove item from the linked list
423  ItemT** ptr = table + hash(item);
424  while (*ptr)
425  {
426  if (*ptr == item)
427  {
428  *ptr = item->next;
429  num_items--;
430  return;
431  }
432  ptr = &((*ptr)->next);
433  }
434  MFEM_ABORT("HashTable<>::Unlink: item not found!");
435 }
436 
437 template<typename ItemT>
438 void HashTable<ItemT>::Delete(ItemT* item)
439 {
440  // remove item from the hash table
441  Unlink(item);
442 
443  // remove from the (ID -> item) map
444  id_to_item[item->id] = NULL;
445 
446  // reuse the ID in the future
447  id_gen.Reuse(item->id);
448 
449  delete item;
450 }
451 
452 template<typename ItemT>
453 void HashTable<ItemT>::Reparent(ItemT* item, int new_p1, int new_p2)
454 {
455  Unlink(item);
456 
457  if (new_p1 > new_p2) { std::swap(new_p1, new_p2); }
458  item->p1 = new_p1;
459  item->p2 = new_p2;
460 
461  // reinsert under new parent IDs
462  int new_idx = hash(new_p1, new_p2);
463  Insert(new_idx, item);
464 }
465 
466 template<typename ItemT>
467 void HashTable<ItemT>::Reparent(ItemT* item,
468  int new_p1, int new_p2, int new_p3, int new_p4)
469 {
470  Unlink(item);
471 
472  internal::sort4(new_p1, new_p2, new_p3, new_p4);
473  item->p1 = new_p1;
474  item->p2 = new_p2;
475  item->p3 = new_p3;
476 
477  // reinsert under new parent IDs
478  int new_idx = hash(new_p1, new_p2, new_p3);
479  Insert(new_idx, item);
480 }
481 
482 template<typename ItemT>
484 {
485  while (cur_id < hash_table.id_to_item.Size()-1)
486  {
487  ++cur_id;
488  cur_item = hash_table.id_to_item[cur_id];
489  if (cur_item) { return; }
490  }
491 
492  // no more items
493  cur_item = NULL;
494 }
495 
496 template<typename ItemT>
498 {
499  return ((mask+1) + id_to_item.Capacity()) * sizeof(ItemT*) +
500  num_items * sizeof(ItemT);
501 }
502 
503 template<typename ItemT>
505 {
506  std::cout << ((mask+1) + id_to_item.Capacity()) * sizeof(ItemT*) << "+"
507  << num_items * sizeof(ItemT);
508 }
509 
510 } // namespace mfem
511 
512 #endif
int Size() const
Logical size of the array.
Definition: array.hpp:109
Iterator(const HashTable< ItemT > &table)
Definition: hash.hpp:163
HashTable(int init_size=32 *1024)
Definition: hash.hpp:222
Iterator over items contained in the HashTable.
Definition: hash.hpp:160
long MemoryUsage() const
Return total size of allocated memory (tables plus items), in bytes.
Definition: hash.hpp:497
void Reparent(ItemT *item, int new_p1, int new_p2)
Make an item hashed under different parent IDs.
Definition: hash.hpp:453
ItemT ** table
Definition: hash.hpp:187
int hash(const Hashed2< ItemT > *item) const
Definition: hash.hpp:199
void Copy(Array &copy) const
Create a copy of the current array.
Definition: array.hpp:160
ItemT & operator*() const
Definition: hash.hpp:167
void Rehash()
Check table load and resize if necessary.
Definition: hash.hpp:389
int hash(int p1, int p2) const
Definition: hash.hpp:192
void Delete(ItemT *item)
Remove an item from the hash table and also delete the item itself.
Definition: hash.hpp:438
IdGenerator(const IdGenerator &other)
Definition: hash.hpp:30
const HashTable< ItemT > & hash_table
Definition: hash.hpp:173
ItemT * Get(OtherT *i1, OtherT *i2)
Definition: hash.hpp:134
ItemT * Get(int p1, int p2)
Get an item whose parents are p1, p2... Create it if it doesn&#39;t exist.
Definition: hash.hpp:310
ItemT * Peek(int id) const
Obtains an item given its ID.
Definition: hash.hpp:150
int Append(const T &el)
Append element to array, resize if necessary.
Definition: array.hpp:376
ItemT * SearchList(ItemT *item, int p1, int p2) const
Definition: hash.hpp:367
ItemT * Peek(OtherT *i1, OtherT *i2, OtherT *i3, OtherT *i4) const
Definition: hash.hpp:146
Iterator & operator++()
Definition: hash.hpp:170
Derived * next
Definition: hash.hpp:82
int hash(const Hashed4< ItemT > *item) const
Definition: hash.hpp:202
Array< ItemT * > id_to_item
mapping table for the Peek(id) method
Definition: hash.hpp:215
ItemT * Peek(int p1, int p2) const
Get an item whose parents are p1, p2... Return NULL if it doesn&#39;t exist.
Definition: hash.hpp:287
void SetSize(int nsize)
Change logical size of the array, keep existing entries.
Definition: array.hpp:331
void DeleteLast()
Delete the last entry.
Definition: array.hpp:151
void Reuse(int id)
Return an ID previously generated by &#39;Get&#39;.
Definition: hash.hpp:46
Derived * next
Definition: hash.hpp:68
void Insert(int idx, ItemT *item)
Definition: hash.hpp:301
IdGenerator(int first_id=0)
Definition: hash.hpp:28
Hashed4(int id)
Definition: hash.hpp:85
int Capacity() const
Definition: array.hpp:119
void Unlink(ItemT *item)
Definition: hash.hpp:420
T & Last()
Return the last element in the array.
Definition: array.hpp:411
Hashed2(int id)
Definition: hash.hpp:71
ItemT * Peek(OtherT *i1, OtherT *i2) const
Definition: hash.hpp:142
ItemT * operator->() const
Definition: hash.hpp:168
void PrintMemoryDetail() const
Definition: hash.hpp:504
ItemT * Get(OtherT *i1, OtherT *i2, OtherT *i3, OtherT *i4)
Definition: hash.hpp:138
int Get()
Generate a unique ID.
Definition: hash.hpp:34
IdGenerator id_gen
id generator for new items
Definition: hash.hpp:214
int hash(int p1, int p2, int p3) const
Definition: hash.hpp:195