1 // Copyright (c) Microsoft Corporation. All rights reserved.
2 // Licensed under the MIT license.
3 
4 #include "kuku/kuku.h"
5 
6 using namespace std;
7 
8 namespace kuku
9 {
query(item_type item) const10     QueryResult KukuTable::query(item_type item) const
11     {
12         if (is_empty_item(item))
13         {
14             throw invalid_argument("item cannot be the empty item");
15         }
16 
17         // Search the hash table
18         for (uint32_t i = 0; i < loc_func_count(); i++)
19         {
20             auto loc = location(item, i);
21             if (are_equal_item(table_[loc], item))
22             {
23                 return { loc, i };
24             }
25         }
26 
27         // Search the stash
28         for (location_type loc = 0; loc < stash_.size(); loc++)
29         {
30             if (are_equal_item(stash_[loc], item))
31             {
32                 return { loc, ~uint32_t(0) };
33             }
34         }
35 
36         // Not found
37         return { 0, max_loc_func_count };
38     }
39 
KukuTable(table_size_type table_size,table_size_type stash_size,uint32_t loc_func_count,item_type loc_func_seed,uint64_t max_probe,item_type empty_item)40     KukuTable::KukuTable(
41         table_size_type table_size, table_size_type stash_size, uint32_t loc_func_count, item_type loc_func_seed,
42         uint64_t max_probe, item_type empty_item)
43         : table_size_(table_size), stash_size_(stash_size), loc_func_seed_(loc_func_seed), max_probe_(max_probe),
44           empty_item_(empty_item), leftover_item_(empty_item_), inserted_items_(0), gen_(random_uint64())
45     {
46         if (loc_func_count < min_loc_func_count || loc_func_count > max_loc_func_count)
47         {
48             throw invalid_argument("loc_func_count is out of range");
49         }
50         if (table_size < min_table_size || table_size > max_table_size)
51         {
52             throw invalid_argument("table_size is out of range");
53         }
54         if (!max_probe)
55         {
56             throw invalid_argument("max_probe cannot be zero");
57         }
58 
59         // Allocate the hash table
60         table_.resize(table_size_, empty_item_);
61 
62         // Create the location (hash) functions
63         generate_loc_funcs(loc_func_count, loc_func_seed_);
64 
65         // Set up the distribution for location function sampling
66         u_ = std::uniform_int_distribution<uint32_t>(0, loc_func_count - 1);
67     }
68 
all_locations(item_type item) const69     set<location_type> KukuTable::all_locations(item_type item) const
70     {
71         if (is_empty_item(item))
72         {
73             throw invalid_argument("item cannot be the empty item");
74         }
75 
76         set<location_type> result;
77         for (auto lf : loc_funcs_)
78         {
79             result.emplace(lf(item));
80         }
81         return result;
82     }
83 
clear_table()84     void KukuTable::clear_table()
85     {
86         size_t sz = table_.size();
87         table_.resize(0);
88         table_.resize(sz, empty_item_);
89         stash_.clear();
90         leftover_item_ = empty_item_;
91         inserted_items_ = 0;
92     }
93 
generate_loc_funcs(uint32_t loc_func_count,item_type seed)94     void KukuTable::generate_loc_funcs(uint32_t loc_func_count, item_type seed)
95     {
96         loc_funcs_.clear();
97         while (loc_func_count--)
98         {
99             loc_funcs_.emplace_back(table_size_, seed);
100             increment_item(seed);
101         }
102     }
103 
insert(item_type item)104     bool KukuTable::insert(item_type item)
105     {
106         // Check if the item is already inserted or is the empty item
107         if (query(item))
108         {
109             return false;
110         }
111 
112         uint64_t level = max_probe_;
113         while (level--)
114         {
115             // Loop over all possible locations
116             for (uint32_t i = 0; i < loc_func_count(); i++)
117             {
118                 location_type loc = location(item, i);
119                 if (is_empty_item(table_[loc]))
120                 {
121                     table_[loc] = item;
122                     inserted_items_++;
123                     return true;
124                 }
125             }
126 
127             // Swap in the current item and in next round try the popped out item
128             item = swap(item, location(item, static_cast<uint32_t>(u_(gen_))));
129         }
130 
131         // level reached zero; try stash
132         if (stash_.size() < stash_size_)
133         {
134             stash_.push_back(item);
135             inserted_items_++;
136             return true;
137         }
138         else
139         {
140             leftover_item_ = item;
141             return false;
142         }
143     }
144 } // namespace kuku
145