small_map.hpp

Go to the documentation of this file.

#pragma once
 
// SPDX-License-Identifier: BSD-3-Clause
// SPDX-FileCopyrightText: Czech Technical University in Prague
 
#include <algorithm>
#include <list>
#include <mutex>
#include <utility>
 
namespace cras
{
 
template<typename K, typename V>
class SmallMap
{
public:
  V& operator[](const K& key)
  {
    return this->insertIfNew(key);
  }
 
  const V& at(const K& key) const
  {
    const auto searchFn = [&key](const auto& item) {return item.first == key;};
    auto it = ::std::find_if(this->data.begin(), this->data.end(), searchFn);
    if (__builtin_expect(it == this->data.end(), 0))
      throw ::std::out_of_range("Key not found");
    return it->second;
  }
 
  bool contains(const K& key) const
  {
    const auto searchFn = [&key](const auto& item) {return item.first == key;};
    auto it = ::std::find_if(this->data.begin(), this->data.end(), searchFn);
    return it != this->data.end();
  }
 
  template<typename... Args>
  V& insertIfNew(const K& key, Args&&... args)
  {
    const auto searchFn = [&key](const auto& item) {return item.first == key;};
    auto it = ::std::find_if(this->data.begin(), this->data.end(), searchFn);
    if (__builtin_expect(it == this->data.end(), 0))
    {
      ::std::unique_lock<::std::mutex> lock(this->mutex);
      // Check once again with the lock; if key is still not there, insert it, otherwise find it
      it = ::std::find_if(this->data.begin(), this->data.end(), searchFn);
      if (__builtin_expect(it == this->data.end(), 1))
        // Do not use emplace_back - its reference-returning variant is C++17 only
        it = this->data.emplace(this->data.end(), key, V{::std::forward<Args>(args)...});
    }
    return it->second;
  }
 
  size_t size() const
  {
    return this->data.size();
  }
 
  bool empty() const
  {
    return this->data.empty();
  }
 
private:
  ::std::list<::std::pair<K, V>> data;
  ::std::mutex mutex;
};
 
 
template<typename K>
class SmallSet
{
public:
  bool contains(const K& key) const
  {
    return ::std::find(this->data.begin(), this->data.end(), key) != this->data.end();
  }
 
  bool insert(const K& key)
  {
    auto it = std::find(this->data.begin(), this->data.end(), key);
    if (__builtin_expect(it == this->data.end(), 0))
    {
      std::unique_lock<std::mutex> lock(this->mutex);
      // Check once again with the lock; if key is still not there, insert it, otherwise find it
      it = std::find(this->data.begin(), this->data.end(), key);
      if (__builtin_expect(it == this->data.end(), 1))
      {
        this->data.emplace(this->data.end(), key);
        return true;
      }
    }
    return false;
  }
 
  size_t size() const
  {
    return this->data.size();
  }
 
  bool empty() const
  {
    return this->data.empty();
  }
 
private:
  ::std::list<K> data;
  ::std::mutex mutex;
};
 
}