diff options
Diffstat (limited to 'requests/packages/urllib3/_collections.py')
| -rw-r--r-- | requests/packages/urllib3/_collections.py | 167 |
1 files changed, 65 insertions, 102 deletions
diff --git a/requests/packages/urllib3/_collections.py b/requests/packages/urllib3/_collections.py index 00b2cd5..282b8d5 100644 --- a/requests/packages/urllib3/_collections.py +++ b/requests/packages/urllib3/_collections.py @@ -1,131 +1,94 @@ # urllib3/_collections.py -# Copyright 2008-2011 Andrey Petrov and contributors (see CONTRIBUTORS.txt) +# Copyright 2008-2013 Andrey Petrov and contributors (see CONTRIBUTORS.txt) # # This module is part of urllib3 and is released under # the MIT License: http://www.opensource.org/licenses/mit-license.php -from collections import deque - +from collections import MutableMapping from threading import RLock -__all__ = ['RecentlyUsedContainer'] - - -class AccessEntry(object): - __slots__ = ('key', 'is_valid') - - def __init__(self, key, is_valid=True): - self.key = key - self.is_valid = is_valid - - -class RecentlyUsedContainer(dict): - """ - Provides a dict-like that maintains up to ``maxsize`` keys while throwing - away the least-recently-used keys beyond ``maxsize``. - """ - - # If len(self.access_log) exceeds self._maxsize * CLEANUP_FACTOR, then we - # will attempt to cleanup the invalidated entries in the access_log - # datastructure during the next 'get' operation. - CLEANUP_FACTOR = 10 - - def __init__(self, maxsize=10): - self._maxsize = maxsize - - self._container = {} - - # We use a deque to to store our keys ordered by the last access. - self.access_log = deque() - self.access_log_lock = RLock() +try: # Python 2.7+ + from collections import OrderedDict +except ImportError: + from .packages.ordered_dict import OrderedDict - # We look up the access log entry by the key to invalidate it so we can - # insert a new authorative entry at the head without having to dig and - # find the old entry for removal immediately. - self.access_lookup = {} - # Trigger a heap cleanup when we get past this size - self.access_log_limit = maxsize * self.CLEANUP_FACTOR +__all__ = ['RecentlyUsedContainer'] - def _invalidate_entry(self, key): - "If exists: Invalidate old entry and return it." - old_entry = self.access_lookup.get(key) - if old_entry: - old_entry.is_valid = False - return old_entry +_Null = object() - def _push_entry(self, key): - "Push entry onto our access log, invalidate the old entry if exists." - self._invalidate_entry(key) - new_entry = AccessEntry(key) - self.access_lookup[key] = new_entry +class RecentlyUsedContainer(MutableMapping): + """ + Provides a thread-safe dict-like container which maintains up to + ``maxsize`` keys while throwing away the least-recently-used keys beyond + ``maxsize``. - self.access_log_lock.acquire() - self.access_log.appendleft(new_entry) - self.access_log_lock.release() + :param maxsize: + Maximum number of recent elements to retain. - def _prune_entries(self, num): - "Pop entries from our access log until we popped ``num`` valid ones." - while num > 0: - self.access_log_lock.acquire() - p = self.access_log.pop() - self.access_log_lock.release() + :param dispose_func: + Every time an item is evicted from the container, + ``dispose_func(value)`` is called. Callback which will get called + """ - if not p.is_valid: - continue # Invalidated entry, skip + ContainerCls = OrderedDict - dict.pop(self, p.key, None) - self.access_lookup.pop(p.key, None) - num -= 1 + def __init__(self, maxsize=10, dispose_func=None): + self._maxsize = maxsize + self.dispose_func = dispose_func - def _prune_invalidated_entries(self): - "Rebuild our access_log without the invalidated entries." - self.access_log_lock.acquire() - self.access_log = deque(e for e in self.access_log if e.is_valid) - self.access_log_lock.release() + self._container = self.ContainerCls() + self.lock = RLock() - def _get_ordered_access_keys(self): - "Return ordered access keys for inspection. Used for testing." - self.access_log_lock.acquire() - r = [e.key for e in self.access_log if e.is_valid] - self.access_log_lock.release() + def __getitem__(self, key): + # Re-insert the item, moving it to the end of the eviction line. + with self.lock: + item = self._container.pop(key) + self._container[key] = item + return item - return r + def __setitem__(self, key, value): + evicted_value = _Null + with self.lock: + # Possibly evict the existing value of 'key' + evicted_value = self._container.get(key, _Null) + self._container[key] = value - def __getitem__(self, key): - item = dict.get(self, key) + # If we didn't evict an existing value, we might have to evict the + # least recently used item from the beginning of the container. + if len(self._container) > self._maxsize: + _key, evicted_value = self._container.popitem(last=False) - if not item: - raise KeyError(key) + if self.dispose_func and evicted_value is not _Null: + self.dispose_func(evicted_value) - # Insert new entry with new high priority, also implicitly invalidates - # the old entry. - self._push_entry(key) + def __delitem__(self, key): + with self.lock: + value = self._container.pop(key) - if len(self.access_log) > self.access_log_limit: - # Heap is getting too big, try to clean up any tailing invalidated - # entries. - self._prune_invalidated_entries() + if self.dispose_func: + self.dispose_func(value) - return item + def __len__(self): + with self.lock: + return len(self._container) - def __setitem__(self, key, item): - # Add item to our container and access log - dict.__setitem__(self, key, item) - self._push_entry(key) + def __iter__(self): + raise NotImplementedError('Iteration over this class is unlikely to be threadsafe.') - # Discard invalid and excess entries - self._prune_entries(len(self) - self._maxsize) + def clear(self): + with self.lock: + # Copy pointers to all values, then wipe the mapping + # under Python 2, this copies the list of values twice :-| + values = list(self._container.values()) + self._container.clear() - def __delitem__(self, key): - self._invalidate_entry(key) - self.access_lookup.pop(key, None) - dict.__delitem__(self, key) + if self.dispose_func: + for value in values: + self.dispose_func(value) - def get(self, key, default=None): - try: - return self[key] - except KeyError: - return default + def keys(self): + with self.lock: + return self._container.keys() |