IntrusiveHashMap.h

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
// Copyright Apache Software Foundation 2019
 
#pragma once
 
#include <vector>
#include <array>
#include <algorithm>
 
#include "swoc/swoc_version.h"
#include "swoc/IntrusiveDList.h"
 
namespace swoc { inline namespace SWOC_VERSION_NS {
template <typename H> class IntrusiveHashMap {
  using self_type = IntrusiveHashMap;
 
public:
  using value_type = typename std::remove_pointer<typename std::remove_reference<decltype(H::next_ptr(nullptr))>::type>::type;
  using key_type = decltype(H::key_of(static_cast<value_type *>(nullptr)));
  using hash_id = decltype(H::hash_of(H::key_of(static_cast<value_type *>(nullptr))));

  enum ExpansionPolicy {
    MANUAL,  
    AVERAGE, 
    MAXIMUM  
  };
 
protected:
  using List = IntrusiveDList<H>;

  struct Bucket {
    struct Linkage {
      static Bucket *&next_ptr(Bucket *b); 
      static Bucket *&prev_ptr(Bucket *b); 
      Bucket *_prev{nullptr};              
      Bucket *_next{nullptr};              
    } _link;
 
    value_type *_v{nullptr}; 
    size_t _count{0};        

    bool _mixed_p{false};

    value_type *limit() const;

    bool contains(value_type *v) const;
 
    void clear(); 
  };
 
public:
  static size_t constexpr DEFAULT_BUCKET_COUNT = 7; 
  static size_t constexpr DEFAULT_EXPANSION_LIMIT = 4; 
  static ExpansionPolicy constexpr DEFAULT_EXPANSION_POLICY = AVERAGE;
 
  using iterator       = typename List::iterator;
  using const_iterator = typename List::const_iterator;

  struct range : public std::pair<iterator, iterator> {
    using super_type = std::pair<iterator, iterator>; 
    using super_type::super_type;                     
 
    // These methods enable treating the range as a view in to the hash map.

    iterator const &begin() const;

    iterator const &end() const;
  };

  struct const_range : public std::pair<const_iterator, const_iterator> {
    using super_type = std::pair<const_iterator, const_iterator>; 

    const_range(range const &r);
 
    using super_type::super_type; 
 
    // These methods enable treating the range as a view in to the hash map.

    const_iterator const &begin() const;

    const_iterator const &end() const;
  };

  IntrusiveHashMap(size_t n = DEFAULT_BUCKET_COUNT);

  IntrusiveHashMap(self_type &&that) = default;

  self_type &clear();
 
  iterator begin();             
  const_iterator begin() const; 
  iterator end();               
  const_iterator end() const;   

  void insert(value_type *v);

  const_iterator find(key_type key) const;
 
  iterator find(key_type key);

  const_iterator find(value_type const *v) const;
 
  iterator find(value_type *v);

  const_range equal_range(key_type key) const;
 
  range equal_range(key_type key);

  iterator iterator_for(value_type *v);
 
  const_iterator iterator_for(const value_type *v) const;

  iterator erase(iterator const &loc);

  iterator erase(range const &r);

  iterator erase(iterator const &start, iterator const &limit);

  bool erase(value_type *value);

  template <typename F> self_type &apply(F &&f);

  void expand();

  size_t count() const;

  size_t bucket_count() const;

  self_type &set_expansion_policy(ExpansionPolicy policy);

  ExpansionPolicy get_expansion_policy() const;

  self_type &set_expansion_limit(size_t n);

  size_t get_expansion_limit() const;
 
protected:
  using Table = std::vector<Bucket>;
 
  List _list;   
  Table _table; 

  IntrusiveDList<typename Bucket::Linkage> _active_buckets;
 
  Bucket *bucket_for(key_type key);
 
  ExpansionPolicy _expansion_policy{DEFAULT_EXPANSION_POLICY}; 
  size_t _expansion_limit{DEFAULT_EXPANSION_LIMIT};            
 
  // noncopyable
  IntrusiveHashMap(const IntrusiveHashMap &) = delete;
 
  IntrusiveHashMap &operator=(const IntrusiveHashMap &) = delete;
 
  // Hash table size prime list.
  static constexpr std::array<size_t, 29> PRIME = {
    {1, 3, 7, 13, 31, 61, 127, 251, 509, 1021,
     2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573,
     2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909}
  };
};
 
template <typename H>
auto
IntrusiveHashMap<H>::Bucket::Linkage::next_ptr(Bucket *b) -> Bucket *& {
  return b->_link._next;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::Bucket::Linkage::prev_ptr(Bucket *b) -> Bucket *& {
  return b->_link._prev;
}
 
// This is designed so that if the bucket is empty, then @c nullptr is returned, which will immediately terminate
// a search loop on an empty bucket because that will start with a nullptr candidate, matching the limit.
template <typename H>
auto
IntrusiveHashMap<H>::Bucket::limit() const -> value_type * {
  Bucket *n{_link._next};
  return n ? n->_v : nullptr;
};
 
template <typename H>
void
IntrusiveHashMap<H>::Bucket::clear() {
  _v       = nullptr;
  _count   = 0;
  _mixed_p = false;
  // Need to clear these, or they persist after an expansion which breaks the active bucket list.
  _link._next = _link._prev = nullptr;
}
 
template <typename H>
bool
IntrusiveHashMap<H>::Bucket::contains(value_type *v) const {
  value_type *x     = _v;
  value_type *limit = this->limit();
  while (x != limit && x != v) {
    x = H::next_ptr(x);
  }
  return x == v;
}
 
// ---------------------
template <typename H>
auto
IntrusiveHashMap<H>::range::begin() const -> iterator const & {
  return super_type::first;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::range::end() const -> iterator const & {
  return super_type::second;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::const_range::begin() const -> const_iterator const & {
  return super_type::first;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::const_range::end() const -> const_iterator const & {
  return super_type::second;
}
 
// ---------------------
 
template <typename H> IntrusiveHashMap<H>::IntrusiveHashMap(size_t n) {
  if (n) {
    _table.resize(*std::lower_bound(PRIME.begin(), PRIME.end(), n));
  }
}
 
template <typename H>
auto
IntrusiveHashMap<H>::bucket_for(key_type key) -> Bucket * {
  return &_table[H::hash_of(key) % _table.size()];
}
 
template <typename H>
auto
IntrusiveHashMap<H>::begin() -> iterator {
  return _list.begin();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::begin() const -> const_iterator {
  return _list.begin();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::end() -> iterator {
  return _list.end();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::end() const -> const_iterator {
  return _list.end();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::clear() -> self_type & {
  for (auto &b : _table) {
    b.clear();
  }
  // Clear container data.
  _list.clear();
  _active_buckets.clear();
  return *this;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::find(key_type key) -> iterator {
  Bucket *b         = this->bucket_for(key);
  value_type *v     = b->_v;
  value_type *limit = b->limit();
  while (v != limit && !H::equal(key, H::key_of(v))) {
    v = H::next_ptr(v);
  }
  return v == limit ? _list.end() : _list.iterator_for(v);
}
 
template <typename H>
auto
IntrusiveHashMap<H>::find(key_type key) const -> const_iterator {
  return const_cast<self_type *>(this)->find(key);
}
 
template <typename H>
auto
IntrusiveHashMap<H>::equal_range(key_type key) -> range {
  iterator first{this->find(key)};
  iterator last{first};
  iterator limit{this->end()};
 
  while (last != limit && H::equal(key, H::key_of(&*last))) {
    ++last;
  }
 
  return range{first, last};
}
 
template <typename H>
auto
IntrusiveHashMap<H>::equal_range(key_type key) const -> const_range {
  return const_cast<self_type *>(this)->equal_range(key);
}
 
template <typename H>
auto
IntrusiveHashMap<H>::iterator_for(const value_type *v) const -> const_iterator {
  return _list.iterator_for(v);
}
 
template <typename H>
auto
IntrusiveHashMap<H>::iterator_for(value_type *v) -> iterator {
  return _list.iterator_for(v);
}
 
template <typename H>
auto
IntrusiveHashMap<H>::find(value_type *v) -> iterator {
  Bucket *b = this->bucket_for(H::key_of(v));
  return b->contains(v) ? _list.iterator_for(v) : this->end();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::find(value_type const *v) const -> const_iterator {
  return const_cast<self_type *>(this)->find(const_cast<value_type *>(v));
}
 
template <typename H>
void
IntrusiveHashMap<H>::insert(value_type *v) {
  auto key         = H::key_of(v);
  Bucket *bucket   = this->bucket_for(key);
  value_type *spot = bucket->_v;
  bool mixed_p     = false; // Found a different key in the bucket.
 
  if (nullptr == spot) { // currently empty bucket, set it and add to active list.
    _list.append(v);
    bucket->_v = v;
    _active_buckets.append(bucket);
  } else {
    value_type *limit = bucket->limit();
 
    // First search the bucket to see if the key is already in it.
    while (spot != limit && !H::equal(key, H::key_of(spot))) {
      spot = H::next_ptr(spot);
    }
    if (spot != bucket->_v) {
      mixed_p = true; // found some other key, it's going to be mixed.
    }
    if (spot != limit) {
      // If an equal key was found, walk past those to insert at the upper end of the range.
      do {
        spot = H::next_ptr(spot);
      } while (spot != limit && H::equal(key, H::key_of(spot)));
      if (spot != limit) { // something not equal past last equivalent, it's going to be mixed.
        mixed_p = true;
      }
    }
 
    _list.insert_before(spot, v);
    if (spot == bucket->_v) { // added before the bucket start, update the start.
      bucket->_v = v;
    }
    bucket->_mixed_p = mixed_p;
  }
  ++bucket->_count;
 
  // auto expand if appropriate.
  if ((AVERAGE == _expansion_policy && (_list.count() / _table.size()) > _expansion_limit) ||
      (MAXIMUM == _expansion_policy && bucket->_count > _expansion_limit && bucket->_mixed_p)) {
    this->expand();
  }
}
 
template <typename H>
auto
IntrusiveHashMap<H>::erase(iterator const &loc) -> iterator {
  value_type *v     = loc;
  iterator zret     = ++(this->iterator_for(v)); // get around no const_iterator -> iterator.
  Bucket *b         = this->bucket_for(H::key_of(v));
  value_type *nv    = H::next_ptr(v);
  value_type *limit = b->limit();
  if (b->_v == v) {    // removed first element in bucket, update bucket
    if (limit == nv) { // that was also the only element, deactivate bucket
      _active_buckets.erase(b);
      b->clear();
    } else {
      b->_v = nv;
      --b->_count;
    }
  }
  _list.erase(loc);
  return zret;
}
 
template <typename H>
bool
IntrusiveHashMap<H>::erase(value_type *value) {
  auto loc = this->find(value);
  if (loc != this->end()) {
    this->erase(loc);
    return true;
  }
  return false;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::erase(iterator const &start, iterator const &limit) -> iterator {
  auto spot{start};
  Bucket *bucket{this->bucket_for(spot)};
  while (spot != limit) {
    auto target         = bucket;
    bucket              = bucket->_link._next; // bump now to avoid forward iteration problems in case of bucket removal.
    value_type *v_limit = bucket ? bucket->_v : nullptr;
    while (spot != v_limit && spot != limit) {
      --(target->_count);
      ++spot;
    }
    if (target->_count == 0) {
      _active_buckets.erase(target);
    }
  }
  _list.erase(start, limit);
  return _list.iterator_for(limit); // convert from const_iterator back to iterator
};
 
template <typename H>
auto
IntrusiveHashMap<H>::erase(range const &r) -> iterator {
  return this->erase(r.first, r.second);
}
 
namespace detail {
// Make @c apply more convenient by allowing the function to take a reference type or pointer type to the container
// elements. The pointer type is the base, plus a shim to convert from a reference type functor to a pointer pointer
// type. The complex return type definition forces only one, but not both, to be valid for a particular functor. This
// also must be done via free functions and not method overloads because the compiler forces a match up of method
// definitions and declarations before any template instantiation.
 
template <typename H, typename F>
auto
IntrusiveHashMapApply(IntrusiveHashMap<H> &map, F &&f)
  -> decltype(f(*static_cast<typename IntrusiveHashMap<H>::value_type *>(nullptr)), map) {
  return map.apply([&f](typename IntrusiveHashMap<H>::value_type *v) { return f(*v); });
}
 
template <typename H, typename F>
auto
IntrusiveHashMapApply(IntrusiveHashMap<H> &map, F &&f)
  -> decltype(f(static_cast<typename IntrusiveHashMap<H>::value_type *>(nullptr)), map) {
  auto spot{map.begin()};
  auto limit{map.end()};
  while (spot != limit) {
    f(spot++); // post increment means @a spot is updated before @a f is applied.
  }
  return map;
}
} // namespace detail
 
template <typename H>
template <typename F>
auto
IntrusiveHashMap<H>::apply(F &&f) -> self_type & {
  return detail::IntrusiveHashMapApply(*this, f);
};
 
template <typename H>
void
IntrusiveHashMap<H>::expand() {
  ExpansionPolicy org_expansion_policy = _expansion_policy; // save for restore.
  value_type *old                      = _list.head();      // save for repopulating.
  auto old_size                        = _table.size();
 
  // Reset to empty state.
  this->clear();
  _table.resize(*std::lower_bound(PRIME.begin(), PRIME.end(), old_size + 1));
 
  _expansion_policy = MANUAL; // disable any auto expand while we're expanding.
  while (old) {
    value_type *v = old;
    old           = H::next_ptr(old);
    this->insert(v);
  }
  // stashed array gets cleaned up when @a tmp goes out of scope.
  _expansion_policy = org_expansion_policy; // reset to original value.
}
 
template <typename H>
size_t
IntrusiveHashMap<H>::count() const {
  return _list.count();
}
 
template <typename H>
size_t
IntrusiveHashMap<H>::bucket_count() const {
  return _table.size();
}
 
template <typename H>
auto
IntrusiveHashMap<H>::set_expansion_policy(ExpansionPolicy policy) -> self_type & {
  _expansion_policy = policy;
  return *this;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::get_expansion_policy() const -> ExpansionPolicy {
  return _expansion_policy;
}
 
template <typename H>
auto
IntrusiveHashMap<H>::set_expansion_limit(size_t n) -> self_type & {
  _expansion_limit = n;
  return *this;
}
 
template <typename H>
size_t
IntrusiveHashMap<H>::get_expansion_limit() const {
  return _expansion_limit;
}
 
}} // namespace swoc::SWOC_VERSION_NS