find() on 0-sized unordered_map causes division by 0

[TheComet]

We have this edge case in our platform:

const auto map = etl::make_unordered_map<int, int>(
  // {5, 10},
  // {7, 3},
);

const auto it = map.find(5);  // crash

The crash occurs in:

    size_type get_bucket_index(const_key_reference key) const
    {
      return key_hash_function(key) % number_of_buckets;
    }

in

    const_iterator find(const_key_reference key) const
    {
      size_t index = get_bucket_index(key);

because number_of_buckets == 0.

My suggested fix is to clamp the capacity to >=1 like so:

  template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = etl::equal_to<TKey>, typename... TPairs>
  constexpr auto make_unordered_map(TPairs&&... pairs) -> etl::unordered_map<
    TKey,
    T,
    (sizeof...(TPairs) == 0 ? 1 : sizeof...(TPairs)),
    (sizeof...(TPairs) == 0 ? 1 : sizeof...(TPairs)),
    THash,
    TKeyEqual>
  {
    return { etl::forward<TPairs>(pairs)... };
  }

[jwellbelove]

I don't think that a zero size container should be reporting its capacity as 1.

[TheComet]

I don't think that a zero size container should be reporting its capacity as 1.

How would you suggest to fix this edgecase?

[helderTZ]

The division by zero is not the only problem in find() on 0-sized unordered_maps.
Later on it derefrences the pbucket pointer that points to the C-style array of buckets.

bucket_t& bucket = *pbucket;

Thing is, for a capacity zero unordered_map, this will lead to a zero sized C-style array, so this is actually UB and dereferencing garbage/non-owned data. This can cause the next empty() check to succeed and erroneously enter the if when there are no buckets:

// Is the bucket not empty?
if  (!bucket.empty())
{

An early return in find() if number_of_buckets > 0 would prevent this, or adding this check in the if (!bucket.empty()) together with a division by zero protection in get_bucket_index().

size_type get_bucket_index(const K& key) const
    {
      return number_of_buckets > 0 ? 0 : key_hash_function(key) % number_of_buckets;
    }

Not sure which is preferable.

[jwellbelove]

How would you suggest to fix this edgecase?

For a zero sized container, find should return end().

[TheComet]

Adding a if (number_of_buckets == 0) { return end(); } is probably the best solution. number_of_buckets is a compile-time constant so the compiler can remove the check.

I also don't think there is anything wrong with clamping the capacity. Or is there any specific reason why one would want to have a zero-capacity hashmap that actually has no memory, as opposed to a zero-sized hashmap with capacity==1?

[jwellbelove]

A reported capacity of 1 implies that 1 element may be inserted, which would be incorrect for a zero sized container.

[jwellbelove]

Actually this doesn't even compile for me.

const auto map = etl::make_unordered_map<int, int>(
  // {5, 10},
  // {7, 3},
);

const auto it = map.find(5);  // crash

ERROR: nonstandard extension used: zero-sized array in struct/union