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 VM_HASH_MAP_H_
#define VM_HASH_MAP_H_

#include "vm/zone.h"

namespace dart {

template <typename KeyValueTrait>
class DirectChainedHashMap: public ValueObject {
 public:
  DirectChainedHashMap() : array_size_(0),
                           lists_size_(0),
                           count_(0),
                           array_(NULL),
                           lists_(NULL),
                           free_list_head_(kNil) {
    ResizeLists(kInitialSize);
    Resize(kInitialSize);
  }

  DirectChainedHashMap(const DirectChainedHashMap& other);

  void Insert(typename KeyValueTrait::Pair kv);

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

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

  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;
    }
  }

 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.
};


template <typename KeyValueTrait>
typename KeyValueTrait::Value
    DirectChainedHashMap<KeyValueTrait>::
        Lookup(typename KeyValueTrait::Key key) const {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

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

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


template <typename KeyValueTrait>
DirectChainedHashMap<KeyValueTrait>::
    DirectChainedHashMap(const DirectChainedHashMap& other)
  : ValueObject(),
    array_size_(other.array_size_),
    lists_size_(other.lists_size_),
    count_(other.count_),
    array_(Thread::Current()->zone()->
           Alloc<HashMapListElement>(other.array_size_)),
    lists_(Thread::Current()->zone()->
           Alloc<HashMapListElement>(other.lists_size_)),
    free_list_head_(other.free_list_head_) {
  memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
  memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
}


template <typename KeyValueTrait>
void DirectChainedHashMap<KeyValueTrait>::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 =
      Thread::Current()->zone()->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);
}


template <typename T>
void DirectChainedHashMap<T>::ResizeLists(intptr_t new_size) {
  ASSERT(new_size > lists_size_);

  HashMapListElement* new_lists =
      Thread::Current()->zone()->
      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) {
    memmove(lists_, old_lists, old_size * sizeof(HashMapListElement));
  }
  for (intptr_t i = old_size; i < lists_size_; ++i) {
    lists_[i].next = free_list_head_;
    free_list_head_ = i;
  }
}


template <typename KeyValueTrait>
void DirectChainedHashMap<KeyValueTrait>::
    Insert(typename KeyValueTrait::Pair kv) {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());

  ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
  // 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(
      static_cast<uword>(KeyValueTrait::Hashcode(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 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 intptr_t Hashcode(Key key) {
    return key->Hashcode();
  }

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

}  // namespace dart

#endif  // VM_HASH_MAP_H_