Add exception handler cache to isolate

runtime/vm/fixed_cache.h

+// 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 {
+
+/*
+  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 no allowed - check with Lookup before insertion.

[Florian Schneider, 2017/02/08 21:34:05]

s/no/not/

[Dmitry Olshansky, 2017/02/09 17:54:34]

Done.

+
+  Optionally Values may have cleanup function to delete
+  any resources they point to.
+*/
+template <class K, class V, intptr_t kSize>
+class FixedCache {
+ public:
+  typedef void (*Deleter)(V*);
+
+  struct Entry {
+    K key;
+    V value;
+  };
+
+  explicit FixedCache(Deleter deleter = NULL) : deleter_(deleter), length_(0) {}
+
+  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_; j-- > i;) {

[Florian Schneider, 2017/02/08 21:34:05]

Can you rewrite this without the update in the test expression for better
readability?

[Dmitry Olshansky, 2017/02/09 17:54:34]

Done.

+      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(); }
+
+ 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.
+  Deleter deleter_;
+  intptr_t length_;
+};
+
+}  // namespace dart
+
+#endif  // RUNTIME_VM_FIXED_CACHE_H_