LCOV - code coverage report
Current view: top level - lts/source - sim_hashtable.cpp (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 108 166 65.1 %
Date: 2019-09-14 00:54:39 Functions: 19 22 86.4 %
Legend: Lines: hit not hit

          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.cpp
      10             : #include "mcrl2/lts/detail/sim_hashtable.h"
      11             : 
      12             : #define NOT_FOUND   (std::size_t)(-1)
      13             : #define END_OF_LIST (std::size_t)(-1)
      14             : #define REMOVED     (std::size_t)(-2)
      15             : 
      16             : /* ---------------- hash_table_iterator ----------------------------- */
      17             : 
      18           0 : hash_table2_iterator::hash_table2_iterator(hash_table2* ht)
      19           0 :   : hash_table(ht)
      20             : {
      21           0 :   bucket_it = hash_table->buckets.begin();
      22           0 :   while (bucket_it != hash_table->buckets.end()
      23           0 :          && (bucket_it->next == REMOVED))
      24             :   {
      25           0 :     ++bucket_it;
      26             :   }
      27           0 : }
      28             : 
      29           0 : void hash_table2_iterator::operator ++()
      30             : {
      31           0 :   if (bucket_it != hash_table->buckets.end())
      32             :   {
      33           0 :     ++bucket_it;
      34           0 :     while (bucket_it != hash_table->buckets.end()
      35           0 :            && (bucket_it->next == REMOVED))
      36             :     {
      37           0 :       ++bucket_it;
      38             :     }
      39             :   }
      40           0 : }
      41             : 
      42         430 : hash_table3_iterator::hash_table3_iterator(hash_table3* ht)
      43         430 :   : hash_table(ht)
      44             : {
      45         430 :   bucket_it = hash_table->buckets.begin();
      46         430 :   end = hash_table->buckets.end();
      47         430 :   while (bucket_it != end && bucket_it->next == REMOVED)
      48             :   {
      49           0 :     ++bucket_it;
      50             :   }
      51         430 : }
      52             : 
      53        3057 : void hash_table3_iterator::operator ++()
      54             : {
      55        3057 :   if (bucket_it != end)
      56             :   {
      57        3057 :     ++bucket_it;
      58        3057 :     while (bucket_it != end && bucket_it->next == REMOVED)
      59             :     {
      60           0 :       ++bucket_it;
      61             :     }
      62             :   }
      63        3057 : }
      64             : 
      65             : /* ---------------- hash_table -------------------------------------- */
      66             : 
      67          32 : hash_table2::hash_table2(std::size_t initsize)
      68             : {
      69          32 :   mask = 1;
      70         672 :   while (mask < initsize)
      71             :   {
      72         320 :     mask = mask << 1;
      73             :   }
      74          32 :   --mask;
      75          32 :   clear();
      76          32 : }
      77             : 
      78          32 : hash_table2::~hash_table2()
      79          32 : {}
      80             : 
      81          64 : void hash_table2::clear()
      82             : {
      83          64 :   table.assign(mask+1,END_OF_LIST);
      84          64 :   buckets.clear();
      85          64 :   removed_count = 0;
      86          64 : }
      87             : 
      88         148 : void hash_table2::add(std::size_t x,std::size_t y)
      89             : {
      90         148 :   std::size_t h = hash(x,y);
      91         148 :   if (hfind(h,x,y) == NOT_FOUND)
      92             :   {
      93         148 :     if (check_table())
      94             :     {
      95           0 :       h = hash(x,y);
      96             :     }
      97             :     bucket2 new_bucket;
      98         148 :     new_bucket.x = x;
      99         148 :     new_bucket.y = y;
     100         148 :     new_bucket.next = table[h];
     101         148 :     table[h] = buckets.size();
     102         148 :     buckets.push_back(new_bucket);
     103             :   }
     104         148 : }
     105             : 
     106         597 : bool hash_table2::find(std::size_t x,std::size_t y)
     107             : {
     108         597 :   return (hfind(hash(x,y),x,y) != NOT_FOUND);
     109             : }
     110             : 
     111           0 : void hash_table2::remove(std::size_t x,std::size_t y)
     112             : {
     113             :   bucket2 b;
     114             :   std::size_t i, prev_i;
     115           0 :   std::size_t h = hash(x,y);
     116           0 :   i = table[h];
     117           0 :   if (i != END_OF_LIST)
     118             :   {
     119           0 :     b = buckets[i];
     120           0 :     if (b.x == x && b.y == y)
     121             :     {
     122           0 :       table[h] = b.next;
     123           0 :       buckets[i].next = REMOVED;
     124           0 :       ++removed_count;
     125           0 :       return;
     126             :     }
     127           0 :     prev_i = i;
     128           0 :     i = b.next;
     129             :   }
     130           0 :   while (i != END_OF_LIST)
     131             :   {
     132           0 :     b = buckets[i];
     133           0 :     if (b.x == x && b.y == y)
     134             :     {
     135           0 :       buckets[prev_i].next = buckets[i].next;
     136           0 :       buckets[i].next = REMOVED;
     137           0 :       ++removed_count;
     138           0 :       return;
     139             :     }
     140           0 :     prev_i = i;
     141           0 :     i = b.next;
     142             :   }
     143             : }
     144             : 
     145         745 : std::size_t hash_table2::hfind(std::size_t h,std::size_t x,std::size_t y)
     146             : {
     147         745 :   std::size_t i = table[h];
     148             :   bucket2 b;
     149         745 :   while (i != END_OF_LIST)
     150             :   {
     151         184 :     b = buckets[i];
     152         184 :     if (b.x == x && b.y == y)
     153             :     {
     154         184 :       return i;
     155             :     }
     156           0 :     i = b.next;
     157             :   }
     158         561 :   return NOT_FOUND;
     159             : }
     160             : 
     161         148 : bool hash_table2::check_table()
     162             : {
     163         148 :   if (4*(buckets.size() - removed_count) >= 3*table.size())
     164             :   {
     165             :     /* table is filled for at least 75%, so let's rehash! */
     166           0 :     mask = (2*mask) + 1;
     167           0 :     table.assign(mask+1,END_OF_LIST);
     168             :     std::size_t h;
     169           0 :     for (std::size_t i = 0; i < buckets.size(); ++i)
     170             :     {
     171           0 :       if (buckets[i].next != REMOVED)
     172             :       {
     173           0 :         h = hash(buckets[i].x,buckets[i].y);
     174           0 :         buckets[i].next = table[h];
     175           0 :         table[h] = i;
     176             :       }
     177             :     }
     178           0 :     return true;
     179             :   }
     180         148 :   return false;
     181             : }
     182             : 
     183         745 : std::size_t hash_table2::hash(std::size_t x, std::size_t y)
     184             : {
     185         745 :   return ((159403*x + 389651*y) & mask);
     186             : }
     187             : 
     188         162 : hash_table3::hash_table3(std::size_t initsize)
     189             : {
     190         162 :   mask = 1;
     191        3402 :   while (mask < initsize)
     192             :   {
     193        1620 :     mask = mask << 1;
     194             :   }
     195         162 :   --mask;
     196         162 :   clear();
     197         162 : }
     198             : 
     199         162 : hash_table3::~hash_table3()
     200         162 : {}
     201             : 
     202         708 : void hash_table3::clear()
     203             : {
     204         708 :   table.assign(mask+1,END_OF_LIST);
     205         708 :   buckets.clear();
     206         708 :   removed_count = 0;
     207         708 : }
     208             : 
     209        5253 : void hash_table3::add(std::size_t x,std::size_t y,std::size_t z)
     210             : {
     211        5253 :   std::size_t h = hash(x,y,z);
     212        5253 :   if (hfind(h,x,y,z) == NOT_FOUND)
     213             :   {
     214        5096 :     if (check_table())
     215             :     {
     216           0 :       h = hash(x,y,z);
     217             :     }
     218             :     bucket3 new_bucket;
     219        5096 :     new_bucket.x = x;
     220        5096 :     new_bucket.y = y;
     221        5096 :     new_bucket.z = z;
     222        5096 :     new_bucket.next = table[h];
     223        5096 :     table[h] = buckets.size();
     224        5096 :     buckets.push_back(new_bucket);
     225             :   }
     226        5253 : }
     227             : 
     228        3702 : bool hash_table3::find(std::size_t x,std::size_t y,std::size_t z)
     229             : {
     230        3702 :   return (hfind(hash(x,y,z),x,y,z) != NOT_FOUND);
     231             : }
     232             : 
     233          28 : void hash_table3::remove(std::size_t x,std::size_t y,std::size_t z)
     234             : {
     235             :   bucket3 b;
     236             :   std::size_t i, prev_i;
     237          28 :   std::size_t h = hash(x,y,z);
     238          28 :   i = table[h];
     239          28 :   if (i != END_OF_LIST)
     240             :   {
     241          28 :     b = buckets[i];
     242          28 :     if (b.x == x && b.y == y && b.z == z)
     243             :     {
     244          26 :       table[h] = b.next;
     245          26 :       buckets[i].next = REMOVED;
     246          26 :       ++removed_count;
     247          54 :       return;
     248             :     }
     249           2 :     prev_i = i;
     250           2 :     i = b.next;
     251             :   }
     252           2 :   while (i != END_OF_LIST)
     253             :   {
     254           2 :     b = buckets[i];
     255           2 :     if (b.x == x && b.y == y && b.z == z)
     256             :     {
     257           2 :       buckets[prev_i].next = buckets[i].next;
     258           2 :       buckets[i].next = REMOVED;
     259           2 :       ++removed_count;
     260           2 :       return;
     261             :     }
     262           0 :     prev_i = i;
     263           0 :     i = b.next;
     264             :   }
     265             : }
     266             : 
     267        8955 : std::size_t hash_table3::hfind(std::size_t h,std::size_t x,std::size_t y,std::size_t z)
     268             : {
     269        8955 :   std::size_t i = table[h];
     270             :   bucket3 b;
     271        9347 :   while (i != END_OF_LIST)
     272             :   {
     273        2242 :     b = buckets[i];
     274        2242 :     if (b.x == x && b.y == y && b.z == z)
     275             :     {
     276        2046 :       return i;
     277             :     }
     278         196 :     i = b.next;
     279             :   }
     280        6909 :   return NOT_FOUND;
     281             : }
     282             : 
     283        5096 : bool hash_table3::check_table()
     284             : {
     285        5096 :   if (4*(buckets.size() - removed_count) >= 3*table.size())
     286             :   {
     287             :     /* table is filled for at least 75%, so let's rehash! */
     288           0 :     mask = (2*mask) + 1;
     289           0 :     table.assign(mask+1,END_OF_LIST);
     290             :     std::size_t h;
     291           0 :     for (std::size_t i = 0; i < buckets.size(); ++i)
     292             :     {
     293           0 :       if (buckets[i].next != REMOVED)
     294             :       {
     295           0 :         h = hash(buckets[i].x,buckets[i].y,buckets[i].z);
     296           0 :         buckets[i].next = table[h];
     297           0 :         table[h] = i;
     298             :       }
     299             :     }
     300           0 :     return true;
     301             :   }
     302        5096 :   return false;
     303             : }
     304             : 
     305        8983 : std::size_t hash_table3::hash(std::size_t x, std::size_t y, std::size_t z)
     306             : {
     307        8983 :   return ((159403*x + 389651*y + 521503*z) & mask);
     308             : }

Generated by: LCOV version 1.12