Line data    Source code

       1              : /*
       2              :  * Copyright (c) 2009-2015:  G-CSC, Goethe University Frankfurt
       3              :  * Author: Sebastian Reiter
       4              :  * 
       5              :  * This file is part of UG4.
       6              :  * 
       7              :  * UG4 is free software: you can redistribute it and/or modify it under the
       8              :  * terms of the GNU Lesser General Public License version 3 (as published by the
       9              :  * Free Software Foundation) with the following additional attribution
      10              :  * requirements (according to LGPL/GPL v3 §7):
      11              :  * 
      12              :  * (1) The following notice must be displayed in the Appropriate Legal Notices
      13              :  * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
      14              :  * 
      15              :  * (2) The following notice must be displayed at a prominent place in the
      16              :  * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
      17              :  * 
      18              :  * (3) The following bibliography is recommended for citation and must be
      19              :  * preserved in all covered files:
      20              :  * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
      21              :  *   parallel geometric multigrid solver on hierarchically distributed grids.
      22              :  *   Computing and visualization in science 16, 4 (2013), 151-164"
      23              :  * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
      24              :  *   flexible software system for simulating pde based models on high performance
      25              :  *   computers. Computing and visualization in science 16, 4 (2013), 165-179"
      26              :  * 
      27              :  * This program is distributed in the hope that it will be useful,
      28              :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      29              :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
      30              :  * GNU Lesser General Public License for more details.
      31              :  */
      32              : 
      33              : #ifndef __H__UG__hash__
      34              : #define __H__UG__hash__
      35              : 
      36              : #include <vector>
      37              : #include <utility>
      38              : #include "hash_iterator.h"
      39              : #include "hash_function.h"
      40              : 
      41              : namespace ug{
      42              : 
      43              : ///     An associative container for key-value pairs, which provides fast access using hash-keys
      44              : /**     \addtogroup ugbase_common_util
      45              :  */
      46              : template <class TKey, class TValue>
      47            4 : class Hash
      48              : {
      49              :         private:
      50              :                 struct Entry;
      51              : 
      52              :         public:
      53              :                 typedef TKey    key_t;
      54              :                 typedef TValue  value_t;
      55              :                 typedef hash_iterator<key_t, value_t, Entry>              iterator;
      56              : //              typedef const_hash_iterator<key_t, value_t, Entry>        const_iterator;
      57              : 
      58              :                 Hash();
      59              :                 Hash(size_t hashSize);
      60              : 
      61              :                 void resize_hash(size_t size);
      62              :                 size_t hash_size() const;
      63              : 
      64              : //              void enable_auto_hash_resize(float maxElemToHashSizeRatio,
      65              : //                                                                       float bestElemToHashSizeRatio);
      66              : //
      67              : //              void disable_auto_hash_resize();
      68              : 
      69              : 
      70              :         ///     Reserves memory for key-value-pair storage.
      71              :         /** \sa capacity*/
      72              :                 void reserve(size_t size);
      73              : 
      74              :         ///     returns the capacity of the container in which key-value-pairs are stored.
      75              :         /**     Use reserve to adjust this capacity. If the capacity would be too small
      76              :          * to insert a new element, it will be automatically increased on element insertion.
      77              :          * \sa reserve*/
      78              :                 size_t capacity() const;
      79              : 
      80              :         ///     returns the number of key-value-pairs currently stored in the hash
      81              :                 size_t size() const;
      82              : 
      83              :                 void clear();
      84              : 
      85              :                 bool empty() const;
      86              :                 bool has_entry(const key_t& key) const;
      87              : 
      88              :                 value_t& get_entry(const key_t& key);
      89              :                 const value_t& get_entry(const key_t& key) const;
      90              :                 bool get_entry(value_t& valOut, const key_t& key) const;
      91              : 
      92              :                 void insert(const key_t& key, const value_t& val);
      93              :                 void erase(const key_t& key);
      94              : 
      95              :                 iterator begin(const key_t& key);
      96              :                 iterator end(const key_t& key);
      97              : 
      98              : //              const_iterator begin(const key_t& key) const;
      99              : //              const_iterator end(const key_t& key) const;
     100              : 
     101              :         private:
     102              :                 size_t hash_index(const key_t& key) const;
     103              :                 size_t find_entry(const key_t& key) const;
     104              :                 inline size_t invalid_index() const     {return -1;}
     105              : 
     106            0 :                 struct Entry{
     107              :                         key_t   key;
     108              :                         value_t value;
     109              :                         size_t  next;
     110              : 
     111              :                         Entry() {}
     112            8 :                         Entry(const key_t& k, const value_t& v) :
     113           11 :                                 key(k), value(v), next(-1)
     114              :                         {}
     115              :                 };
     116              : 
     117              :                 std::vector<Entry>        m_entries;
     118              :                 size_t                          m_numEntries;
     119              :                 size_t                          m_firstUnusedEntry;
     120              : 
     121              :         /**     each entry holds a pair of indices pointing to the first and the
     122              :          * last entry for the given hash-key.*/
     123              :                 std::vector<std::pair<size_t, size_t> >     m_hashList;
     124              : 
     125              : };
     126              : 
     127              : }// end of namespace
     128              : 
     129              : 
     130              : #include "hash_impl.hpp"
     131              : 
     132              : #endif