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