clang-format runtime/vm

runtime/vm/hash_table.h

 // Copyright (c) 2014, 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.
 
 #ifndef RUNTIME_VM_HASH_TABLE_H_
 #define RUNTIME_VM_HASH_TABLE_H_
 
 #include "platform/assert.h"
 #include "vm/object.h"
 
@@ skipping 54 matching lines @@
 // The header tracks the number of entries in each state.
 // Any object except Object::sentinel() and Object::transition_sentinel()
 // may be stored as a key. Any object may be stored in a payload.
 //
 // Parameters
 //  KeyTraits: defines static methods
 //    bool IsMatch(const Key& key, const Object& obj) and
 //    uword Hash(const Key& key) for any number of desired lookup key types.
 //  kPayloadSize: number of components of the payload in each entry.
 //  kMetaDataSize: number of elements reserved (e.g., for iteration order data).
-template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize>
+template <typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize>
 class HashTable : public ValueObject {
  public:
   typedef KeyTraits Traits;
   // Uses the passed in handles for all handle operations.
   // 'Release' must be called at the end to obtain the final table
   // after potential growth/shrinkage.
   HashTable(Object* key, Smi* index, Array* data)
       : key_handle_(key),
         smi_handle_(index),
         data_(data),
@@ skipping 34 matching lines @@
     return kFirstKeyIndex + (kEntrySize * num_entries);
   }
 
   // Initializes an empty table.
   void Initialize() const {
     ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
     *smi_handle_ = Smi::New(0);
     data_->SetAt(kOccupiedEntriesIndex, *smi_handle_);
     data_->SetAt(kDeletedEntriesIndex, *smi_handle_);
 
-NOT_IN_PRODUCT(
+#if !defined(PRODUCT)
     data_->SetAt(kNumGrowsIndex, *smi_handle_);
     data_->SetAt(kNumLT5LookupsIndex, *smi_handle_);
     data_->SetAt(kNumLT25LookupsIndex, *smi_handle_);
     data_->SetAt(kNumGT25LookupsIndex, *smi_handle_);
-)  // !PRODUCT
+#endif  // !defined(PRODUCT)
 
     for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
       data_->SetAt(i, Object::sentinel());
     }
   }
 
   // Returns whether 'key' matches any key in the table.
-  template<typename Key>
+  template <typename Key>
   bool ContainsKey(const Key& key) const {
     return FindKey(key) != -1;
   }
 
   // Returns the entry that matches 'key', or -1 if none exists.
-  template<typename Key>
+  template <typename Key>
   intptr_t FindKey(const Key& key) const {
     const intptr_t num_entries = NumEntries();
     ASSERT(NumOccupied() < num_entries);
     // TODO(koda): Add salt.
     NOT_IN_PRODUCT(intptr_t collisions = 0;)
     uword hash = KeyTraits::Hash(key);
     intptr_t probe = hash % num_entries;
     // TODO(koda): Consider quadratic probing.
     while (true) {
       if (IsUnused(probe)) {
@@ skipping 12 matching lines @@
       probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
     return -1;
   }
 
   // Sets *entry to either:
   // - an occupied entry matching 'key', and returns true, or
   // - an unused/deleted entry where a matching key may be inserted,
   //   and returns false.
-  template<typename Key>
+  template <typename Key>
   bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const {
     const intptr_t num_entries = NumEntries();
     ASSERT(entry != NULL);
     ASSERT(NumOccupied() < num_entries);
     NOT_IN_PRODUCT(intptr_t collisions = 0;)
     uword hash = KeyTraits::Hash(key);
     intptr_t probe = hash % num_entries;
     intptr_t deleted = -1;
     // TODO(koda): Consider quadratic probing.
     while (true) {
@@ skipping 71 matching lines @@
     InternalSetKey(entry, Object::transition_sentinel());
     AdjustSmiValueAt(kOccupiedEntriesIndex, -1);
     AdjustSmiValueAt(kDeletedEntriesIndex, 1);
   }
   intptr_t NumEntries() const {
     return (data_->Length() - kFirstKeyIndex) / kEntrySize;
   }
   intptr_t NumUnused() const {
     return NumEntries() - NumOccupied() - NumDeleted();
   }
-  intptr_t NumOccupied() const {
-    return GetSmiValueAt(kOccupiedEntriesIndex);
-  }
-  intptr_t NumDeleted() const {
-    return GetSmiValueAt(kDeletedEntriesIndex);
-  }
-  Object& KeyHandle() const {
-    return *key_handle_;
-  }
-  Smi& SmiHandle() const {
-    return *smi_handle_;
-  }
+  intptr_t NumOccupied() const { return GetSmiValueAt(kOccupiedEntriesIndex); }
+  intptr_t NumDeleted() const { return GetSmiValueAt(kDeletedEntriesIndex); }
+  Object& KeyHandle() const { return *key_handle_; }
+  Smi& SmiHandle() const { return *smi_handle_; }
 
-NOT_IN_PRODUCT(
-  intptr_t NumGrows() const {
-    return GetSmiValueAt(kNumGrowsIndex);
-  }
+#if !defined(PRODUCT)
+  intptr_t NumGrows() const { return GetSmiValueAt(kNumGrowsIndex); }
   intptr_t NumLT5Collisions() const {
     return GetSmiValueAt(kNumLT5LookupsIndex);
   }
   intptr_t NumLT25Collisions() const {
     return GetSmiValueAt(kNumLT25LookupsIndex);
   }
   intptr_t NumGT25Collisions() const {
     return GetSmiValueAt(kNumGT25LookupsIndex);
   }
-  void UpdateGrowth() const {
-    AdjustSmiValueAt(kNumGrowsIndex, 1);
-  }
+  void UpdateGrowth() const { AdjustSmiValueAt(kNumGrowsIndex, 1); }
   void UpdateCollisions(intptr_t collisions) const {
     if (data_->raw()->IsVMHeapObject()) {
       return;
     }
     if (collisions < 5) {
       AdjustSmiValueAt(kNumLT5LookupsIndex, 1);
     } else if (collisions < 25) {
       AdjustSmiValueAt(kNumLT25LookupsIndex, 1);
     } else {
       AdjustSmiValueAt(kNumGT25LookupsIndex, 1);
     }
   }
   void PrintStats() const {
     if (!KeyTraits::ReportStats()) {
       return;
     }
+    // clang-format off
     OS::Print("Stats for %s table :\n"
               " Size of table = %" Pd ",Number of Occupied entries = %" Pd "\n"
               " Number of Grows = %" Pd "\n"
               " Number of look ups with < 5 collisions = %" Pd "\n"
               " Number of look ups with < 25 collisions = %" Pd "\n"
               " Number of look ups with > 25 collisions = %" Pd "\n",
               KeyTraits::Name(),
               NumEntries(), NumOccupied(),
               NumGrows(),
               NumLT5Collisions(), NumLT25Collisions(), NumGT25Collisions());
+    // clang-format on
   }
-)  // !PRODUCT
+#endif  // !PRODUCT
 
  protected:
   static const intptr_t kOccupiedEntriesIndex = 0;
   static const intptr_t kDeletedEntriesIndex = 1;
 #if defined(PRODUCT)
   static const intptr_t kHeaderSize = kDeletedEntriesIndex + 1;
 #else
   static const intptr_t kNumGrowsIndex = 2;
   static const intptr_t kNumLT5LookupsIndex = 3;
   static const intptr_t kNumLT25LookupsIndex = 4;
@@ skipping 41 matching lines @@
   Smi* smi_handle_;
   // Exactly one of these is non-NULL, depending on whether Release was called.
   Array* data_;
   Array* released_data_;
 
   friend class HashTables;
 };
 
 
 // Table with unspecified iteration order. No payload overhead or metadata.
-template<typename KeyTraits, intptr_t kUserPayloadSize>
+template <typename KeyTraits, intptr_t kUserPayloadSize>
 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> {
  public:
   typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable;
   static const intptr_t kPayloadSize = kUserPayloadSize;
   explicit UnorderedHashTable(RawArray* data)
       : BaseTable(Thread::Current()->zone(), data) {}
   UnorderedHashTable(Zone* zone, RawArray* data) : BaseTable(zone, data) {}
   UnorderedHashTable(Object* key, Smi* value, Array* data)
       : BaseTable(key, value, data) {}
   // Note: Does not check for concurrent modification.
   class Iterator {
    public:
     explicit Iterator(const UnorderedHashTable* table)
         : table_(table), entry_(-1) {}
     bool MoveNext() {
       while (entry_ < (table_->NumEntries() - 1)) {
         ++entry_;
         if (table_->IsOccupied(entry_)) {
           return true;
         }
       }
       return false;
     }
-    intptr_t Current() {
-      return entry_;
-    }
+    intptr_t Current() { return entry_; }
 
    private:
     const UnorderedHashTable* table_;
     intptr_t entry_;
   };
 
   // No extra book-keeping needed for Initialize, InsertKey, DeleteEntry.
 };
 
 
 class HashTables : public AllStatic {
  public:
   // Allocates and initializes a table.
-  template<typename Table>
+  template <typename Table>
   static RawArray* New(intptr_t initial_capacity,
                        Heap::Space space = Heap::kNew) {
-    Table table(Thread::Current()->zone(), Array::New(
-        Table::ArrayLengthForNumOccupied(initial_capacity), space));
+    Table table(
+        Thread::Current()->zone(),
+        Array::New(Table::ArrayLengthForNumOccupied(initial_capacity), space));
     table.Initialize();
     return table.Release().raw();
   }
 
-  template<typename Table>
+  template <typename Table>
   static RawArray* New(const Array& array) {
     Table table(Thread::Current()->zone(), array.raw());
     table.Initialize();
     return table.Release().raw();
   }
 
   // Clears 'to' and inserts all elements from 'from', in iteration order.
   // The tables must have the same user payload size.
-  template<typename From, typename To>
+  template <typename From, typename To>
   static void Copy(const From& from, const To& to) {
     COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize);
     to.Initialize();
     ASSERT(from.NumOccupied() < to.NumEntries());
     typename From::Iterator it(&from);
     Object& obj = Object::Handle();
     while (it.MoveNext()) {
       intptr_t from_entry = it.Current();
       obj = from.GetKey(from_entry);
       intptr_t to_entry = -1;
       const Object& key = obj;
       bool present = to.FindKeyOrDeletedOrUnused(key, &to_entry);
       ASSERT(!present);
       to.InsertKey(to_entry, obj);
       for (intptr_t i = 0; i < From::kPayloadSize; ++i) {
         obj = from.GetPayload(from_entry, i);
         to.UpdatePayload(to_entry, i, obj);
       }
     }
   }
 
-  template<typename Table>
+  template <typename Table>
   static void EnsureLoadFactor(double low, double high, const Table& table) {
     double current = (1 + table.NumOccupied() + table.NumDeleted()) /
-        static_cast<double>(table.NumEntries());
+                     static_cast<double>(table.NumEntries());
     if (low <= current && current < high) {
       return;
     }
     double target = (low + high) / 2.0;
     intptr_t new_capacity = (1 + table.NumOccupied()) / target;
-    Table new_table(New<Table>(
-        new_capacity,
-        table.data_->IsOld() ? Heap::kOld : Heap::kNew));
+    Table new_table(New<Table>(new_capacity,
+                               table.data_->IsOld() ? Heap::kOld : Heap::kNew));
     Copy(table, new_table);
     *table.data_ = new_table.Release().raw();
     NOT_IN_PRODUCT(table.UpdateGrowth(); table.PrintStats();)
   }
 
   // Serializes a table by concatenating its entries as an array.
-  template<typename Table>
+  template <typename Table>
   static RawArray* ToArray(const Table& table, bool include_payload) {
     const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1;
     Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size));
     typename Table::Iterator it(&table);
     Object& obj = Object::Handle();
     intptr_t result_index = 0;
     while (it.MoveNext()) {
       intptr_t entry = it.Current();
       obj = table.GetKey(entry);
       result.SetAt(result_index++, obj);
       if (include_payload) {
         for (intptr_t i = 0; i < Table::kPayloadSize; ++i) {
           obj = table.GetPayload(entry, i);
           result.SetAt(result_index++, obj);
         }
       }
     }
     return result.raw();
   }
 };
 
 
-template<typename BaseIterTable>
+template <typename BaseIterTable>
 class HashMap : public BaseIterTable {
  public:
   explicit HashMap(RawArray* data)
       : BaseIterTable(Thread::Current()->zone(), data) {}
   HashMap(Zone* zone, RawArray* data) : BaseIterTable(zone, data) {}
   HashMap(Object* key, Smi* value, Array* data)
       : BaseIterTable(key, value, data) {}
-  template<typename Key>
+  template <typename Key>
   RawObject* GetOrNull(const Key& key, bool* present = NULL) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (present != NULL) {
       *present = (entry != -1);
     }
     return (entry == -1) ? Object::null() : BaseIterTable::GetPayload(entry, 0);
   }
   bool UpdateOrInsert(const Object& key, const Object& value) const {
     EnsureCapacity();
     intptr_t entry = -1;
     bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
     if (!present) {
       BaseIterTable::InsertKey(entry, key);
     }
     BaseIterTable::UpdatePayload(entry, 0, value);
     return present;
   }
   // Update the value of an existing key. Note that 'key' need not be an Object.
-  template<typename Key>
+  template <typename Key>
   void UpdateValue(const Key& key, const Object& value) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     ASSERT(entry != -1);
     BaseIterTable::UpdatePayload(entry, 0, value);
   }
   // If 'key' is not present, maps it to 'value_if_absent'. Returns the final
   // value in the map.
   RawObject* InsertOrGetValue(const Object& key,
                               const Object& value_if_absent) const {
     EnsureCapacity();
     intptr_t entry = -1;
     if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
       BaseIterTable::InsertKey(entry, key);
       BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
       return value_if_absent.raw();
     } else {
       return BaseIterTable::GetPayload(entry, 0);
     }
   }
   // Like InsertOrGetValue, but calls NewKey to allocate a key object if needed.
-  template<typename Key>
+  template <typename Key>
   RawObject* InsertNewOrGetValue(const Key& key,
                                  const Object& value_if_absent) const {
     EnsureCapacity();
     intptr_t entry = -1;
     if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
       BaseIterTable::KeyHandle() =
           BaseIterTable::BaseTable::Traits::NewKey(key);
       BaseIterTable::InsertKey(entry, BaseIterTable::KeyHandle());
       BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
       return value_if_absent.raw();
     } else {
       return BaseIterTable::GetPayload(entry, 0);
     }
   }
 
-  template<typename Key>
+  template <typename Key>
   bool Remove(const Key& key) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (entry == -1) {
       return false;
     } else {
       BaseIterTable::DeleteEntry(entry);
       return true;
     }
   }
 
-  void Clear() const {
-    BaseIterTable::Initialize();
-  }
+  void Clear() const { BaseIterTable::Initialize(); }
 
  protected:
   void EnsureCapacity() const {
     static const double kMaxLoadFactor = 0.75;
     // We currently never shrink.
     HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this);
   }
 };
 
 
-template<typename KeyTraits>
+template <typename KeyTraits>
 class UnorderedHashMap : public HashMap<UnorderedHashTable<KeyTraits, 1> > {
  public:
   typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap;
   explicit UnorderedHashMap(RawArray* data)
       : BaseMap(Thread::Current()->zone(), data) {}
   UnorderedHashMap(Zone* zone, RawArray* data) : BaseMap(zone, data) {}
   UnorderedHashMap(Object* key, Smi* value, Array* data)
       : BaseMap(key, value, data) {}
 };
 
 
-template<typename BaseIterTable>
+template <typename BaseIterTable>
 class HashSet : public BaseIterTable {
  public:
   explicit HashSet(RawArray* data)
       : BaseIterTable(Thread::Current()->zone(), data) {}
   HashSet(Zone* zone, RawArray* data) : BaseIterTable(zone, data) {}
   HashSet(Object* key, Smi* value, Array* data)
       : BaseIterTable(key, value, data) {}
   bool Insert(const Object& key) {
     EnsureCapacity();
     intptr_t entry = -1;
@@ skipping 11 matching lines @@
     intptr_t entry = -1;
     if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
       BaseIterTable::InsertKey(entry, key);
       return key.raw();
     } else {
       return BaseIterTable::GetKey(entry);
     }
   }
 
   // Like InsertOrGet, but calls NewKey to allocate a key object if needed.
-  template<typename Key>
+  template <typename Key>
   RawObject* InsertNewOrGet(const Key& key) const {
     EnsureCapacity();
     intptr_t entry = -1;
     if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
       BaseIterTable::KeyHandle() =
           BaseIterTable::BaseTable::Traits::NewKey(key);
       BaseIterTable::InsertKey(entry, BaseIterTable::KeyHandle());
       return BaseIterTable::KeyHandle().raw();
     } else {
       return BaseIterTable::GetKey(entry);
     }
   }
 
-  template<typename Key>
+  template <typename Key>
   RawObject* GetOrNull(const Key& key, bool* present = NULL) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (present != NULL) {
       *present = (entry != -1);
     }
     return (entry == -1) ? Object::null() : BaseIterTable::GetKey(entry);
   }
 
-  template<typename Key>
+  template <typename Key>
   bool Remove(const Key& key) const {
     intptr_t entry = BaseIterTable::FindKey(key);
     if (entry == -1) {
       return false;
     } else {
       BaseIterTable::DeleteEntry(entry);
       return true;
     }
   }
 
-  void Clear() const {
-    BaseIterTable::Initialize();
-  }
+  void Clear() const { BaseIterTable::Initialize(); }
 
  protected:
   void EnsureCapacity() const {
     static const double kMaxLoadFactor = 0.75;
     // We currently never shrink.
     HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this);
   }
 };
 
 
-template<typename KeyTraits>
+template <typename KeyTraits>
 class UnorderedHashSet : public HashSet<UnorderedHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<UnorderedHashTable<KeyTraits, 0> > BaseSet;
   explicit UnorderedHashSet(RawArray* data)
       : BaseSet(Thread::Current()->zone(), data) {
     ASSERT(data != Array::null());
   }
   UnorderedHashSet(Zone* zone, RawArray* data) : BaseSet(zone, data) {}
   UnorderedHashSet(Object* key, Smi* value, Array* data)
       : BaseSet(key, value, data) {}
 };
 
 }  // namespace dart
 
 #endif  // RUNTIME_VM_HASH_TABLE_H_