OLD | NEW |
1 // Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #ifndef RUNTIME_VM_FIXED_CACHE_H_ | 5 #ifndef RUNTIME_VM_FIXED_CACHE_H_ |
6 #define RUNTIME_VM_FIXED_CACHE_H_ | 6 #define RUNTIME_VM_FIXED_CACHE_H_ |
7 | 7 |
8 #include <stddef.h> | 8 #include <stddef.h> |
9 #include <stdint.h> | 9 #include <stdint.h> |
10 | 10 |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
46 | 46 |
47 for (intptr_t j = length_ - 1; j >= i; j--) { | 47 for (intptr_t j = length_ - 1; j >= i; j--) { |
48 pairs_[j + 1] = pairs_[j]; | 48 pairs_[j + 1] = pairs_[j]; |
49 } | 49 } |
50 | 50 |
51 length_ += 1; | 51 length_ += 1; |
52 pairs_[i].key = key; | 52 pairs_[i].key = key; |
53 pairs_[i].value = value; | 53 pairs_[i].value = value; |
54 } | 54 } |
55 | 55 |
56 void Clear() { | 56 void Clear() { length_ = 0; } |
57 length_ = 0; | |
58 } | |
59 | 57 |
60 private: | 58 private: |
61 intptr_t LowerBound(K key) { | 59 intptr_t LowerBound(K key) { |
62 intptr_t low = 0, high = length_; | 60 intptr_t low = 0, high = length_; |
63 while (low != high) { | 61 while (low != high) { |
64 intptr_t mid = low + (high - low) / 2; | 62 intptr_t mid = low + (high - low) / 2; |
65 if (key < pairs_[mid].key) { | 63 if (key < pairs_[mid].key) { |
66 high = mid; | 64 high = mid; |
67 } else if (key > pairs_[mid].key) { | 65 } else if (key > pairs_[mid].key) { |
68 low = mid + 1; | 66 low = mid + 1; |
69 } else { | 67 } else { |
70 low = high = mid; | 68 low = high = mid; |
71 } | 69 } |
72 } | 70 } |
73 return low; | 71 return low; |
74 } | 72 } |
75 | 73 |
76 Entry pairs_[kCapacity]; // Sorted array of pairs. | 74 Entry pairs_[kCapacity]; // Sorted array of pairs. |
77 intptr_t length_; | 75 intptr_t length_; |
78 }; | 76 }; |
79 | 77 |
80 } // namespace dart | 78 } // namespace dart |
81 | 79 |
82 #endif // RUNTIME_VM_FIXED_CACHE_H_ | 80 #endif // RUNTIME_VM_FIXED_CACHE_H_ |
OLD | NEW |