Add exception handler cache to isolate

runtime/vm/fixed_cache.h

Index: runtime/vm/fixed_cache.h
diff --git a/runtime/vm/fixed_cache.h b/runtime/vm/fixed_cache.h
new file mode 100644
index 0000000000000000000000000000000000000000..145cb63cd8504a191b4c1f97e2ca45c79b643535
--- /dev/null
+++ b/runtime/vm/fixed_cache.h
@@ -0,0 +1,94 @@
+// Copyright (c) 2017, 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_FIXED_CACHE_H_
+#define RUNTIME_VM_FIXED_CACHE_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+namespace dart {
+
+/*

[Vyacheslav Egorov (Google), 2017/02/10 12:45:35]

Style:

I think this should better be 

//
//
//
//

style comment.

We don't use multiline /* */ comments and when we use them we do it like this:

/*
 *
 */

[Dmitry Olshansky, 2017/02/10 16:32:14]

Done.

+  A simple sorted fixed size Key-Value storage.
+
+  Assumes both Key and Value are POD-like objects.
+
+  Keys must be comparable with operator<.
+
+  Duplicates are not allowed - check with Lookup before insertion.
+
+  Optionally Values may have cleanup function to delete
+  any resources they point to.
+*/
+template <class K, class V, intptr_t kSize>
+class FixedCache {

[Florian Schneider, 2017/02/09 19:25:55]

Please add a unit test fixed_cache_test.cc for the different cases.
(empty cache, partially full cache, full cache, insertion at start, end, middle)

[Dmitry Olshansky, 2017/02/10 16:32:14]

Done.

+ public:
+  typedef void (*Deleter)(V*);
+
+  struct Entry {
+    K key;
+    V value;
+  };
+
+  explicit FixedCache(Deleter deleter = NULL) : deleter_(deleter), length_(0) {}

[Vyacheslav Egorov (Google), 2017/02/10 12:45:35]

maybe kSize better be called kCapacity and length_ -> size_?

[Dmitry Olshansky, 2017/02/10 16:32:14]

Done.

+
+  V* Lookup(K key) {
+    intptr_t i = LowerBound(key);
+    if (i != length_ && pairs_[i].key == key) return &pairs_[i].value;
+    return NULL;
+  }
+
+  void Insert(K key, V value) {
+    intptr_t i = LowerBound(key);
+
+    if (length_ == kSize) {
+      if (deleter_) deleter_(&pairs_[length_ - 1].value);
+      length_ = kSize - 1;
+      if (i == kSize) i = kSize - 1;
+    }
+
+    for (intptr_t j = length_ - 1; j >= i; j--) {

[Vyacheslav Egorov (Google), 2017/02/10 12:45:35]

Can this be just a memmove(...)?

[Dmitry Olshansky, 2017/02/10 16:32:14]

Actually yes, as long as Key is POD. But let's keep it as it.

+      pairs_[j + 1] = pairs_[j];
+    }
+
+    length_ += 1;
+    pairs_[i].key = key;
+    pairs_[i].value = value;
+  }
+
+  void Clear() {
+    if (deleter_) {
+      for (intptr_t i = 0; i < length_; i++) {
+        deleter_(&pairs_[i].value);
+      }
+    }
+    length_ = 0;
+  }
+
+  ~FixedCache() { Clear(); }

[Vyacheslav Egorov (Google), 2017/02/10 12:45:36]

Put destructor next to contructor.

[Dmitry Olshansky, 2017/02/10 16:32:14]

Done.

+
+ private:
+  intptr_t LowerBound(K key) {
+    intptr_t low = 0, high = length_;
+    while (low != high) {
+      intptr_t mid = low + (high - low) / 2;
+      if (key < pairs_[mid].key) {
+        high = mid;
+      } else if (key > pairs_[mid].key) {
+        low = mid + 1;
+      } else {
+        low = high = mid;
+      }
+    }
+    return low;
+  }
+  Entry pairs_[kSize];  // Sorted array of pairs.

[Vyacheslav Egorov (Google), 2017/02/10 12:45:35]

empty line before fields

[Dmitry Olshansky, 2017/02/10 16:32:14]

Done.

+  Deleter deleter_;
+  intptr_t length_;
+};
+
+}  // namespace dart
+
+#endif  // RUNTIME_VM_FIXED_CACHE_H_