1// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_FIXED_CACHE_H_
6#define RUNTIME_VM_FIXED_CACHE_H_
7
8#include <stddef.h>
9#include <stdint.h>
10
11#include "vm/lockers.h"
12
13namespace dart {
14
15// A simple sorted fixed size Key-Value storage.
16//
17// Assumes both Key and Value are default-constructible objects.
18//
19// Keys must be comparable with operator<.
20//
21// Duplicates are not allowed - check with Lookup before insertion.
22//
23template <class K, class V, intptr_t kCapacity>
24class FixedCache {
25 public:
26 struct Entry {
27 K key;
28 V value;
29 };
30
31 FixedCache() : length_(0) {}
32
33 ~FixedCache() { Clear(); }
34
35 V* Lookup(K key) {
36 MutexLocker ml(&mutex_);
37
38 intptr_t i = LowerBound(key);
39 if (i != length_ && pairs_[i].key == key) return &pairs_[i].value;
40 return NULL;
41 }
42
43 void Insert(K key, V value) {
44 MutexLocker ml(&mutex_);
45
46 intptr_t i = LowerBound(key);
47
48 if (length_ == kCapacity) {
49 length_ = kCapacity - 1;
50 if (i == kCapacity) i = kCapacity - 1;
51 }
52
53 for (intptr_t j = length_ - 1; j >= i; j--) {
54 pairs_[j + 1] = pairs_[j];
55 }
56
57 length_ += 1;
58 pairs_[i].key = key;
59 pairs_[i].value = value;
60 }
61
62 void Clear() {
63 MutexLocker ml(&mutex_);
64 length_ = 0;
65 }
66
67 private:
68 intptr_t LowerBound(K key) {
69 intptr_t low = 0, high = length_;
70 while (low != high) {
71 intptr_t mid = low + (high - low) / 2;
72 if (key < pairs_[mid].key) {
73 high = mid;
74 } else if (key > pairs_[mid].key) {
75 low = mid + 1;
76 } else {
77 low = high = mid;
78 }
79 }
80 return low;
81 }
82
83 // We protect any operation on the [FixedCache] because multiple isolates from
84 // the same [IsolateGroup] can access this cache concurrently (as can the GC
85 // when it clears it).
86 Mutex mutex_;
87 Entry pairs_[kCapacity]; // Sorted array of pairs.
88 intptr_t length_;
89};
90
91} // namespace dart
92
93#endif // RUNTIME_VM_FIXED_CACHE_H_
94