// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_IDENTITY_MAP_H_
#define V8_IDENTITY_MAP_H_

#include "src/base/functional.h"
#include "src/handles.h"

namespace v8 {
namespace internal {

// Forward declarations.
class Heap;
class Zone;

// Base class of identity maps contains shared code for all template
// instantions.
class IdentityMapBase {
 protected:
  // Allow Tester to access internals, including changing the address of objects
  // within the {keys_} array in order to simulate a moving GC.
  friend class IdentityMapTester;

  typedef void** RawEntry;

  IdentityMapBase(Heap* heap, Zone* zone)
      : heap_(heap),
        zone_(zone),
        gc_counter_(-1),
        size_(0),
        mask_(0),
        keys_(nullptr),
        values_(nullptr) {}
  ~IdentityMapBase();

  RawEntry GetEntry(Object* key);
  RawEntry FindEntry(Object* key);
  void Clear();

 private:
  // Internal implementation should not be called directly by subclasses.
  int LookupIndex(Object* address);
  int InsertIndex(Object* address);
  void Rehash();
  void Resize();
  RawEntry Lookup(Object* key);
  RawEntry Insert(Object* key);
  int Hash(Object* address);

  base::hash<uintptr_t> hasher_;
  Heap* heap_;
  Zone* zone_;
  int gc_counter_;
  int size_;
  int mask_;
  Object** keys_;
  void** values_;
};

// Implements an identity map from object addresses to a given value type {V}.
// The map is robust w.r.t. garbage collection by synchronization with the
// supplied {heap}.
//  * Keys are treated as strong roots.
//  * SMIs are valid keys, except SMI #0.
//  * The value type {V} must be reinterpret_cast'able to {void*}
//  * The value type {V} must not be a heap type.
template <typename V>
class IdentityMap : public IdentityMapBase {
 public:
  IdentityMap(Heap* heap, Zone* zone) : IdentityMapBase(heap, zone) {}

  // Searches this map for the given key using the object's address
  // as the identity, returning:
  //    found => a pointer to the storage location for the value
  //    not found => a pointer to a new storage location for the value
  V* Get(Handle<Object> key) { return Get(*key); }
  V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); }

  // Searches this map for the given key using the object's address
  // as the identity, returning:
  //    found => a pointer to the storage location for the value
  //    not found => {nullptr}
  V* Find(Handle<Object> key) { return Find(*key); }
  V* Find(Object* key) { return reinterpret_cast<V*>(FindEntry(key)); }

  // Set the value for the given key.
  void Set(Handle<Object> key, V v) { Set(*key, v); }
  void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; }

  // Removes all elements from the map.
  void Clear() { IdentityMapBase::Clear(); }
};
}  // namespace internal
}  // namespace v8

#endif  // V8_IDENTITY_MAP_H_