iframe-proxy | Sunbelt Computer Software

History

79 lines (64 loc) · 2.23 KB

Raw

cdef object _LRU_MARKER = object()

@cython.final

cdef class LruCache:

cdef:

object _dict

int _maxsize

object _dict_move_to_end

object _dict_get

# We use an OrderedDict for LRU implementation. Operations:

# * We use a simple `__setitem__` to push a new entry:

# `entries[key] = new_entry`

# That will push `new_entry` to the *end* of the entries dict.

# * When we have a cache hit, we call

# `entries.move_to_end(key, last=True)`

# to move the entry to the *end* of the entries dict.

# * When we need to remove entries to maintain `max_size`, we call

# `entries.popitem(last=False)`

# to remove an entry from the *beginning* of the entries dict.

# So new entries and hits are always promoted to the end of the

# entries dict, whereas the unused one will group in the

# beginning of it.

def __init__(self, *, maxsize):

if maxsize <= 0:

raise ValueError(

f'maxsize is expected to be greater than 0, got {maxsize}')

self._dict = col_OrderedDict()

self._dict_move_to_end = self._dict.move_to_end

self._dict_get = self._dict.get

self._maxsize = maxsize

cdef get(self, key, default):

o = self._dict_get(key, _LRU_MARKER)

if o is _LRU_MARKER:

return default

self._dict_move_to_end(key) # last=True

return o

cdef inline needs_cleanup(self):

return len(self._dict) > self._maxsize

cdef inline cleanup_one(self):

k, _ = self._dict.popitem(last=False)

return k

def __getitem__(self, key):

o = self._dict[key]

self._dict_move_to_end(key) # last=True

return o

def __setitem__(self, key, o):

if key in self._dict:

self._dict[key] = o

self._dict_move_to_end(key) # last=True

else:

self._dict[key] = o

while self.needs_cleanup():

self.cleanup_one()

def __delitem__(self, key):

del self._dict[key]

def __contains__(self, key):

return key in self._dict

def __len__(self):

return len(self._dict)

def __iter__(self):

return iter(self._dict)

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

lru.pyx

Latest commit

History

lru.pyx

File metadata and controls