v8源码解析之SymbolTable（v8 0.1.5）

theanarkh

发布于 2020-11-02 14:31:59

4240

发布于 2020-11-02 14:31:59

文章被收录于专栏：原创分享

SymbolTable是哈希表的子类，元素大小是一个Object*。SymbolTable主要使用哈希表来存储字符串，给定一个字符串，算出哈希值，然后插入哈希表中。后续根据哈希值进行读取。哈希表本身不负责对元素进行哈希，而是由数据方提供哈希值。哈希表只是根据这个哈希值计算出该元素在哈希表的位置。

class SymbolTable: public HashTable<0, 1> {
 public:
  // 查找str对应的Symbol对象，存到s中，如果没有则新增
  Object* LookupSymbol(Vector<const char> str, Object** s);
  Object* LookupString(String* key, Object** s);

  // Casting.
  static inline SymbolTable* cast(Object* obj);

 private:
  Object* LookupKey(Key* key, Object** s);
  class Utf8Key;   // Key based on utf8 string.
  class StringKey;  // Key based on String*.

  DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable);
};

SymbolTable的定义比较简单，我们看一下具体的实现。1 Utf8Key Utf8Key继承于HashTable::Key，封装了key原始的值、对应的哈希值、原始值对应的堆对象。Utf8Key代表以字符串作为哈希Key。

// Utf8Key carries a vector of chars as key.
class SymbolTable::Utf8Key : public SymbolTable::Key {
 public:
  // key对应的内容 
  explicit Utf8Key(Vector<const char> string)
      : string_(string), hash_(0) { }
  // key是否相等
  bool IsMatch(Object* other) {
    if (!other->IsString()) return false;
    return String::cast(other)->IsEqualTo(string_);
  }
  // 返回哈希函数，由String类提供
  HashFunction GetHashFunction() {
    return StringHash;
  }
  // 哈希函数
  uint32_t Hash() {
    // 计算过了则直接返回
    if (hash_ != 0) return hash_;
    unibrow::Utf8InputBuffer<> buffer(string_.start(),
                                      static_cast<unsigned>(string_.length()));
    chars_ = buffer.Length();
    // 否则用String类提供的函数计算
    hash_ = String::ComputeHashCode(&buffer, chars_);
    return hash_;
  }
  // 根据key申请一个包含了key内容的堆对象
  Object* GetObject() {
    // 还没有计算哈希值则计算
    if (hash_ == 0) Hash();
    unibrow::Utf8InputBuffer<> buffer(string_.start(),
                                      static_cast<unsigned>(string_.length()));
    // 申请一个Symbol对象，实际上是一个字符串对象                                  
    return Heap::AllocateSymbol(&buffer, chars_, hash_);
  }
  // 返回obj的哈希值
  static uint32_t StringHash(Object* obj) {
    return String::cast(obj)->Hash();
  }
  // key是否是字符串
  bool IsStringKey() { return true; }
  // key的字符串值
  Vector<const char> string_;
  // key对应的哈希值
  uint32_t hash_;
  // key字符串的长度
  int chars_;  // Caches the number of characters when computing the hash code.
};

2 StringKey StringKey继承于HashTable::Key，是对哈希表key的管理。StringKey代表以字符串对象作为哈希Key。

class SymbolTable::StringKey : public SymbolTable::Key {
 public:
  explicit StringKey(String* string) : string_(string) { }

  HashFunction GetHashFunction() {
    return StringHash;
  }

  bool IsMatch(Object* other) {
    if (!other->IsString()) return false;
    return String::cast(other)->Equals(string_);
  }

  uint32_t Hash() { return string_->Hash(); }

  Object* GetObject() {
    // 找出字符串对应的map类型
    Map* map = Heap::SymbolMapForString(string_);
    if (map != NULL) {
      string_->set_map(map);
      return string_;
    }
    // Otherwise allocate a new symbol.
    StringInputBuffer buffer(string_);
    return Heap::AllocateSymbol(&buffer, string_->length(), string_->Hash());
  }

  static uint32_t StringHash(Object* obj) {
    return String::cast(obj)->Hash();
  }

  bool IsStringKey() { return true; }

  String* string_;
};

StringKey和Utf8Key类似，都是对key的管理。3 LookupString和LookupSymbol 这两个函数都是对LookupKey的封装。用于通过key查找对应的值。

Object* SymbolTable::LookupString(String* string, Object** s) {
  StringKey key(string);
  return LookupKey(&key, s);
}

Object* SymbolTable::LookupSymbol(Vector<const char> str, Object** s) {
  Utf8Key key(str);
  return LookupKey(&key, s);
}

4 LookupKey

// 从哈希表中查找一个key的值
Object* SymbolTable::LookupKey(Key* key, Object** s) {
  // 根据key找到哈希表中的相对位置，如果存在的话
  int entry = FindEntry(key);

  // 已经存在哈希表，则返回值
  if (entry != -1) {
    *s = KeyAt(entry);
    return this;
  }

  // 不存在则新增，必要的时候扩容
  Object* obj = EnsureCapacity(1, key);
  if (obj->IsFailure()) return obj;

  // 创建key对应的对象
  Object* symbol = key->GetObject();
  if (symbol->IsFailure()) return symbol;

  // If the symbol table grew as part of EnsureCapacity, obj is not
  // the current symbol table and therefore we cannot use
  // SymbolTable::cast here.
  SymbolTable* table = reinterpret_cast<SymbolTable*>(obj);

  // Add the new symbol and return it along with the symbol table.
  // 找到插入的相对位置
  entry = table->FindInsertionEntry(symbol, key->Hash());
  // 算出插入的真正位置，插入哈希表
  table->set(EntryToIndex(entry), symbol);
  // 已使用元素加一
  table->ElementAdded();
  *s = symbol;
  return table;
}

结构如下