[PATCH] D51676: [clangd] Use TopN instead of std::priority_queue

[Kirill Bobyrev via Phabricator via cfe-commits]

kbobyrev created this revision.
kbobyrev added reviewers: ioeric, ilya-biryukov, sammccall.
kbobyrev added a project: clang-tools-extra.
Herald added subscribers: kadircet, arphaman, jkorous, MaskRay.

Quality.cpp defines a structure for convenient storage of Top N items, it 
should be used instead of the `std::priority_queue` with slightly obscure 
semantics.

This patch does not affect functionality.


https://reviews.llvm.org/D51676

Files:
  clang-tools-extra/clangd/index/MemIndex.cpp


Index: clang-tools-extra/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/clangd/index/MemIndex.cpp
+++ clang-tools-extra/clangd/index/MemIndex.cpp
@@ -10,7 +10,7 @@
 #include "MemIndex.h"
 #include "../FuzzyMatch.h"
 #include "../Logger.h"
-#include <queue>
+#include "../Quality.h"
 
 namespace clang {
 namespace clangd {
@@ -26,7 +26,7 @@
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
-  std::priority_queue<std::pair<float, const Symbol *>> Top;
+  TopN<std::pair<float, const Symbol *>> Top(Req.MaxCandidateCount);
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
@@ -39,15 +39,14 @@
       continue;
 
     if (auto Score = Filter.match(Sym->Name)) {
-      Top.emplace(-*Score * quality(*Sym), Sym);
-      if (Top.size() > Req.MaxCandidateCount) {
+      // Top.push(...) returns true if the capacity is reached and the heap had
+      // to pop() and item before inserting a new one.
+      if (Top.push({*Score * quality(*Sym), Sym}))
         More = true;
-        Top.pop();
-      }
     }
   }
-  for (; !Top.empty(); Top.pop())
-    Callback(*Top.top().second);
+  for (const auto &Item : std::move(Top).items())
+    Callback(*Item.second);
   return More;
 }
 



Index: clang-tools-extra/clangd/index/MemIndex.cpp
===================================================================
--- clang-tools-extra/clangd/index/MemIndex.cpp
+++ clang-tools-extra/clangd/index/MemIndex.cpp
@@ -10,7 +10,7 @@
 #include "MemIndex.h"
 #include "../FuzzyMatch.h"
 #include "../Logger.h"
-#include <queue>
+#include "../Quality.h"
 
 namespace clang {
 namespace clangd {
@@ -26,7 +26,7 @@
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
-  std::priority_queue<std::pair<float, const Symbol *>> Top;
+  TopN<std::pair<float, const Symbol *>> Top(Req.MaxCandidateCount);
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
@@ -39,15 +39,14 @@
       continue;
 
     if (auto Score = Filter.match(Sym->Name)) {
-      Top.emplace(-*Score * quality(*Sym), Sym);
-      if (Top.size() > Req.MaxCandidateCount) {
+      // Top.push(...) returns true if the capacity is reached and the heap had
+      // to pop() and item before inserting a new one.
+      if (Top.push({*Score * quality(*Sym), Sym}))
         More = true;
-        Top.pop();
-      }
     }
   }
-  for (; !Top.empty(); Top.pop())
-    Callback(*Top.top().second);
+  for (const auto &Item : std::move(Top).items())
+    Callback(*Item.second);
   return More;
 }
 

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits