Line data    Source code

       1             : // Author(s): Bas Ploeger
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : /// \file sim_hashtable.h
      10             : /// \brief Header file for hash table data structure used by the
      11             : /// simulation preorder algorithm.
      12             : 
      13             : /* This class implements a hash table for storing triples of unsigned
      14             :  * integers. Triples can be added, removed and checked for presence.
      15             :  * Note however that removing a triple does not free space and re-adding
      16             :  * a removed triple does not reuse the previously removed entry but
      17             :  * creates new entry.
      18             :  * Hence, although this does not lead to incorrect results, this hash
      19             :  * table implementation is intended for applications in which removed
      20             :  * triples will never (or rarely) be added again. */
      21             : 
      22             : #ifndef SIM_HASHTABLE_H
      23             : #define SIM_HASHTABLE_H
      24             : #include <cstddef>
      25             : #include <vector>
      26             : 
      27             : struct bucket2
      28             : {
      29             :   std::size_t x,y;
      30             :   std::size_t next;
      31             : };
      32             : 
      33             : struct bucket3
      34             : {
      35             :   std::size_t x,y,z;
      36             :   std::size_t next;
      37             : };
      38             : 
      39             : class hash_table2
      40             : {
      41             :   public:
      42             :     hash_table2(std::size_t initsize);
      43             :     ~hash_table2();
      44             :     void clear();
      45             :     void add(std::size_t x,std::size_t y);
      46             :     bool find(std::size_t x,std::size_t y);
      47             :     void remove(std::size_t x,std::size_t y);
      48             : 
      49             :   private:
      50             :     std::vector<bucket2> buckets;
      51             :     std::vector<std::size_t> table;
      52             :     std::size_t mask;
      53             :     std::size_t removed_count;
      54             :     std::size_t hash(std::size_t x,std::size_t y);
      55             :     std::size_t hfind(std::size_t h,std::size_t x,std::size_t y);
      56             :     bool check_table();
      57             : 
      58             :     friend class hash_table2_iterator;
      59             : };
      60             : 
      61             : class hash_table2_iterator
      62             : {
      63             :   public:
      64             :     hash_table2_iterator(hash_table2* ht);
      65           0 :     bool is_end()
      66             :     {
      67           0 :       return (bucket_it == hash_table->buckets.end());
      68             :     }
      69             :     void operator ++();
      70           0 :     std::size_t get_x()
      71             :     {
      72           0 :       return bucket_it->x;
      73             :     }
      74           0 :     std::size_t get_y()
      75             :     {
      76           0 :       return bucket_it->y;
      77             :     }
      78             :   private:
      79             :     std::vector<bucket2>::iterator bucket_it;
      80             :     hash_table2* hash_table;
      81             : };
      82             : 
      83             : 
      84             : class hash_table3
      85             : {
      86             :   public:
      87             :     hash_table3(std::size_t initsize);
      88             :     ~hash_table3();
      89             :     void clear();
      90             :     void add(std::size_t x,std::size_t y,std::size_t z);
      91             :     bool find(std::size_t x,std::size_t y,std::size_t z);
      92             :     void remove(std::size_t x,std::size_t y,std::size_t z);
      93       10565 :     std::size_t get_num_elements()
      94             :     {
      95       10565 :       return buckets.size() - removed_count;
      96             :     }
      97             : 
      98             :   private:
      99             :     std::vector<bucket3> buckets;
     100             :     std::vector<std::size_t> table;
     101             :     std::size_t mask;
     102             :     std::size_t removed_count;
     103             :     std::size_t hash(std::size_t x,std::size_t y,std::size_t z);
     104             :     std::size_t hfind(std::size_t h,std::size_t x,std::size_t y,std::size_t z);
     105             :     bool check_table();
     106             : 
     107             :     friend class hash_table3_iterator;
     108             : };
     109             : 
     110             : class hash_table3_iterator
     111             : {
     112             :   public:
     113             :     hash_table3_iterator(hash_table3* ht);
     114       12642 :     bool is_end()
     115             :     {
     116       12642 :       return (bucket_it == end);
     117             :     }
     118             :     void operator ++();
     119        3057 :     std::size_t get_x()
     120             :     {
     121        3057 :       return bucket_it->x;
     122             :     }
     123           0 :     std::size_t get_y()
     124             :     {
     125           0 :       return bucket_it->y;
     126             :     }
     127           0 :     std::size_t get_z()
     128             :     {
     129           0 :       return bucket_it->z;
     130             :     }
     131        9585 :     void set(std::size_t i)
     132             :     {
     133        9585 :       bucket_it = hash_table->buckets.begin() + i;
     134        9585 :     }
     135        9732 :     void set_end(std::size_t i)
     136             :     {
     137        9732 :       end = hash_table->buckets.begin() + i;
     138        9732 :     }
     139             :   private:
     140             :     std::vector<bucket3>::iterator bucket_it;
     141             :     std::vector<bucket3>::iterator end;
     142             :     hash_table3* hash_table;
     143             : };
     144             : 
     145             : #endif