util/unordered_set.hpp

   1 /*
   2  * Copyright (c) 2021 Arm Limited.
   3  *
   4  * SPDX-License-Identifier: MIT
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a copy
   7  * of this software and associated documentation files (the "Software"), to
   8  * deal in the Software without restriction, including without limitation the
   9  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  10  * sell copies of the Software, and to permit persons to whom the Software is
  11  * furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in all
  14  * copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24 #pragma once
  25
  26 #include <unordered_set>
  27 #include "custom_allocator.hpp"
  28 #include "optional.hpp"
  29
  30 namespace util
  31 {
  32 /**
  33  * @brief This utility class has the same purpose as std::unordered_set, but
  34  *        ensures that the operations that could result in out of memory
  35  *        exceptions don't throw them and also ensures that the memory can
  36  *        only be allocated by an custom_allocator.
  37  */
  38 template <typename Key,
  39    typename Hash = std::hash<Key>,
  40    typename Comparator = std::equal_to<Key>,
  41    typename Allocator = util::custom_allocator<Key>>
  42 class unordered_set : public std::unordered_set<Key, Hash, Comparator, Allocator>
  43 {
  44    using value_type = Key;
  45    using base = std::unordered_set<Key, Hash, Comparator, Allocator>;
  46    using size_type = typename base::size_type;
  47    using iterator = typename base::iterator;
  48
  49 public:
  50    /**
  51     * Delete all member functions that can cause allocation failure by throwing std::bad_alloc.
  52     */
  53    unordered_set(const unordered_set &) = delete;
  54    unordered_set &operator=(const unordered_set &) = delete;
  55
  56    void insert() = delete;
  57    void emplace() = delete;
  58    void emplace_hint() = delete;
  59    void rehash() = delete;
  60    void reserve() = delete;
  61
  62    /**
  63     * @brief Construct a new unordered set object with a custom allocator.
  64     *
  65     * @param allocator The allocator that will be used.
  66     */
  67    explicit unordered_set(util::custom_allocator<Key> allocator)
  68       : base(allocator)
  69    {
  70    }
  71
  72    /**
  73     * @brief Like std::unordered_set.insert but doesn't throw on out of memory errors.
  74     *
  75     * @param value The value to insert in the map.
  76     * @return util::optional<std::pair<iterator,bool>> If successful, the optional will
  77     *         contain the same return value as from std::unordered_set.insert, otherwise
  78     *         if out of memory, optional will be empty.
  79     */
  80    util::optional<std::pair<iterator, bool>> try_insert(const value_type &value) noexcept
  81    {
  82       try
  83       {
  84          return {base::insert(value)};
  85       }
  86       catch (const std::bad_alloc &e)
  87       {
  88          return {};
  89       }
  90    }
  91
  92    /**
  93     * @brief Like std::unordered_set.reserve but doesn't throw on out of memory errors.
  94     *
  95     * @param size The new capacity of the container. Same as std::unordered_set.reserve.
  96     * @return true If the container was resized successfuly.
  97     * @return false If the host has run out of memory
  98     */
  99    bool try_reserve(size_type size)
 100    {
 101       try
 102       {
 103          base::reserve(size);
 104          return true;
 105       }
 106       catch(std::bad_alloc& e)
 107       {
 108          return false;
 109       }
 110    }
 111
 112    /**
 113     * @brief Like std::unordered_set.rehash but doesn't throw on out of memory errors.
 114     *
 115     * @param count Number of buckets. Same as std::unordered_set.rehash.
 116     * @return true If the container was rehashed successfuly.
 117     * @return false If the host has run out of memory
 118     */
 119    bool try_rehash(size_type count)
 120    {
 121       try
 122       {
 123          base::rehash(count);
 124          return true;
 125       }
 126       catch(std::bad_alloc& e)
 127       {
 128          return false;
 129       }
 130    }
 131 };
 132 } // namespace util