kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

hash_map.cc (5603B)


      1 #include "hash_map.hh"
      2 
      3 #include "clock.hh"
      4 #include "string.hh"
      5 #include "unit_tests.hh"
      6 #include "format.hh"
      7 #include "debug.hh"
      8 
      9 #include <random>
     10 #include <algorithm>
     11 #include <unordered_map>
     12 
     13 namespace Kakoune
     14 {
     15 
     16 UnitTest test_hash_map{[] {
     17     // Basic usage
     18     {
     19         HashMap<int, int> map;
     20         map.insert({10, 1});
     21         map.insert({20, 2});
     22         kak_assert(map.find_index(0) == -1);
     23         kak_assert(map.find_index(10) == 0);
     24         kak_assert(map.find_index(20) == 1);
     25         kak_assert(map[10] == 1);
     26         kak_assert(map[20] == 2);
     27         kak_assert(map[30] == 0);
     28         map[30] = 3;
     29         kak_assert(map.find_index(30) == 2);
     30         map.remove(20);
     31         kak_assert(map.find_index(30) == 1);
     32         kak_assert(map.size() == 2);
     33     }
     34 
     35     // Replace Multiple entries with the same key
     36     {
     37         HashMap<int, int> map;
     38         map.insert({10, 1});
     39         map.insert({10, 2});
     40         kak_assert(map.find_index(10) == 0);
     41         kak_assert(map.size() == 1);
     42         kak_assert(map[10] == 2);
     43         map.remove(10);
     44         kak_assert(map.find_index(10) == -1);
     45     }
     46 
     47     // Multiple entries with the same key
     48     {
     49         MultiHashMap<int, int> map;
     50         map.insert({10, 1});
     51         map.insert({10, 2});
     52         kak_assert(map.find_index(10) == 0);
     53         map.remove(10);
     54         kak_assert(map.find_index(10) == 0);
     55         map.remove(10);
     56         kak_assert(map.find_index(10) == -1);
     57         map.insert({20, 1});
     58         map.insert({20, 2});
     59         map.remove_all(20);
     60         kak_assert(map.find_index(20) == -1);
     61     }
     62 
     63     // Check hash compatible support
     64     {
     65         HashMap<String, int> map;
     66         map.insert({"test", 10});
     67         kak_assert(map["test"_sv] == 10);
     68         map.remove("test"_sv);
     69     }
     70 
     71     // make sure we get what we expect from the hash map
     72     {
     73         std::random_device dev;
     74         std::default_random_engine re{dev()};
     75         std::uniform_int_distribution<int> dist;
     76 
     77         HashMap<int, int> map;
     78         Vector<std::pair<int, int>> ref;
     79 
     80         for (int i = 0; i < 100; ++i)
     81         {
     82             auto key = dist(re), value = dist(re);
     83             ref.push_back({key, value});
     84             map.insert({key, value});
     85 
     86             std::shuffle(ref.begin(), ref.end(), re);
     87             for (auto& elem : ref)
     88             {
     89                 auto it = map.find(elem.first);
     90                 kak_assert(it != map.end() and it->value == elem.second);
     91             }
     92         }
     93     }
     94 }};
     95 
     96 UnitTest test_hash_set{[] {
     97     // Basic usage
     98     {
     99         HashSet<int> set;
    100         set.insert(10);
    101         set.insert(20);
    102         kak_assert(set.find_index(0) == -1);
    103         kak_assert(set.find_index(10) == 0);
    104         kak_assert(set.find_index(20) == 1);
    105         kak_assert(set[10] == 10);
    106         kak_assert(set[20] == 20);
    107         kak_assert(set[30] == 30);
    108         set[30];
    109         kak_assert(set.find_index(30) == 2);
    110         set.remove(20);
    111         kak_assert(set.find_index(30) == 1);
    112         kak_assert(set.size() == 2);
    113     }
    114 
    115     // Replace Multiple entries with the same key
    116     {
    117         HashSet<int> set;
    118         set.insert(10);
    119         set.insert(10);
    120         kak_assert(set.find_index(10) == 0);
    121         kak_assert(set.size() == 1);
    122         set.remove(10);
    123         kak_assert(set.find_index(10) == -1);
    124     }
    125 
    126     // Multiple entries with the same key
    127     {
    128         MultiHashSet<int> set;
    129         set.insert(10);
    130         set.insert(10);
    131         kak_assert(set.find_index(10) == 0);
    132         set.remove(10);
    133         kak_assert(set.find_index(10) == 0);
    134         set.remove(10);
    135         kak_assert(set.find_index(10) == -1);
    136         set.insert(20);
    137         set.insert(20);
    138         set.remove_all(20);
    139         kak_assert(set.find_index(20) == -1);
    140     }
    141 
    142     // Check hash compatible support
    143     {
    144         HashSet<String> set;
    145         set.insert("test");
    146         kak_assert(set["test"_sv] == "test");
    147         set.remove("test"_sv);
    148     }
    149 }};
    150 
    151 template<typename Map>
    152 void do_profile(size_t count, StringView type)
    153 {
    154     std::random_device dev;
    155     std::default_random_engine re{dev()};
    156     std::uniform_int_distribution<size_t> dist{0, count};
    157 
    158     Vector<size_t> vec;
    159     for (size_t i = 0; i < count; ++i)
    160         vec.push_back(i);
    161     std::shuffle(vec.begin(), vec.end(), re);
    162 
    163     Map map;
    164     auto start = Clock::now();
    165 
    166     for (auto v : vec)
    167         map.insert({v, dist(re)});
    168     auto after_insert = Clock::now();
    169 
    170     for (size_t i = 0; i < count; ++i)
    171         ++map[dist(re)];
    172     auto after_read = Clock::now();
    173 
    174     for (size_t i = 0; i < count; ++i)
    175         map.erase(dist(re));
    176     auto after_remove = Clock::now();
    177 
    178     int c = 0;
    179     for (auto v : vec)
    180     {
    181         auto it = map.find(v);
    182         if (it != map.end())
    183             ++c;
    184     }
    185     auto after_find = Clock::now();
    186 
    187     using namespace std::chrono;
    188     write_to_debug_buffer(format("{} ({}) -- inserts: {}us, reads: {}us, remove: {}us, find: {}us ({})", type, count,
    189                                  duration_cast<microseconds>(after_insert - start).count(),
    190                                  duration_cast<microseconds>(after_read - after_insert).count(),
    191                                  duration_cast<microseconds>(after_remove - after_read).count(),
    192                                  duration_cast<microseconds>(after_find - after_remove).count(),
    193                                  c));
    194 }
    195 
    196 void profile_hash_maps()
    197 {
    198     for (auto i : { 1000, 10000, 100000, 1000000, 10000000 })
    199     {
    200         do_profile<std::unordered_map<size_t, size_t>>(i, "UnorderedMap");
    201         do_profile<HashMap<size_t, size_t>>(i, "     HashMap");
    202     }
    203 }
    204 
    205 }