1 #ifndef __COMPILE_TIME_BITS_HPP_INCLUDED__ 2 #define __COMPILE_TIME_BITS_HPP_INCLUDED__ 3 4 /* $Id: compile_time_bits.hpp 620372 2020-11-20 16:51:49Z vakatov $ 5 * =========================================================================== 6 * 7 * PUBLIC DOMAIN NOTICE 8 * National Center for Biotechnology Information 9 * 10 * This software/database is a "United States Government Work" under the 11 * terms of the United States Copyright Act. It was written as part of 12 * the author's official duties as a United States Government employee and 13 * thus cannot be copyrighted. This software/database is freely available 14 * to the public for use. The National Library of Medicine and the U.S. 15 * Government have not placed any restriction on its use or reproduction. 16 * 17 * Although all reasonable efforts have been taken to ensure the accuracy 18 * and reliability of the software and data, the NLM and the U.S. 19 * Government do not and cannot warrant the performance or results that 20 * may be obtained by using this software or data. The NLM and the U.S. 21 * Government disclaim all warranties, express or implied, including 22 * warranties of performance, merchantability or fitness for any particular 23 * purpose. 24 * 25 * Please cite the author in any work or product based on this material. 26 * 27 * =========================================================================== 28 * 29 * Authors: Sergiy Gotvyanskyy 30 * 31 * File Description: 32 * 33 * various compile time structures and functions 34 * 35 * 36 */ 37 38 #include <cstddef> 39 #include <utility> 40 #include <cstdint> 41 #include <corelib/tempstr.hpp> 42 43 #include "ct_crc32.hpp" 44 #include <corelib/ncbistr.hpp> 45 46 namespace compile_time_bits 47 { 48 template<class T, size_t N> 49 struct const_array 50 { 51 using _MyT = const_array<T, N>; 52 using value_type = T; 53 using size_type = std::size_t; 54 using difference_type = std::ptrdiff_t; 55 using reference = value_type&; 56 using const_reference = const value_type&; 57 using pointer = value_type*; 58 using const_pointer = const value_type*; 59 using container_type = value_type[N]; 60 using const_iterator = const value_type*; 61 using iterator = value_type*; 62 63 static constexpr size_t m_size = N; 64 sizecompile_time_bits::const_array65 static constexpr size_t size() noexcept { return N; } capacitycompile_time_bits::const_array66 static constexpr size_t capacity() noexcept { return N; } operator []compile_time_bits::const_array67 constexpr const_reference operator[](size_t _pos) const noexcept { return m_data[_pos]; } operator []compile_time_bits::const_array68 constexpr reference operator[](size_t _pos) noexcept { return m_data[_pos]; } begincompile_time_bits::const_array69 constexpr const_iterator begin() const noexcept { return m_data; } endcompile_time_bits::const_array70 constexpr const_iterator end() const noexcept { return m_data + size(); } cbegincompile_time_bits::const_array71 constexpr const_iterator cbegin() const noexcept { return m_data; } cendcompile_time_bits::const_array72 constexpr const_iterator cend() const noexcept { return m_data + size(); } begincompile_time_bits::const_array73 constexpr iterator begin() noexcept { return m_data; } endcompile_time_bits::const_array74 constexpr iterator end() noexcept { return m_data + size(); } datacompile_time_bits::const_array75 constexpr const value_type* data() const noexcept { return m_data; } 76 77 78 container_type m_data; 79 80 template<typename _Alloc> operator std::vector<value_type,_Alloc>compile_time_bits::const_array81 operator std::vector<value_type, _Alloc>() const 82 { 83 std::vector<value_type, _Alloc> vec; 84 vec.reserve(size()); 85 vec.assign(begin(), end()); 86 return vec; 87 } 88 }; 89 90 template <class T, std::size_t N, std::size_t... I> 91 constexpr const_array<std::remove_cv_t<T>, N> to_array_impl(T (& a)[N],std::index_sequence<I...>)92 to_array_impl(T(&a)[N], std::index_sequence<I...>) 93 { 94 return { {a[I]...} }; 95 } 96 97 template <class T, std::size_t N> 98 constexpr auto to_array(T(&&a)[N]) 99 { 100 return to_array_impl(a, std::make_index_sequence<N>{}); 101 } 102 template <class T, std::size_t N> to_array(T (& a)[N])103 constexpr auto to_array(T(&a)[N]) 104 { 105 return to_array_impl(a, std::make_index_sequence<N>{}); 106 } 107 108 template<class T> 109 struct const_array<T, 0> 110 { 111 using const_iterator = const T*; 112 using value_type = T; 113 114 static constexpr size_t m_size = 0; 115 sizecompile_time_bits::const_array116 constexpr size_t size() const noexcept { return 0; } capacitycompile_time_bits::const_array117 constexpr size_t capacity() const noexcept { return 0; } begincompile_time_bits::const_array118 constexpr const_iterator begin() const noexcept { return nullptr; } endcompile_time_bits::const_array119 constexpr const_iterator end() const noexcept { return nullptr; } datacompile_time_bits::const_array120 const value_type* data() const noexcept { return nullptr; } 121 122 template<typename _Alloc> operator std::vector<value_type,_Alloc>compile_time_bits::const_array123 operator std::vector<value_type, _Alloc>() const 124 { 125 return std::vector<value_type, _Alloc>(); 126 } 127 }; 128 129 template<class... _Types> 130 class const_tuple; 131 132 template<> 133 class const_tuple<> 134 { // empty tuple 135 public: 136 }; 137 138 template<class _This, 139 class... _Rest> 140 class const_tuple<_This, _Rest...> 141 : private const_tuple<_Rest...> 142 { // recursive tuple definition 143 public: 144 typedef _This _This_type; 145 typedef const_tuple<_Rest...> _Mybase; 146 _This _Myfirst; // the stored element 147 148 149 constexpr const_tuple() noexcept = default; const_tuple(const _This & _f,const _Rest &..._rest)150 constexpr const_tuple(const _This& _f, const _Rest&..._rest) noexcept 151 : _Mybase(_rest...), _Myfirst( _f ) 152 { 153 } 154 template<typename _T0, typename..._Other> const_tuple(_T0 && _f0,_Other &&...other)155 constexpr const_tuple(_T0&& _f0, _Other&&...other) noexcept 156 : _Mybase(std::forward<_Other>(other)...), _Myfirst( std::forward<_T0>(_f0) ) 157 { 158 } 159 }; 160 161 template<ncbi::NStr::ECase case_sensitive> 162 struct string_view 163 { 164 using sv = ncbi::CTempString; 165 166 constexpr string_view() = default; 167 168 template<size_t N> string_viewcompile_time_bits::string_view169 constexpr string_view(const char(&s)[N]) noexcept 170 : m_len{ N - 1 }, m_data{ s } 171 {} 172 string_viewcompile_time_bits::string_view173 constexpr string_view(const char* s, size_t len) noexcept 174 : m_len{ len }, m_data{ s } 175 {} 176 string_viewcompile_time_bits::string_view177 string_view(const ncbi::CTempString& view) 178 :m_len{ view.size() }, m_data{ view.data() } 179 {} 180 c_strcompile_time_bits::string_view181 constexpr const char* c_str() const noexcept { return m_data; } datacompile_time_bits::string_view182 constexpr const char* data() const noexcept { return m_data; } sizecompile_time_bits::string_view183 constexpr size_t size() const noexcept { return m_len; } 184 operator ncbi::CTempStringExcompile_time_bits::string_view185 operator ncbi::CTempStringEx() const noexcept 186 { 187 return ncbi::CTempStringEx(m_data, m_len, ncbi::CTempStringEx::eNoZeroAtEnd); 188 } operator ncbi::CTempStringcompile_time_bits::string_view189 operator ncbi::CTempString() const noexcept 190 { 191 return ncbi::CTempString(m_data, m_len); 192 } 193 template<class C, class T, class A> operator std::basic_string<C,T,A>compile_time_bits::string_view194 operator std::basic_string<C, T, A>() const 195 { 196 return std::string(m_data, m_len); 197 } operator []compile_time_bits::string_view198 constexpr char operator[](size_t pos) const 199 { 200 return m_data[pos]; 201 } operator !=compile_time_bits::string_view202 bool operator!=(const sv& o) const noexcept 203 { 204 return (case_sensitive == ncbi::NStr::eCase ? ncbi::NStr::CompareCase(*this, o) : ncbi::NStr::CompareNocase(*this, o)) != 0; 205 } operator ==compile_time_bits::string_view206 bool operator==(const sv& o) const noexcept 207 { 208 return (case_sensitive == ncbi::NStr::eCase ? ncbi::NStr::CompareCase(*this, o) : ncbi::NStr::CompareNocase(*this, o)) == 0; 209 } 210 size_t m_len{ 0 }; 211 const char* m_data{ nullptr }; 212 }; 213 214 template<ncbi::NStr::ECase case_sensitive, class _Hash = ct::SaltedCRC32<case_sensitive>> 215 class CHashString 216 { 217 public: 218 using hash_func = _Hash; 219 using hash_type = typename _Hash::type; 220 using sv = string_view<case_sensitive>; 221 222 constexpr CHashString() noexcept = default; 223 224 template<size_t N> CHashString(const char (& s)[N])225 constexpr CHashString(const char(&s)[N]) noexcept 226 : m_data{s}, m_len{N-1}, m_hash{hash_func::ct(s)} 227 {} 228 CHashString(const sv & s)229 CHashString(const sv& s) noexcept 230 : m_data{s.data()}, m_len{s.size()}, m_hash(hash_func::rt(s.data(), s.size())) 231 {} 232 operator <(const CHashString & o) const233 constexpr bool operator<(const CHashString& o) const noexcept 234 { 235 return m_hash < o.m_hash; 236 } operator !=(const CHashString & o) const237 constexpr bool operator!=(const CHashString& o) const noexcept 238 { 239 return m_hash != o.m_hash; 240 } operator ==(const CHashString & o) const241 constexpr bool operator==(const CHashString& o) const noexcept 242 { 243 return m_hash == o.m_hash; 244 } operator hash_type() const245 constexpr operator hash_type() const noexcept 246 { 247 return m_hash; 248 } operator sv() const249 constexpr operator sv() const noexcept 250 { 251 return sv(m_data, m_len); 252 } 253 protected: 254 255 const char* m_data{nullptr}; 256 size_t m_len{ 0 }; 257 hash_type m_hash{ 0 }; 258 }; 259 } 260 261 namespace ct 262 { 263 using namespace compile_time_bits; 264 } 265 266 namespace std 267 {// these are backported implementations of C++17 methods 268 constexpr size_t hardware_destructive_interference_size = 64; 269 constexpr size_t hardware_constructive_interference_size = 64; 270 271 template<size_t i, class T, size_t N> get(const ct::const_array<T,N> & in)272 constexpr const T& get(const ct::const_array<T, N>& in) noexcept 273 { 274 return in[i]; 275 } 276 template<class T, size_t N> size(const ct::const_array<T,N> &)277 constexpr size_t size(const ct::const_array<T, N>& /*in*/) noexcept 278 { 279 return N; 280 } 281 template<class T, size_t N> begin(const ct::const_array<T,N> & in)282 constexpr auto begin(const ct::const_array<T, N>& in) noexcept 283 -> typename ct::const_array<T, N>::const_iterator 284 { 285 return in.begin(); 286 } 287 template<class T, size_t N> end(const ct::const_array<T,N> & in)288 constexpr auto end(const ct::const_array<T, N>& in) noexcept 289 -> typename ct::const_array<T, N>::const_iterator 290 { 291 return in.end(); 292 } 293 294 //template<class> 295 // false value attached to a dependent name (for static_assert) 296 //constexpr bool always_false = false; 297 298 template<size_t _Index> 299 class tuple_element<_Index, ct::const_tuple<>> 300 { // enforce bounds checking 301 //static_assert(always_false<integral_constant<size_t, _Index>>, 302 // "tuple index out of bounds"); 303 }; 304 305 template<class _This, class... _Rest> 306 class tuple_element<0, ct::const_tuple<_This, _Rest...>> 307 { // select first element 308 public: 309 using type = _This; 310 using _Ttype = ct::const_tuple<_This, _Rest...>; 311 }; 312 313 template<size_t _Index, class _This, class... _Rest> 314 class tuple_element<_Index, ct::const_tuple<_This, _Rest...>> 315 : public tuple_element<_Index - 1, ct::const_tuple<_Rest...>> 316 { // recursive tuple_element definition 317 }; 318 319 template<size_t _Index, 320 class... _Types> 321 constexpr const typename tuple_element<_Index, ct::const_tuple<_Types...>>::type& get(const ct::const_tuple<_Types...> & _Tuple)322 get(const ct::const_tuple<_Types...>& _Tuple) noexcept 323 { // get const reference to _Index element of tuple 324 typedef typename tuple_element<_Index, ct::const_tuple<_Types...>>::_Ttype _Ttype; 325 return (((const _Ttype&)_Tuple)._Myfirst); 326 } 327 328 template<class _Traits, ncbi::NStr::ECase cs> inline operator <<(basic_ostream<char,_Traits> & _Ostr,const ct::string_view<cs> & v)329 basic_ostream<char, _Traits>& operator<<(basic_ostream<char, _Traits>& _Ostr, const ct::string_view<cs>& v) 330 {// Padding is not implemented yet 331 _Ostr.write(v.data(), v.size()); 332 return _Ostr; 333 } 334 335 template<class T, size_t N> 336 class tuple_size<ct::const_array<T, N>>: 337 public integral_constant<size_t, N> 338 { }; 339 } 340 341 namespace compile_time_bits 342 { 343 template<typename _Value> 344 struct simple_sort_traits 345 { 346 using value_type = typename _Value::value_type; 347 using hash_type = typename _Value::hash_type; 348 using init_type = typename _Value::init_type; 349 350 struct Pred 351 { 352 template<typename _Input> operator ()compile_time_bits::simple_sort_traits::Pred353 constexpr bool operator()(const _Input& input, size_t l, size_t r) 354 { 355 return input[l] < input[r]; 356 } 357 }; 358 template<typename _Input> constructcompile_time_bits::simple_sort_traits359 static constexpr value_type construct(const _Input& input, size_t I) 360 { 361 return input[I]; 362 } get_hashcompile_time_bits::simple_sort_traits363 static constexpr hash_type get_hash(const init_type& v) 364 { 365 return v; 366 } 367 }; 368 369 template<typename _T1, typename _T2> 370 struct straight_sort_traits 371 { 372 using init_type = std::pair<typename _T1::init_type, typename _T2::init_type>; 373 using value_type = std::pair<typename _T1::value_type, typename _T2::value_type>; 374 using hash_type = typename _T1::hash_type; 375 376 struct Pred 377 { 378 template<typename _Input> operator ()compile_time_bits::straight_sort_traits::Pred379 constexpr bool operator()(const _Input& input, size_t l, size_t r) 380 { 381 return input[l].first < input[r].first; 382 } 383 }; get_hashcompile_time_bits::straight_sort_traits384 static constexpr hash_type get_hash(const init_type& v) 385 { 386 return static_cast<hash_type>(v.first); 387 } 388 template<typename _Input> constructcompile_time_bits::straight_sort_traits389 static constexpr value_type construct(const _Input& input, size_t I) 390 { 391 return value_type{ input[I].first, input[I].second }; 392 } 393 }; 394 395 template<typename _T1, typename _T2> 396 struct flipped_sort_traits 397 { 398 using init_type = std::pair<typename _T1::init_type, typename _T2::init_type>; 399 using value_type = std::pair<typename _T2::value_type, typename _T1::value_type>; 400 using hash_type = typename _T2::hash_type; 401 402 struct Pred 403 { 404 template<typename _Input> operator ()compile_time_bits::flipped_sort_traits::Pred405 constexpr bool operator()(const _Input& input, size_t l, size_t r) 406 { 407 return input[l].second < input[r].second; 408 } 409 }; get_hashcompile_time_bits::flipped_sort_traits410 static constexpr hash_type get_hash(const init_type& v) 411 { 412 return v.second; 413 } 414 template<typename _Input> constructcompile_time_bits::flipped_sort_traits415 static constexpr value_type construct(const _Input& input, size_t I) 416 { 417 return value_type{ input[I].second, input[I].first }; 418 } 419 }; 420 421 // array that is aligned within CPU cache lines 422 // its base address and size are both aligned to fit cache lines 423 template<typename _HashType, size_t N> 424 class aligned_index 425 { 426 public: 427 static constexpr size_t alignment = std::hardware_constructive_interference_size; 428 get_aligned_size(size_t align)429 static constexpr size_t get_aligned_size(size_t align) noexcept 430 { 431 size_t requested_memory = sizeof(const_array<_HashType, N>); 432 size_t aligned_blocks = (requested_memory + align - 1) / align; 433 size_t aligned_size = (aligned_blocks * align) / sizeof(_HashType); 434 return aligned_size; 435 } 436 static const size_t aligned_size = get_aligned_size(alignment); 437 static const size_t size = N; 438 439 // uncomment this alignment statement to observe test_compile_time unit test failure 440 alignas(alignment) 441 const_array<_HashType, aligned_size> m_array{}; 442 }; 443 444 template<typename _HashType> 445 class const_index 446 { 447 public: 448 constexpr const_index() = default; 449 450 template<size_t N> const_index(const aligned_index<_HashType,N> & _init)451 constexpr const_index(const aligned_index<_HashType, N>& _init) 452 : m_values{ _init.m_array.data() }, 453 m_realsize{ N }, 454 m_aligned_size{ _init.m_array.size() } 455 { 456 } lower_bound(_HashType value) const457 size_t lower_bound(_HashType value) const noexcept 458 { 459 auto it = std::lower_bound(m_values, m_values + m_realsize, value); 460 return std::distance(m_values, it); 461 } upper_bound(_HashType value) const462 size_t upper_bound(_HashType value) const noexcept 463 { 464 auto it = std::upper_bound(m_values, m_values + m_realsize, value); 465 return std::distance(m_values, it); 466 } equal_range(_HashType value) const467 std::pair<size_t,size_t> equal_range(_HashType value) const noexcept 468 { 469 auto range = std::equal_range(m_values, m_values + m_realsize, value); 470 return std::make_pair( 471 std::distance(m_values, range.first), 472 std::distance(m_values, range.second)); 473 } 474 const _HashType* m_values = nullptr; 475 const size_t m_realsize = 0; 476 const size_t m_aligned_size = 0; 477 }; 478 479 // compile time sort algorithm 480 // uses insertion sort https://en.wikipedia.org/wiki/Insertion_sort 481 template<typename _Traits, bool remove_duplicates> 482 class TInsertSorter 483 { 484 public: 485 using sort_traits = _Traits; 486 using init_type = typename _Traits::init_type; 487 using value_type = typename _Traits::value_type; 488 using hash_type = typename _Traits::hash_type; 489 490 template<size_t N> operator ()(const init_type (& init)[N]) const491 constexpr auto operator()(const init_type(&init)[N]) const noexcept 492 { 493 auto indices = make_indices(init); 494 auto hashes = construct_hashes(init, indices, std::make_index_sequence<aligned_index<hash_type, N>::aligned_size > {}); 495 auto values = construct_values(init, indices, std::make_index_sequence<N>{}); 496 return std::make_pair(hashes, values); 497 } 498 499 protected: 500 501 template<typename _Indices, typename _Value> insert_down(_Indices & indices,size_t head,size_t tail,_Value current)502 static constexpr void insert_down(_Indices& indices, size_t head, size_t tail, _Value current) 503 { 504 auto saved = current; 505 while (head != tail) 506 { 507 auto prev = tail--; 508 indices[prev] = indices[tail]; 509 } 510 indices[head] = saved; 511 } 512 template<typename _Indices, typename _Input> const_lower_bound(const _Indices & indices,const _Input & input,size_t last,size_t value)513 static constexpr size_t const_lower_bound(const _Indices& indices, const _Input& input, size_t last, size_t value) 514 { 515 typename _Traits::Pred pred{}; 516 size_t _UFirst = 0; 517 size_t _Count = last; 518 519 while (0 < _Count) 520 { // divide and conquer, find half that contains answer 521 const size_t _Count2 = _Count >> 1; // TRANSITION, VSO#433486 522 const size_t _UMid = _UFirst + _Count2; 523 if (pred(input, indices[_UMid], value)) 524 { // try top half 525 _UFirst = (_UMid + 1); // _Next_iter(_UMid); 526 _Count -= _Count2 + 1; 527 } 528 else 529 { 530 _Count = _Count2; 531 } 532 } 533 534 return _UFirst; 535 } 536 template<typename _Indices, typename _Input> const_upper_bound(const _Indices & indices,const _Input & input,size_t last,size_t value)537 static constexpr size_t const_upper_bound(const _Indices& indices, const _Input& input, size_t last, size_t value) 538 { 539 typename _Traits::Pred pred{}; 540 size_t _UFirst = 0; 541 size_t _Count = last; 542 543 while (0 < _Count) 544 { // divide and conquer, find half that contains answer 545 const size_t _Count2 = _Count >> 1; // TRANSITION, VSO#433486 546 const size_t _UMid = _UFirst + _Count2; 547 if (pred(input, value, indices[_UMid])) 548 { 549 _Count = _Count2; 550 } 551 else 552 { // try top half 553 _UFirst = (_UMid + 1); // _Next_iter(_UMid); 554 _Count -= _Count2 + 1; 555 } 556 } 557 558 return (_UFirst); 559 } 560 561 template<typename _Indices, typename _Input> insert_sort_indices(_Indices & result,const _Input & input)562 static constexpr size_t insert_sort_indices(_Indices& result, const _Input& input) 563 { 564 typename _Traits::Pred pred{}; 565 auto size = result.size(); 566 if (size < 2) 567 return size; 568 569 // current is the first element of the unsorted part of the array 570 size_t current = 0; 571 // the last inserted element into sorted part of the array 572 size_t last = current; 573 result[0] = 0; 574 current++; 575 576 while (current != result.size()) 577 { 578 if (pred(input, result[last], current)) 579 {// optimization for presorted arrays 580 result[++last] = current; 581 } 582 else { 583 // we may exclude last element since it's already known as smaller then current 584 // using const_upper_bound helps to preserve the order of rows with identical hash values 585 // using const_upper_bound will reverse that order 586 auto fit = const_upper_bound(result, input, last, current); 587 bool move_it = !remove_duplicates; 588 if (remove_duplicates) 589 { 590 move_it = (fit == 0) || pred(input, result[fit-1], current); 591 } 592 if (move_it) 593 { 594 ++last; 595 insert_down(result, fit, last, current); 596 } 597 } 598 ++current; 599 } 600 if (remove_duplicates) 601 {// fill the rest of the indices with maximum value 602 current = last; 603 while (++current != result.size()) 604 { 605 result[current] = result[last]; 606 } 607 } 608 return 1 + last; 609 } 610 611 template<typename T, size_t N> make_indices(const T (& input)[N])612 static constexpr auto make_indices(const T(&input)[N]) noexcept 613 { 614 const_array<size_t, N> indices{}; 615 auto real_size = insert_sort_indices(indices, input); 616 return std::make_pair(real_size, indices); 617 } 618 619 template<size_t I, typename _Input, typename _Indices> select_hash(const _Input & init,const _Indices & indices)620 static constexpr hash_type select_hash(const _Input& init, const _Indices& indices) noexcept 621 { 622 size_t real_size = indices.first; 623 if (I < real_size) 624 return sort_traits::get_hash(init[indices.second[I]]); 625 else 626 return std::numeric_limits<hash_type>::max(); 627 } 628 629 template<size_t N, typename _Indices, std::size_t... I> construct_hashes(const init_type (& init)[N],const _Indices & indices,std::index_sequence<I...>)630 static constexpr auto construct_hashes(const init_type(&init)[N], const _Indices& indices, std::index_sequence<I...> /*is_unused*/) noexcept 631 -> aligned_index<hash_type, N> 632 { 633 return { { select_hash<I>(init, indices) ...} }; 634 } 635 636 template<typename _Input, typename _Indices, std::size_t... I> construct_values(const _Input & input,const _Indices & indices,std::index_sequence<I...>)637 static constexpr auto construct_values(const _Input& input, const _Indices& indices, std::index_sequence<I...>) noexcept 638 -> const_array<value_type, sizeof...(I)> 639 { 640 auto real_size = indices.first; 641 return { { sort_traits::construct(input, indices.second[I < real_size ? I : real_size - 1]) ...} }; 642 } 643 }; 644 645 using tagStrCase = std::integral_constant<ncbi::NStr::ECase, ncbi::NStr::eCase>; 646 using tagStrNocase = std::integral_constant<ncbi::NStr::ECase, ncbi::NStr::eNocase>; 647 648 // we only support strings, integral types and enums 649 // write your own DeduceHashedType specialization if required 650 template<typename _BaseType, typename _InitType = _BaseType, typename _HashType = void> 651 struct DeduceHashedType 652 { 653 using value_type = _BaseType; 654 using init_type = _InitType; 655 using hash_type = _HashType; 656 static constexpr bool can_index = std::numeric_limits<hash_type>::is_integer; 657 }; 658 659 template<typename _BaseType> 660 struct DeduceHashedType<_BaseType, 661 typename std::enable_if<std::is_enum<_BaseType>::value, _BaseType>::type> 662 : DeduceHashedType<_BaseType, _BaseType, typename std::underlying_type<_BaseType>::type> 663 { 664 }; 665 666 template<typename _BaseType> 667 struct DeduceHashedType<_BaseType, 668 typename std::enable_if<std::numeric_limits<_BaseType>::is_integer, _BaseType>::type> 669 : DeduceHashedType<_BaseType, _BaseType, _BaseType> 670 { 671 }; 672 673 template<ncbi::NStr::ECase case_sensitive> 674 struct DeduceHashedType<std::integral_constant<ncbi::NStr::ECase, case_sensitive>> 675 : DeduceHashedType<string_view<case_sensitive>, CHashString<case_sensitive>, typename CHashString<case_sensitive>::hash_type> 676 { 677 }; 678 679 template<> 680 struct DeduceHashedType<const char*> 681 : DeduceHashedType<tagStrCase> 682 { 683 }; 684 685 template<> 686 struct DeduceHashedType<char*> 687 : DeduceHashedType<tagStrCase> 688 { 689 }; 690 691 template<class Traits, class Allocator> 692 struct DeduceHashedType<std::basic_string<char, Traits, Allocator>> 693 : DeduceHashedType<tagStrCase> 694 { 695 }; 696 697 template<typename _First, typename _Second> 698 struct DeduceHashedType<std::pair<_First, _Second>> 699 { 700 using first_type = DeduceHashedType<_First>; 701 using second_type = DeduceHashedType<_Second>; 702 using value_type = std::pair<typename first_type::value_type, typename second_type::value_type>; 703 using init_type = value_type; 704 }; 705 template<typename..._Types> 706 struct DeduceHashedType<std::tuple<_Types...>> 707 { 708 using hashed_type = ct::const_tuple<DeduceHashedType<_Types>...>; 709 using value_type = ct::const_tuple<typename DeduceHashedType<_Types>::value_type...>; 710 using init_type = value_type; 711 }; 712 713 template<typename _Key, typename _Value> 714 class const_set_map_base 715 { 716 public: 717 using hashed_key = DeduceHashedType<_Key>; 718 using hashed_value = DeduceHashedType<_Value>; 719 720 using value_type = typename hashed_value::value_type; 721 using size_type = std::size_t; 722 using difference_type = std::ptrdiff_t; 723 using reference = const value_type&; 724 using const_reference = const value_type&; 725 using pointer = const value_type*; 726 using const_pointer = const value_type*; 727 using iterator = const value_type*; 728 using const_iterator = const value_type*; 729 using reverse_iterator = std::reverse_iterator<iterator>; 730 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 731 732 using intermediate = typename hashed_key::value_type; 733 734 constexpr const_set_map_base() = default; 735 736 template<typename _InitProxy> const_set_map_base(const _InitProxy & _proxy)737 constexpr const_set_map_base(const _InitProxy& _proxy) 738 : m_values{ _proxy.second.data() }, 739 m_index{ _proxy.first }, 740 m_realsize{ _proxy.second.size() } 741 {} 742 begin() const743 constexpr const_iterator begin() const noexcept { return m_values; } cbegin() const744 constexpr const_iterator cbegin() const noexcept { return m_values; } end() const745 constexpr const_iterator end() const noexcept { return m_values + m_realsize; } cend() const746 constexpr const_iterator cend() const noexcept { return m_values + m_realsize; } capacity() const747 constexpr size_type capacity() const noexcept { return m_realsize; } size() const748 constexpr size_type size() const noexcept { return m_realsize; } max_size() const749 constexpr size_type max_size() const noexcept { return m_realsize; } empty() const750 constexpr bool empty() const noexcept { return m_realsize == 0; } 751 752 // alias to decide whether _Key can be constructed from _Arg 753 template<typename _K, typename _Arg> 754 using if_available = typename std::enable_if< 755 std::is_constructible<intermediate, _K>::value, _Arg>::type; 756 757 template<typename K> 758 if_available<K, const_iterator> lower_bound(K && _key) const759 lower_bound(K&& _key) const 760 { 761 intermediate temp = std::forward<K>(_key); 762 typename hashed_key::init_type key(temp); 763 hash_type hash(std::move(key)); 764 auto offset = m_index.lower_bound(hash); 765 return begin() + offset; 766 } 767 template<typename K> 768 if_available<K, const_iterator> upped_bound(K && _key) const769 upped_bound(K&& _key) const 770 { 771 intermediate temp = std::forward<K>(_key); 772 typename hashed_key::init_type key(temp); 773 hash_type hash(std::move(key)); 774 auto offset = m_index.upped_bound(hash); 775 return begin() + offset; 776 } 777 778 template<typename K> 779 if_available<K, std::pair<const_iterator, const_iterator>> equal_range(K && _key) const780 equal_range(K&& _key) const 781 { 782 intermediate temp = std::forward<K>(_key); 783 typename hashed_key::init_type key(temp); 784 hash_type hash(std::move(key)); 785 auto _range = m_index.equal_range(hash); 786 return std::make_pair( 787 begin() + _range.first, 788 begin() + _range.second); 789 } get_alignment() const790 size_t get_alignment() const 791 { 792 return std::uintptr_t(m_index.m_values) % std::hardware_constructive_interference_size; 793 } 794 protected: 795 796 using hash_type = typename hashed_key::hash_type; 797 const value_type* m_values = nullptr; 798 const_index<hash_type> m_index{}; 799 size_type m_realsize = 0; 800 }; 801 802 // this helper packs set of bits into an array usefull for initialisation of bitset 803 // using C++14 804 805 template<class _Ty, size_t array_size> 806 struct bitset_traits 807 { 808 using array_t = const_array<_Ty, array_size>; 809 810 static constexpr int width = 8 * sizeof(_Ty); 811 812 struct range_t 813 { 814 size_t m_from; 815 size_t m_to; 816 }; 817 check_rangecompile_time_bits::bitset_traits818 static constexpr bool check_range(const range_t& range, size_t i) 819 { 820 return (range.m_from <= i && i <= range.m_to); 821 } 822 823 template <size_t I> assemble_maskcompile_time_bits::bitset_traits824 static constexpr _Ty assemble_mask(const range_t& _init) 825 { 826 constexpr auto _min = I * width; 827 constexpr auto _max = I * width + width - 1; 828 if (check_range(_init, _min) && check_range(_init, _max)) 829 return std::numeric_limits<_Ty>::max(); 830 831 _Ty ret = 0; 832 for (size_t j = 0; j < width; ++j) 833 { 834 bool is_set = check_range(_init, j + _min); 835 if (is_set) 836 ret |= (_Ty(1) << j); 837 } 838 return ret; 839 } 840 template <size_t I, typename _O> assemble_maskcompile_time_bits::bitset_traits841 static constexpr _Ty assemble_mask(const std::initializer_list<_O>& _init) 842 { 843 _Ty ret = 0; 844 constexpr auto _min = I * width; 845 constexpr auto _max = I * width + width - 1; 846 for (unsigned rec : _init) 847 { 848 if (_min <= rec && rec <= _max) 849 { 850 ret |= _Ty(1) << (rec % width); 851 } 852 } 853 return ret; 854 } 855 template <size_t I, size_t N> assemble_maskcompile_time_bits::bitset_traits856 static constexpr _Ty assemble_mask(const char(&_init)[N]) 857 { 858 _Ty ret = 0; 859 _Ty mask = 1; 860 constexpr auto _min = I * width; 861 constexpr auto _max = I * width + width; 862 for (size_t pos = _min; pos < _max && pos < N; ++pos) 863 { 864 if (_init[pos] == '1') ret |= mask; 865 mask = mask << 1; 866 } 867 return ret; 868 } 869 template <typename _Input, std::size_t... I> assemble_bitsetcompile_time_bits::bitset_traits870 static constexpr array_t assemble_bitset(const _Input& _init, std::index_sequence<I...>) 871 { 872 return { {assemble_mask<I>(_init)...} }; 873 } 874 875 template<typename _O> set_bitscompile_time_bits::bitset_traits876 static constexpr array_t set_bits(std::initializer_list<_O> args) 877 { 878 return assemble_bitset(args, std::make_index_sequence<array_size>{}); 879 } 880 template<typename _T> set_rangecompile_time_bits::bitset_traits881 static constexpr array_t set_range(_T from, _T to) 882 { 883 return assemble_bitset(range_t{ static_cast<size_t>(from), static_cast<size_t>(to) }, std::make_index_sequence<array_size>{}); 884 } 885 template<size_t N> count_bitscompile_time_bits::bitset_traits886 static constexpr size_t count_bits(const char(&in)[N]) 887 { 888 size_t ret{ 0 }; 889 for (size_t i = 0; i < N; ++i) 890 { 891 if (in[i]=='1') ++ret; 892 } 893 return ret; 894 } 895 template<size_t N> set_bitscompile_time_bits::bitset_traits896 static constexpr array_t set_bits(const char(&in)[N]) 897 { 898 return assemble_bitset(in, std::make_index_sequence<array_size>{}); 899 } 900 }; 901 } 902 903 #endif 904 905