runtime/vm/hash_map.h

// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#ifndef RUNTIME_VM_HASH_MAP_H_
#define RUNTIME_VM_HASH_MAP_H_

#include "platform/utils.h"
#include "vm/growable_array.h"  // For Malloc, EmptyBase
#include "vm/hash.h"
#include "vm/zone.h"

namespace dart {

template <typename KeyValueTrait, typename B, typename Allocator = Zone>
class BaseDirectChainedHashMap : public B {
 public:
  explicit BaseDirectChainedHashMap(Allocator* allocator)
      : array_size_(0),
        lists_size_(0),
        count_(0),
        array_(NULL),
        lists_(NULL),
        free_list_head_(kNil),
        allocator_(allocator) {
    ResizeLists(kInitialSize);
    Resize(kInitialSize);
  }

  BaseDirectChainedHashMap(const BaseDirectChainedHashMap& other);

  intptr_t Length() const { return count_; }

  virtual ~BaseDirectChainedHashMap() {
    allocator_->template Free<HashMapListElement>(array_, array_size_);
    allocator_->template Free<HashMapListElement>(lists_, lists_size_);
  }

  // Assumes that no existing pair in the map has a key equal to [kv.key].
  void Insert(typename KeyValueTrait::Pair kv);
  bool Remove(typename KeyValueTrait::Key key);

  // If a pair already exists in the map with an equal key, replace that pair
  // with this one. Otherwise, insert the pair as a new entry.
  //
  // Note: Insert operates in constant time, while Update must walk the chained
  // entries for a given hash value, checking keys for equality. However, if
  // multiple value updates are needed for the same key, only using Update
  // guarantees constant space usage whereas Insert does not.
  void Update(typename KeyValueTrait::Pair kv);

  typename KeyValueTrait::Value LookupValue(
      typename KeyValueTrait::Key key) const;

  typename KeyValueTrait::Pair* Lookup(typename KeyValueTrait::Key key) const;
  bool HasKey(typename KeyValueTrait::Key key) const {
    return Lookup(key) != NULL;
  }

  intptr_t Size() const { return count_; }
  bool IsEmpty() const { return count_ == 0; }

  virtual void Clear() {
    if (!IsEmpty()) {
      count_ = 0;
      InitArray(array_, array_size_);
      InitArray(lists_, lists_size_);
      lists_[0].next = kNil;
      for (intptr_t i = 1; i < lists_size_; ++i) {
        lists_[i].next = i - 1;
      }
      free_list_head_ = lists_size_ - 1;
    }
  }

  class Iterator {
   public:
    typename KeyValueTrait::Pair* Next();

    void Reset() {
      array_index_ = 0;
      list_index_ = kNil;
    }

   private:
    explicit Iterator(const BaseDirectChainedHashMap& map)
        : map_(map), array_index_(0), list_index_(kNil) {}

    const BaseDirectChainedHashMap& map_;
    intptr_t array_index_;
    intptr_t list_index_;

    template <typename T, typename Bs, typename A>
    friend class BaseDirectChainedHashMap;
  };

  Iterator GetIterator() const { return Iterator(*this); }

 protected:
  // A linked list of T values.  Stored in arrays.
  struct HashMapListElement {
    HashMapListElement() : kv(), next(kNil) {}
    typename KeyValueTrait::Pair kv;
    intptr_t next;  // Index in the array of the next list element.
  };
  static const intptr_t kNil = -1;  // The end of a linked list

  static void InitArray(HashMapListElement* array, intptr_t size) {
    for (intptr_t i = 0; i < size; ++i) {
      array[i] = HashMapListElement();
    }
  }

  // Must be a power of 2.
  static const intptr_t kInitialSize = 16;

  void Resize(intptr_t new_size);
  void ResizeLists(intptr_t new_size);
  uword Bound(uword value) const { return value & (array_size_ - 1); }

  intptr_t array_size_;
  intptr_t lists_size_;
  intptr_t count_;             // The number of values stored in the HashMap.
  HashMapListElement* array_;  // Primary store - contains the first value
  // with a given hash.  Colliding elements are stored in linked lists.
  HashMapListElement* lists_;  // The linked lists containing hash collisions.
  intptr_t free_list_head_;  // Unused elements in lists_ are on the free list.
  Allocator* allocator_;

 private:
  void operator=(const BaseDirectChainedHashMap& other) = delete;
};

template <typename KeyValueTrait, typename B, typename Allocator>
BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::BaseDirectChainedHashMap(
    const BaseDirectChainedHashMap& other)
    : B(),
      array_size_(other.array_size_),
      lists_size_(other.lists_size_),
      count_(other.count_),
      array_(other.allocator_->template Alloc<HashMapListElement>(
          other.array_size_)),
      lists_(other.allocator_->template Alloc<HashMapListElement>(
          other.lists_size_)),
      free_list_head_(other.free_list_head_),
      allocator_(other.allocator_) {
  memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
  memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
}

template <typename KeyValueTrait, typename B, typename Allocator>
typename KeyValueTrait::Pair*
BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Lookup(
    typename KeyValueTrait::Key key) const {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  uword hash = KeyValueTrait::Hash(key);
  uword pos = Bound(hash);
  if (KeyValueTrait::ValueOf(array_[pos].kv) != kNoValue) {
    if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) {
      return &array_[pos].kv;
    }

    intptr_t next = array_[pos].next;
    while (next != kNil) {
      if (KeyValueTrait::IsKeyEqual(lists_[next].kv, key)) {
        return &lists_[next].kv;
      }
      next = lists_[next].next;
    }
  }
  return NULL;
}

template <typename KeyValueTrait, typename B, typename Allocator>
typename KeyValueTrait::Value
BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::LookupValue(
    typename KeyValueTrait::Key key) const {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
  typename KeyValueTrait::Pair* pair = Lookup(key);
  return (pair == NULL) ? kNoValue : KeyValueTrait::ValueOf(*pair);
}

template <typename KeyValueTrait, typename B, typename Allocator>
typename KeyValueTrait::Pair*
BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Iterator::Next() {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  // Return the current lists_ entry (if any), advancing list_index_.
  if (list_index_ != kNil) {
    intptr_t current = list_index_;
    list_index_ = map_.lists_[current].next;
    return &map_.lists_[current].kv;
  }

  // When we're done with the list, we'll continue with the next array
  // slot.
  while ((array_index_ < map_.array_size_) &&
         KeyValueTrait::ValueOf(map_.array_[array_index_].kv) == kNoValue) {
    ++array_index_;
  }
  if (array_index_ < map_.array_size_) {
    const intptr_t old_array_index = array_index_;
    ++array_index_;
    list_index_ = map_.array_[old_array_index].next;
    return &map_.array_[old_array_index].kv;
  }

  return nullptr;
}

template <typename KeyValueTrait, typename B, typename Allocator>
void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Resize(
    intptr_t new_size) {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  ASSERT(new_size > count_);
  // Hashing the values into the new array has no more collisions than in the
  // old hash map, so we can use the existing lists_ array, if we are careful.

  // Make sure we have at least one free element.
  if (free_list_head_ == kNil) {
    ResizeLists(lists_size_ << 1);
  }

  HashMapListElement* new_array =
      allocator_->template Alloc<HashMapListElement>(new_size);
  InitArray(new_array, new_size);

  HashMapListElement* old_array = array_;
  intptr_t old_size = array_size_;

  intptr_t old_count = count_;
  count_ = 0;
  array_size_ = new_size;
  array_ = new_array;

  if (old_array != NULL) {
    // Iterate over all the elements in lists, rehashing them.
    for (intptr_t i = 0; i < old_size; ++i) {
      if (KeyValueTrait::ValueOf(old_array[i].kv) != kNoValue) {
        intptr_t current = old_array[i].next;
        while (current != kNil) {
          Insert(lists_[current].kv);
          intptr_t next = lists_[current].next;
          lists_[current].next = free_list_head_;
          free_list_head_ = current;
          current = next;
        }
        // Rehash the directly stored value.
        Insert(old_array[i].kv);
      }
    }
  }
  USE(old_count);
  ASSERT(count_ == old_count);
  allocator_->template Free<HashMapListElement>(old_array, old_size);
}

template <typename KeyValueTrait, typename B, typename Allocator>
void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::ResizeLists(
    intptr_t new_size) {
  ASSERT(new_size > lists_size_);

  HashMapListElement* new_lists =
      allocator_->template Alloc<HashMapListElement>(new_size);
  InitArray(new_lists, new_size);

  HashMapListElement* old_lists = lists_;
  intptr_t old_size = lists_size_;

  lists_size_ = new_size;
  lists_ = new_lists;

  if (old_lists != NULL) {
    for (intptr_t i = 0; i < old_size; i++) {
      lists_[i] = old_lists[i];
    }
  }
  for (intptr_t i = old_size; i < lists_size_; ++i) {
    lists_[i].next = free_list_head_;
    free_list_head_ = i;
  }
  allocator_->template Free<HashMapListElement>(old_lists, old_size);
}

template <typename KeyValueTrait, typename B, typename Allocator>
void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Insert(
    typename KeyValueTrait::Pair kv) {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
  // TODO(dartbug.com/38018): Add assert that Lookup returns nullptr for key.

  // Resizing when half of the hashtable is filled up.
  if (count_ >= array_size_ >> 1) Resize(array_size_ << 1);
  ASSERT(count_ < array_size_);
  count_++;
  uword pos = Bound(KeyValueTrait::Hash(KeyValueTrait::KeyOf(kv)));
  if (KeyValueTrait::ValueOf(array_[pos].kv) == kNoValue) {
    array_[pos].kv = kv;
    array_[pos].next = kNil;
  } else {
    if (free_list_head_ == kNil) {
      ResizeLists(lists_size_ << 1);
    }
    intptr_t new_element_pos = free_list_head_;
    ASSERT(new_element_pos != kNil);
    free_list_head_ = lists_[free_list_head_].next;
    lists_[new_element_pos].kv = kv;
    lists_[new_element_pos].next = array_[pos].next;
    ASSERT(array_[pos].next == kNil ||
           KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue);
    array_[pos].next = new_element_pos;
  }
}

template <typename KeyValueTrait, typename B, typename Allocator>
void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Update(
    typename KeyValueTrait::Pair kv) {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
  if (auto const old_kv = Lookup(KeyValueTrait::KeyOf(kv))) {
    *old_kv = kv;
  } else {
    Insert(kv);
  }
}

template <typename KeyValueTrait, typename B, typename Allocator>
bool BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Remove(
    typename KeyValueTrait::Key key) {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  uword pos = Bound(KeyValueTrait::Hash(key));

  // Check to see if the first element in the bucket is the one we want to
  // remove.
  if (KeyValueTrait::ValueOf(array_[pos].kv) == kNoValue) return false;
  if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) {
    if (array_[pos].next == kNil) {
      array_[pos] = HashMapListElement();
    } else {
      intptr_t next = array_[pos].next;
      array_[pos] = lists_[next];
      lists_[next] = HashMapListElement();
      lists_[next].next = free_list_head_;
      free_list_head_ = next;
    }
    count_--;
    return true;
  }

  intptr_t current = array_[pos].next;

  // If there's only the single element in the bucket and it does not match the
  // key to be removed, just return.
  if (current == kNil) {
    return false;
  }

  // Check the case where the second element in the bucket is the one to be
  // removed.
  if (KeyValueTrait::IsKeyEqual(lists_[current].kv, key)) {
    array_[pos].next = lists_[current].next;
    lists_[current] = HashMapListElement();
    lists_[current].next = free_list_head_;
    free_list_head_ = current;
    count_--;
    return true;
  }

  // Finally, iterate through the rest of the bucket to see if we can find the
  // entry that matches our key.
  intptr_t previous = -1;
  while (!KeyValueTrait::IsKeyEqual(lists_[current].kv, key)) {
    previous = current;
    current = lists_[current].next;

    if (current == kNil) {
      // Could not find entry with provided key to remove.
      return false;
    }
  }

  lists_[previous].next = lists_[current].next;
  lists_[current] = HashMapListElement();
  lists_[current].next = free_list_head_;
  free_list_head_ = current;
  count_--;
  return true;
}

template <typename KeyValueTrait>
class DirectChainedHashMap
    : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> {
 public:
  DirectChainedHashMap()
      : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(
            ASSERT_NOTNULL(ThreadState::Current()->zone())) {}

  explicit DirectChainedHashMap(Zone* zone)
      : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(
            ASSERT_NOTNULL(zone)) {}

  // There is a current use of the copy constructor in CSEInstructionMap
  // (compiler/backend/redundancy_elimination.cc), so work is needed if we
  // want to disallow it.
  DirectChainedHashMap(const DirectChainedHashMap& other)
      : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>(other) {}

 private:
  void operator=(const DirectChainedHashMap& other) = delete;
};

template <typename KeyValueTrait>
class MallocDirectChainedHashMap
    : public BaseDirectChainedHashMap<KeyValueTrait, MallocAllocated, Malloc> {
 public:
  MallocDirectChainedHashMap()
      : BaseDirectChainedHashMap<KeyValueTrait, MallocAllocated, Malloc>(NULL) {
  }

  // The only use of the copy constructor seems to be in hash_map_test.cc.
  // Not disallowing it for now just in case there are other users.
  MallocDirectChainedHashMap(const MallocDirectChainedHashMap& other)
      : BaseDirectChainedHashMap<KeyValueTrait, MallocAllocated, Malloc>(
            other) {}

 private:
  void operator=(const MallocDirectChainedHashMap& other) = delete;
};

template <typename KeyValueTrait>
class ZoneDirectChainedHashMap
    : public BaseDirectChainedHashMap<KeyValueTrait, ZoneAllocated, Zone> {
 public:
  ZoneDirectChainedHashMap()
      : BaseDirectChainedHashMap<KeyValueTrait, ZoneAllocated, Zone>(
            ThreadState::Current()->zone()) {}
  explicit ZoneDirectChainedHashMap(Zone* zone)
      : BaseDirectChainedHashMap<KeyValueTrait, ZoneAllocated, Zone>(zone) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(ZoneDirectChainedHashMap);
};

template <typename T>
class PointerKeyValueTrait {
 public:
  typedef T* Value;
  typedef T* Key;
  typedef T* Pair;

  static Key KeyOf(Pair kv) { return kv; }

  static Value ValueOf(Pair kv) { return kv; }

  static inline uword Hash(Key key) { return key->Hash(); }

  static inline bool IsKeyEqual(Pair kv, Key key) { return kv->Equals(*key); }
};

template <typename T>
class NumbersKeyValueTrait {
 public:
  typedef T Value;
  typedef intptr_t Key;
  typedef T Pair;

  static intptr_t KeyOf(Pair kv) { return kv.first(); }
  static T ValueOf(Pair kv) { return kv; }
  static inline uword Hash(Key key) { return key; }
  static inline bool IsKeyEqual(Pair kv, Key key) { return kv.first() == key; }
};

template <typename K, typename V>
class RawPointerKeyValueTrait {
 public:
  typedef K* Key;
  typedef V Value;

  struct Pair {
    Key key;
    Value value;
    Pair() : key(NULL), value() {}
    Pair(const Key key, const Value& value) : key(key), value(value) {}
    Pair(const Pair& other) : key(other.key), value(other.value) {}
    Pair& operator=(const Pair&) = default;
  };

  static Key KeyOf(Pair kv) { return kv.key; }
  static Value ValueOf(Pair kv) { return kv.value; }
  static uword Hash(Key key) { return reinterpret_cast<intptr_t>(key); }
  static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; }
};

class CStringSetKeyValueTrait : public PointerKeyValueTrait<const char> {
 public:
  using Key = PointerKeyValueTrait<const char>::Key;
  using Value = PointerKeyValueTrait<const char>::Value;
  using Pair = PointerKeyValueTrait<const char>::Pair;

  static uword Hash(Key key) {
    ASSERT(key != nullptr);
    return Utils::StringHash(key, strlen(key));
  }
  static bool IsKeyEqual(Pair kv, Key key) {
    ASSERT(kv != nullptr && key != nullptr);
    return kv == key || strcmp(kv, key) == 0;
  }
};

template <typename B, typename Allocator>
class BaseCStringSet
    : public BaseDirectChainedHashMap<CStringSetKeyValueTrait, B, Allocator> {
 public:
  explicit BaseCStringSet(Allocator* allocator)
      : BaseDirectChainedHashMap<CStringSetKeyValueTrait, B, Allocator>(
            allocator) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(BaseCStringSet);
};

class ZoneCStringSet : public BaseCStringSet<ZoneAllocated, Zone> {
 public:
  ZoneCStringSet()
      : BaseCStringSet<ZoneAllocated, Zone>(ThreadState::Current()->zone()) {}
  explicit ZoneCStringSet(Zone* zone)
      : BaseCStringSet<ZoneAllocated, Zone>(zone) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(ZoneCStringSet);
};

struct CStringIntMapKeyValueTrait {
  using Key = const char*;
  using Value = intptr_t;

  static constexpr Value kNoValue = kIntptrMin;

  struct Pair {
    Key key;
    Value value;
    Pair() : key(nullptr), value(kNoValue) {}
    Pair(const Key key, const Value& value) : key(key), value(value) {}
    Pair(const Pair& other) : key(other.key), value(other.value) {}
    Pair& operator=(const Pair&) = default;
  };

  static Key KeyOf(const Pair& pair) { return pair.key; }
  static Value ValueOf(const Pair& pair) { return pair.value; }
  static uword Hash(const Key& key) {
    ASSERT(key != nullptr);
    return Utils::StringHash(key, strlen(key));
  }
  static bool IsKeyEqual(const Pair& kv, const Key& key) {
    ASSERT(kv.key != nullptr && key != nullptr);
    return kv.key == key || strcmp(kv.key, key) == 0;
  }
};

template <typename B, typename Allocator>
class BaseCStringIntMap
    : public BaseDirectChainedHashMap<CStringIntMapKeyValueTrait,
                                      B,
                                      Allocator> {
 public:
  explicit BaseCStringIntMap(Allocator* allocator)
      : BaseDirectChainedHashMap<CStringIntMapKeyValueTrait, B, Allocator>(
            allocator) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(BaseCStringIntMap);
};

class CStringIntMap : public BaseCStringIntMap<ValueObject, Zone> {
 public:
  CStringIntMap()
      : BaseCStringIntMap<ValueObject, Zone>(ThreadState::Current()->zone()) {}
  explicit CStringIntMap(Zone* zone)
      : BaseCStringIntMap<ValueObject, Zone>(zone) {}

 private:
  DISALLOW_COPY_AND_ASSIGN(CStringIntMap);
};

template <typename V>
class IntKeyRawPointerValueTrait {
 public:
  typedef intptr_t Key;
  typedef V Value;

  struct Pair {
    Key key;
    Value value;
    Pair() : key(0), value() {}
    Pair(const Key key, const Value& value) : key(key), value(value) {}
    Pair(const Pair& other) : key(other.key), value(other.value) {}
    Pair& operator=(const Pair&) = default;
  };

  static Key KeyOf(Pair kv) { return kv.key; }
  static Value ValueOf(Pair kv) { return kv.value; }
  static uword Hash(Key key) { return key; }
  static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; }
};

template <typename V>
class IntMap : public DirectChainedHashMap<IntKeyRawPointerValueTrait<V> > {
 public:
  IntMap() : DirectChainedHashMap<IntKeyRawPointerValueTrait<V>>() {}
  explicit IntMap(Zone* zone)
      : DirectChainedHashMap<IntKeyRawPointerValueTrait<V>>(zone) {}

  typedef typename IntKeyRawPointerValueTrait<V>::Key Key;
  typedef typename IntKeyRawPointerValueTrait<V>::Value Value;
  typedef typename IntKeyRawPointerValueTrait<V>::Pair Pair;

  inline void Insert(const Key& key, const Value& value) {
    Pair pair(key, value);
    DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Insert(pair);
  }

  inline V Lookup(const Key& key) {
    Pair* pair =
        DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Lookup(key);
    if (pair == NULL) {
      return V();
    } else {
      return pair->value;
    }
  }

  inline Pair* LookupPair(const Key& key) {
    return DirectChainedHashMap<IntKeyRawPointerValueTrait<V> >::Lookup(key);
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(IntMap);
};

template <typename V>
class IdentitySetKeyValueTrait {
 public:
  // Typedefs needed for the DirectChainedHashMap template.
  typedef V Key;
  typedef V Value;
  typedef V Pair;

  static Key KeyOf(Pair kv) { return kv; }

  static Value ValueOf(Pair kv) { return kv; }

  static inline uword Hash(Key key) {
    return Utils::StringHash(reinterpret_cast<const char*>(&key), sizeof(key));
  }

  static inline bool IsKeyEqual(Pair pair, Key key) { return pair == key; }
};

}  // namespace dart

#endif  // RUNTIME_VM_HASH_MAP_H_