Use new hash table template for compressing token streams.

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 7608 matching lines @@
   const ExternalTypedData& stream = ExternalTypedData::Handle(
       ExternalTypedData::New(kExternalTypedDataUint8ArrayCid,
                              data, len, Heap::kOld));
   stream.AddFinalizer(data, DataFinalizer);
   const TokenStream& result = TokenStream::Handle(TokenStream::New());
   result.SetStream(stream);
   return result.raw();
 }
 
 
+// CompressedTokenMap maps String and LiteralToken keys to Smi values.
+// It also supports lookup by Scanner::TokenDescriptor.
+class CompressedTokenTraits {
+ public:
+  static bool IsMatch(const Scanner::TokenDescriptor& descriptor,
+                      const Object& key) {
+    if (!key.IsLiteralToken()) {
+      return false;
+    }
+    const LiteralToken& token = LiteralToken::Cast(key);
+    return (token.literal() == descriptor.literal->raw()) &&
+           (token.kind() == descriptor.kind);
+  }
+
+  // Only for non-descriptor lookup and table expansion.
+  static bool IsMatch(const Object& a, const Object& b) {
+    return a.raw() == b.raw();
+  }
+
+  static uword Hash(const Scanner::TokenDescriptor& descriptor) {
+    return descriptor.literal->Hash();
+  }
+
+  static uword Hash(const Object& key) {
+    if (key.IsLiteralToken()) {
+      return String::HashRawSymbol(LiteralToken::Cast(key).literal());
+    } else {
+      return String::Cast(key).Hash();
+    }
+  }
+};
+typedef UnorderedHashMap<CompressedTokenTraits> CompressedTokenMap;
+
+
 // Helper class for creation of compressed token stream data.
 class CompressedTokenStreamData : public ValueObject {
  public:
-  static const intptr_t kInitialSize = 16 * KB;
+  static const intptr_t kInitialBufferSize = 16 * KB;
   CompressedTokenStreamData() :
       buffer_(NULL),
-      stream_(&buffer_, Reallocate, kInitialSize),
-      token_objects_(GrowableObjectArray::Handle(
-          GrowableObjectArray::New(kInitialTokenCount, Heap::kOld))),
-      token_obj_(Object::Handle()),
-      literal_token_(LiteralToken::Handle()),
-      literal_str_(String::Handle()) {
-    token_objects_.Add(Object::null_string());
+      stream_(&buffer_, Reallocate, kInitialBufferSize),
+      tokens_(Array::Handle(
+          HashTables::New<CompressedTokenMap>(kInitialTableSize))) {
   }
   ~CompressedTokenStreamData() {
+    // Safe to discard the hash table now.
+    tokens_.Release();
   }
 
-  // Add an IDENT token into the stream and the token objects array.
+  // Add an IDENT token into the stream and the token hash map.
   void AddIdentToken(const String* ident) {
-    // If the IDENT token is already in the tokens object array use the
-    // same index instead of duplicating it.
-    intptr_t index = FindIdentIndex(ident);
-    if (index == -1) {
-      WriteIndex(token_objects_.Length());
-      ASSERT(ident != NULL);
-      token_objects_.Add(*ident);
+    ASSERT(ident->IsSymbol());
+    intptr_t index = tokens_.NumOccupied();
+    intptr_t entry;
+    if (!tokens_.FindKeyOrDeletedOrUnused(*ident, &entry)) {
+      tokens_.InsertKey(entry, *ident);
+      tokens_.UpdatePayload(entry, 0, Smi::Handle(Smi::New(index)));
+      HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, tokens_);
     } else {
-      WriteIndex(index);
+      index = Smi::Value(Smi::RawCast(tokens_.GetPayload(entry, 0)));
     }
+    WriteIndex(index);
   }
 
-  // Add a LITERAL token into the stream and the token objects array.
-  void AddLiteralToken(Token::Kind kind, const String* literal) {
-    // If the literal token is already in the tokens object array use the
-    // same index instead of duplicating it.
-    intptr_t index = FindLiteralIndex(kind, literal);
-    if (index == -1) {
-      WriteIndex(token_objects_.Length());
-      ASSERT(literal != NULL);
-      literal_token_ = LiteralToken::New(kind, *literal);
-      token_objects_.Add(literal_token_);
+  // Add a LITERAL token into the stream and the token hash map.
+  void AddLiteralToken(const Scanner::TokenDescriptor& descriptor) {
+    ASSERT(descriptor.literal->IsSymbol());
+    intptr_t index = tokens_.NumOccupied();
+    intptr_t entry;
+    if (!tokens_.FindKeyOrDeletedOrUnused(descriptor, &entry)) {
+      LiteralToken& new_literal = LiteralToken::Handle(
+          LiteralToken::New(descriptor.kind, *descriptor.literal));
+      tokens_.InsertKey(entry, new_literal);
+      tokens_.UpdatePayload(entry, 0, Smi::Handle(Smi::New(index)));
+      HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, tokens_);
     } else {
-      WriteIndex(index);
+      index = Smi::Value(Smi::RawCast(tokens_.GetPayload(entry, 0)));
     }
+    WriteIndex(index);
   }
 
   // Add a simple token into the stream.
   void AddSimpleToken(intptr_t kind) {
     stream_.WriteUnsigned(kind);
   }
 
   // Return the compressed token stream.
   uint8_t* GetStream() const { return buffer_; }
 
   // Return the compressed token stream length.
   intptr_t Length() const { return stream_.bytes_written(); }
 
-  // Return the token objects array.
-  const GrowableObjectArray& TokenObjects() const {
-    return token_objects_;
+  // Generate and return the token objects array.
+  RawArray* MakeTokenObjectsArray() const {
+    Array& result = Array::Handle(
+        Array::New(tokens_.NumOccupied(), Heap::kOld));
+    CompressedTokenMap::Iterator it(&tokens_);
+    Object& key = Object::Handle();
+    while (it.MoveNext()) {
+      intptr_t entry = it.Current();
+      key = tokens_.GetKey(entry);
+      result.SetAt(Smi::Value(Smi::RawCast(tokens_.GetPayload(entry, 0))), key);
+    }
+    return result.raw();
   }
 
  private:
-  intptr_t FindIdentIndex(const String* ident) {
-    ASSERT(ident != NULL);
-    ASSERT(ident->IsSymbol());
-    intptr_t hash_value = ident->Hash() % kTableSize;
-    GrowableArray<intptr_t>& value = ident_table_[hash_value];
-    for (intptr_t i = 0; i < value.length(); i++) {
-      intptr_t index = value[i];
-      if (token_objects_.At(index) == ident->raw()) {
-        return index;
-      }
-    }
-    value.Add(token_objects_.Length());
-    return -1;
-  }
-
-  intptr_t FindLiteralIndex(Token::Kind kind, const String* literal) {
-    ASSERT(literal != NULL);
-    ASSERT(literal->IsSymbol());
-    intptr_t hash_value = literal->Hash() % kTableSize;
-    GrowableArray<intptr_t>& value = literal_table_[hash_value];
-    for (intptr_t i = 0; i < value.length(); i++) {
-      intptr_t index = value[i];
-      token_obj_ = token_objects_.At(index);
-      const LiteralToken& token = LiteralToken::Cast(token_obj_);
-      if ((kind == token.kind()) && (token.literal() == literal->raw())) {
-        return index;
-      }
-    }
-    value.Add(token_objects_.Length());
-    return -1;
-  }
-
   void WriteIndex(intptr_t value) {
     stream_.WriteUnsigned(value + Token::kNumTokens);
   }
 
   static uint8_t* Reallocate(uint8_t* ptr,
                              intptr_t old_size,
                              intptr_t new_size) {
     void* new_ptr = ::realloc(reinterpret_cast<void*>(ptr), new_size);
     return reinterpret_cast<uint8_t*>(new_ptr);
   }
 
-  static const int kInitialTokenCount = 32;
-  static const intptr_t kTableSize = 1024;
+  static const intptr_t kInitialTableSize = 32;
+  static const double kMaxLoadFactor = 0.75;
 
   uint8_t* buffer_;
   WriteStream stream_;
-  GrowableArray<intptr_t> ident_table_[kTableSize];
-  GrowableArray<intptr_t> literal_table_[kTableSize];
-  const GrowableObjectArray& token_objects_;
-  Object& token_obj_;
-  LiteralToken& literal_token_;
-  String& literal_str_;
+  CompressedTokenMap tokens_;
 
   DISALLOW_COPY_AND_ASSIGN(CompressedTokenStreamData);
 };
 
 
 RawTokenStream* TokenStream::New(const Scanner::GrowableTokenStream& tokens,
                                  const String& private_key) {
   // Copy the relevant data out of the scanner into a compressed stream of
   // tokens.
   CompressedTokenStreamData data;
   intptr_t len = tokens.length();
   for (intptr_t i = 0; i < len; i++) {
     Scanner::TokenDescriptor token = tokens[i];
     if (token.kind == Token::kIDENT) {  // Identifier token.
       if (FLAG_compiler_stats) {
         CompilerStats::num_ident_tokens_total += 1;
       }
       data.AddIdentToken(token.literal);
     } else if (Token::NeedsLiteralToken(token.kind)) {  // Literal token.
       if (FLAG_compiler_stats) {
         CompilerStats::num_literal_tokens_total += 1;
       }
-      data.AddLiteralToken(token.kind, token.literal);
+      data.AddLiteralToken(token);
     } else {  // Keyword, pseudo keyword etc.
       ASSERT(token.kind < Token::kNumTokens);
       data.AddSimpleToken(token.kind);
     }
   }
   if (FLAG_compiler_stats) {
     CompilerStats::num_tokens_total += len;
   }
   data.AddSimpleToken(Token::kEOS);  // End of stream.
 
   // Create and setup the token stream object.
   const ExternalTypedData& stream = ExternalTypedData::Handle(
       ExternalTypedData::New(kExternalTypedDataUint8ArrayCid,
                              data.GetStream(), data.Length(), Heap::kOld));
   stream.AddFinalizer(data.GetStream(), DataFinalizer);
   const TokenStream& result = TokenStream::Handle(New());
   result.SetPrivateKey(private_key);
+  const Array& token_objects = Array::Handle(data.MakeTokenObjectsArray());
   {
     NoGCScope no_gc;
     result.SetStream(stream);
-    const Array& tokens = Array::Handle(Array::MakeArray(data.TokenObjects()));
-    result.SetTokenObjects(tokens);
+    result.SetTokenObjects(token_objects);
   }
   return result.raw();
 }
 
 
 const char* TokenStream::ToCString() const {
   return "TokenStream";
 }
 
 
@@ skipping 11295 matching lines @@
   return tag_label.ToCString();
 }
 
 
 void UserTag::PrintJSONImpl(JSONStream* stream, bool ref) const {
   Instance::PrintJSONImpl(stream, ref);
 }
 
 
 }  // namespace dart