text: /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
  /*
   *     Copyright 2016 Couchbase, Inc
   *
   *   Licensed under the Apache License, Version 2.0 (the "License");
   *   you may not use this file except in compliance with the License.
   *   You may obtain a copy of the License at
   *
   *       http://www.apache.org/licenses/LICENSE-2.0
   *
   *   Unless required by applicable law or agreed to in writing, software
   *   distributed under the License is distributed on an "AS IS" BASIS,
   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   *   See the License for the specific language governing permissions and
   *   limitations under the License.
   */
  
  /**
   * AtomicUnorderedMap - A thread-safe map class.
   *
   * AtomicUnorderedMap is a thread-safe unordered map (associative array).
   * Elements can be added, removed and found concurrently from different
   * threads safely.
   *
   *
   * THREAD SAFETY
   * Items are returned by value (instead of via an iterator) - this ensures that
   * once an item is passed back to the caller, it can safely be accessed even if
   * another thread has concurrently deleted it from the map.
   *
   * While this may seen limiting, the value type can be a (smart) pointer if
   * desired, removing the need to copy the actual underlying object. However,
   * if a pointer type is used then operations on the pointed-to objects are
   * *not* automatically thread-safe. In other words, while you can safely call
   * insert(<ptr>) from multiple threads, you *cannot* safely mutate the object
   * pointed to (by the pointer which insert() returns) from multiple threads
   * without additional synchronization. For example, having an per-object
   * mutex, or making the object atomic.
   *
   *
   * FUNCTIONALITY
   * Implements a relatively simple set of operations modeled on
   * std::unordered_map:
   *
   *   - size() to return the number of elements in the map.
   *   - insert() to add an element
   *   - find() to search for an element
   *   - erase() to delete an element
   *   - clear() to delete all elements
   *
   * Iteration, a la `auto it = begin(); it++; ...` isn't directly supported;
   * the main reason is that another thread may have removed an item between
   * calling begin() and moving to the next item, so it's not possible to ensure
   * all elements are acted on. Instead, a number of functions similar to
   * std::algorithm are provided:
   *
   *   - find_if() to search for the first element matching a given predicate.
   *   - for_each() to apply a function to every element in the map.
   *
   *
   * LOCKING STRATEGIES
   * There are two locking strategies available:
   * - Internal locking, where the methods themselves lock on entry (and unlock
   *   on exit).
   * - External locking, where a lock is acquired before calling the methods.
   *
   * For simple use-cases internal locking is sufficient (and safer) - the caller
   * doesn't have to concern themselves with locking, and can rely on the object
   * doing the right thing.
   * However if the caller needs to ensure that multiple operations on the map
   * are atomic (e.g. find()ing an item and then conditionally erase()ing it) then
   * external locking can be used.
   *
   * For example, to atomically remove an key only if it's value is false:
   *
   *     typedef AtomicUnorderedMap<int, bool> M; // Key:int, Value:bool
   *     M map;
   *     ...
   *     { // Create new scope for external lock guard.
   *         std::lock_guard<M> guard(map);
   *         bool it = map.find(key_of_interest, guard);
   *         if (it && *it == false) {
   *             map.erase(it, guard);
   *         }
   *     } // end of scope, map unlocked.
   *
   * Note that the guard is passed into the find() and erase() functions to
   * indicate that an external lock is already acquired (and hence an internal
   * lock should not be acquired).
   *
   * See Boost Synchronization
   * (http://www.boost.org/doc/libs/1_60_0/doc/html/thread/synchronization.html)
   * for more details & background on the internal / external locking strategies
   * used here.
   */
  
  #pragma once
  
  #include "config.h"
  
  #include "atomic.h"
  
  #include <algorithm>
  #include <mutex>
  #include <unordered_map>
  
  template<class Key,
           class T,
           class Hash = std::hash<Key>,
           class KeyEqual = std::equal_to<Key>,
           class Allocator = std::allocator< std::pair<const Key, T> > >
  class AtomicUnorderedMap;
  
  template<class Key, class T, class Hash, class KeyEqual,
           class Allocator>
  class AtomicUnorderedMap {
  public:
  
      using map_type = AtomicUnorderedMap<Key, T, Hash, KeyEqual, Allocator>;
  
      // Alias to simplify all the other defs
      using base_map_type = typename std::unordered_map<Key, T, Hash,
                                                        KeyEqual, Allocator>;
  
      // Map to the type aliases in the underlying map.
      using key_type = typename base_map_type::key_type;
      using mapped_type = typename base_map_type::mapped_type;
      using value_type = typename base_map_type::value_type;
      using size_type = typename base_map_type::size_type;
  
      size_type size() const {
          std::lock_guard<std::mutex> guard(this->mutex); // internally locked
          return map.size();
      }
  
      /* Lookup */
  
      /** Searches for the given key in the map.
       *  Returns a pair consisting of:
       *  - the found element (or a default-constructed element if not found)
       *  - and bool denoting if the given key was found.
       */
      std::pair<T, bool> find(const Key& key, std::lock_guard<map_type>&) {
          // Externally locked)
          auto iter = map.find(key);
          if (iter != map.end()) {
              return {iter->second, true};
          } else {
              return std::make_pair(T(), false);
          }
      }
      std::pair<T, bool> find(const Key& key) {
          std::lock_guard<map_type> guard(*this); // internally locked
          return find(key, guard);
      }
  
      /** Searches for first element which matches the given predicate.
       *  Returns a pair consisting of:
       *  - the first found element (or a default-constructed element if not found)
       *  - and bool denoting if a matching element was found.
       */
      template<class UnaryPredicate>
      std::pair<T, bool>  find_if(UnaryPredicate p) {
          std::lock_guard<map_type> guard(*this); // internally locked
          auto iter = std::find_if(map.begin(), map.end(), p);
          if (iter != map.end()) {
              return {iter->second, true};
          } else {
              return std::make_pair(T(), false);
          }
      }
  
      /* Modifiers */
  
      void clear(std::lock_guard<map_type>&) {
          // Externally locked
          map.clear();
      }
      void clear() {
          std::lock_guard<map_type> guard(*this); // internally locked
          clear(guard);
      }
  
      /** Applies the given function object to every element in the map.
       */
      template<class UnaryFunction>
      void for_each(UnaryFunction f, std::lock_guard<map_type>&) {
          // Externally locked
          std::for_each(map.begin(), map.end(), f);
      }
  
      template<class UnaryFunction>
      void for_each(UnaryFunction f) {
          std::lock_guard<map_type> guard(*this); // internally locked
          for_each(f, guard);
      }
  
      /**
       * Attempts to erase the given key from the map.
       *  Returns a pair consisting of:
       *  - the erased element (or a default-constructed element if not found)
       *  - and bool denoting if the given key was erased.
       */
      std::pair<T, bool> erase(const key_type& key, std::lock_guard<map_type>&) {
          // Externally locked
          auto iter = map.find(key);
          if (iter != map.end()) {
              T result = iter->second;
              map.erase(iter);
              return {result, true};
          } else {
              return std::make_pair(T(), false);
          }
      }
      std::pair<T, bool> erase(const key_type& key) {
          std::lock_guard<map_type> guard(*this); // internally locked
          return erase(key, guard);
      }
  
      /**
       * Attempts to insert the given key into the map, if it does not already
       * exist.
       *  Returns true if the element was inserted, or false if an element
       *  with the given key already exists.
       */
      bool insert(const value_type& value) {
          std::lock_guard<map_type> guard(*this); // internally locked
          auto result = map.insert(value);
          return result.second;
      }
  
      /*
       * Locking
       *
       * Note: Prefer to use RAII-style lock holders (e.g. std::lock_guard<>())
       *       instead of the raw methods here.
       */
  
      /* Explicitly locks the container. */
      void lock() {
          mutex.lock();
      }
  
      void unlock() {
          mutex.unlock();
      }
  
  private:
      std::unordered_map<Key, T, Hash, KeyEqual, Allocator> map;
      mutable std::mutex mutex;
  };
  