def test_eviction(self):
        cache = LruCache(2)
        cache[1] = 1
        cache[2] = 2

        self.assertEquals(cache.get(1), 1)
        self.assertEquals(cache.get(2), 2)

        cache[3] = 3

        self.assertEquals(cache.get(1), None)
        self.assertEquals(cache.get(2), 2)
        self.assertEquals(cache.get(3), 3)

    def test_clear(self):
        m1 = Mock()
        m2 = Mock()
        cache = LruCache(5)

        cache.set("key1", "value", callbacks=[m1])
        cache.set("key2", "value", callbacks=[m2])

        self.assertEquals(m1.call_count, 0)
        self.assertEquals(m2.call_count, 0)

        cache.clear()

        self.assertEquals(m1.call_count, 1)
        self.assertEquals(m2.call_count, 1)

    def __init__(self, hs):
        self.hs = hs
        self.clock = hs.get_clock()
        self.store = hs.get_datastore()
        self.state = hs.get_state_handler()
        self.TOKEN_NOT_FOUND_HTTP_STATUS = 401

        self.token_cache = LruCache(CACHE_SIZE_FACTOR * 10000)
        register_cache("cache", "token_cache", self.token_cache)

    def test_pop(self):
        m = Mock()
        cache = LruCache(1)

        cache.set("key", "value", callbacks=[m])
        self.assertFalse(m.called)

        cache.pop("key")
        self.assertEquals(m.call_count, 1)

        cache.set("key", "value")
        self.assertEquals(m.call_count, 1)

        cache.pop("key")
        self.assertEquals(m.call_count, 1)

    def __init__(self, name, max_entries=1000, keylen=1, tree=False):
        cache_type = TreeCache if tree else dict
        self.cache = LruCache(
            max_size=max_entries, keylen=keylen, cache_type=cache_type
        )

        self.name = name
        self.keylen = keylen
        self.sequence = 0
        self.thread = None
        self.metrics = register_cache(name, self.cache)

    def test_evict(self):
        cache = LruCache(5, size_callback=len)
        cache["key1"] = [0]
        cache["key2"] = [1, 2]
        cache["key3"] = [3]
        cache["key4"] = [4]

        self.assertEquals(cache["key1"], [0])
        self.assertEquals(cache["key2"], [1, 2])
        self.assertEquals(cache["key3"], [3])
        self.assertEquals(cache["key4"], [4])
        self.assertEquals(len(cache), 5)

        cache["key5"] = [5, 6]

        self.assertEquals(len(cache), 4)
        self.assertEquals(cache.get("key1"), None)
        self.assertEquals(cache.get("key2"), None)
        self.assertEquals(cache["key3"], [3])
        self.assertEquals(cache["key4"], [4])
        self.assertEquals(cache["key5"], [5, 6])

    def __init__(self, name, max_entries=1000):
        self.cache = LruCache(max_size=max_entries)

        self.name = name
        self.sequence = 0
        self.thread = None
        # caches_by_name[name] = self.cache

        class Sentinel(object):
            __slots__ = []

        self.sentinel = Sentinel()
        caches_by_name[name] = self.cache

    def __init__(self, name, max_entries=1000):
        self.cache = LruCache(max_size=max_entries, size_callback=len)

        self.name = name
        self.sequence = 0
        self.thread = None
        # caches_by_name[name] = self.cache

        class Sentinel(object):
            __slots__ = []

        self.sentinel = Sentinel()
        self.metrics = register_cache(name, self.cache)

 def test_setdefault(self):
     cache = LruCache(1)
     self.assertEquals(cache.setdefault("key", 1), 1)
     self.assertEquals(cache.get("key"), 1)
     self.assertEquals(cache.setdefault("key", 2), 1)
     self.assertEquals(cache.get("key"), 1)
     cache["key"] = 2  # Make sure overriding works.
     self.assertEquals(cache.get("key"), 2)

    def __init__(self, name, max_entries=1000, keylen=1, tree=False, iterable=False):
        cache_type = TreeCache if tree else dict
        self._pending_deferred_cache = cache_type()

        self.cache = LruCache(
            max_size=max_entries, keylen=keylen, cache_type=cache_type,
            size_callback=(lambda d: len(d)) if iterable else None,
            evicted_callback=self._on_evicted,
        )

        self.name = name
        self.keylen = keylen
        self.thread = None
        self.metrics = register_cache("cache", name, self.cache)

    def test_del_multi(self):
        cache = LruCache(4, 2, cache_type=TreeCache)
        cache[("animal", "cat")] = "mew"
        cache[("animal", "dog")] = "woof"
        cache[("vehicles", "car")] = "vroom"
        cache[("vehicles", "train")] = "chuff"

        self.assertEquals(len(cache), 4)

        self.assertEquals(cache.get(("animal", "cat")), "mew")
        self.assertEquals(cache.get(("vehicles", "car")), "vroom")
        cache.del_multi(("animal",))
        self.assertEquals(len(cache), 2)
        self.assertEquals(cache.get(("animal", "cat")), None)
        self.assertEquals(cache.get(("animal", "dog")), None)
        self.assertEquals(cache.get(("vehicles", "car")), "vroom")
        self.assertEquals(cache.get(("vehicles", "train")), "chuff")

 def test_get_set(self):
     cache = LruCache(1)
     cache["key"] = "value"
     self.assertEquals(cache.get("key"), "value")
     self.assertEquals(cache["key"], "value")

class Auth(object):
    """
    FIXME: This class contains a mix of functions for authenticating users
    of our client-server API and authenticating events added to room graphs.
    """
    def __init__(self, hs):
        self.hs = hs
        self.clock = hs.get_clock()
        self.store = hs.get_datastore()
        self.state = hs.get_state_handler()
        self.TOKEN_NOT_FOUND_HTTP_STATUS = 401

        self.token_cache = LruCache(CACHE_SIZE_FACTOR * 10000)
        register_cache("cache", "token_cache", self.token_cache)

        self._account_validity = hs.config.account_validity

    @defer.inlineCallbacks
    def check_from_context(self, room_version, event, context, do_sig_check=True):
        prev_state_ids = yield context.get_prev_state_ids(self.store)
        auth_events_ids = yield self.compute_auth_events(
            event, prev_state_ids, for_verification=True,
        )
        auth_events = yield self.store.get_events(auth_events_ids)
        auth_events = {
            (e.type, e.state_key): e for e in itervalues(auth_events)
        }
        self.check(
            room_version, event,
            auth_events=auth_events, do_sig_check=do_sig_check,
        )

    def check(self, room_version, event, auth_events, do_sig_check=True):
        """ Checks if this event is correctly authed.

        Args:
            room_version (str): version of the room
            event: the event being checked.
            auth_events (dict: event-key -> event): the existing room state.


        Returns:
            True if the auth checks pass.
        """
        with Measure(self.clock, "auth.check"):
            event_auth.check(
                room_version, event, auth_events, do_sig_check=do_sig_check
            )

    @defer.inlineCallbacks
    def check_joined_room(self, room_id, user_id, current_state=None):
        """Check if the user is currently joined in the room
        Args:
            room_id(str): The room to check.
            user_id(str): The user to check.
            current_state(dict): Optional map of the current state of the room.
                If provided then that map is used to check whether they are a
                member of the room. Otherwise the current membership is
                loaded from the database.
        Raises:
            AuthError if the user is not in the room.
        Returns:
            A deferred membership event for the user if the user is in
            the room.
        """
        if current_state:
            member = current_state.get(
                (EventTypes.Member, user_id),
                None
            )
        else:
            member = yield self.state.get_current_state(
                room_id=room_id,
                event_type=EventTypes.Member,
                state_key=user_id
            )

        self._check_joined_room(member, user_id, room_id)
        defer.returnValue(member)

    @defer.inlineCallbacks
    def check_user_was_in_room(self, room_id, user_id):
        """Check if the user was in the room at some point.
        Args:
            room_id(str): The room to check.
            user_id(str): The user to check.
        Raises:
            AuthError if the user was never in the room.
        Returns:
            A deferred membership event for the user if the user was in the
            room. This will be the join event if they are currently joined to
            the room. This will be the leave event if they have left the room.
        """
        member = yield self.state.get_current_state(
            room_id=room_id,
            event_type=EventTypes.Member,
            state_key=user_id
        )
        membership = member.membership if member else None

#.........这里部分代码省略.........

class Cache(object):
    __slots__ = (
        "cache",
        "max_entries",
        "name",
        "keylen",
        "sequence",
        "thread",
        "metrics",
    )

    def __init__(self, name, max_entries=1000, keylen=1, tree=False):
        cache_type = TreeCache if tree else dict
        self.cache = LruCache(
            max_size=max_entries, keylen=keylen, cache_type=cache_type
        )

        self.name = name
        self.keylen = keylen
        self.sequence = 0
        self.thread = None
        self.metrics = register_cache(name, self.cache)

    def check_thread(self):
        expected_thread = self.thread
        if expected_thread is None:
            self.thread = threading.current_thread()
        else:
            if expected_thread is not threading.current_thread():
                raise ValueError(
                    "Cache objects can only be accessed from the main thread"
                )

    def get(self, key, default=_CacheSentinel, callback=None):
        val = self.cache.get(key, _CacheSentinel, callback=callback)
        if val is not _CacheSentinel:
            self.metrics.inc_hits()
            return val

        self.metrics.inc_misses()

        if default is _CacheSentinel:
            raise KeyError()
        else:
            return default

    def update(self, sequence, key, value, callback=None):
        self.check_thread()
        if self.sequence == sequence:
            # Only update the cache if the caches sequence number matches the
            # number that the cache had before the SELECT was started (SYN-369)
            self.prefill(key, value, callback=callback)

    def prefill(self, key, value, callback=None):
        self.cache.set(key, value, callback=callback)

    def invalidate(self, key):
        self.check_thread()
        if not isinstance(key, tuple):
            raise TypeError(
                "The cache key must be a tuple not %r" % (type(key),)
            )

        # Increment the sequence number so that any SELECT statements that
        # raced with the INSERT don't update the cache (SYN-369)
        self.sequence += 1
        self.cache.pop(key, None)

    def invalidate_many(self, key):
        self.check_thread()
        if not isinstance(key, tuple):
            raise TypeError(
                "The cache key must be a tuple not %r" % (type(key),)
            )
        self.sequence += 1
        self.cache.del_multi(key)

    def invalidate_all(self):
        self.check_thread()
        self.sequence += 1
        self.cache.clear()

class Cache(object):
    __slots__ = (
        "cache",
        "max_entries",
        "name",
        "keylen",
        "thread",
        "metrics",
        "_pending_deferred_cache",
    )

    def __init__(self, name, max_entries=1000, keylen=1, tree=False, iterable=False):
        cache_type = TreeCache if tree else dict
        self._pending_deferred_cache = cache_type()

        self.cache = LruCache(
            max_size=max_entries, keylen=keylen, cache_type=cache_type,
            size_callback=(lambda d: len(d)) if iterable else None,
            evicted_callback=self._on_evicted,
        )

        self.name = name
        self.keylen = keylen
        self.thread = None
        self.metrics = register_cache("cache", name, self.cache)

    def _on_evicted(self, evicted_count):
        self.metrics.inc_evictions(evicted_count)

    def check_thread(self):
        expected_thread = self.thread
        if expected_thread is None:
            self.thread = threading.current_thread()
        else:
            if expected_thread is not threading.current_thread():
                raise ValueError(
                    "Cache objects can only be accessed from the main thread"
                )

    def get(self, key, default=_CacheSentinel, callback=None, update_metrics=True):
        """Looks the key up in the caches.

        Args:
            key(tuple)
            default: What is returned if key is not in the caches. If not
                specified then function throws KeyError instead
            callback(fn): Gets called when the entry in the cache is invalidated
            update_metrics (bool): whether to update the cache hit rate metrics

        Returns:
            Either a Deferred or the raw result
        """
        callbacks = [callback] if callback else []
        val = self._pending_deferred_cache.get(key, _CacheSentinel)
        if val is not _CacheSentinel:
            val.callbacks.update(callbacks)
            if update_metrics:
                self.metrics.inc_hits()
            return val.deferred

        val = self.cache.get(key, _CacheSentinel, callbacks=callbacks)
        if val is not _CacheSentinel:
            self.metrics.inc_hits()
            return val

        if update_metrics:
            self.metrics.inc_misses()

        if default is _CacheSentinel:
            raise KeyError()
        else:
            return default

    def set(self, key, value, callback=None):
        callbacks = [callback] if callback else []
        self.check_thread()
        entry = CacheEntry(
            deferred=value,
            callbacks=callbacks,
        )

        existing_entry = self._pending_deferred_cache.pop(key, None)
        if existing_entry:
            existing_entry.invalidate()

        self._pending_deferred_cache[key] = entry

        def shuffle(result):
            existing_entry = self._pending_deferred_cache.pop(key, None)
            if existing_entry is entry:
                self.cache.set(key, result, entry.callbacks)
            else:
                # oops, the _pending_deferred_cache has been updated since
                # we started our query, so we are out of date.
                #
                # Better put back whatever we took out. (We do it this way
                # round, rather than peeking into the _pending_deferred_cache
                # and then removing on a match, to make the common case faster)
                if existing_entry is not None:
                    self._pending_deferred_cache[key] = existing_entry
#.........这里部分代码省略.........

 def test_setdefault(self):
     cache = LruCache(1)
     self.assertEquals(cache.setdefault("key", 1), 1)
     self.assertEquals(cache.get("key"), 1)
     self.assertEquals(cache.setdefault("key", 2), 1)
     self.assertEquals(cache.get("key"), 1)

class DictionaryCache(object):
    """Caches key -> dictionary lookups, supporting caching partial dicts, i.e.
    fetching a subset of dictionary keys for a particular key.
    """

    def __init__(self, name, max_entries=1000):
        self.cache = LruCache(max_size=max_entries)

        self.name = name
        self.sequence = 0
        self.thread = None
        # caches_by_name[name] = self.cache

        class Sentinel(object):
            __slots__ = []

        self.sentinel = Sentinel()
        caches_by_name[name] = self.cache

    def check_thread(self):
        expected_thread = self.thread
        if expected_thread is None:
            self.thread = threading.current_thread()
        else:
            if expected_thread is not threading.current_thread():
                raise ValueError(
                    "Cache objects can only be accessed from the main thread"
                )

    def get(self, key, dict_keys=None):
        entry = self.cache.get(key, self.sentinel)
        if entry is not self.sentinel:
            cache_counter.inc_hits(self.name)

            if dict_keys is None:
                return DictionaryEntry(entry.full, dict(entry.value))
            else:
                return DictionaryEntry(entry.full, {
                    k: entry.value[k]
                    for k in dict_keys
                    if k in entry.value
                })

        cache_counter.inc_misses(self.name)
        return DictionaryEntry(False, {})

    def invalidate(self, key):
        self.check_thread()

        # Increment the sequence number so that any SELECT statements that
        # raced with the INSERT don't update the cache (SYN-369)
        self.sequence += 1
        self.cache.pop(key, None)

    def invalidate_all(self):
        self.check_thread()
        self.sequence += 1
        self.cache.clear()

    def update(self, sequence, key, value, full=False):
        self.check_thread()
        if self.sequence == sequence:
            # Only update the cache if the caches sequence number matches the
            # number that the cache had before the SELECT was started (SYN-369)
            if full:
                self._insert(key, value)
            else:
                self._update_or_insert(key, value)

    def _update_or_insert(self, key, value):
        entry = self.cache.setdefault(key, DictionaryEntry(False, {}))
        entry.value.update(value)

    def _insert(self, key, value):
        self.cache[key] = DictionaryEntry(True, value)

class DictionaryCache(object):
    """Caches key -> dictionary lookups, supporting caching partial dicts, i.e.
    fetching a subset of dictionary keys for a particular key.
    """

    def __init__(self, name, max_entries=1000):
        self.cache = LruCache(max_size=max_entries, size_callback=len)

        self.name = name
        self.sequence = 0
        self.thread = None
        # caches_by_name[name] = self.cache

        class Sentinel(object):
            __slots__ = []

        self.sentinel = Sentinel()
        self.metrics = register_cache(name, self.cache)

    def check_thread(self):
        expected_thread = self.thread
        if expected_thread is None:
            self.thread = threading.current_thread()
        else:
            if expected_thread is not threading.current_thread():
                raise ValueError(
                    "Cache objects can only be accessed from the main thread"
                )

    def get(self, key, dict_keys=None):
        """Fetch an entry out of the cache

        Args:
            key
            dict_key(list): If given a set of keys then return only those keys
                that exist in the cache.

        Returns:
            DictionaryEntry
        """
        entry = self.cache.get(key, self.sentinel)
        if entry is not self.sentinel:
            self.metrics.inc_hits()

            if dict_keys is None:
                return DictionaryEntry(entry.full, entry.known_absent, dict(entry.value))
            else:
                return DictionaryEntry(entry.full, entry.known_absent, {
                    k: entry.value[k]
                    for k in dict_keys
                    if k in entry.value
                })

        self.metrics.inc_misses()
        return DictionaryEntry(False, set(), {})

    def invalidate(self, key):
        self.check_thread()

        # Increment the sequence number so that any SELECT statements that
        # raced with the INSERT don't update the cache (SYN-369)
        self.sequence += 1
        self.cache.pop(key, None)

    def invalidate_all(self):
        self.check_thread()
        self.sequence += 1
        self.cache.clear()

    def update(self, sequence, key, value, full=False, known_absent=None):
        """Updates the entry in the cache

        Args:
            sequence
            key
            value (dict): The value to update the cache with.
            full (bool): Whether the given value is the full dict, or just a
                partial subset there of. If not full then any existing entries
                for the key will be updated.
            known_absent (set): Set of keys that we know don't exist in the full
                dict.
        """
        self.check_thread()
        if self.sequence == sequence:
            # Only update the cache if the caches sequence number matches the
            # number that the cache had before the SELECT was started (SYN-369)
            if known_absent is None:
                known_absent = set()
            if full:
                self._insert(key, value, known_absent)
            else:
                self._update_or_insert(key, value, known_absent)

    def _update_or_insert(self, key, value, known_absent):
        # We pop and reinsert as we need to tell the cache the size may have
        # changed

        entry = self.cache.pop(key, DictionaryEntry(False, set(), {}))
        entry.value.update(value)
        entry.known_absent.update(known_absent)
#.........这里部分代码省略.........