WeakDict's

1 Function

WeakDict's are very similar to normal Python dictionaries, with the following essential exceptions:

• all values in a WeakDict must be instances of WeakValue (or a derived class)
• the reference to a value in a WeakDict is NOT counted in the reference count of the value. Thus, it does not prevent the value from being garbaged collected.
• When a value is garbaged collected, the corresponding entry disappears from the WeakDict.

WeakDict's have an asymptotic timing efficiency similar to normal Python dicts. Deletion of WeakValue's can take linear time in the number of uses in WeakDict's.

The implementation is mostly in the Python module weakdict with some functions realized in _weakdict.c.

2 Download

• 0.02 Sources (Python and C): 12 kB tgz file
  Compilation and installation are currently only supported for Unix plattforms. See the README file for details.
• 0.01 Win32 binaries for Python 1.5.1/1.5.2a: 9 kB zip file thanks to David Ascher.

3 Example

from weakdict import WeakValue, WeakDict

class TreeNode(WeakValue):
  """a tree node with list of children and parent reference."""

  _children= _parent= None
  
  def __init__(self): # would usually have more parameters
    WeakValue.__init__(self)
    
  def getChildren(self):
    """returns children tuple of *self*."""
    children= self._children
    if children is None: return ()
    return tuple(children)

  def getParent(self):
    """returns parent of *self*; 'None' if there is no parent."""
    p= self._parent
    if p is None: return None
    else:
      # p is a WeakDict
      return p.get('parent')

  def insertBefore(self,node,before=None):
    """inserts *node* as child before *before*; if *before* in 'None',
    *node* becomes the last child."""
    children= self._children
    if children is None: children= self._children= []
    if before is None: children.append(node)
    else:
      i= children.index(before)
      children.insert(i,node)
    node._setParent(self)

  def _setParent(self,parent):
    """sets the parent reference to *parent*.

    A WeakDict is used to represent the reference in order to avoid cycles.
    """
    parentref= self._parent
    if parentref is None: parentref= self._parent= WeakDict()
    parentref['parent']= parent


def Main():
  """Build a tree, get reference to a leaf, then kill the tree."""
  root= TreeNode()
  innerNode= TreeNode(); root.insertBefore(innerNode,None)
  leaf= TreeNode(); innerNode.insertBefore(leaf,None)
  print "the tree is a chain of 3 elements: root, innernode, leaf"
  print 'leaf.getParent(), innerNode:', leaf.getParent(), innerNode
  print 'innerNode.getParent(), root:', innerNode.getParent(), root
  print "del root: innernode looses its parent"
  del root
  print 'innerNode.getParent():', innerNode.getParent()
  print "del innerNode: leaf looses its parent"
  del innerNode
  print 'leaf.getParent():', leaf.getParent()


if __name__ == '__main__':
  Main()

4 Versions

0.02

• fixed: has_key and __getitem__ on a new, still empty weakdict resulted in a SystemException.
  
• fixed: __setitem__ with a non hashable key caused (correctly) a type error but screwed up the weak value such that a segment violation resulted, when the weak value was finally deleted.