GPU Program Caching

gpu/command_buffer/service/program_cache_lru_helper.h

Index: gpu/command_buffer/service/program_cache_lru_helper.h
diff --git a/gpu/command_buffer/service/program_cache_lru_helper.h b/gpu/command_buffer/service/program_cache_lru_helper.h
new file mode 100644
index 0000000000000000000000000000000000000000..44dca357d7e65a0f40bab769dab8c90478cddc40
--- /dev/null
+++ b/gpu/command_buffer/service/program_cache_lru_helper.h
@@ -0,0 +1,56 @@
+// Copyright (c) 201 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 GPU_COMMAND_BUFFER_SERVICE_PROGRAM_CACHE_LRU_HELPER_H_
+#define GPU_COMMAND_BUFFER_SERVICE_PROGRAM_CACHE_LRU_HELPER_H_
+
+#include "base/basictypes.h"
+#include "base/hash_tables.h"
+#include "gpu/gpu_export.h"
+#include "net/disk_cache/hash.h"
+
+#include <list>
+
+namespace gpu {
+namespace gles2 {
+
+// LRU helper for the program cache, operates in O(1) time.
+// This class uses a linked list with a hash map.  Both copy their string keys,
+// so be mindful that keys you insert will be stored again twice in memory.
+class GPU_EXPORT ProgramCacheLruHelper {
+ public:
+  ProgramCacheLruHelper() {}
+  // clears the lru queue
+  void Clear();
+  // returns true if the lru queue is empty
+  bool IsEmpty();
+  // inserts or refreshes a key in the queue
+  void KeyUsed(const std::string& key);
+  // removes + returns the lru key from the queue.
+  // If the queue is empty, "" is returned (you should use isEmpty())
+  std::string EvictKey();
+
+ private:
+  struct FastHash {

[greggman, 2012/06/25 18:53:03]

do you really need FastHash?

[dmurph, 2012/06/26 02:32:56]

Hell yeah!
http://www.azillionmonkeys.com/qed/hash.html

+    const inline uint32 operator()(const std::string& key) const {
+      if (key.empty())
+        return 0;
+      return disk_cache::SuperFastHash(key.data(),
+                                       static_cast<int>(key.size()));
+    }
+  };
+  typedef std::list<std::string> StringList;
+  typedef base::hash_map<std::string,
+                         StringList::iterator,
+                         FastHash> IteratorMap;
+  StringList queue;
+  IteratorMap location_map;
+
+  DISALLOW_COPY_AND_ASSIGN(ProgramCacheLruHelper);
+};
+
+} // namespace gles2
+} // namespace gpu
+
+#endif // GPU_COMMAND_BUFFER_SERVICE_PROGRAM_CACHE_LRU_HELPER_H_