MFEM  v4.0
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 #include "globals.hpp"
18 
19 namespace mfem
20 {
21 
22 /** A concept for items that should be used in HashTable and be accessible by
23  * hashing two IDs.
24  */
25 struct Hashed2
26 {
27  int p1, p2;
28  int next;
29 };
30 
31 /** A concept for items that should be used in HashTable and be accessible by
32  * hashing four IDs.
33  */
34 struct Hashed4
35 {
36  int p1, p2, p3; // NOTE: p4 is neither hashed nor stored
37  int next;
38 };
39 
40 
41 /** HashTable is a container for items that require associative access through
42  * pairs (or quadruples) of indices:
43  *
44  * (p1, p2) -> item
45  * (p1, p2, p3, p4) -> item
46  *
47  * An example of this are edges and faces in a mesh. Each edge is uniquely
48  * identified by two parent vertices and so can be easily accessed from
49  * different elements using this class. Similarly for faces.
50  *
51  * The order of the p1, p2, ... indices is not relevant as they are sorted
52  * each time this class is invoked.
53  *
54  * There are two main methods this class provides. The Get(...) methods always
55  * return an item given the two or four indices. If the item didn't previously
56  * exist, the methods creates a new one. The Find(...) methods, on the other
57  * hand, just return NULL or -1 if the item doesn't exist.
58  *
59  * Each new item is automatically assigned a unique ID - the index of the item
60  * inside the BlockArray. The IDs may (but need not) be used as p1, p2, ... of
61  * other items.
62  *
63  * The item type (T) needs to follow either the Hashed2 or the Hashed4
64  * concept. It is easiest to just inherit from these structs.
65  *
66  * All items in the container can also be accessed sequentially using the
67  * provided iterator.
68  */
69 template<typename T>
70 class HashTable : public BlockArray<T>
71 {
72 protected:
74 
75 public:
76  HashTable(int block_size = 16*1024, int init_hash_size = 32*1024);
77  HashTable(const HashTable& other); // deep copy
78  ~HashTable();
79 
80  /// Get item whose parents are p1, p2... Create it if it doesn't exist.
81  T* Get(int p1, int p2);
82  T* Get(int p1, int p2, int p3, int p4);
83 
84  /// Get id of item whose parents are p1, p2... Create it if it doesn't exist.
85  int GetId(int p1, int p2);
86  int GetId(int p1, int p2, int p3, int p4);
87 
88  /// Find item whose parents are p1, p2... Return NULL if it doesn't exist.
89  T* Find(int p1, int p2);
90  T* Find(int p1, int p2, int p3, int p4);
91 
92  const T* Find(int p1, int p2) const;
93  const T* Find(int p1, int p2, int p3, int p4) const;
94 
95  /// Find id of item whose parents are p1, p2... Return -1 if it doesn't exist.
96  int FindId(int p1, int p2) const;
97  int FindId(int p1, int p2, int p3, int p4) const;
98 
99  /// Return the number of elements currently stored in the HashTable.
100  int Size() const { return Base::Size() - unused.Size(); }
101 
102  /// Return the total number of ids (used and unused) in the HashTable.
103  int NumIds() const { return Base::Size(); }
104 
105  /// Return the number of free/unused ids in the HashTable.
106  int NumFreeIds() const { return unused.Size(); }
107 
108  /// Return true if item 'id' exists in (is used by) the container.
109  /** It is assumed that 0 <= id < NumIds(). */
110  bool IdExists(int id) const { return (Base::At(id).next != -2); }
111 
112  /// Remove an item from the hash table.
113  /** Its id will be reused by newly added items. */
114  void Delete(int id);
115 
116  /// Make an item hashed under different parent IDs.
117  void Reparent(int id, int new_p1, int new_p2);
118  void Reparent(int id, int new_p1, int new_p2, int new_p3, int new_p4);
119 
120  /// Return total size of allocated memory (tables plus items), in bytes.
121  long MemoryUsage() const;
122 
123  void PrintMemoryDetail() const;
124 
125  class iterator : public Base::iterator
126  {
127  protected:
128  friend class HashTable;
129  typedef typename Base::iterator base;
130 
131  iterator() { }
132  iterator(const base &it) : base(it)
133  {
134  while (base::good() && (*this)->next == -2) { base::next(); }
135  }
136 
137  public:
139  {
140  while (base::next(), base::good() && (*this)->next == -2) { }
141  return *this;
142  }
143  };
144 
146  {
147  protected:
148  friend class HashTable;
149  typedef typename Base::const_iterator base;
150 
152  const_iterator(const base &it) : base(it)
153  {
154  while (base::good() && (*this)->next == -2) { base::next(); }
155  }
156 
157  public:
159  {
160  while (base::next(), base::good() && (*this)->next == -2) { }
161  return *this;
162  }
163  };
164 
165  iterator begin() { return iterator(Base::begin()); }
166  iterator end() { return iterator(); }
167 
168  const_iterator cbegin() const { return const_iterator(Base::cbegin()); }
169  const_iterator cend() const { return const_iterator(); }
170 
171 protected:
172  int* table;
173  int mask;
175 
176  // hash functions (NOTE: the constants are arbitrary)
177  inline int Hash(int p1, int p2) const
178  { return (984120265*p1 + 125965121*p2) & mask; }
179 
180  inline int Hash(int p1, int p2, int p3) const
181  { return (984120265*p1 + 125965121*p2 + 495698413*p3) & mask; }
182 
183  // Delete() and Reparent() use one of these:
184  inline int Hash(const Hashed2& item) const
185  { return Hash(item.p1, item.p2); }
186 
187  inline int Hash(const Hashed4& item) const
188  { return Hash(item.p1, item.p2, item.p3); }
189 
190  int SearchList(int id, int p1, int p2) const;
191  int SearchList(int id, int p1, int p2, int p3) const;
192 
193  inline void Insert(int idx, int id, T &item);
194  void Unlink(int idx, int id);
195 
196  /// Check table load factor and resize if necessary
197  inline void CheckRehash();
198  void DoRehash();
199 };
200 
201 
202 // implementation
203 
204 template<typename T>
205 HashTable<T>::HashTable(int block_size, int init_hash_size)
206  : Base(block_size)
207 {
208  mask = init_hash_size-1;
209  MFEM_VERIFY(!(init_hash_size & mask), "init_size must be a power of two.");
210 
211  table = new int[init_hash_size];
212  for (int i = 0; i < init_hash_size; i++) { table[i] = -1; }
213 }
214 
215 template<typename T>
217  : Base(other), mask(other.mask)
218 {
219  int size = mask+1;
220  table = new int[size];
221  memcpy(table, other.table, size*sizeof(int));
222  other.unused.Copy(unused);
223 }
224 
225 template<typename T>
227 {
228  delete [] table;
229 }
230 
231 namespace internal
232 {
233 
234 inline void sort3(int &a, int &b, int &c)
235 {
236  if (a > b) { std::swap(a, b); }
237  if (a > c) { std::swap(a, c); }
238  if (b > c) { std::swap(b, c); }
239 }
240 
241 inline void sort4(int &a, int &b, int &c, int &d)
242 {
243  if (a > b) { std::swap(a, b); }
244  if (a > c) { std::swap(a, c); }
245  if (a > d) { std::swap(a, d); }
246  sort3(b, c, d);
247 }
248 
249 } // internal
250 
251 template<typename T>
252 inline T* HashTable<T>::Get(int p1, int p2)
253 {
254  return &(Base::At(GetId(p1, p2)));
255 }
256 
257 template<typename T>
258 inline T* HashTable<T>::Get(int p1, int p2, int p3, int p4)
259 {
260  return &(Base::At(GetId(p1, p2, p3, p4)));
261 }
262 
263 template<typename T>
264 int HashTable<T>::GetId(int p1, int p2)
265 {
266  // search for the item in the hashtable
267  if (p1 > p2) { std::swap(p1, p2); }
268  int idx = Hash(p1, p2);
269  int id = SearchList(table[idx], p1, p2);
270  if (id >= 0) { return id; }
271 
272  // not found - use an unused item or create a new one
273  int new_id;
274  if (unused.Size())
275  {
276  new_id = unused.Last();
277  unused.DeleteLast();
278  }
279  else
280  {
281  new_id = Base::Append();
282  }
283  T& item = Base::At(new_id);
284  item.p1 = p1;
285  item.p2 = p2;
286 
287  // insert into hashtable
288  Insert(idx, new_id, item);
289  CheckRehash();
290 
291  return new_id;
292 }
293 
294 template<typename T>
295 int HashTable<T>::GetId(int p1, int p2, int p3, int p4)
296 {
297  // search for the item in the hashtable
298  internal::sort4(p1, p2, p3, p4);
299  int idx = Hash(p1, p2, p3);
300  int id = SearchList(table[idx], p1, p2, p3);
301  if (id >= 0) { return id; }
302 
303  // not found - use an unused item or create a new one
304  int new_id;
305  if (unused.Size())
306  {
307  new_id = unused.Last();
308  unused.DeleteLast();
309  }
310  else
311  {
312  new_id = Base::Append();
313  }
314  T& item = Base::At(new_id);
315  item.p1 = p1;
316  item.p2 = p2;
317  item.p3 = p3;
318 
319  // insert into hashtable
320  Insert(idx, new_id, item);
321  CheckRehash();
322 
323  return new_id;
324 }
325 
326 template<typename T>
327 inline T* HashTable<T>::Find(int p1, int p2)
328 {
329  int id = FindId(p1, p2);
330  return (id >= 0) ? &(Base::At(id)) : NULL;
331 }
332 
333 template<typename T>
334 inline T* HashTable<T>::Find(int p1, int p2, int p3, int p4)
335 {
336  int id = FindId(p1, p2, p3, p4);
337  return (id >= 0) ? &(Base::At(id)) : NULL;
338 }
339 
340 template<typename T>
341 inline const T* HashTable<T>::Find(int p1, int p2) const
342 {
343  int id = FindId(p1, p2);
344  return (id >= 0) ? &(Base::At(id)) : NULL;
345 }
346 
347 template<typename T>
348 inline const T* HashTable<T>::Find(int p1, int p2, int p3, int p4) const
349 {
350  int id = FindId(p1, p2, p3, p4);
351  return (id >= 0) ? &(Base::At(id)) : NULL;
352 }
353 
354 template<typename T>
355 int HashTable<T>::FindId(int p1, int p2) const
356 {
357  if (p1 > p2) { std::swap(p1, p2); }
358  return SearchList(table[Hash(p1, p2)], p1, p2);
359 }
360 
361 template<typename T>
362 int HashTable<T>::FindId(int p1, int p2, int p3, int p4) const
363 {
364  internal::sort4(p1, p2, p3, p4);
365  return SearchList(table[Hash(p1, p2, p3)], p1, p2, p3);
366 }
367 
368 template<typename T>
369 int HashTable<T>::SearchList(int id, int p1, int p2) const
370 {
371  while (id >= 0)
372  {
373  const T& item = Base::At(id);
374  if (item.p1 == p1 && item.p2 == p2) { return id; }
375  id = item.next;
376  }
377  return -1;
378 }
379 
380 template<typename T>
381 int HashTable<T>::SearchList(int id, int p1, int p2, int p3) const
382 {
383  while (id >= 0)
384  {
385  const T& item = Base::At(id);
386  if (item.p1 == p1 && item.p2 == p2 && item.p3 == p3) { return id; }
387  id = item.next;
388  }
389  return -1;
390 }
391 
392 template<typename T>
394 {
395  const int fill_factor = 2;
396 
397  // is the table overfull?
398  if (Base::Size() > (mask+1) * fill_factor)
399  {
400  DoRehash();
401  }
402 }
403 
404 template<typename T>
406 {
407  delete [] table;
408 
409  // double the table size
410  int new_table_size = 2*(mask+1);
411  table = new int[new_table_size];
412  for (int i = 0; i < new_table_size; i++) { table[i] = -1; }
413  mask = new_table_size-1;
414 
415 #if defined(MFEM_DEBUG) && !defined(MFEM_USE_MPI)
416  mfem::out << _MFEM_FUNC_NAME << ": rehashing to size " << new_table_size
417  << std::endl;
418 #endif
419 
420  // reinsert all items
421  for (iterator it = begin(); it != end(); ++it)
422  {
423  Insert(Hash(*it), it.index(), *it);
424  }
425 }
426 
427 template<typename T>
428 inline void HashTable<T>::Insert(int idx, int id, T &item)
429 {
430  // add item at the beginning of the linked list
431  item.next = table[idx];
432  table[idx] = id;
433 }
434 
435 template<typename T>
436 void HashTable<T>::Unlink(int idx, int id)
437 {
438  // remove item from the linked list
439  int* p_id = table + idx;
440  while (*p_id >= 0)
441  {
442  T& item = Base::At(*p_id);
443  if (*p_id == id)
444  {
445  *p_id = item.next;
446  return;
447  }
448  p_id = &(item.next);
449  }
450  MFEM_ABORT("HashTable<>::Unlink: item not found!");
451 }
452 
453 template<typename T>
455 {
456  T& item = Base::At(id);
457  Unlink(Hash(item), id);
458  item.next = -2; // mark item as unused
459  unused.Append(id); // add its id to the unused ids
460 }
461 
462 template<typename T>
463 void HashTable<T>::Reparent(int id, int new_p1, int new_p2)
464 {
465  T& item = Base::At(id);
466  Unlink(Hash(item), id);
467 
468  if (new_p1 > new_p2) { std::swap(new_p1, new_p2); }
469  item.p1 = new_p1;
470  item.p2 = new_p2;
471 
472  // reinsert under new parent IDs
473  int new_idx = Hash(new_p1, new_p2);
474  Insert(new_idx, id, item);
475 }
476 
477 template<typename T>
479  int new_p1, int new_p2, int new_p3, int new_p4)
480 {
481  T& item = Base::At(id);
482  Unlink(Hash(item), id);
483 
484  internal::sort4(new_p1, new_p2, new_p3, new_p4);
485  item.p1 = new_p1;
486  item.p2 = new_p2;
487  item.p3 = new_p3;
488 
489  // reinsert under new parent IDs
490  int new_idx = Hash(new_p1, new_p2, new_p3);
491  Insert(new_idx, id, item);
492 }
493 
494 template<typename T>
496 {
497  return (mask+1) * sizeof(int) + Base::MemoryUsage() + unused.MemoryUsage();
498 }
499 
500 template<typename T>
502 {
503  mfem::out << Base::MemoryUsage() << " + " << (mask+1) * sizeof(int)
504  << " + " << unused.MemoryUsage();
505 }
506 
507 } // namespace mfem
508 
509 #endif
Array< int > unused
Definition: hash.hpp:174
int Size() const
Logical size of the array.
Definition: array.hpp:118
int Hash(int p1, int p2, int p3) const
Definition: hash.hpp:180
int Hash(const Hashed4 &item) const
Definition: hash.hpp:187
const_iterator cbegin() const
Definition: array.hpp:546
void Unlink(int idx, int id)
Definition: hash.hpp:436
void Delete(int id)
Remove an item from the hash table.
Definition: hash.hpp:454
bool IdExists(int id) const
Return true if item &#39;id&#39; exists in (is used by) the container.
Definition: hash.hpp:110
HashTable(int block_size=16 *1024, int init_hash_size=32 *1024)
Definition: hash.hpp:205
int Size() const
Return the number of items actually stored.
Definition: array.hpp:452
int SearchList(int id, int p1, int p2) const
Definition: hash.hpp:369
void Copy(Array &copy) const
Create a copy of the current array.
Definition: array.hpp:795
iterator & operator++()
Definition: hash.hpp:138
T * Get(int p1, int p2)
Get item whose parents are p1, p2... Create it if it doesn&#39;t exist.
Definition: hash.hpp:252
const_iterator(const base &it)
Definition: hash.hpp:152
void PrintMemoryDetail() const
Definition: hash.hpp:501
int Hash(int p1, int p2) const
Definition: hash.hpp:177
int Size() const
Return the number of elements currently stored in the HashTable.
Definition: hash.hpp:100
void CheckRehash()
Check table load factor and resize if necessary.
Definition: hash.hpp:393
iterator begin()
Definition: array.hpp:543
const_iterator & operator++()
Definition: hash.hpp:158
void Reparent(int id, int new_p1, int new_p2)
Make an item hashed under different parent IDs.
Definition: hash.hpp:463
T * Find(int p1, int p2)
Find item whose parents are p1, p2... Return NULL if it doesn&#39;t exist.
Definition: hash.hpp:327
iterator(const base &it)
Definition: hash.hpp:132
iterator end()
Definition: hash.hpp:166
int * table
Definition: hash.hpp:172
int NumIds() const
Return the total number of ids (used and unused) in the HashTable.
Definition: hash.hpp:103
int Hash(const Hashed2 &item) const
Definition: hash.hpp:184
BlockArray< T > Base
Definition: hash.hpp:73
int NumFreeIds() const
Return the number of free/unused ids in the HashTable.
Definition: hash.hpp:106
int next
Definition: hash.hpp:37
iterator begin()
Definition: hash.hpp:165
long MemoryUsage() const
Return total size of allocated memory (tables plus items), in bytes.
Definition: hash.hpp:495
const_iterator cbegin() const
Definition: hash.hpp:168
int GetId(int p1, int p2)
Get id of item whose parents are p1, p2... Create it if it doesn&#39;t exist.
Definition: hash.hpp:264
Base::iterator base
Definition: hash.hpp:129
Base::const_iterator base
Definition: hash.hpp:149
OutStream out(std::cout)
Global stream used by the library for standard output. Initially it uses the same std::streambuf as s...
Definition: globals.hpp:64
int FindId(int p1, int p2) const
Find id of item whose parents are p1, p2... Return -1 if it doesn&#39;t exist.
Definition: hash.hpp:355
T & At(int index)
Access item of the array.
Definition: array.hpp:436
int next
Definition: hash.hpp:28
void DoRehash()
Definition: hash.hpp:405
void Insert(int idx, int id, T &item)
Definition: hash.hpp:428
const_iterator cend() const
Definition: hash.hpp:169