// Copyright 2017 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_OBJECTS_STRING_TABLE_H_
#define V8_OBJECTS_STRING_TABLE_H_

#include "src/common/assert-scope.h"
#include "src/objects/string.h"
#include "src/roots/roots.h"

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

// A generic key for lookups into the string table, which allows heteromorphic
// lookup and on-demand creation of new strings.
class StringTableKey {
 public:
  virtual ~StringTableKey() = default;
  inline StringTableKey(uint32_t raw_hash_field, int length);

  uint32_t raw_hash_field() const {
    DCHECK_NE(0, raw_hash_field_);
    return raw_hash_field_;
  }

  inline uint32_t hash() const;
  int length() const { return length_; }

 protected:
  inline void set_raw_hash_field(uint32_t raw_hash_field);

 private:
  uint32_t raw_hash_field_ = 0;
  int length_;
};

class SeqOneByteString;

// StringTable, for internalizing strings. The Lookup methods are designed to be
// thread-safe, in combination with GC safepoints.
//
// The string table layout is defined by its Data implementation class, see
// StringTable::Data for details.
class V8_EXPORT_PRIVATE StringTable {
 public:
  static constexpr Smi empty_element() { return Smi::FromInt(0); }
  static constexpr Smi deleted_element() { return Smi::FromInt(1); }

  explicit StringTable(Isolate* isolate);
  ~StringTable();

  int Capacity() const;
  int NumberOfElements() const;

  // Find string in the string table. If it is not there yet, it is
  // added. The return value is the string found.
  Handle<String> LookupString(Isolate* isolate, Handle<String> key);

  // Find string in the string table, using the given key. If the string is not
  // there yet, it is created (by the key) and added. The return value is the
  // string found.
  template <typename StringTableKey, typename IsolateT>
  Handle<String> LookupKey(IsolateT* isolate, StringTableKey* key);

  // {raw_string} must be a tagged String pointer.
  // Returns a tagged pointer: either a Smi if the string is an array index, an
  // internalized string, or a Smi sentinel.
  static Address TryStringToIndexOrLookupExisting(Isolate* isolate,
                                                  Address raw_string);

  void Print(PtrComprCageBase cage_base) const;
  size_t GetCurrentMemoryUsage() const;

  // The following methods must be called either while holding the write lock,
  // or while in a Heap safepoint.
  void IterateElements(RootVisitor* visitor);
  void DropOldData();
  void NotifyElementsRemoved(int count);

  void VerifyIfOwnedBy(Isolate* isolate);

 private:
  class Data;

  Data* EnsureCapacity(PtrComprCageBase cage_base, int additional_elements);

  std::atomic<Data*> data_;
  // Write mutex is mutable so that readers of concurrently mutated values (e.g.
  // NumberOfElements) are allowed to lock it while staying const.
  mutable base::Mutex write_mutex_;
  Isolate* isolate_;
};

// Mapping from forwarding indices (stored in a string's hash field) to
// internalized strings.
// The table is organised in "blocks". As writes only append new entries, the
// organisation in blocks allows lock-free writes. We need a lock only for
// growing the table (adding more blocks). When the vector holding the blocks
// needs to grow, we keep a copy of the old vector alive to allow concurrent
// reads while the vector is relocated.
class StringForwardingTable {
 public:
  // Capacity for the first block.
  static constexpr int kInitialBlockSize = 16;
  static_assert(base::bits::IsPowerOfTwo(kInitialBlockSize));
  static constexpr int kInitialBlockSizeHighestBit =
      kBitsPerInt - base::bits::CountLeadingZeros32(kInitialBlockSize) - 1;
  // Initial capacity in the block vector.
  static constexpr int kInitialBlockVectorCapacity = 4;
  static constexpr Smi deleted_element() { return Smi::FromInt(0); }

  explicit StringForwardingTable(Isolate* isolate);
  ~StringForwardingTable();

  inline int Size();
  // Returns the index of the added string pair.
  int Add(Isolate* isolate, String string, String forward_to);
  String GetForwardString(Isolate* isolate, int index) const;
  static Address GetForwardStringAddress(Isolate* isolate, int index);
  void IterateElements(RootVisitor* visitor);
  void Reset();
  void UpdateAfterEvacuation();

 private:
  class Block;
  class BlockVector;

  // Returns the block for a given index and sets the index within this block
  // as out parameter.
  static inline uint32_t BlockForIndex(int index, uint32_t* index_in_block_out);
  static inline uint32_t IndexInBlock(int index, uint32_t block);
  static inline uint32_t CapacityForBlock(uint32_t block);

  void InitializeBlockVector();
  // Ensure that |block| exists in the BlockVector already. If not, a new block
  // is created (with capacity double the capacity of the last block) and
  // inserted into the BlockVector. The BlockVector itself might grow (to double
  // the capacity).
  BlockVector* EnsureCapacity(uint32_t block);

  Isolate* isolate_;
  std::atomic<BlockVector*> blocks_;
  // We need a vector of BlockVectors to keep old BlockVectors alive when we
  // grow the table, due to concurrent reads that may still hold a pointer to
  // them. |block_vector_sotrage_| is only accessed while we grow with the mutex
  // held. All regular access go through |block_|, which holds a pointer to the
  // current BlockVector.
  std::vector<std::unique_ptr<BlockVector>> block_vector_storage_;
  std::atomic<int> next_free_index_;
  base::Mutex grow_mutex_;
};

}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_STRING_TABLE_H_