| 1 | /*
|
| 2 | * Souffle - A Datalog Compiler
|
| 3 | * Copyright (c) 2021, The Souffle Developers. All rights reserved
|
| 4 | * Licensed under the Universal Permissive License v 1.0 as shown at:
|
| 5 | * - https://opensource.org/licenses/UPL
|
| 6 | * - <souffle root>/licenses/SOUFFLE-UPL.txt
|
| 7 | */
|
| 8 | #pragma once
|
| 9 |
|
| 10 | #include "ConcurrentInsertOnlyHashMap.h"
|
| 11 | #include "souffle/utility/ParallelUtil.h"
|
| 12 |
|
| 13 | namespace souffle {
|
| 14 | /**
|
| 15 | * A simple implementation of a cache that can be used during interation and compilation
|
| 16 | * to store frequently used values or values that are expensive to compute (e.g., regex).
|
| 17 | */
|
| 18 | template <class Key, class Value, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
|
| 19 | class KeyFactory = details::Factory<Key>>
|
| 20 | struct ConcurrentCache {
|
| 21 | #ifdef _OPENMP
|
| 22 | using CacheImpl = ConcurrentInsertOnlyHashMap<ConcurrentLanes, Key, Value, Hash, KeyEqual, KeyFactory>;
|
| 23 | #else
|
| 24 | using CacheImpl = ConcurrentInsertOnlyHashMap<SeqConcurrentLanes, Key, Value, Hash, KeyEqual, KeyFactory>;
|
| 25 | #endif
|
| 26 |
|
| 27 | ConcurrentCache(const std::size_t LaneCount = 1) : lanes(LaneCount), cache(LaneCount, 8) {}
|
| 28 | ~ConcurrentCache() = default;
|
| 29 |
|
| 30 | void setNumLanes(const std::size_t NumLanes) {
|
| 31 | lanes.setNumLanes(NumLanes);
|
| 32 | cache.setNumLanes(NumLanes);
|
| 33 | }
|
| 34 |
|
| 35 | /**
|
| 36 | * @brief Lookup the specified key in the cache.
|
| 37 | *
|
| 38 | * If the key is in the cache, then the associated value is returned. Otherwise,
|
| 39 | * if the key, is not in the cache, the supplied function is invoked to construct
|
| 40 | * the value from the key.
|
| 41 | *
|
| 42 | * The cache is not modified if the constructor function throws an exception.
|
| 43 | * @param key the key for caching
|
| 44 | * @param constructor a functor that takes a key and produces a value
|
| 45 | * @return the cached value that is associated with the key
|
| 46 | */
|
| 47 | template <class CTOR>
|
| 48 | const Value& getOrCreate(const Key& key, const CTOR& constructor) {
|
| 49 | typename CacheImpl::lane_id lane = lanes.threadLane();
|
| 50 | auto entry = cache.weakFind(lane, key);
|
| 51 | if (entry == nullptr) {
|
| 52 | auto node = cache.node(constructor(key));
|
| 53 | auto result = cache.get(lane, node, key);
|
| 54 | if (!result.second) {
|
| 55 | // we need to delete the temporary node, since someone else
|
| 56 | // already created the same node concurrently
|
| 57 | delete node;
|
| 58 | }
|
| 59 | entry = result.first;
|
| 60 | }
|
| 61 | return entry->second;
|
| 62 | }
|
| 63 |
|
| 64 | /**
|
| 65 | * @brief Lookup the value associated with the specified key.
|
| 66 | *
|
| 67 | * If the key does not exist, constructs a value using
|
| 68 | * the key.
|
| 69 | *
|
| 70 | * This function forwards to getOrCreate
|
| 71 | * @param key the key to lookup
|
| 72 | * @return the cached value that is associated with the key
|
| 73 | */
|
| 74 | inline const Value& getOrCreate(const Key& key) {
|
| 75 | return getOrCreate(key, [](auto p) { return Value(p); });
|
| 76 | }
|
| 77 |
|
| 78 | ConcurrentLanes lanes;
|
| 79 |
|
| 80 | CacheImpl cache;
|
| 81 | };
|
| 82 |
|
| 83 | } // namespace souffle
|