ceph/src/boost/boost/hana/map.hpp

   1 /*!
   2 @file
   3 Defines `boost::hana::map`.
   4
   5 @copyright Louis Dionne 2013-2017
   6 Distributed under the Boost Software License, Version 1.0.
   7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
   8  */
   9
  10 #ifndef BOOST_HANA_MAP_HPP
  11 #define BOOST_HANA_MAP_HPP
  12
  13 #include <boost/hana/fwd/map.hpp>
  14
  15 #include <boost/hana/all_of.hpp>
  16 #include <boost/hana/basic_tuple.hpp>
  17 #include <boost/hana/bool.hpp>
  18 #include <boost/hana/concept/comparable.hpp>
  19 #include <boost/hana/concept/constant.hpp>
  20 #include <boost/hana/concept/product.hpp>
  21 #include <boost/hana/config.hpp>
  22 #include <boost/hana/contains.hpp>
  23 #include <boost/hana/core/is_a.hpp>
  24 #include <boost/hana/core/make.hpp>
  25 #include <boost/hana/core/to.hpp>
  26 #include <boost/hana/detail/decay.hpp>
  27 #include <boost/hana/detail/fast_and.hpp>
  28 #include <boost/hana/detail/has_duplicates.hpp>
  29 #include <boost/hana/detail/hash_table.hpp>
  30 #include <boost/hana/detail/intrinsics.hpp>
  31 #include <boost/hana/detail/operators/adl.hpp>
  32 #include <boost/hana/detail/operators/comparable.hpp>
  33 #include <boost/hana/detail/operators/searchable.hpp>
  34 #include <boost/hana/equal.hpp>
  35 #include <boost/hana/find.hpp>
  36 #include <boost/hana/first.hpp>
  37 #include <boost/hana/fold_left.hpp>
  38 #include <boost/hana/functional/demux.hpp>
  39 #include <boost/hana/functional/on.hpp>
  40 #include <boost/hana/functional/partial.hpp>
  41 #include <boost/hana/fwd/any_of.hpp>
  42 #include <boost/hana/fwd/at_key.hpp>
  43 #include <boost/hana/fwd/difference.hpp>
  44 #include <boost/hana/fwd/erase_key.hpp>
  45 #include <boost/hana/fwd/intersection.hpp>
  46 #include <boost/hana/fwd/is_subset.hpp>
  47 #include <boost/hana/fwd/keys.hpp>
  48 #include <boost/hana/fwd/union.hpp>
  49 #include <boost/hana/insert.hpp>
  50 #include <boost/hana/integral_constant.hpp>
  51 #include <boost/hana/keys.hpp>
  52 #include <boost/hana/length.hpp>
  53 #include <boost/hana/optional.hpp>
  54 #include <boost/hana/remove_if.hpp>
  55 #include <boost/hana/second.hpp>
  56 #include <boost/hana/unpack.hpp>
  57 #include <boost/hana/value.hpp>
  58
  59
  60 #include <cstddef>
  61 #include <type_traits>
  62 #include <utility>
  63
  64
  65 BOOST_HANA_NAMESPACE_BEGIN
  66     //////////////////////////////////////////////////////////////////////////
  67     // operators
  68     //////////////////////////////////////////////////////////////////////////
  69     namespace detail {
  70         template <>
  71         struct comparable_operators<map_tag> {
  72             static constexpr bool value = true;
  73         };
  74     }
  75
  76     //////////////////////////////////////////////////////////////////////////
  77     // map
  78     //////////////////////////////////////////////////////////////////////////
  79     //! @cond
  80     namespace detail {
  81         template <typename ...>
  82         struct storage_is_default_constructible;
  83         template <typename ...T>
  84         struct storage_is_default_constructible<hana::basic_tuple<T...>> {
  85             static constexpr bool value = detail::fast_and<
  86                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T)...
  87             >::value;
  88         };
  89
  90         template <typename ...>
  91         struct storage_is_copy_constructible;
  92         template <typename ...T>
  93         struct storage_is_copy_constructible<hana::basic_tuple<T...>> {
  94             static constexpr bool value = detail::fast_and<
  95                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T const&)...
  96             >::value;
  97         };
  98
  99         template <typename ...>
 100         struct storage_is_move_constructible;
 101         template <typename ...T>
 102         struct storage_is_move_constructible<hana::basic_tuple<T...>> {
 103             static constexpr bool value = detail::fast_and<
 104                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T&&)...
 105             >::value;
 106         };
 107
 108         template <typename ...>
 109         struct storage_is_copy_assignable;
 110         template <typename ...T>
 111         struct storage_is_copy_assignable<hana::basic_tuple<T...>> {
 112             static constexpr bool value = detail::fast_and<
 113                 BOOST_HANA_TT_IS_ASSIGNABLE(T, T const&)...
 114             >::value;
 115         };
 116
 117         template <typename ...>
 118         struct storage_is_move_assignable;
 119         template <typename ...T>
 120         struct storage_is_move_assignable<hana::basic_tuple<T...>> {
 121             static constexpr bool value = detail::fast_and<
 122                 BOOST_HANA_TT_IS_ASSIGNABLE(T, T&&)...
 123             >::value;
 124         };
 125
 126         template <typename HashTable, typename Storage>
 127         struct map_impl
 128             : detail::searchable_operators<map_impl<HashTable, Storage>>
 129             , detail::operators::adl<map_impl<HashTable, Storage>>
 130         {
 131             using hash_table_type = HashTable;
 132             using storage_type = Storage;
 133
 134             Storage storage;
 135
 136             using hana_tag = map_tag;
 137
 138             template <typename ...P, typename = typename std::enable_if<
 139                 std::is_same<
 140                     Storage,
 141                     hana::basic_tuple<typename detail::decay<P>::type...>
 142                 >::value
 143             >::type>
 144             explicit constexpr map_impl(P&& ...pairs)
 145                 : storage{static_cast<P&&>(pairs)...}
 146             { }
 147
 148             explicit constexpr map_impl(Storage&& xs)
 149                 : storage(static_cast<Storage&&>(xs))
 150             { }
 151
 152             template <typename ...Dummy, typename = typename std::enable_if<
 153                 detail::storage_is_default_constructible<Storage, Dummy...>::value
 154             >::type>
 155             constexpr map_impl()
 156                 : storage()
 157             { }
 158
 159             template <typename ...Dummy, typename = typename std::enable_if<
 160                 detail::storage_is_copy_constructible<Storage, Dummy...>::value
 161             >::type>
 162             constexpr map_impl(map_impl const& other)
 163                 : storage(other.storage)
 164             { }
 165
 166             template <typename ...Dummy, typename = typename std::enable_if<
 167                 detail::storage_is_move_constructible<Storage, Dummy...>::value
 168             >::type>
 169             constexpr map_impl(map_impl&& other)
 170                 : storage(static_cast<Storage&&>(other.storage))
 171             { }
 172
 173             template <typename ...Dummy, typename = typename std::enable_if<
 174                 detail::storage_is_move_assignable<Storage, Dummy...>::value
 175             >::type>
 176             constexpr map_impl& operator=(map_impl&& other) {
 177                 storage = static_cast<Storage&&>(other.storage);
 178                 return *this;
 179             }
 180
 181             template <typename ...Dummy, typename = typename std::enable_if<
 182                 detail::storage_is_copy_assignable<Storage, Dummy...>::value
 183             >::type>
 184             constexpr map_impl& operator=(map_impl const& other) {
 185                 storage = other.storage;
 186                 return *this;
 187             }
 188
 189             // Prevent the compiler from defining the default copy and move
 190             // constructors, which interfere with the SFINAE above.
 191             ~map_impl() = default;
 192         };
 193         //! @endcond
 194
 195         template <typename Storage>
 196         struct KeyAtIndex {
 197             template <std::size_t i>
 198             using apply = decltype(hana::first(hana::at_c<i>(std::declval<Storage>())));
 199         };
 200
 201         template <typename ...Pairs>
 202         struct make_map_type {
 203             using Storage = hana::basic_tuple<Pairs...>;
 204             using HashTable = typename detail::make_hash_table<
 205                 detail::KeyAtIndex<Storage>::template apply, sizeof...(Pairs)
 206             >::type;
 207             using type = detail::map_impl<HashTable, Storage>;
 208         };
 209     }
 210
 211     //////////////////////////////////////////////////////////////////////////
 212     // make<map_tag>
 213     //////////////////////////////////////////////////////////////////////////
 214     template <>
 215     struct make_impl<map_tag> {
 216         template <typename ...Pairs>
 217         static constexpr auto apply(Pairs&& ...pairs) {
 218 #if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE)
 219             static_assert(detail::fast_and<hana::Product<Pairs>::value...>::value,
 220             "hana::make_map(pairs...) requires all the 'pairs' to be Products");
 221
 222             static_assert(detail::fast_and<
 223                 hana::Comparable<decltype(hana::first(pairs))>::value...
 224             >::value,
 225             "hana::make_map(pairs...) requires all the keys to be Comparable");
 226
 227             static_assert(detail::fast_and<
 228                 hana::Constant<
 229                     decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
 230                 >::value...
 231             >::value,
 232             "hana::make_map(pairs...) requires all the keys to be "
 233             "Comparable at compile-time");
 234
 235             //! @todo
 236             //! This can be implemented more efficiently by doing the check
 237             //! inside each bucket instead.
 238             static_assert(!detail::has_duplicates<decltype(hana::first(pairs))...>::value,
 239             "hana::make_map({keys, values}...) requires all the keys to be unique");
 240
 241             static_assert(!detail::has_duplicates<decltype(hana::hash(hana::first(pairs)))...>::value,
 242             "hana::make_map({keys, values}...) requires all the keys to have different hashes");
 243 #endif
 244
 245             using Map = typename detail::make_map_type<typename detail::decay<Pairs>::type...>::type;
 246             return Map{hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...)};
 247         }
 248     };
 249
 250     //////////////////////////////////////////////////////////////////////////
 251     // keys
 252     //////////////////////////////////////////////////////////////////////////
 253     template <>
 254     struct keys_impl<map_tag> {
 255         template <typename Map>
 256         static constexpr decltype(auto) apply(Map&& map) {
 257             return hana::transform(static_cast<Map&&>(map).storage, hana::first);
 258         }
 259     };
 260
 261     //////////////////////////////////////////////////////////////////////////
 262     // values
 263     //////////////////////////////////////////////////////////////////////////
 264     //! @cond
 265     template <typename Map>
 266     constexpr decltype(auto) values_t::operator()(Map&& map) const {
 267         return hana::transform(static_cast<Map&&>(map).storage, hana::second);
 268     }
 269     //! @endcond
 270
 271     //////////////////////////////////////////////////////////////////////////
 272     // insert
 273     //////////////////////////////////////////////////////////////////////////
 274     template <>
 275     struct insert_impl<map_tag> {
 276         template <typename Map, typename Pair>
 277         static constexpr auto helper(Map&& map, Pair&& pair, ...) {
 278             using RawMap = typename std::remove_reference<Map>::type;
 279             using HashTable = typename RawMap::hash_table_type;
 280             using NewHashTable = typename detail::bucket_insert<
 281                 HashTable,
 282                 decltype(hana::first(pair)),
 283                 decltype(hana::length(map.storage))::value
 284             >::type;
 285
 286             using NewStorage = decltype(
 287                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
 288             );
 289             return detail::map_impl<NewHashTable, NewStorage>(
 290                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
 291             );
 292         }
 293
 294         template <typename Map, typename Pair, std::size_t i>
 295         static constexpr auto
 296         helper(Map&& map, Pair&&,
 297                hana::optional<std::integral_constant<std::size_t, i>>)
 298         {
 299             return static_cast<Map&&>(map);
 300         }
 301
 302         //! @todo
 303         //! Here, we insert only if the key is not already in the map.
 304         //! This should be handled by `bucket_insert`, and that would also
 305         //! be more efficient.
 306         template <typename Map, typename Pair>
 307         static constexpr auto apply(Map&& map, Pair&& pair) {
 308             using RawMap = typename std::remove_reference<Map>::type;
 309             using Storage = typename RawMap::storage_type;
 310             using HashTable = typename RawMap::hash_table_type;
 311             using Key = decltype(hana::first(pair));
 312             using MaybeIndex = typename detail::find_index<
 313               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 314             >::type;
 315             return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{});
 316         }
 317     };
 318
 319     //////////////////////////////////////////////////////////////////////////
 320     // erase_key
 321     //////////////////////////////////////////////////////////////////////////
 322     template <>
 323     struct erase_key_impl<map_tag> {
 324         //! @todo
 325         //! We could implement some kind of `bucket_erase` metafunction
 326         //! that would be much more efficient than this.
 327         template <typename Map, typename Key>
 328         static constexpr auto
 329         erase_key_helper(Map&& map, Key const&, hana::false_) {
 330             return static_cast<Map&&>(map);
 331         }
 332
 333         template <typename Map, typename Key>
 334         static constexpr auto
 335         erase_key_helper(Map&& map, Key const& key, hana::true_) {
 336             return hana::unpack(
 337                 hana::remove_if(static_cast<Map&&>(map).storage,
 338                                 hana::on(hana::equal.to(key), hana::first)),
 339                 hana::make_map
 340             );
 341         }
 342
 343         template <typename Map, typename Key>
 344         static constexpr auto apply_impl(Map&& map, Key const& key, hana::false_) {
 345             return erase_key_helper(static_cast<Map&&>(map), key,
 346                                     hana::contains(map, key));
 347         }
 348
 349         template <typename Map, typename Key>
 350         static constexpr auto apply_impl(Map&& map, Key const&, hana::true_) {
 351             return static_cast<Map&&>(map);
 352         }
 353
 354         template <typename Map, typename Key>
 355         static constexpr auto apply(Map&& map, Key const& key) {
 356             constexpr bool is_empty = decltype(hana::length(map))::value == 0;
 357             return apply_impl(static_cast<Map&&>(map), key, hana::bool_<is_empty>{});
 358         }
 359     };
 360
 361     //////////////////////////////////////////////////////////////////////////
 362     // Comparable
 363     //////////////////////////////////////////////////////////////////////////
 364     template <>
 365     struct equal_impl<map_tag, map_tag> {
 366         template <typename M1, typename M2>
 367         static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
 368             return hana::false_c;
 369         }
 370
 371         template <typename M1, typename M2>
 372         static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) {
 373             return hana::all_of(hana::keys(m1), hana::demux(equal)(
 374                 hana::partial(hana::find, m1),
 375                 hana::partial(hana::find, m2)
 376             ));
 377         }
 378
 379         template <typename M1, typename M2>
 380         static constexpr auto apply(M1 const& m1, M2 const& m2) {
 381             return equal_impl::equal_helper(m1, m2, hana::bool_c<
 382                 decltype(hana::length(m1.storage))::value ==
 383                 decltype(hana::length(m2.storage))::value
 384             >);
 385         }
 386     };
 387
 388     //////////////////////////////////////////////////////////////////////////
 389     // Searchable
 390     //////////////////////////////////////////////////////////////////////////
 391     template <>
 392     struct find_impl<map_tag> {
 393         template <typename Map>
 394         static constexpr auto find_helper(Map&&, ...) {
 395             return hana::nothing;
 396         }
 397
 398         template <typename Map, std::size_t i>
 399         static constexpr auto
 400         find_helper(Map&& map, hana::optional<std::integral_constant<std::size_t, i>>) {
 401             return hana::just(hana::second(hana::at_c<i>(static_cast<Map&&>(map).storage)));
 402         }
 403
 404         template <typename Map, typename Key>
 405         static constexpr auto apply(Map&& map, Key const&) {
 406             using RawMap = typename std::remove_reference<Map>::type;
 407             using Storage = typename RawMap::storage_type;
 408             using HashTable = typename RawMap::hash_table_type;
 409             using MaybeIndex = typename detail::find_index<
 410               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 411             >::type;
 412             return find_helper(static_cast<Map&&>(map), MaybeIndex{});
 413         }
 414     };
 415
 416     template <>
 417     struct find_if_impl<map_tag> {
 418         template <typename M, typename Pred>
 419         static constexpr auto apply(M&& map, Pred&& pred) {
 420             return hana::transform(
 421                 hana::find_if(static_cast<M&&>(map).storage,
 422                     hana::compose(static_cast<Pred&&>(pred), hana::first)),
 423                 hana::second
 424             );
 425         }
 426     };
 427
 428     template <>
 429     struct contains_impl<map_tag> {
 430         template <typename Map, typename Key>
 431         static constexpr auto apply(Map const&, Key const&) {
 432             using RawMap = typename std::remove_reference<Map>::type;
 433             using HashTable = typename RawMap::hash_table_type;
 434             using Storage = typename RawMap::storage_type;
 435             using MaybeIndex = typename detail::find_index<
 436                 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 437             >::type;
 438             return hana::bool_<!decltype(hana::is_nothing(MaybeIndex{}))::value>{};
 439         }
 440     };
 441
 442     template <>
 443     struct any_of_impl<map_tag> {
 444         template <typename M, typename Pred>
 445         static constexpr auto apply(M const& map, Pred const& pred)
 446         { return hana::any_of(hana::keys(map), pred); }
 447     };
 448
 449     template <>
 450     struct is_subset_impl<map_tag, map_tag> {
 451         template <typename Ys>
 452         struct all_contained {
 453             Ys const& ys;
 454             template <typename ...X>
 455             constexpr auto operator()(X const& ...x) const {
 456                 return hana::bool_c<detail::fast_and<
 457                     hana::value<decltype(hana::contains(ys, x))>()...
 458                 >::value>;
 459             }
 460         };
 461
 462         template <typename Xs, typename Ys>
 463         static constexpr auto apply(Xs const& xs, Ys const& ys) {
 464             auto ys_keys = hana::keys(ys);
 465             return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys});
 466         }
 467     };
 468
 469     template <>
 470     struct at_key_impl<map_tag> {
 471         template <typename Map, typename Key>
 472         static constexpr decltype(auto) apply(Map&& map, Key const&) {
 473             using RawMap = typename std::remove_reference<Map>::type;
 474             using HashTable = typename RawMap::hash_table_type;
 475             using Storage = typename RawMap::storage_type;
 476             using MaybeIndex = typename detail::find_index<
 477                 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 478             >::type;
 479             static_assert(!decltype(hana::is_nothing(MaybeIndex{}))::value,
 480                 "hana::at_key(map, key) requires the 'key' to be present in the 'map'");
 481             constexpr std::size_t index = decltype(*MaybeIndex{}){}();
 482             return hana::second(hana::at_c<index>(static_cast<Map&&>(map).storage));
 483         }
 484     };
 485
 486     //////////////////////////////////////////////////////////////////////////
 487     // union_
 488     //////////////////////////////////////////////////////////////////////////
 489     template <>
 490     struct union_impl<map_tag> {
 491         template <typename Xs, typename Ys>
 492         static constexpr auto apply(Xs&& xs, Ys&& ys) {
 493             return hana::fold_left(static_cast<Xs&&>(xs), static_cast<Ys&&>(ys),
 494                                    hana::insert);
 495         }
 496     };
 497
 498     //////////////////////////////////////////////////////////////////////////
 499     // intersection_
 500     //////////////////////////////////////////////////////////////////////////
 501     namespace detail {
 502         template <typename Ys>
 503         struct map_insert_if_contains {
 504             Ys const& ys;
 505
 506             // Second template param will be pair
 507             // Get its key and check if it exists, if it does, insert key, value pair.
 508             template <typename Result, typename Pair>
 509             static constexpr auto helper(Result&& result, Pair&& pair, hana::true_) {
 510                 return hana::insert(static_cast<Result&&>(result), static_cast<Pair&&>(pair));
 511             }
 512
 513             template <typename Result, typename Pair>
 514             static constexpr auto helper(Result&& result, Pair&&, hana::false_) {
 515                 return static_cast<Result&&>(result);
 516             }
 517
 518             template <typename Result, typename Pair>
 519             constexpr auto operator()(Result&& result, Pair&& pair) const {
 520                 constexpr bool keep = hana::value<decltype(hana::contains(ys, hana::first(pair)))>();
 521                 return map_insert_if_contains::helper(static_cast<Result&&>(result),
 522                                                       static_cast<Pair&&>(pair),
 523                                                       hana::bool_c<keep>);
 524             }
 525         };
 526     }
 527
 528     template <>
 529     struct intersection_impl<map_tag> {
 530         template <typename Xs, typename Ys>
 531         static constexpr auto apply(Xs&& xs, Ys const& ys) {
 532             return hana::fold_left(static_cast<Xs&&>(xs), hana::make_map(),
 533                                    detail::map_insert_if_contains<Ys>{ys});
 534         }
 535     };
 536
 537     //////////////////////////////////////////////////////////////////////////
 538     // difference
 539     //////////////////////////////////////////////////////////////////////////
 540     template <>
 541     struct difference_impl<map_tag> {
 542         template <typename Xs, typename Ys>
 543         static constexpr auto apply(Xs&& xs, Ys&& ys) {
 544             return hana::fold_left(
 545                     hana::keys(static_cast<Ys&&>(ys)),
 546                     static_cast<Xs&&>(xs),
 547                     hana::erase_key);
 548         }
 549     };
 550
 551     //////////////////////////////////////////////////////////////////////////
 552     // Foldable
 553     //////////////////////////////////////////////////////////////////////////
 554     template <>
 555     struct unpack_impl<map_tag> {
 556         template <typename M, typename F>
 557         static constexpr decltype(auto) apply(M&& map, F&& f) {
 558             return hana::unpack(static_cast<M&&>(map).storage,
 559                                 static_cast<F&&>(f));
 560         }
 561     };
 562
 563     //////////////////////////////////////////////////////////////////////////
 564     // Construction from a Foldable
 565     //////////////////////////////////////////////////////////////////////////
 566     template <typename F>
 567     struct to_impl<map_tag, F, when<hana::Foldable<F>::value>> {
 568         template <typename Xs>
 569         static constexpr decltype(auto) apply(Xs&& xs) {
 570             return hana::fold_left(
 571                 static_cast<Xs&&>(xs), hana::make_map(), hana::insert
 572             );
 573         }
 574     };
 575 BOOST_HANA_NAMESPACE_END
 576
 577 #endif // !BOOST_HANA_MAP_HPP