v8::internal::StringHasher Class Reference

#include <objects.h>

Inheritance diagram for v8::internal::StringHasher:

Collaboration diagram for v8::internal::StringHasher:

Public Member Functions
	StringHasher (int length, uint32_t seed)
	INLINE (static uint32_t AddCharacterCore(uint32_t running_hash, uint16_t c))
	INLINE (static uint32_t GetHashCore(uint32_t running_hash))

Static Public Member Functions
template<typename schar >
static uint32_t	HashSequentialString (const schar *chars, int length, uint32_t seed)
static uint32_t	ComputeUtf8Hash (Vector< const char > chars, uint32_t seed, int *utf16_length_out)
static uint32_t	MakeArrayIndexHash (uint32_t value, int length)

Static Public Attributes
static const int	kZeroHash = 27

Protected Member Functions
uint32_t	GetHashField ()
bool	has_trivial_hash ()
template<typename Char >
void	AddCharacters (const Char *chars, int len)

Private Member Functions
void	AddCharacter (uint16_t c)
bool	UpdateIndex (uint16_t c)
	DISALLOW_COPY_AND_ASSIGN (StringHasher)

Private Attributes
int	length_
uint32_t	raw_running_hash_
uint32_t	array_index_
bool	is_array_index_
bool	is_first_char_

Detailed Description

Definition at line 8341 of file objects.h.

Constructor & Destructor Documentation

StringHasher()

v8::internal::StringHasher::StringHasher ( int  length, uint32_t  seed  )

inlineexplicit

Definition at line 6478 of file objects-inl.h.

  : length_(length),
    raw_running_hash_(seed),
    array_index_(0),
    is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize),
    is_first_char_(true) {
  DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
}

References DCHECK, and raw_running_hash_.

Member Function Documentation

AddCharacter()

void v8::internal::StringHasher::AddCharacter ( uint16_t  c )

inlineprivate

Definition at line 6512 of file objects-inl.h.

                                          {
  // Use the Jenkins one-at-a-time hash function to update the hash
  // for the given character.
  raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
}

References raw_running_hash_.

Referenced by AddCharacters(), and ComputeUtf8Hash().

Here is the caller graph for this function:

AddCharacters()

template<typename Char >

void v8::internal::StringHasher::AddCharacters ( const Char *  chars, int  len  )

inlineprotected

Definition at line 6543 of file objects-inl.h.

                                                                     {
  DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
  int i = 0;
  if (is_array_index_) {
    for (; i < length; i++) {
      AddCharacter(chars[i]);
      if (!UpdateIndex(chars[i])) {
        i++;
        break;
      }
    }
  }
  for (; i < length; i++) {
    DCHECK(!is_array_index_);
    AddCharacter(chars[i]);
  }
}

References AddCharacter(), DCHECK, is_array_index_, and UpdateIndex().

Referenced by HashSequentialString(), v8::internal::IteratingStringHasher::VisitOneByteString(), and v8::internal::IteratingStringHasher::VisitTwoByteString().

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeUtf8Hash()

uint32_t v8::internal::StringHasher::ComputeUtf8Hash ( Vector< const char >  chars, uint32_t  seed, int *  utf16_length_out  )

static

Definition at line 8956 of file objects.cc.

                                                              {
  int vector_length = chars.length();
  // Handle some edge cases
  if (vector_length <= 1) {
    DCHECK(vector_length == 0 ||
           static_cast<uint8_t>(chars.start()[0]) <=
               unibrow::Utf8::kMaxOneByteChar);
    *utf16_length_out = vector_length;
    return HashSequentialString(chars.start(), vector_length, seed);
  }
  // Start with a fake length which won't affect computation.
  // It will be updated later.
  StringHasher hasher(String::kMaxArrayIndexSize, seed);
  unsigned remaining = static_cast<unsigned>(vector_length);
  const uint8_t* stream = reinterpret_cast<const uint8_t*>(chars.start());
  int utf16_length = 0;
  bool is_index = true;
  DCHECK(hasher.is_array_index_);
  while (remaining > 0) {
    unsigned consumed = 0;
    uint32_t c = unibrow::Utf8::ValueOf(stream, remaining, &consumed);
    DCHECK(consumed > 0 && consumed <= remaining);
    stream += consumed;
    remaining -= consumed;
    bool is_two_characters = c > unibrow::Utf16::kMaxNonSurrogateCharCode;
    utf16_length += is_two_characters ? 2 : 1;
    // No need to keep hashing. But we do need to calculate utf16_length.
    if (utf16_length > String::kMaxHashCalcLength) continue;
    if (is_two_characters) {
      uint16_t c1 = unibrow::Utf16::LeadSurrogate(c);
      uint16_t c2 = unibrow::Utf16::TrailSurrogate(c);
      hasher.AddCharacter(c1);
      hasher.AddCharacter(c2);
      if (is_index) is_index = hasher.UpdateIndex(c1);
      if (is_index) is_index = hasher.UpdateIndex(c2);
    } else {
      hasher.AddCharacter(c);
      if (is_index) is_index = hasher.UpdateIndex(c);
    }
  }
  *utf16_length_out = static_cast<int>(utf16_length);
  // Must set length here so that hash computation is correct.
  hasher.length_ = utf16_length;
  return hasher.GetHashField();
}

References AddCharacter(), DCHECK, GetHashField(), HashSequentialString(), is_array_index_, v8::internal::String::kMaxArrayIndexSize, v8::internal::String::kMaxHashCalcLength, unibrow::Utf16::kMaxNonSurrogateCharCode, unibrow::Utf8::kMaxOneByteChar, unibrow::Utf16::LeadSurrogate(), v8::internal::Vector< T >::length(), length_, v8::internal::Vector< T >::start(), unibrow::Utf16::TrailSurrogate(), UpdateIndex(), and unibrow::Utf8::ValueOf().

Referenced by v8::internal::Utf8StringKey::Hash().

Here is the call graph for this function:

Here is the caller graph for this function:

DISALLOW_COPY_AND_ASSIGN()

v8::internal::StringHasher::DISALLOW_COPY_AND_ASSIGN ( StringHasher  )

private

GetHashField()

uint32_t v8::internal::StringHasher::GetHashField ( )

protected

Definition at line 8943 of file objects.cc.

                                    {
  if (length_ <= String::kMaxHashCalcLength) {
    if (is_array_index_) {
      return MakeArrayIndexHash(array_index_, length_);
    }
    return (GetHashCore(raw_running_hash_) << String::kHashShift) |
           String::kIsNotArrayIndexMask;
  } else {
    return (length_ << String::kHashShift) | String::kIsNotArrayIndexMask;
  }
}

References array_index_, is_array_index_, v8::internal::Name::kHashShift, v8::internal::Name::kIsNotArrayIndexMask, v8::internal::String::kMaxHashCalcLength, length_, MakeArrayIndexHash(), and raw_running_hash_.

Referenced by ComputeUtf8Hash(), v8::internal::IteratingStringHasher::Hash(), and HashSequentialString().

Here is the call graph for this function:

Here is the caller graph for this function:

has_trivial_hash()

bool v8::internal::StringHasher::has_trivial_hash ( )

inlineprotected

Definition at line 6488 of file objects-inl.h.

                                    {
  return length_ > String::kMaxHashCalcLength;
}

References v8::internal::String::kMaxHashCalcLength, and length_.

Referenced by v8::internal::IteratingStringHasher::Hash(), and HashSequentialString().

Here is the caller graph for this function:

HashSequentialString()

template<typename schar >

uint32_t v8::internal::StringHasher::HashSequentialString ( const schar *  chars, int  length, uint32_t  seed  )

inlinestatic

Definition at line 6563 of file objects-inl.h.

                                                           {
  StringHasher hasher(length, seed);
  if (!hasher.has_trivial_hash()) hasher.AddCharacters(chars, length);
  return hasher.GetHashField();
}

References AddCharacters(), GetHashField(), and has_trivial_hash().

Referenced by ComputeUtf8Hash(), v8::internal::NativeObjectsExplorer::FindOrAddGroupInfo(), v8::internal::HeapObjectsMap::GenerateId(), v8::internal::StringsStorage::GetEntry(), v8::internal::SeqOneByteSubStringKey::Hash(), v8::internal::HeapSnapshotJSONSerializer::INLINE(), and v8::internal::TwoCharHashTableKey::TwoCharHashTableKey().

Here is the call graph for this function:

Here is the caller graph for this function:

INLINE() [1/2]

v8::internal::StringHasher::INLINE

(

static uint32_t

AddCharacterCoreuint32_t running_hash, uint16_t c

)

INLINE() [2/2]

v8::internal::StringHasher::INLINE

(

static uint32_t

GetHashCoreuint32_t running_hash

)

MakeArrayIndexHash()

uint32_t v8::internal::StringHasher::MakeArrayIndexHash ( uint32_t  value, int  length  )

static

Definition at line 8925 of file objects.cc.

                                                                    {
  // For array indexes mix the length into the hash as an array index could
  // be zero.
  DCHECK(length > 0);
  DCHECK(length <= String::kMaxArrayIndexSize);
  DCHECK(TenToThe(String::kMaxCachedArrayIndexLength) <
         (1 << String::kArrayIndexValueBits));
 
  value <<= String::ArrayIndexValueBits::kShift;
  value |= length << String::ArrayIndexLengthBits::kShift;
 
  DCHECK((value & String::kIsNotArrayIndexMask) == 0);
  DCHECK((length > String::kMaxCachedArrayIndexLength) ||
         (value & String::kContainsCachedArrayIndexMask) == 0);
  return value;
}

References DCHECK, v8::internal::String::kArrayIndexValueBits, v8::internal::String::kContainsCachedArrayIndexMask, v8::internal::Name::kIsNotArrayIndexMask, v8::internal::String::kMaxArrayIndexSize, v8::internal::String::kMaxCachedArrayIndexLength, v8::internal::BitFieldBase< T, shift, size, U >::kShift, and v8::internal::TenToThe().

Referenced by GetHashField(), and v8::internal::RUNTIME_FUNCTION().

Here is the call graph for this function:

Here is the caller graph for this function:

UpdateIndex()

bool v8::internal::StringHasher::UpdateIndex ( uint16_t  c )

inlineprivate

Definition at line 6519 of file objects-inl.h.

                                         {
  DCHECK(is_array_index_);
  if (c < '0' || c > '9') {
    is_array_index_ = false;
    return false;
  }
  int d = c - '0';
  if (is_first_char_) {
    is_first_char_ = false;
    if (c == '0' && length_ > 1) {
      is_array_index_ = false;
      return false;
    }
  }
  if (array_index_ > 429496729U - ((d + 2) >> 3)) {
    is_array_index_ = false;
    return false;
  }
  array_index_ = array_index_ * 10 + d;
  return true;
}

References array_index_, DCHECK, is_array_index_, is_first_char_, and length_.

Referenced by AddCharacters(), and ComputeUtf8Hash().

Here is the caller graph for this function:

Member Data Documentation

array_index_

uint32_t v8::internal::StringHasher::array_index_

private

Definition at line 8388 of file objects.h.

Referenced by GetHashField(), and UpdateIndex().

is_array_index_

bool v8::internal::StringHasher::is_array_index_

private

Definition at line 8389 of file objects.h.

Referenced by AddCharacters(), ComputeUtf8Hash(), GetHashField(), and UpdateIndex().

is_first_char_

bool v8::internal::StringHasher::is_first_char_

private

Definition at line 8390 of file objects.h.

Referenced by UpdateIndex().

kZeroHash

const int v8::internal::StringHasher::kZeroHash = 27

static

Definition at line 8363 of file objects.h.

Referenced by v8::internal::TwoCharHashTableKey::TwoCharHashTableKey().

length_

int v8::internal::StringHasher::length_

private

Definition at line 8386 of file objects.h.

Referenced by ComputeUtf8Hash(), GetHashField(), has_trivial_hash(), and UpdateIndex().

raw_running_hash_

uint32_t v8::internal::StringHasher::raw_running_hash_

private

Definition at line 8387 of file objects.h.

Referenced by AddCharacter(), GetHashField(), and StringHasher().

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/objects.h
• /mnt/V8SourceCode/src/objects-inl.h
• /mnt/V8SourceCode/src/objects.cc