fixed_cache.h

Go to the documentation of this file.

// 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>
 
#include "vm/lockers.h"
 
namespace dart {
 
// A simple sorted fixed size Key-Value storage.
//
// Assumes both Key and Value are default-constructible objects.
//
// Keys must be comparable with operator<.
//
// Duplicates are not allowed - check with Lookup before insertion.
//
template <class K, class V, intptr_t kCapacity>
class FixedCache {
 public:
  struct Entry {
    K key;
    V value;
  };
 
  FixedCache() : length_(0) {}
 
  ~FixedCache() { Clear(); }
 
  V* Lookup(K key) {
    MutexLocker ml(&mutex_);
 
    intptr_t i = LowerBound(key);
    if (i != length_ && pairs_[i].key == key) return &pairs_[i].value;
    return nullptr;
  }
 
  void Insert(K key, V value) {
    MutexLocker ml(&mutex_);
 
    intptr_t i = LowerBound(key);
 
    if (length_ == kCapacity) {
      length_ = kCapacity - 1;
      if (i == kCapacity) i = kCapacity - 1;
    }
 
    for (intptr_t j = length_ - 1; j >= i; j--) {
      pairs_[j + 1] = pairs_[j];
    }
 
    length_ += 1;
    pairs_[i].key = key;
    pairs_[i].value = value;
  }
 
  void Clear() {
    MutexLocker ml(&mutex_);
    length_ = 0;
  }
 
 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;
  }
 
  // We protect any operation on the [FixedCache] because multiple isolates from
  // the same [IsolateGroup] can access this cache concurrently (as can the GC
  // when it clears it).
  Mutex mutex_;
  Entry pairs_[kCapacity];  // Sorted array of pairs.
  intptr_t length_;
};
 
}  // namespace dart
 
#endif  // RUNTIME_VM_FIXED_CACHE_H_