Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
cache = {} # the cache to store function results
sentinel = object() # sentinel object for the default value of map.get
hits = misses = 0 # hits and misses of the cache
lock = RLock() if thread_safe else DummyWithable() # ensure thread-safe
if ttl is not None: # set up values toolkit according to ttl
values_toolkit = values_toolkit_with_ttl
else:
values_toolkit = values_toolkit_without_ttl
if custom_key_maker is not None: # use custom make_key function
make_key = custom_key_maker
else:
if order_independent: # set up keys toolkit according to order_independent
make_key = keys_toolkit_order_independent.make_key
else:
make_key = keys_toolkit_order_dependent.make_key
lfu_freq_list_root = _FreqNode.root() # LFU frequency list root
def wrapper(*args, **kwargs):
"""
The actual wrapper
"""
nonlocal hits, misses
key = make_key(args, kwargs)
cache_expired = False
with lock:
result = _access_lfu_cache(cache, key, sentinel)
if result is not sentinel:
if values_toolkit.is_cache_value_valid(result):
hits += 1
return values_toolkit.retrieve_result_from_cache_value(result)
else:
cache_expired = True
cache_node = cache[key]
else:
# Key does not exist
# Access failed
return sentinel
freq_node = cache_node.parent
target_frequency = freq_node.frequency + 1
if freq_node.next.frequency != target_frequency:
# The next node on the frequency list has a frequency value different from
# (the frequency of the current node) + 1, which means we need to construct
# a new frequency node and an empty cache root node
# Then we move the current node to the newly created cache list
# Create a cache root and a frequency root
cache_root = _CacheNode.root()
new_freq_node = _FreqNode(freq_node, freq_node.next, target_frequency, cache_root)
cache_root.parent = new_freq_node
# Modify references
cache_node.prev.next = cache_node.next
cache_node.next.prev = cache_node.prev
cache_node.prev = cache_node.next = cache_root
cache_root.prev = cache_root.next = cache_node
new_freq_node.next.prev = new_freq_node.prev.next = new_freq_node
cache_node.parent = cache_root.parent
else:
# We can move the cache node to the cache list of the next node on the frequency list
# Find the head element of the next cache list
next_cache_head = freq_node.next.cache_head
if first_freq_node.cache_head.next == first_freq_node.cache_head:
# Getting here means that we just deleted the only data node in the cache list
# under the first frequency list
# Note: there is still an empty sentinel node
# We then need to destroy the sentinel node and its parent frequency node too
first_freq_node.cache_head.destroy()
first_freq_node.destroy()
first_freq_node = root.next # update
# Delete from cache
del cache[old_key]
# Prepare a new frequency node, a cache root node and a cache data node
empty_cache_root = _CacheNode.root()
freq_node = _FreqNode(root, first_freq_node, 1, empty_cache_root)
cache_node = _CacheNode(empty_cache_root, empty_cache_root, freq_node, key, value)
empty_cache_root.parent = freq_node
# Modify references
root.next.prev = root.next = freq_node
empty_cache_root.prev = empty_cache_root.next = cache_node
else:
# We can find the last element in the cache list under the first frequency list
# Moving it to the head and replace the stored data with a new key and a new value
# This is more efficient
# Find the target
cache_head = first_freq_node.cache_head
manipulated_node = cache_head.prev
# use another name so it can be accessed later
cache_node = manipulated_node
# Delete from cache
del cache[old_key]
else:
# The cache is not full
if first_freq_node.frequency != 1:
# The first element in frequency list has its frequency other than 1 (> 1)
# Creating a new node in frequency list with 1 as its frequency required
# We also need to create a new cache list and attach it to this new node
# Create a cache root and a frequency node
cache_root = _CacheNode.root()
freq_node = _FreqNode(root, first_freq_node, 1, cache_root)
cache_root.parent = freq_node
# Create another cache node to store data
cache_node = _CacheNode(cache_root, cache_root, freq_node, key, value)
# Modify references
cache_root.prev = cache_root.next = cache_node
first_freq_node.prev = root.next = freq_node # note: DO NOT swap "=", because first_freq_node == root.next
else:
# We create a new cache node in the cache list
# under the frequency node with frequency 1
# Create a cache node and store data in it
cache_head = first_freq_node.cache_head
cache_node = _CacheNode(cache_head, cache_head.next, first_freq_node, key, value)