Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/platform/scheduler/base/work_queue_sets.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "platform/scheduler/base/work_queue_sets.h"
 
 #include "base/logging.h"
 #include "platform/scheduler/base/work_queue.h"
 
 namespace blink {
 namespace scheduler {
 namespace internal {
 
 WorkQueueSets::WorkQueueSets(size_t num_sets, const char* name)
     : enqueue_order_to_work_queue_maps_(num_sets), name_(name) {}
 
 WorkQueueSets::~WorkQueueSets() {}
 
 void WorkQueueSets::AddQueue(WorkQueue* work_queue, size_t set_index) {
   DCHECK(!work_queue->work_queue_sets());
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   work_queue->AssignToWorkQueueSets(this);
   work_queue->AssignSetIndex(set_index);
   if (!has_enqueue_order)
     return;
-  enqueue_order_to_work_queue_maps_[set_index].insert(
+  enqueue_order_to_work_queue_maps_[set_index].insertUnique(
       std::make_pair(enqueue_order, work_queue));
 }
 
 void WorkQueueSets::RemoveQueue(WorkQueue* work_queue) {
   DCHECK_EQ(this, work_queue->work_queue_sets());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   work_queue->AssignToWorkQueueSets(nullptr);
   if (!has_enqueue_order)
     return;
@@ skipping 10 matching lines @@
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   size_t old_set = work_queue->work_queue_set_index();
   DCHECK_LT(old_set, enqueue_order_to_work_queue_maps_.size());
   DCHECK_NE(old_set, set_index);
   work_queue->AssignSetIndex(set_index);
   if (!has_enqueue_order)
     return;
   enqueue_order_to_work_queue_maps_[old_set].erase(enqueue_order);
-  enqueue_order_to_work_queue_maps_[set_index].insert(
+  enqueue_order_to_work_queue_maps_[set_index].insertUnique(
       std::make_pair(enqueue_order, work_queue));
 }
 
 void WorkQueueSets::OnPushQueue(WorkQueue* work_queue) {
   // NOTE if this function changes, we need to keep |WorkQueueSets::AddQueue| in
   // sync.
   DCHECK_EQ(this, work_queue->work_queue_sets());
   EnqueueOrder enqueue_order;
   bool has_enqueue_order = work_queue->GetFrontTaskEnqueueOrder(&enqueue_order);
   DCHECK(has_enqueue_order);
   size_t set_index = work_queue->work_queue_set_index();
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size())
       << " set_index = " << set_index;
-  enqueue_order_to_work_queue_maps_[set_index].insert(
+  enqueue_order_to_work_queue_maps_[set_index].insertUnique(
       std::make_pair(enqueue_order, work_queue));
 }
 
 void WorkQueueSets::OnPopQueue(WorkQueue* work_queue) {
   // Assume that |work_queue| contains the lowest enqueue_order.
   size_t set_index = work_queue->work_queue_set_index();
   DCHECK_EQ(this, work_queue->work_queue_sets());
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
   DCHECK(!enqueue_order_to_work_queue_maps_[set_index].empty())
       << " set_index = " << set_index;
   DCHECK_EQ(enqueue_order_to_work_queue_maps_[set_index].begin()->second,
             work_queue)
       << " set_index = " << set_index;
-  EnqueueOrderToWorkQueueMap::iterator old_it =
-      enqueue_order_to_work_queue_maps_[set_index].begin();
   EnqueueOrder enqueue_order;
   if (work_queue->GetFrontTaskEnqueueOrder(&enqueue_order)) {
-    // Amortized O(1) if the new location is close to |old_it|, otherwise
-    // O(log n).
-    enqueue_order_to_work_queue_maps_[set_index].insert(
-        std::make_pair(enqueue_order, work_queue));
+    enqueue_order_to_work_queue_maps_[set_index].ChangeKeyUnique(
+        enqueue_order_to_work_queue_maps_[set_index].begin(), enqueue_order);
+  } else {
+    enqueue_order_to_work_queue_maps_[set_index].erase(
+        enqueue_order_to_work_queue_maps_[set_index].begin());
   }
-  // O(1)
-  enqueue_order_to_work_queue_maps_[set_index].erase(old_it);
 }
 
 bool WorkQueueSets::GetOldestQueueInSet(size_t set_index,
                                         WorkQueue** out_work_queue) const {
   DCHECK_LT(set_index, enqueue_order_to_work_queue_maps_.size());
   if (enqueue_order_to_work_queue_maps_[set_index].empty())
     return false;
   *out_work_queue =
       enqueue_order_to_work_queue_maps_[set_index].begin()->second;
 #ifndef NDEBUG
@@ skipping 34 matching lines @@
     return true;
   }
 
   return false;
 }
 #endif
 
 }  // namespace internal
 }  // namespace scheduler
 }  // namespace blink