// Copyright 2022 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_FORWARDING_TABLE_H_
#define V8_OBJECTS_STRING_FORWARDING_TABLE_H_

#include "src/objects/string.h"

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

namespace v8 {
namespace internal {

// Mapping from forwarding indices (stored in a string's hash field) to
// internalized strings/external resources.
// The table is used to handle string transitions (temporarily until the next
// full GC, during which actual string transitions happen) that overwrite the
// string buffer. In particular these are Internalization and Externalization.
// 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 unused_element() { return Smi::FromInt(0); }
  static constexpr Smi deleted_element() { return Smi::FromInt(1); }

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

  inline int size() const;
  inline bool empty() const;
  // Returns the index of the added record.
  int AddForwardString(String string, String forward_to);
  template <typename T>
  EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
  int AddExternalResourceAndHash(String string, T* resource, uint32_t raw_hash);
  void UpdateForwardString(int index, String forward_to);
  // Returns true when the resource was set. When an external resource is
  // already set for the record, false is returned and the resource not stored.
  // The caller is responsible for disposing the resource.
  template <typename T>
  EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
  bool TryUpdateExternalResource(int index, T* resource);
  String GetForwardString(PtrComprCageBase cage_base, int index) const;
  static Address GetForwardStringAddress(Isolate* isolate, int index);
  V8_EXPORT_PRIVATE uint32_t GetRawHash(PtrComprCageBase cage_base,
                                        int index) const;
  static uint32_t GetRawHashStatic(Isolate* isolate, int index);
  v8::String::ExternalStringResourceBase* GetExternalResource(
      int index, bool* is_one_byte) const;

  template <typename Func>
  V8_INLINE void IterateElements(Func&& callback);
  // Dispose all external resources stored in the table.
  void TearDown();
  void Reset();
  void UpdateAfterEvacuation();

  class Record;

 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_FORWARDING_TABLE_H_