def seen_prebuilt_key(self, x):
     # In case we are an r_dict, we don't ask for the hash ourselves.
     # Note that if the custom hashing function ends up asking for
     # the hash of x, then it must use compute_hash() itself, so it
     # works out.
     if not self.dictkey.custom_eq_hash:
         compute_hash(x)

    def test_hash_preservation(self):
        from pypy.rlib.objectmodel import compute_hash
        from pypy.rlib.objectmodel import current_object_addr_as_int
        class C:
            pass
        class D(C):
            pass
        c = C()
        d = D()
        compute_hash(d)     # force to be cached on 'd', but not on 'c'
        #
        def fn():
            d2 = D()
            return (compute_hash(d2),
                    current_object_addr_as_int(d2),
                    compute_hash(c),
                    compute_hash(d),
                    compute_hash(("Hi", None, (7.5, 2, d))))
        
        f = self.getcompiled(fn)
        res = f()

        # xxx the next line is too precise, checking the exact implementation
        assert res[0] == res[1]
        assert res[2] != compute_hash(c)     # likely
        assert res[3] == compute_hash(d)
        assert res[4] == compute_hash(("Hi", None, (7.5, 2, d)))

 def fn():
     d2 = D()
     return (compute_hash(d2),
             current_object_addr_as_int(d2),
             compute_hash(c),
             compute_hash(d),
             compute_hash(("Hi", None, (7.5, 2, d))))

 def define_hash_preservation(cls):
     from pypy.rlib.objectmodel import compute_hash
     from pypy.rlib.objectmodel import compute_identity_hash
     from pypy.rlib.objectmodel import current_object_addr_as_int
     class C:
         pass
     class D(C):
         pass
     c = C()
     d = D()
     h_d = compute_hash(d)     # force to be cached on 'd', but not on 'c'
     h_t = compute_hash(("Hi", None, (7.5, 2, d)))
     S = lltype.GcStruct('S', ('x', lltype.Signed),
                              ('a', lltype.Array(lltype.Signed)))
     s = lltype.malloc(S, 15, zero=True)
     h_s = compute_identity_hash(s)   # varsized: hash not saved/restored
     #
     def f():
         if compute_hash(c) != compute_identity_hash(c): return 12
         if compute_hash(d) != h_d: return 13
         if compute_hash(("Hi", None, (7.5, 2, d))) != h_t: return 14
         c2 = C()
         h_c2 = compute_hash(c2)
         if compute_hash(c2) != h_c2: return 15
         if compute_identity_hash(s) == h_s: return 16   # unlikely
         i = 0
         while i < 6:
             rgc.collect()
             if compute_hash(c2) != h_c2: return i
             i += 1
         return 42
     return f

    def _pure_lookup_where_with_method_cache(w_self, name, version_tag):
        space = w_self.space
        SHIFT = r_uint.BITS - space.config.objspace.std.methodcachesizeexp
        version_tag_as_int = current_object_addr_as_int(version_tag)
        # ^^^Note: if the version_tag object is moved by a moving GC, the
        # existing method cache entries won't be found any more; new
        # entries will be created based on the new address.  The
        # assumption is that the version_tag object won't keep moving all
        # the time - so using the fast current_object_addr_as_int() instead
        # of a slower solution like hash() is still a good trade-off.
        hash_name = compute_hash(name)
        method_hash = r_uint(intmask(version_tag_as_int * hash_name)) >> SHIFT
        cached_version_tag = space.method_cache_versions[method_hash]
        if cached_version_tag is version_tag:
            cached_name = space.method_cache_names[method_hash]
            if cached_name is name:
                tup = space.method_cache_lookup_where[method_hash]
                if space.config.objspace.std.withmethodcachecounter:
                    space.method_cache_hits[name] = \
                            space.method_cache_hits.get(name, 0) + 1
#                print "hit", w_self, name
                return tup
        tup = w_self._lookup_where_all_typeobjects(name)
        space.method_cache_versions[method_hash] = version_tag
        space.method_cache_names[method_hash] = name
        space.method_cache_lookup_where[method_hash] = tup
        if space.config.objspace.std.withmethodcachecounter:
            space.method_cache_misses[name] = \
                    space.method_cache_misses.get(name, 0) + 1
#        print "miss", w_self, name
        return tup

 def _index_cache(self, selector):
     space = self.space
     cache = space.fromcache(IndexCache)
     SHIFT2 = r_uint.BITS - space.config.objspace.std.methodcachesizeexp
     SHIFT1 = SHIFT2 - 5
     attrs_as_int = objectmodel.current_object_addr_as_int(self)
     # ^^^Note: see comment in typeobject.py for
     # _pure_lookup_where_with_method_cache()
     hash_selector = objectmodel.compute_hash(selector)
     product = intmask(attrs_as_int * hash_selector)
     index_hash = (r_uint(product) ^ (r_uint(product) << SHIFT1)) >> SHIFT2
     # ^^^Note2: same comment too
     cached_attr = cache.attrs[index_hash]
     if cached_attr is self:
         cached_selector = cache.selectors[index_hash]
         if cached_selector == selector:
             index = cache.indices[index_hash]
             if space.config.objspace.std.withmethodcachecounter:
                 name = selector[0]
                 cache.hits[name] = cache.hits.get(name, 0) + 1
             return index
     index = self._index(selector)
     cache.attrs[index_hash] = self
     cache.selectors[index_hash] = selector
     cache.indices[index_hash] = index
     if space.config.objspace.std.withmethodcachecounter:
         name = selector[0]
         cache.misses[name] = cache.misses.get(name, 0) + 1
     return index

 def f(n):
     x = ''
     while n > 13:
         myjitdriver.can_enter_jit(n=n, x=x)
         myjitdriver.jit_merge_point(n=n, x=x)
         x += chr(n)
         n -= 1
     return compute_hash(x)

 def descr_code__hash__(self):
     space = self.space
     result =  compute_hash(self.co_name)
     result ^= self.co_argcount
     result ^= self.co_nlocals
     result ^= self.co_flags
     result ^= self.co_firstlineno
     result ^= compute_hash(self.co_code)
     for name in self.co_varnames:  result ^= compute_hash(name)
     for name in self.co_freevars:  result ^= compute_hash(name)
     for name in self.co_cellvars:  result ^= compute_hash(name)
     w_result = space.wrap(intmask(result))
     for w_name in self.co_names_w:
         w_result = space.xor(w_result, space.hash(w_name))
     for w_const in self.co_consts_w:
         w_result = space.xor(w_result, space.hash(w_const))
     return w_result

def hash__Unicode(space, w_uni):
    s = w_uni._value
    if space.config.objspace.std.withrope:
        # be compatible with the special ropes hash
        # XXX no caching
        if len(s) == 0:
            return space.wrap(0)
        x = 0
        for c in s:
            x = intmask((1000003 * x) + ord(c))
        x <<= 1
        x ^= len(s)
        x ^= ord(s[0])
        h = intmask(x)
        return space.wrap(h)
    x = compute_hash(s)
    return space.wrap(x)

 def f():
     if compute_hash(c) != compute_identity_hash(c): return 12
     if compute_hash(d) != h_d: return 13
     if compute_hash(("Hi", None, (7.5, 2, d))) != h_t: return 14
     c2 = C()
     h_c2 = compute_hash(c2)
     if compute_hash(c2) != h_c2: return 15
     if compute_identity_hash(s) == h_s: return 16   # unlikely
     i = 0
     while i < 6:
         rgc.collect()
         if compute_hash(c2) != h_c2: return i
         i += 1
     return 42

 def hash(self, space):
     # XXX duplicate logic from tupleobject.py
     mult = 1000003
     x = 0x345678
     z = nValues
     for i in iter_n:
         value = getattr(self, 'value%s' % i)
         if typetuple[i] == object:
             y = space.int_w(space.hash(value))
         elif typetuple[i] == float:
             # get the correct hash for float which is an
             # integer & other less frequent cases
             from pypy.objspace.std.floatobject import _hash_float
             y = _hash_float(space, value)
         else:
             y = compute_hash(value)
         x = (x ^ y) * mult
         z -= 1
         mult += 82520 + z + z
     x += 97531
     return space.wrap(intmask(x))

    def _pure_lookup_where_with_method_cache(w_self, name, version_tag):
        space = w_self.space
        cache = space.fromcache(MethodCache)
        SHIFT2 = r_uint.BITS - space.config.objspace.std.methodcachesizeexp
        SHIFT1 = SHIFT2 - 5
        version_tag_as_int = current_object_addr_as_int(version_tag)
        # ^^^Note: if the version_tag object is moved by a moving GC, the
        # existing method cache entries won't be found any more; new
        # entries will be created based on the new address.  The
        # assumption is that the version_tag object won't keep moving all
        # the time - so using the fast current_object_addr_as_int() instead
        # of a slower solution like hash() is still a good trade-off.
        hash_name = compute_hash(name)
        product = intmask(version_tag_as_int * hash_name)
        method_hash = (r_uint(product) ^ (r_uint(product) << SHIFT1)) >> SHIFT2
        # ^^^Note2: we used to just take product>>SHIFT2, but on 64-bit
        # platforms SHIFT2 is really large, and we loose too much information
        # that way (as shown by failures of the tests that typically have
        # method names like 'f' who hash to a number that has only ~33 bits).
        cached_version_tag = cache.versions[method_hash]
        if cached_version_tag is version_tag:
            cached_name = cache.names[method_hash]
            if cached_name is name:
                tup = cache.lookup_where[method_hash]
                if space.config.objspace.std.withmethodcachecounter:
                    cache.hits[name] = cache.hits.get(name, 0) + 1
#                print "hit", w_self, name
                return tup
        tup = w_self._lookup_where_all_typeobjects(name)
        cache.versions[method_hash] = version_tag
        cache.names[method_hash] = name
        cache.lookup_where[method_hash] = tup
        if space.config.objspace.std.withmethodcachecounter:
            cache.misses[name] = cache.misses.get(name, 0) + 1
#        print "miss", w_self, name
        return tup

 def hash(self, storage):
     return compute_hash(self.unerase(storage))

 def f(n):
     s = malloc(UNICODE, n)
     s.hash = 0
     for i in range(n):
         s.chars[i] = unichr(ord("A") + i)
     return s.gethash() - compute_hash(u"ABCDE")

 def hash(self):
     return (compute_hash(self.name) ^ intmask(self.left.hash() << 1) ^
             intmask(self.right.hash() << 2))

 def f(x):
     return objectmodel.compute_hash(x)

def hash__String(space, w_str):
    s = w_str._value
    x = compute_hash(s)
    return wrapint(space, x)

 def _get_hash_(self):
     return compute_hash(self.value)

 def fn():
     obj = None
     return compute_hash(obj)

 def f(n):
     return compute_hash((n, 6)) == compute_hash((3, n * 2))