Prefetch cache pt1 - MRU

chrome/browser/autocomplete/answers_cache.h

+// Copyright 2014 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.
+
+#ifndef CHROME_BROWSER_AUTOCOMPLETE_ANSWERS_CACHE_H_
+#define CHROME_BROWSER_AUTOCOMPLETE_ANSWERS_CACHE_H_
+
+#include <list>
+
+#include "base/basictypes.h"
+#include "base/strings/string16.h"
+
+struct AnswersQueryData {
+  AnswersQueryData();
+  AnswersQueryData(const base::string16& full_query_text,
+                   const base::string16& query_type);
+  base::string16 full_query_text;
+  base::string16 query_type;
+};
+
+// Cache for the most-recently seen answer for AiS.

[Peter Kasting, 2014/08/11 22:15:33]

Nit: Probably should spell out "AiS"

[groby-ooo-7-16, 2014/08/12 01:16:26]

Done.

+class AnswersCache {
+ public:
+  explicit AnswersCache(size_t max_entries);
+  ~AnswersCache();
+
+  // Get the top answer query completion for the query term. The query data

[Peter Kasting, 2014/08/11 22:15:33]

Nit: Get -> Gets (and similar below)

[groby-ooo-7-16, 2014/08/12 01:16:26]

Done.

+  // will contain empty query text and type if no matching data was found.
+  AnswersQueryData GetTopAnswerEntry(const base::string16& query);
+
+  // Register a query that received an answer suggestion.
+  void UpdateRecentAnswers(const base::string16& full_query_text,
+                           const base::string16& query_type);
+
+  bool IsEmpty();  // Signal if cache is empty.

[Peter Kasting, 2014/08/11 22:15:33]

Nit: Put the comment above the function.

[groby-ooo-7-16, 2014/08/12 01:16:26]

Done.

+
+ private:
+  size_t max_entries_;
+  typedef std::list<AnswersQueryData> Cache;

[Peter Kasting, 2014/08/11 22:15:33]

Did you consider a priority_queue (or queue or deque) for this?  I'm not
convinced they'd actually be better, I was just wondering whether something like
a priority_queue (sorting based on timestamps, I guess?) would lead to any less
code in terms of keeping the list sorted properly.

It seems like using a list is pretty efficient, though... maybe it doesn't
really matter much.

[groby-ooo-7-16, 2014/08/12 01:16:26]

I've considered a queue/priority_queue, yes. But 

a) queue/priority_queue has no iterators.
b) The only time ordering changes is during insert/get, when I already have the
element available to re-place in a different spot
c) It rises the annoying issue of strictly monotonic timestamps. (Esp. for
testing)

dequeue has O(n) behavior for removal. (Not that it'll matter horribly much :)

So list seemed the best fit.

On 2014/08/11 22:15:33, Peter Kasting wrote:

+  Cache cache_;
+
+  DISALLOW_COPY_AND_ASSIGN(AnswersCache);
+};
+
+#endif  // CHROME_BROWSER_AUTOCOMPLETE_ANSWERS_CACHE_H_