Ticket #15367: coerce_dict.pyx

File coerce_dict.pyx, 52.3 KB (added by nbruin, 8 years ago)

MonoDict? and TripleDict? implemented by open addressing

Line 
1#*****************************************************************************
2#       Copyright (C) 2007 Robert Bradshaw <robertwb@math.washington.edu>
3#                     2012 Simon King <simon.king@uni-jena.de>
4#                     2013 Nils Bruin <nbruin@sfu.ca>
5#
6#  Distributed under the terms of the GNU General Public License (GPL)
7#
8#                  http://www.gnu.org/licenses/
9#*****************************************************************************
10"""
11Containers for storing coercion data
12
13This module provides :class:`TripleDict` and :class:`MonoDict`. These are
14structures similar to :class:`~weakref.WeakKeyDictionary` in Python's weakref
15module, and are optimized for lookup speed. The keys for :class:`TripleDict`
16consist of triples (k1,k2,k3) and are looked up by identity rather than
17equality. The keys are stored by weakrefs if possible. If any one of the
18components k1, k2, k3 gets garbage collected, then the entry is removed from
19the :class:`TripleDict`.
20
21Key components that do not allow for weakrefs are stored via a normal
22refcounted reference. That means that any entry stored using a triple
23(k1,k2,k3) so that none of the k1,k2,k3 allows a weak reference behaves
24as an entry in a normal dictionary: Its existence in :class:`TripleDict`
25prevents it from being garbage collected.
26
27That container currently is used to store coercion and conversion maps between
28two parents (:trac:`715`) and to store homsets of pairs of objects of a
29category (:trac:`11521`). In both cases, it is essential that the parent
30structures remain garbage collectable, it is essential that the data access is
31faster than with a usual :class:`~weakref.WeakKeyDictionary`, and we enforce
32the "unique parent condition" in Sage (parent structures should be identical
33if they are equal).
34
35:class:`MonoDict` behaves similarly, but it takes a single item as a key. It
36is used for caching the parents which allow a coercion map into a fixed other
37parent (:trac:`12313`).
38
39By :trac:`14159`, :class:`MonoDict` and :class:`TripleDict` can be optionally
40used with weak references on the values.
41
42"""
43from cpython.list cimport *
44from cpython.mem cimport *
45from cpython.string cimport PyString_FromString
46from libc.string cimport memset
47from weakref import KeyedRef
48
49from cpython cimport Py_XINCREF, Py_XDECREF
50
51cdef extern from "Python.h":
52
53    Py_ssize_t PyInt_AsSsize_t(PyObject* io)
54    PyObject* PyWeakref_GetObject(object ref)
55    PyObject* Py_None
56    int PyList_SetItem(object list, Py_ssize_t index,PyObject * item) except -1
57
58    ctypedef int (*visitproc)(PyObject* ob, void* arg)
59    ctypedef struct PyTypeObject:
60        void * tp_traverse
61        void * tp_clear
62
63cpdef inline Py_ssize_t signed_id(x):
64    """
65    A function like Python's :func:`id` returning *signed* integers,
66    which are guaranteed to fit in a ``Py_ssize_t``.
67
68    Theoretically, there is no guarantee that two different Python
69    objects have different ``signed_id()`` values. However, under the
70    mild assumption that a C pointer fits in a ``Py_ssize_t``, this
71    is guaranteed.
72
73    TESTS::
74
75        sage: a = 1.23e45  # some object
76        sage: from sage.structure.coerce_dict import signed_id
77        sage: s = signed_id(a)
78        sage: id(a) == s or id(a) == s + 2**32 or id(a) == s + 2**64
79        True
80        sage: signed_id(a) <= sys.maxsize
81        True
82    """
83    return <Py_ssize_t><void *>(x)
84
85#it's important that this is not an interned string: this object
86#must be a unique sentinel. We could reuse the "dummy" sentinel
87#that is defined in python's dictobject.c
88
89cdef object dummy_object = PyString_FromString("dummy")
90cdef PyObject* dummy = <PyObject*><void *>dummy_object
91
92############################################
93# A note about how to store "id" keys in python structures:
94#
95# We use the type Py_ssize_t to store "id"s generated by the signed_id
96# function defined above. Assuming that Py_ssize_t is the same as a C
97# long (which is true on most Unix-like systems), this also has the
98# advantage that these Py_ssize_t values are stored as a Python "int"
99# (as opposed to "long"), which allow for fast conversion to/from C
100# types.
101#
102# There is one place where we have to be careful about signs:
103# Our hash values most naturally live in Py_ssize_t. We convert those into
104# an index into our bucket list by taking the hash modulo the number of buckets.
105# However, the modulo operator in C preserves the sign of the number we take the
106# modulus of, which is not what we want.
107# The solution is to always do
108# (<size_t> h) % modulus
109# to ensure we're doing an unsigned modulus.
110
111cdef struct mono_cell:
112    void* key_id
113    PyObject* key_weakref
114    PyObject* value
115
116cdef object extract_mono_cell(mono_cell *cell):
117    #takes the refcounted components from a mono_cell
118    #and puts them in a list and returns it.
119    #The mono_cell itself is marked as "freed".
120    #The refcounts originally accounting for the
121    #presence in the mono_cell now account for the presence
122    #in the returned list.
123    #
124    #the returned result is only used to throw away:
125    #an advantage is that the containing list participates
126    #in CPython's trashcan, which prevents stack overflow
127    #on large dereffing cascades.
128    #
129    #a slight disadvantage is that this routine needs to
130    #allocate a list (mainly just to be thrown away)
131    if cell.key_id != NULL and cell.key_id != dummy :
132        L=PyList_New(2)
133        PyList_SetItem(L,0,cell.key_weakref)
134        PyList_SetItem(L,1,cell.value)
135        cell.key_id=dummy
136        cell.key_weakref=NULL
137        cell.value=NULL
138        return L
139    else:
140        raise RuntimeError("unused mono_cell")
141
142cdef struct triple_cell:
143    void* key_id1
144    void* key_id2
145    void* key_id3
146    PyObject* key_weakref1
147    PyObject* key_weakref2
148    PyObject* key_weakref3
149    PyObject* value
150
151cdef object extract_triple_cell(triple_cell *cell):
152    #see extract_mono_cell for the rationale
153    #behind this routine.
154    if cell.key_id1 != NULL and cell.key_id1 != dummy :
155        L=PyList_New(4)
156        PyList_SetItem(L,0,cell.key_weakref1)
157        PyList_SetItem(L,1,cell.key_weakref2)
158        PyList_SetItem(L,2,cell.key_weakref3)
159        PyList_SetItem(L,3,cell.value)
160        cell.key_id1=dummy
161        cell.key_id2=NULL
162        cell.key_id3=NULL
163        cell.key_weakref1=NULL
164        cell.key_weakref2=NULL
165        cell.key_weakref3=NULL
166        cell.value=NULL
167        return L
168    else:
169        raise RuntimeError("unused triple_cell")
170
171cdef class MonoDict:
172    """
173    This is a hashtable specifically designed for (read) speed in
174    the coercion model.
175
176    It differs from a python WeakKeyDictionary in the following important ways:
177
178       - Comparison is done using the 'is' rather than '==' operator.
179       - Only weak references to the keys are stored if at all possible.
180         Keys that do not allow for weak references are stored with a normal
181         refcounted reference.
182       - The callback of the weak references is safe against recursion, see below.
183
184    There are special cdef set/get methods for faster access.
185    It is bare-bones in the sense that not all dictionary methods are
186    implemented.
187
188    IMPLEMENTATION:
189
190    It is implemented as a hash table with open addressing, similar to python's
191    dict.
192
193    If ki supports weak references then ri is a weak reference to ki with a
194    callback to remove the entry from the dictionary if ki gets garbage
195    collected. If ki is does not support weak references then ri is identical to ki.
196    In the latter case the presence of the key in the dictionary prevents it from
197    being garbage collected.
198
199    INPUT:
200
201    - ``size`` -- unused parameter, present for backward compatibility.
202    - ``data`` -- optional iterable defining initial data.
203    - ``threshold`` -- unused parameter, present for backward compatibility.
204    - ``weak_values`` -- optional bool (default False). If it is true, weak references
205      to the values in this dictionary will be used, when possible.
206
207    EXAMPLES::
208
209        sage: from sage.structure.coerce_dict import MonoDict
210        sage: L = MonoDict(31)
211        sage: a = 'a'; b = 'ab'; c = -15
212        sage: L[a] = 1
213        sage: L[b] = 2
214        sage: L[c] = 3
215
216    The key is expected to be a unique object. Hence, the item stored for ``c``
217    can not be obtained by providing another equal number::
218
219        sage: L[a]
220        1
221        sage: L[b]
222        2
223        sage: L[c]
224        3
225        sage: L[-15]
226        Traceback (most recent call last):
227        ...
228        KeyError: -15
229
230    Not all features of Python dictionaries are available, but iteration over
231    the dictionary items is possible::
232
233        sage: # for some reason the following failed in "make ptest"
234        sage: # on some installations, see #12313 for details
235        sage: sorted(L.iteritems()) # random layout
236        [(-15, 3), ('a', 1), ('ab', 2)]
237        sage: # the following seems to be more consistent
238        sage: set(L.iteritems())
239        set([('a', 1), ('ab', 2), (-15, 3)])
240        sage: del L[c]
241        sage: sorted(L.iteritems())
242        [('a', 1), ('ab', 2)]
243        sage: len(L)
244        2
245        sage: for i in range(1000):
246        ...       L[i] = i
247        sage: len(L)
248        1002
249        sage: L['a']
250        1
251        sage: L['c']
252        Traceback (most recent call last):
253        ...
254        KeyError: 'c'
255
256    Note that this kind of dictionary is also used for caching actions
257    and coerce maps. In previous versions of Sage, the cache was by
258    strong references and resulted in a memory leak in the following
259    example. However, this leak was fixed by :trac:`715`, using
260    weak references::
261
262        sage: K = GF(1<<55,'t')
263        sage: for i in range(50):
264        ...     a = K.random_element()
265        ...     E = EllipticCurve(j=a)
266        ...     P = E.random_point()
267        ...     Q = 2*P
268        sage: import gc
269        sage: n = gc.collect()
270        sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field
271        sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)]
272        sage: len(LE)    # indirect doctest
273        1
274
275    TESTS:
276
277    Here, we demonstrate the use of weak values.
278    ::
279
280        sage: M = MonoDict(13)
281        sage: MW = MonoDict(13, weak_values=True)
282        sage: class Foo: pass
283        sage: a = Foo()
284        sage: b = Foo()
285        sage: k = 1
286        sage: M[k] = a
287        sage: MW[k] = b
288        sage: M[k] is a
289        True
290        sage: MW[k] is b
291        True
292        sage: k in M
293        True
294        sage: k in MW
295        True
296
297    While ``M`` uses a strong reference to ``a``, ``MW`` uses a *weak*
298    reference to ``b``, and after deleting ``b``, the corresponding item of
299    ``MW`` will be removed during the next garbage collection::
300
301        sage: import gc
302        sage: del a,b
303        sage: _ = gc.collect()
304        sage: k in M
305        True
306        sage: k in MW
307        False
308        sage: len(MW)
309        0
310        sage: len(M)
311        1
312
313   Note that ``MW`` also accepts values that do not allow for weak references::
314
315        sage: MW[k] = int(5)
316        sage: MW[k]
317        5
318
319    The following demonstrates that :class:`MonoDict` is safer than
320    :class:`~weakref.WeakKeyDictionary` against recursions created by nested
321    callbacks; compare :trac:`15069` (the mechanism used now is different, though)::
322
323        sage: M = MonoDict(11)
324        sage: class A: pass
325        sage: a = A()
326        sage: prev = a
327        sage: for i in range(1000):
328        ....:     newA = A()
329        ....:     M[prev] = newA
330        ....:     prev = newA
331        sage: len(M)
332        1000
333        sage: del a
334        sage: len(M)
335        0
336
337    The corresponding example with a Python :class:`weakref.WeakKeyDictionary`
338    would result in a too deep recursion during deletion of the dictionary
339    items::
340
341        sage: import weakref
342        sage: M = weakref.WeakKeyDictionary()
343        sage: a = A()
344        sage: prev = a
345        sage: for i in range(1000):
346        ....:     newA = A()
347        ....:     M[prev] = newA
348        ....:     prev = newA
349        sage: len(M)
350        1000
351        sage: del a
352        Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <function remove at ...> ignored
353        sage: len(M)>0
354        True
355
356    Check that also in the presence of circular references, :class:`MonoDict`
357    gets properly collected::
358   
359        sage: import gc
360        sage: def count_type(T):
361        ....:     return len([c for c in gc.get_objects() if isinstance(c,T)])
362        sage: _=gc.collect()
363        sage: N=count_type(MonoDict)
364        sage: for i in range(100):
365        ....:     V = [ MonoDict(11,{"id":j+100*i}) for j in range(100)]
366        ....:     n= len(V)
367        ....:     for i in range(n): V[i][V[(i+1)%n]]=(i+1)%n
368        ....:     del V
369        ....:     _=gc.collect()
370        ....:     assert count_type(MonoDict) == N
371        sage: count_type(MonoDict) == N
372        True
373
374    AUTHORS:
375
376    - Simon King (2012-01)
377    - Nils Bruin (2012-08)
378    - Simon King (2013-02)
379    - Nils Bruin (2013-11)
380    """
381    cdef mono_cell* lookup(self, PyObject* key):
382        """
383        This routine is used for all cases where a (potential) spot for
384        a key is looked up. The returned value is a pointer into the dictionary
385        store that either contains an entry with the requested key or a free spot
386        where an entry for that key should go.
387        """
388        cdef size_t perturb
389        cdef size_t mask = self.mask
390        cdef mono_cell* table = self.table
391        cdef mono_cell* cursor
392        cdef mono_cell* first_freed = NULL
393
394        #We seed our starting probe using the higher bits of the key as well.
395        #Our hash is a memory location, so the bottom bits are likely 0.
396
397        cdef size_t i = ((<size_t>key)>>8+(<size_t>key))
398        if key == NULL or key == dummy:
399            print("Request to look up invalid key")
400        cursor = &(table[i & mask])
401        # if the cell was never used, the entry wasn't there
402        perturb = (<size_t>key)>>3
403
404        #the probing algorithm is heavily inspired by python's own dict.
405        #there is always at least one NULL entry in the store, and the probe
406        #sequence eventually covers the entire store (see python's dictobject.c),
407        #so the loop below does terminate. Since this loop executes only
408        #straightforward C, we know the table will not change.
409
410        while (cursor.key_id != key):
411            if cursor.key_id == NULL:
412                return first_freed if (first_freed != NULL) else cursor
413            if first_freed == NULL and cursor.key_id == dummy:
414                first_freed = cursor
415            i = 5*i + perturb +1
416            cursor = &(table[i & mask])
417            perturb = perturb >> 5
418        return cursor
419   
420    cdef resize(self):
421        """
422        Resize dictionary. That can also mean shrink! Size is always a power of 2.
423        """
424        cdef mono_cell* old_table=self.table
425        cdef size_t old_mask = self.mask
426        cdef size_t newsize = 8
427        cdef size_t minsize = 2*self.used
428        cdef size_t i
429        cdef mono_cell* cursor
430        cdef mono_cell* entry
431        while newsize < minsize:
432            newsize = newsize<<1
433        cdef mono_cell* table = <mono_cell*> PyMem_Malloc((newsize)*sizeof(mono_cell))
434        if table == NULL:
435            raise MemoryError()
436        memset(table,0,(newsize)*sizeof(mono_cell))
437       
438        #we're done with memory activity. We can move the new (empty) table into place:
439       
440        self.table = table
441        self.mask = newsize-1
442        self.used = 0
443        self.fill = 0
444       
445        #and move all entries over. We're not changing any refcounts here, so this is a very
446        #tight loop that doesn't need to worry about tables changing.
447       
448        for i in range(old_mask+1):
449            entry = &(old_table[i])
450            if entry.key_id != NULL and entry.key_id != dummy:
451                cursor=self.lookup(<PyObject*>(entry.key_id))
452                assert cursor.key_id == NULL
453                cursor[0]=entry[0]
454                self.used +=1
455                self.fill +=1
456        PyMem_Free(old_table)
457   
458    def __init__(self, size=11, data=None, threshold=0.7, weak_values=False):
459        """
460        Create a special dict using singletons for keys.
461
462        EXAMPLES::
463
464            sage: from sage.structure.coerce_dict import MonoDict
465            sage: L = MonoDict(31)
466            sage: a = 'a'
467            sage: L[a] = 1
468            sage: L[a]
469            1
470            sage: L = MonoDict({a: 1})
471            sage: L[a]
472            1
473        """
474        #if only one argument is supplied and it's iterable, use it for data rather than
475        #for size. This way we're compatible with the old calling sequence (an integer is
476        #just ignored) and we can also use the more usual construction.
477        if data is None:
478            try:
479                data=size.iteritems()
480            except AttributeError:
481                try:
482                    data=iter(size)
483                except TypeError:
484                    pass
485        else:
486            try:
487                data=data.iteritems()
488            except AttributeError:
489                pass
490        if self.table != NULL:
491            raise RuntimeError("table already initialized. Called __init__ second time?")
492        cdef minsize = 8
493        cdef size_t newsize = 1<<3
494        while newsize < minsize:
495            newsize = newsize <<1
496        self.mask = newsize - 1
497        cdef mono_cell* table = <mono_cell*> PyMem_Malloc(newsize*sizeof(mono_cell))
498        if table == NULL:
499            raise MemoryError()
500        memset(table,0,newsize*sizeof(mono_cell))
501        self.table = table
502        self.used = 0
503        self.fill = 0
504
505        #our eraser is defined using a closure
506        def eraser(r):
507            cdef MonoDict cself = self
508           
509            #upon table teardown the table could be set to NULL, in which case
510            #erasing is not required
511            if cself.table == NULL:
512                return
513               
514            cdef mono_cell* cursor = cself.lookup(<PyObject*><Py_ssize_t>r.key)
515            if (cursor.key_id != NULL and  cursor.key_id != dummy):
516                if (cursor.key_weakref == <PyObject*><void*>r or cursor.value == <PyObject*><void*>r):
517                    L=extract_mono_cell(cursor)
518                    self.used -= 1
519                else:
520                    #this should probably never happen
521                    raise RuntimeError("eraser: key match but no weakref match")
522            else:
523                #this is conceivable, but I haven't seen it happen.
524                #raise RuntimeError("eraser: no key match")
525                pass
526        self.eraser = eraser
527        self.weak_values = weak_values
528        if data:
529            for k,v in data:
530                self.set(k,v)
531
532    def __dealloc__(self):
533        """
534        Ensure that the memory allocated by a MonoDict is properly freed.
535        """
536        #is this required or does this get called anyway if we set tp_clear properly?
537        #at least it's safe, since MonoDict_clear check if it has already run.
538        MonoDict_clear(self)
539
540    def __len__(self):
541        """
542        The number of items in self.
543        EXAMPLES::
544
545            sage: from sage.structure.coerce_dict import MonoDict
546            sage: L = MonoDict(37)
547            sage: a = 'a'; b = 'b'; c = 'c'
548            sage: L[a] = 1
549            sage: L[a] = -1 # re-assign
550            sage: L[b] = 1
551            sage: L[c] = None
552            sage: len(L)
553            3
554        """
555        return self.used
556
557    def __contains__(self, k):
558        """
559        Test if the dictionary contains a given key.
560
561        EXAMPLES::
562
563            sage: from sage.structure.coerce_dict import MonoDict
564            sage: L = MonoDict(31)
565            sage: a = 'a'; b = 'ab'; c = 15
566            sage: L[a] = 1
567            sage: L[b] = 2
568            sage: L[c] = 3
569            sage: c in L         # indirect doctest
570            True
571
572        The keys are compared by identity, not by equality. Hence, we have::
573
574            sage: c == 15
575            True
576            sage: 15 in L
577            False
578        """
579        cdef mono_cell* cursor = self.lookup(<PyObject*><void*>k)
580        if cursor.key_id == NULL or cursor.key_id == dummy:
581            return False
582        r = <object>cursor.key_weakref
583        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
584            return False
585        elif not(self.weak_values):
586            return True
587        else:
588            value = <object>cursor.value
589            return (not isinstance(value,KeyedRef)) or PyWeakref_GetObject(value) != Py_None
590
591    def __getitem__(self, k):
592        """
593        Get the value corresponding to a key.
594
595        EXAMPLES::
596
597            sage: from sage.structure.coerce_dict import MonoDict
598            sage: L = MonoDict(31)
599            sage: a = 'a'; b = 'b'; c = 15
600            sage: L[a] = 1
601            sage: L[b] = 2
602            sage: L[c] = 3
603            sage: L[c]                  # indirect doctest
604            3
605
606        Note that the keys are supposed to be unique::
607
608            sage: c==15
609            True
610            sage: c is 15
611            False
612            sage: L[15]
613            Traceback (most recent call last):
614            ...
615            KeyError: 15
616        """
617        return self.get(k)
618
619    cdef get(self, object k):
620        cdef mono_cell* cursor = self.lookup(<PyObject*><void *>k)
621        if cursor.key_id == NULL or cursor.key_id == dummy:
622            raise KeyError, k
623        r = <object>cursor.key_weakref
624        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
625            raise KeyError, k
626        value = <object>cursor.value
627        if self.weak_values and isinstance(value,KeyedRef):
628            value = <object>PyWeakref_GetObject(value)
629            if value is None:
630                raise KeyError, k
631        return value
632
633    def __setitem__(self, k, value):
634        """
635        Set the value corresponding to a key.
636
637        EXAMPLES::
638
639            sage: from sage.structure.coerce_dict import MonoDict
640            sage: L = MonoDict(31)
641            sage: a = 'a'
642            sage: L[a] = -1   # indirect doctest
643            sage: L[a]
644            -1
645            sage: L[a] = 1
646            sage: L[a]
647            1
648            sage: len(L)
649            1
650        """
651        self.set(k,value)
652
653    cdef set(self,object k, object value):
654        cdef mono_cell entry
655        cdef PyObject* old_value = NULL
656        cdef bint maybe_resize = False
657        entry.key_id = <void*>k
658        if self.weak_values:
659            try:
660                value_store = KeyedRef(value,self.eraser,<Py_ssize_t><void *>(k))
661                entry.value = <PyObject*><void*>value_store
662            except TypeError:
663                entry.value = <PyObject*><void*>value
664        else:
665            entry.value = <PyObject*><void*>value
666        Py_XINCREF(entry.value)
667        cursor = self.lookup(<PyObject*><void*>k)
668        if cursor.key_id == NULL or cursor.key_id == dummy:
669            self.used += 1
670            if cursor.key_id == NULL:
671                self.fill += 1
672                maybe_resize = True
673            try:
674                key_store=KeyedRef(k,self.eraser,<Py_ssize_t><void *>(k))
675                entry.key_weakref = <PyObject*><void*>key_store
676            except TypeError:
677                entry.key_weakref = <PyObject*><void*>k
678            Py_XINCREF(entry.key_weakref)
679
680            #we're taking a bit of a gamble here: we're assuming the dictionary has
681            #not been resized (otherwise cursor might not be a valid location
682            #anymore). The only way in which that could happen is if the allocation
683            #activity above forced a GC that triggered code that ADDS entries to this
684            #dictionary: the dictionary can only get reshaped if self.fill increases.
685            #(as happens below). Note that we're holding a strong ref to the dict
686            #itself, so that's not liable to disappear.
687            #for the truly paranoid: we could detect a change by checking if self.table
688            #has changed value
689            cursor[0] = entry
690
691            #this is the one place where resize gets called:
692            if maybe_resize and 3*self.fill > 2*self.mask: self.resize()
693        else:
694            old_value = cursor.value
695            cursor.value = entry.value
696            Py_XDECREF(old_value)
697
698    def __delitem__(self, k):
699        """
700        Delete the value corresponding to a key.
701
702        EXAMPLES::
703
704            sage: from sage.structure.coerce_dict import MonoDict
705            sage: L = MonoDict(31)
706            sage: a = 15
707            sage: L[a] = -1
708            sage: len(L)
709            1
710
711        Note that the keys are unique, hence using a key that is equal but not
712        identical to a results in an error::
713
714            sage: del L[15]
715            Traceback (most recent call last):
716            ...
717            KeyError: 15
718            sage: a in L
719            True
720            sage: del L[a]
721            sage: len(L)
722            0
723            sage: a in L
724            False
725        """
726        cdef mono_cell* cursor = self.lookup(<PyObject *><void *>k)
727        if cursor.key_id == NULL or cursor.key_id==dummy:
728            raise KeyError, k
729        L=extract_mono_cell(cursor)
730        self.used -= 1
731
732    def iteritems(self):
733        """
734        EXAMPLES::
735
736            sage: from sage.structure.coerce_dict import MonoDict
737            sage: L = MonoDict(31)
738            sage: L[1] = None
739            sage: L[2] = True
740            sage: list(sorted(L.iteritems()))
741            [(1, None), (2, True)]
742        """
743        #iteration is tricky because the table could change from under us.
744        #the following iterates properly if the dictionary does not
745        #get "resize"d, which is guaranteed if no NEW entries in the
746        #dictionary are introduced. At least we make sure to get our data fresh
747        #from "self" every iteration, so that at least we're not reading random memory
748        #(if the dictionary changes, it's not guaranteed you get to see any particular entry)
749        cdef size_t i = 0
750        while i <= self.mask:
751            cursor = &(self.table[i])
752            i += 1
753            if cursor.key_id != NULL and cursor.key_id != dummy:
754                key = <object>(cursor.key_weakref)
755                value = <object>(cursor.value)
756                if isinstance(key,KeyedRef):
757                    key = <object>PyWeakref_GetObject(key)
758                    if key is None:
759                        print "found defunct key"
760                        continue
761                if self.weak_values and isinstance(value,KeyedRef):
762                    value = <object>PyWeakref_GetObject(value)
763                    if value is None:
764                        print "found defunct value"
765                        continue
766                yield (key, value)
767 
768    def pr(self):
769        cdef size_t i = 0
770        print "weak_values:",self.weak_values
771        print "used:",self.used
772        print "fill:",self.fill
773        print "mask:",self.mask
774        while i <= self.mask:
775            cursor = &(self.table[i])
776            i+=1
777            if cursor.key_id == NULL:
778                s0 = "-NUL-"
779            elif cursor.key_id == dummy:
780                s0 = "dummy"
781            else:
782                s0 = str(<long>cursor.key_id)
783            s1 = "NULL" if (cursor.key_weakref == NULL) else (str(<object>cursor.key_weakref))
784            s2 = "NULL" if (cursor.value == NULL) else (str(<object>cursor.value))
785            print "%s %s %s %s"%(i,s0,s1,s2)
786                       
787    def __reduce__(self):
788        """
789        Note that we don't expect equality as this class concerns itself with
790        object identity rather than object equality.
791
792        EXAMPLES::
793
794            sage: from sage.structure.coerce_dict import MonoDict
795            sage: L = MonoDict(31)
796            sage: L[1] = True
797            sage: loads(dumps(L)) == L
798            False
799            sage: list(loads(dumps(L)).iteritems())
800            [(1, True)]
801        """
802        return MonoDict, (11, dict(self.iteritems()), 0.7)
803
804#the cython supplied tp_traverse and tp_clear do not take the dynamically
805#allocated table into account, so we have to supply our own.
806#the only additional link to follow (that cython does pick up and we have
807#to replicate here) is the "eraser" which in its closure stores a reference
808#back to the dictionary itself (meaning that MonoDicts only disappear
809#on cyclic GC)
810
811cdef int MonoDict_traverse(MonoDict op, visitproc visit, void *arg):
812    cdef int r
813    if op.table == NULL:
814        return 0
815    table=op.table
816    cdef size_t i = 0
817    if (<void*>(op.eraser)):
818        r=visit(<PyObject*><void*>(op.eraser),arg)
819        if r: return r
820    for i in range(op.mask+1):
821        cursor = &table[i]
822        if cursor.key_id != NULL and cursor.key_id != dummy:
823            r=visit(cursor.key_weakref,arg)
824            if r: return r
825            r=visit(cursor.value,arg)
826            if r: return r
827    return 0
828
829
830#we clear a monodict by taking first taking away the table before dereffing
831#its contents. That shortcuts callbacks, so we deref the entries straight here.
832#that means this code does not participate in Python's trashcan the way that
833#deletion code based on extract_mono_cell does, so there is probably a way
834#this code can be used to overflow the C stack. It would have to be a pretty
835#devious example, though.
836cdef int MonoDict_clear(MonoDict op):   
837    if op.table == NULL:
838        return 0
839
840    tmp=op.eraser
841    cdef mono_cell* table=op.table
842    cdef size_t mask=op.mask
843    op.table=NULL
844   
845    op.eraser=None
846    op.mask=0
847    op.used=0
848    op.fill=0
849   
850    #this deletion method incurs an extra refcount +-, but it seems very difficult in cython to do it
851    #any other way and still be sure that the reference op.eraser is gone by the time the object gets
852    #deallocated.
853    del tmp
854    for i in range(mask+1):
855        cursor = &(table[i])
856        if cursor.key_id != NULL and cursor.key_id != dummy:
857            cursor.key_id = dummy
858            Py_XDECREF(cursor.key_weakref)
859            Py_XDECREF(cursor.value)
860    PyMem_Free(table)
861    return 0
862
863(<PyTypeObject *><void *>MonoDict).tp_traverse = &MonoDict_traverse
864(<PyTypeObject *><void *>MonoDict).tp_clear = &MonoDict_clear
865
866cdef class TripleDict:
867    """
868    This is a hashtable specifically designed for (read) speed in
869    the coercion model.
870
871    It differs from a python dict in the following important ways:
872
873       - All keys must be sequence of exactly three elements. All sequence
874         types (tuple, list, etc.) map to the same item.
875       - Comparison is done using the 'is' rather than '==' operator.
876
877    There are special cdef set/get methods for faster access.
878    It is bare-bones in the sense that not all dictionary methods are
879    implemented.
880
881    It is implemented as a list of lists (hereafter called buckets). The bucket is
882    chosen according to a very simple hash based on the object pointer, and each
883    bucket is of the form [id(k1), id(k2), id(k3), r1, r2, r3, value, id(k1),
884    id(k2), id(k3), r1, r2, r3, value, ...], on which a linear search is performed.
885    If a key component ki supports weak references then ri is a weak reference to
886    ki; otherwise ri is identical to ki.
887
888    INPUT:
889
890    - ``size`` -- an integer, the initial number of buckets. To spread objects
891      evenly, the size should ideally be a prime, and certainly not divisible
892      by 2.
893    - ``data`` -- optional iterable defining initial data.
894    - ``threshold`` -- optional number, default `0.7`. It determines how frequently
895      the dictionary will be resized (large threshold implies rare resizing).
896    - ``weak_values`` -- optional bool (default False). If it is true, weak references
897      to the values in this dictionary will be used, when possible.
898
899    If any of the key components k1,k2,k3 (this can happen for a key component
900    that supports weak references) gets garbage collected then the entire
901    entry disappears. In that sense this structure behaves like a nested
902    :class:`~weakref.WeakKeyDictionary`.
903
904    EXAMPLES::
905
906        sage: from sage.structure.coerce_dict import TripleDict
907        sage: L = TripleDict(31)
908        sage: a = 'a'; b = 'b'; c = 'c'
909        sage: L[a,b,c] = 1
910        sage: L[a,b,c]
911        1
912        sage: L[c,b,a] = -1
913        sage: list(L.iteritems())     # random order of output.
914        [(('c', 'b', 'a'), -1), (('a', 'b', 'c'), 1)]
915        sage: del L[a,b,c]
916        sage: list(L.iteritems())
917        [(('c', 'b', 'a'), -1)]
918        sage: len(L)
919        1
920        sage: for i in range(1000):
921        ...       L[i,i,i] = i
922        sage: len(L)
923        1001
924        sage: L = TripleDict(101, L)
925        sage: L = TripleDict(3, L)
926        sage: L[c,b,a]
927        -1
928        sage: L[a,b,c]
929        Traceback (most recent call last):
930        ...
931        KeyError: ('a', 'b', 'c')
932        sage: L[a]
933        Traceback (most recent call last):
934        ...
935        KeyError: 'a'
936        sage: L[a] = 1
937        Traceback (most recent call last):
938        ...
939        KeyError: 'a'
940
941    The following illustrates why even sizes are bad (setting the threshold
942    zero, so that no beneficial resizing happens)::
943
944        sage: L = TripleDict(4, L, threshold=0)
945
946    Note that this kind of dictionary is also used for caching actions
947    and coerce maps. In previous versions of Sage, the cache was by
948    strong references and resulted in a memory leak in the following
949    example. However, this leak was fixed by :trac:`715`, using weak
950    references::
951
952        sage: K = GF(1<<55,'t')
953        sage: for i in range(50):
954        ...     a = K.random_element()
955        ...     E = EllipticCurve(j=a)
956        ...     P = E.random_point()
957        ...     Q = 2*P
958        sage: import gc
959        sage: n = gc.collect()
960        sage: from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field
961        sage: LE = [x for x in gc.get_objects() if isinstance(x, EllipticCurve_finite_field)]
962        sage: len(LE)    # indirect doctest
963        1
964
965    TESTS:
966
967    Here, we demonstrate the use of weak values.
968    ::
969
970        sage: class Foo: pass
971        sage: T = TripleDict(13)
972        sage: TW = TripleDict(13, weak_values=True)
973        sage: a = Foo()
974        sage: b = Foo()
975        sage: k = 1
976        sage: T[a,k,k]=1
977        sage: T[k,a,k]=2
978        sage: T[k,k,a]=3
979        sage: T[k,k,k]=a
980        sage: TW[b,k,k]=1
981        sage: TW[k,b,k]=2
982        sage: TW[k,k,b]=3
983        sage: TW[k,k,k]=b
984        sage: len(T)
985        4
986        sage: len(TW)
987        4
988        sage: (k,k,k) in T
989        True
990        sage: (k,k,k) in TW
991        True
992        sage: T[k,k,k] is a
993        True
994        sage: TW[k,k,k] is b
995        True
996
997    Now, ``T`` holds a strong reference to ``a``, namely in ``T[k,k,k]``. Hence,
998    when we delete ``a``, *all* items of ``T`` survive::
999
1000        sage: del a
1001        sage: _ = gc.collect()
1002        sage: len(T)
1003        4
1004
1005    Only when we remove the strong reference, the items become collectable::
1006
1007        sage: del T[k,k,k]
1008        sage: _ = gc.collect()
1009        sage: len(T)
1010        0
1011
1012    The situation is different for ``TW``, since it only holds *weak*
1013    references to ``a``. Therefore, all items become collectable after
1014    deleting ``a``::
1015
1016        sage: del b
1017        sage: _ = gc.collect()
1018        sage: len(TW)
1019        0
1020
1021    .. NOTE::
1022
1023        The index `h` corresponding to the key [k1, k2, k3] is computed as a
1024        value of unsigned type size_t as follows:
1025
1026        .. MATH::
1027
1028            h = id(k1) + 13*id(k2) xor 503 id(k3)
1029
1030        The natural type for this quantity is Py_ssize_t, which is a signed
1031        quantity with the same length as size_t. Storing it in a signed way gives the most
1032        efficient storage into PyInt, while preserving sign information.
1033
1034        As usual for a hashtable, we take h modulo some integer to obtain the bucket
1035        number into which to store the key/value pair. A problem here is that C mandates
1036        sign-preservation for the modulo operator "%". We cast to an unsigned type, i.e.,
1037        (<size_t> h)% N
1038        If we don't do this we may end up indexing lists with negative indices, which may lead to
1039        segfaults if using the non-error-checking python macros, as happens here.
1040
1041        This has been observed on 32 bits systems, see :trac:`715` for details.
1042
1043    AUTHORS:
1044
1045    - Robert Bradshaw, 2007-08
1046
1047    - Simon King, 2012-01
1048
1049    - Nils Bruin, 2012-08
1050
1051    - Simon King, 2013-02
1052
1053    - Nils Bruin, 2013-11
1054    """
1055    cdef triple_cell* lookup(self, PyObject* key1, PyObject* key2, PyObject* key3):
1056        #returns a pointer to where key should be stored in this dictionary.
1057        cdef size_t perturb
1058        cdef size_t mask = self.mask
1059        cdef triple_cell* table = self.table
1060        cdef triple_cell* cursor
1061        cdef triple_cell* first_freed = NULL
1062        #we device some hash that reasonably depends on bits of all keys
1063        #making sure it's not commutative and also involves some of the higher order
1064        #bits at an early stage.
1065        cdef size_t key = <size_t>key1 + (<size_t>key2)<<2 + (<size_t>key3)<<4
1066        cdef size_t i = key>>8 + key
1067        cursor = &(table[i & mask])
1068        perturb = (key)>>3
1069        while (cursor.key_id1 != key1 or cursor.key_id2 != key2 or cursor.key_id3 != key3):
1070            if cursor.key_id1 == NULL:
1071                return first_freed if (first_freed != NULL) else cursor
1072            if first_freed == NULL and cursor.key_id1 == dummy:
1073                first_freed = cursor
1074            i = 5*i + perturb +1
1075            cursor = &(table[i & mask])
1076            perturb = perturb >> 5
1077        return cursor
1078
1079    cdef resize(self):
1080        cdef triple_cell* old_table=self.table
1081        cdef size_t old_mask = self.mask
1082        cdef size_t newsize = 8
1083        cdef size_t minsize = 2*self.used
1084        cdef size_t i
1085        cdef triple_cell* cursor
1086        cdef triple_cell* entry
1087        while newsize < minsize:
1088            newsize = newsize<<1
1089        cdef triple_cell* table = <triple_cell*> PyMem_Malloc((newsize)*sizeof(triple_cell))
1090        if table == NULL:
1091            raise MemoryError()
1092        memset(table,0,(newsize)*sizeof(triple_cell))
1093        self.table = table
1094        self.mask = newsize-1
1095        self.used = 0
1096        self.fill = 0
1097        for i in range(old_mask+1):
1098            entry = &(old_table[i])
1099            if entry.key_id1 != NULL and entry.key_id1 != dummy:
1100                cursor=self.lookup(<PyObject*>(entry.key_id1),<PyObject*>(entry.key_id2),<PyObject*>(entry.key_id3))
1101                assert cursor.key_id1 == NULL
1102                cursor[0]=entry[0]
1103                self.used +=1
1104                self.fill +=1
1105        PyMem_Free(old_table)
1106
1107    def __init__(self, size=11, data=None, threshold=0.7, weak_values=False):
1108        """
1109        Create a special dict using triples for keys.
1110
1111        EXAMPLES::
1112
1113            sage: from sage.structure.coerce_dict import TripleDict
1114            sage: L = TripleDict(31)
1115            sage: a = 'a'; b = 'b'; c = 'c'
1116            sage: L[a,b,c] = 1
1117            sage: L[a,b,c]
1118            1
1119        """
1120        #if only one argument is supplied and it's iterable, use it for data rather than
1121        #for size
1122        if data is None:
1123            try:
1124                data=size.iteritems()
1125            except AttributeError:
1126                try:
1127                    data=iter(size)
1128                except TypeError:
1129                    pass
1130        else:
1131            try:
1132                data=data.iteritems()
1133            except AttributeError:
1134                pass
1135        if self.table != NULL:
1136            raise RuntimeError("table already initialized. Called __init__ second time?")
1137        cdef minsize = 8
1138        cdef size_t newsize = 1<<3
1139        while newsize < minsize:
1140            newsize = newsize <<1
1141        self.mask = newsize - 1
1142        cdef triple_cell* table = <triple_cell*> PyMem_Malloc(newsize*sizeof(triple_cell))
1143        if table == NULL:
1144            raise MemoryError()
1145        memset(table,0,newsize*sizeof(triple_cell))
1146        self.table = table
1147        self.used = 0
1148        self.fill = 0
1149
1150        def eraser(r):
1151            cdef TripleDict cself = self
1152            if cself.table == NULL:
1153                return
1154                       
1155            k1,k2,k3 = r.key
1156            cdef triple_cell* cursor = cself.lookup(<PyObject*><Py_ssize_t>k1,<PyObject*><Py_ssize_t>k2,<PyObject*><Py_ssize_t>k3)
1157            if (cursor.key_id1 != NULL and  cursor.key_id1 != dummy):
1158                if (cursor.key_weakref1 == <PyObject*><void*>r or 
1159                        cursor.key_weakref2 == <PyObject*><void*>r or
1160                        cursor.key_weakref3 == <PyObject*><void*>r or
1161                        cursor.value == <PyObject*><void*>r):
1162                    L=extract_triple_cell(cursor)
1163                    self.used -= 1
1164                else:
1165                    raise RuntimeError("eraser: key match but no weakref match")
1166            else:
1167                #raise RuntimeError("eraser: no key match")
1168                pass 
1169        self.eraser = eraser
1170        self.weak_values = weak_values
1171        if data:
1172            for k,v in data:
1173                self[k]=v
1174
1175    def __dealloc__(self):
1176        #is this required? (TripleDict_clear is safe to call multiple times)
1177        TripleDict_clear(self)
1178       
1179    def __len__(self):
1180        """
1181        The number of items in self.
1182
1183        EXAMPLES::
1184
1185            sage: from sage.structure.coerce_dict import TripleDict
1186            sage: L = TripleDict(37)
1187            sage: a = 'a'; b = 'b'; c = 'c'
1188            sage: L[a,b,c] = 1
1189            sage: L[a,b,c] = -1 # re-assign
1190            sage: L[a,c,b] = 1
1191            sage: L[a,a,None] = None
1192            sage: len(L)
1193            3
1194        """
1195        return self.used
1196
1197    def __contains__(self, k):
1198        """
1199        Test if the dictionary contains a given key.
1200
1201        EXAMPLES::
1202
1203            sage: from sage.structure.coerce_dict import TripleDict
1204            sage: L = TripleDict(31)
1205            sage: a = 'a'; b = 'ab'; c = 15
1206            sage: L[a,b,c] = 123
1207            sage: (a,b,c) in L         # indirect doctest
1208            True
1209
1210        The keys are compared by identity, not by equality. Hence, we have::
1211
1212            sage: c == 15
1213            True
1214            sage: (a,b,15) in L
1215            False
1216        """
1217        cdef object k1,k2,k3
1218        try:
1219            k1, k2, k3 = k
1220        except (TypeError,ValueError):
1221            raise KeyError, k
1222        cdef triple_cell* cursor = self.lookup(<PyObject*><void*>k1,<PyObject*><void*>k2,<PyObject*><void*>k3)
1223        if cursor.key_id1 == NULL or cursor.key_id1 == dummy:
1224            return False
1225        r = <object>cursor.key_weakref1
1226        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1227            return False
1228        r = <object>cursor.key_weakref2
1229        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1230            return False
1231        r = <object>cursor.key_weakref3
1232        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1233            return False
1234        if not(self.weak_values):
1235            return True
1236        value = <object>cursor.value
1237        return (not isinstance(value,KeyedRef)) or PyWeakref_GetObject(value) != Py_None
1238
1239    def __getitem__(self, k):
1240        """
1241        Get the value corresponding to a key.
1242
1243        EXAMPLES::
1244
1245            sage: from sage.structure.coerce_dict import TripleDict
1246            sage: L = TripleDict(31)
1247            sage: a = 'a'; b = 'b'; c = 'c'
1248            sage: L[a,b,c] = 1
1249            sage: L[a,b,c]
1250            1
1251        """
1252        cdef object k1,k2,k3
1253        try:
1254            k1, k2, k3 = k
1255        except (TypeError,ValueError):
1256            raise KeyError, k
1257        return self.get(k1, k2, k3)
1258
1259    cdef get(self, object k1, object k2, object k3):
1260        cdef triple_cell* cursor = self.lookup(<PyObject*><void *>k1,<PyObject*><void *>k2,<PyObject*><void *>k3)
1261        if cursor.key_id1 == NULL or cursor.key_id1 == dummy:
1262            raise KeyError, (k1, k2, k3)
1263        r = <object>cursor.key_weakref1
1264        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1265            raise KeyError, (k1, k2, k3)
1266        r = <object>cursor.key_weakref2
1267        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1268            raise KeyError, (k1, k2, k3)
1269        r = <object>cursor.key_weakref3
1270        if isinstance(r, KeyedRef) and PyWeakref_GetObject(r) == Py_None:
1271            raise KeyError, (k1, k2, k3)
1272        value = <object>cursor.value
1273        if self.weak_values and isinstance(value,KeyedRef):
1274            value = <object>PyWeakref_GetObject(value)
1275            if value is None:
1276                raise KeyError, (k1, k2, k3)
1277        return value
1278
1279    def __setitem__(self, k, value):
1280        """
1281        Set the value corresponding to a key.
1282
1283        EXAMPLES::
1284
1285            sage: from sage.structure.coerce_dict import TripleDict
1286            sage: L = TripleDict(31)
1287            sage: a = 'a'; b = 'b'; c = 'c'
1288            sage: L[a,b,c] = -1
1289            sage: L[a,b,c]
1290            -1
1291        """
1292        cdef object k1,k2,k3
1293        try:
1294            k1, k2, k3 = k
1295        except (TypeError,ValueError):
1296            raise KeyError, k
1297        self.set(k1, k2, k3, value)
1298
1299    cdef set(self, object k1, object k2, object k3, value):
1300        cdef triple_cell entry
1301        cdef PyObject* old_value = NULL
1302        cdef bint maybe_resize = False
1303        entry.key_id1 = <void*>k1
1304        entry.key_id2 = <void*>k2
1305        entry.key_id3 = <void*>k3
1306        k = (<Py_ssize_t><void *>(k1),<Py_ssize_t><void *>(k2),<Py_ssize_t><void *>(k3))
1307        if self.weak_values:
1308            try:
1309                value_store = KeyedRef(value,self.eraser,k)
1310                entry.value = <PyObject*><void*>value_store
1311            except TypeError:
1312                entry.value = <PyObject*><void*>value
1313        else:
1314            entry.value = <PyObject*><void*>value
1315        Py_XINCREF(entry.value)
1316        cursor = self.lookup(<PyObject*><void*>k1,<PyObject*><void*>k2,<PyObject*><void*>k3)
1317        if cursor.key_id1 == NULL or cursor.key_id1 == dummy:
1318            self.used += 1
1319            if cursor.key_id1 == NULL:
1320                self.fill += 1
1321                maybe_resize = True
1322            try:
1323                key_store=KeyedRef(k1,self.eraser,k)
1324                entry.key_weakref1 = <PyObject*><void*>key_store
1325            except TypeError:
1326                entry.key_weakref1 = <PyObject*><void*>k1
1327            Py_XINCREF(entry.key_weakref1)
1328            try:
1329                key_store=KeyedRef(k2,self.eraser,k)
1330                entry.key_weakref2 = <PyObject*><void*>key_store
1331            except TypeError:
1332                entry.key_weakref2 = <PyObject*><void*>k2
1333            Py_XINCREF(entry.key_weakref2)
1334            try:
1335                key_store=KeyedRef(k3,self.eraser,k)
1336                entry.key_weakref3 = <PyObject*><void*>key_store
1337            except TypeError:
1338                entry.key_weakref3 = <PyObject*><void*>k3
1339            Py_XINCREF(entry.key_weakref3)
1340           
1341            #we're taking a bit of a gamble here: we're assuming the dictionary has
1342            #not been resized (otherwise cursor might not be a valid location
1343            #anymore). The only way in which that could happen is if the allocation
1344            #activity above forced a GC that triggered code that ADDS entries to this
1345            #dictionary: the dictionary can only get reshaped if self.fill increases.
1346            #(as happens below). Note that we're holding a strong ref to the dict
1347            #itself, so that's not liable to disappear.
1348            #for the truly paranoid: we could detect a change by checking if self.table
1349            #has changed value
1350            cursor[0] = entry
1351           
1352             #this is the only place where resize gets called:
1353            if maybe_resize and 3*self.fill > 2*self.mask: self.resize()
1354        else:
1355            old_value = cursor.value
1356            cursor.value = entry.value
1357            Py_XDECREF(old_value)
1358
1359    def __delitem__(self, k):
1360        """
1361        Delete the value corresponding to a key.
1362
1363        EXAMPLES::
1364
1365            sage: from sage.structure.coerce_dict import TripleDict
1366            sage: L = TripleDict(31)
1367            sage: a = 'a'; b = 'b'; c = 'c'
1368            sage: L[a,b,c] = -1
1369            sage: (a,b,c) in L
1370            True
1371            sage: del L[a,b,c]
1372            sage: len(L)
1373            0
1374            sage: (a,b,c) in L
1375            False
1376        """
1377        cdef object k1,k2,k3
1378        try:
1379            k1, k2, k3 = k
1380        except (TypeError,ValueError):
1381            raise KeyError, k
1382        cdef triple_cell* cursor = self.lookup(<PyObject *><void *>k1,<PyObject *><void *>k2,<PyObject *><void *>k3)
1383        if cursor.key_id1 == NULL or cursor.key_id1==dummy:
1384            raise KeyError, k
1385        L=extract_triple_cell(cursor)
1386        self.used -= 1
1387
1388    def iteritems(self):
1389        """
1390        EXAMPLES::
1391
1392            sage: from sage.structure.coerce_dict import TripleDict
1393            sage: L = TripleDict(31)
1394            sage: L[1,2,3] = None
1395            sage: list(L.iteritems())
1396            [((1, 2, 3), None)]
1397        """
1398       
1399        cdef size_t i = 0
1400        while i <= self.mask:
1401            cursor = &(self.table[i])
1402            i += 1
1403            if cursor.key_id1 != NULL and cursor.key_id1 != dummy:
1404                key1 = <object>(cursor.key_weakref1)
1405                key2 = <object>(cursor.key_weakref2)
1406                key3 = <object>(cursor.key_weakref3)
1407                value = <object>(cursor.value)
1408                if isinstance(key1,KeyedRef):
1409                    key1 = <object>PyWeakref_GetObject(key1)
1410                    if key1 is None:
1411                        print "found defunct key1"
1412                        continue
1413                if isinstance(key2,KeyedRef):
1414                    key2 = <object>PyWeakref_GetObject(key2)
1415                    if key2 is None:
1416                        print "found defunct key2"
1417                        continue
1418                if isinstance(key3,KeyedRef):
1419                    key3 = <object>PyWeakref_GetObject(key3)
1420                    if key3 is None:
1421                        print "found defunct key3"
1422                        continue
1423                if self.weak_values and isinstance(value,KeyedRef):
1424                    value = <object>PyWeakref_GetObject(value)
1425                    if value is None:
1426                        print "found defunct value"
1427                        continue
1428                yield ((key1,key2,key3), value)
1429
1430    def __reduce__(self):
1431        """
1432        Note that we don't expect equality as this class concerns itself with
1433        object identity rather than object equality.
1434
1435        EXAMPLES::
1436
1437            sage: from sage.structure.coerce_dict import TripleDict
1438            sage: L = TripleDict(31)
1439            sage: L[1,2,3] = True
1440            sage: loads(dumps(L)) == L
1441            False
1442            sage: list(loads(dumps(L)).iteritems())
1443            [((1, 2, 3), True)]
1444        """
1445        return TripleDict, (11, dict(self.iteritems()), 0.7)
1446
1447#the cython supplied tp_traverse and tp_clear do not take the dynamically
1448#allocated table into account, so we have to supply our own.
1449#the only additional link to follow (that cython does pick up and we have
1450#to replicate here) is the "eraser" which in its closure stores a reference
1451#back to the dictionary itself (meaning that MonoDicts only disappear
1452#on cyclic GC)
1453
1454cdef int TripleDict_traverse(TripleDict op, visitproc visit, void *arg):
1455    cdef int r
1456    if op.table == NULL:
1457        return 0
1458    table=op.table
1459    cdef size_t i = 0
1460    if (<void*>(op.eraser)):
1461        r=visit(<PyObject*><void*>(op.eraser),arg)
1462        if r: return r
1463    for i in range(op.mask+1):
1464        cursor = &table[i]
1465        if cursor.key_id1 != NULL and cursor.key_id1 != dummy:
1466            r=visit(cursor.key_weakref1,arg)
1467            if r: return r
1468            r=visit(cursor.key_weakref2,arg)
1469            if r: return r
1470            r=visit(cursor.key_weakref3,arg)
1471            if r: return r
1472            r=visit(cursor.value,arg)
1473            if r: return r
1474    return 0
1475           
1476cdef int TripleDict_clear(TripleDict op):
1477    if op.table == NULL:
1478        return 0
1479
1480    tmp=op.eraser
1481    cdef triple_cell* table=op.table
1482    cdef size_t mask=op.mask
1483    op.table=NULL
1484    op.eraser=None
1485    op.mask=0
1486    op.used=0
1487    op.fill=0
1488
1489    #refcount dance to ensure op.eraser==None when the actual object gets deallocated
1490    del tmp
1491    for i in range(mask+1):
1492        cursor = &(table[i])
1493        if cursor.key_id1 != NULL and cursor.key_id1 != dummy:
1494            cursor.key_id1 = dummy
1495            Py_XDECREF(cursor.key_weakref1)
1496            Py_XDECREF(cursor.key_weakref2)
1497            Py_XDECREF(cursor.key_weakref3)
1498            Py_XDECREF(cursor.value)
1499    PyMem_Free(table)
1500    return 0
1501
1502(<PyTypeObject *><void *>TripleDict).tp_traverse = &TripleDict_traverse
1503(<PyTypeObject *><void *>TripleDict).tp_clear = &TripleDict_clear