← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Martin Pool
  • Date: 2009-09-14 02:30:23 UTC
  • mto: This revision was merged to the branch mainline in revision 4693.
  • Revision ID: mbp@sourcefrog.net-20090914023023-ros0f3ndo04j3bww
https://launchpad.net/bugs/429151
Clearer docs about bzr help.  (Thanks to Naoki)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
51
51
 
52
52
    void Py_INCREF(object)
53
53
 
54
 
from collections import deque
55
54
import gc
56
55
 
57
56
from bzrlib import errors, revision
89
88
                PyList_Append(keys, child.key)
90
89
            return keys
91
90
 
92
 
    property parent_keys:
93
 
        def __get__(self):
94
 
            if self.parents is None:
95
 
                return None
96
 
            
97
 
            cdef _KnownGraphNode parent
98
 
 
99
 
            keys = []
100
 
            for parent in self.parents:
101
 
                PyList_Append(keys, parent.key)
102
 
            return keys
103
 
    
104
91
    cdef clear_references(self):
105
92
        self.parents = None
106
93
        self.children = None
193
180
    """This is a class which assumes we already know the full graph."""
194
181
 
195
182
    cdef public object _nodes
196
 
    cdef public object _known_heads
 
183
    cdef object _known_heads
197
184
    cdef public int do_cache
198
185
 
199
186
    def __init__(self, parent_map, do_cache=True):
233
220
            node = <_KnownGraphNode>temp_node
234
221
        return node
235
222
 
236
 
    cdef _populate_parents(self, _KnownGraphNode node, parent_keys):
237
 
        cdef Py_ssize_t num_parent_keys, pos
238
 
        cdef _KnownGraphNode parent_node
239
 
 
240
 
        num_parent_keys = len(parent_keys)
241
 
        # We know how many parents, so we pre allocate the tuple
242
 
        parent_nodes = PyTuple_New(num_parent_keys)
243
 
        for pos from 0 <= pos < num_parent_keys:
244
 
            # Note: it costs us 10ms out of 40ms to lookup all of these
245
 
            #       parents, it doesn't seem to be an allocation overhead,
246
 
            #       but rather a lookup overhead. There doesn't seem to be
247
 
            #       a way around it, and that is one reason why
248
 
            #       KnownGraphNode maintains a direct pointer to the parent
249
 
            #       node.
250
 
            # We use [] because parent_keys may be a tuple or list
251
 
            parent_node = self._get_or_create_node(parent_keys[pos])
252
 
            # PyTuple_SET_ITEM will steal a reference, so INCREF first
253
 
            Py_INCREF(parent_node)
254
 
            PyTuple_SET_ITEM(parent_nodes, pos, parent_node)
255
 
            PyList_Append(parent_node.children, node)
256
 
        node.parents = parent_nodes
257
 
 
258
223
    def _initialize_nodes(self, parent_map):
259
224
        """Populate self._nodes.
260
225
 
265
230
          child keys,
266
231
        """
267
232
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
268
 
        cdef Py_ssize_t pos
 
233
        cdef Py_ssize_t pos, pos2, num_parent_keys
269
234
        cdef _KnownGraphNode node
270
235
        cdef _KnownGraphNode parent_node
271
236
 
276
241
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
277
242
            key = <object>temp_key
278
243
            parent_keys = <object>temp_parent_keys
 
244
            num_parent_keys = len(parent_keys)
279
245
            node = self._get_or_create_node(key)
280
 
            self._populate_parents(node, parent_keys)
 
246
            # We know how many parents, so we pre allocate the tuple
 
247
            parent_nodes = PyTuple_New(num_parent_keys)
 
248
            for pos2 from 0 <= pos2 < num_parent_keys:
 
249
                # Note: it costs us 10ms out of 40ms to lookup all of these
 
250
                #       parents, it doesn't seem to be an allocation overhead,
 
251
                #       but rather a lookup overhead. There doesn't seem to be
 
252
                #       a way around it, and that is one reason why
 
253
                #       KnownGraphNode maintains a direct pointer to the parent
 
254
                #       node.
 
255
                # We use [] because parent_keys may be a tuple or list
 
256
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
257
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
258
                Py_INCREF(parent_node)
 
259
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
 
260
                PyList_Append(parent_node.children, node)
 
261
            node.parents = parent_nodes
281
262
 
282
263
    def _find_tails(self):
283
264
        cdef PyObject *temp_node
341
322
                    # anymore
342
323
                    child.seen = 0
343
324
 
344
 
    def add_node(self, key, parent_keys):
345
 
        """Add a new node to the graph.
346
 
 
347
 
        If this fills in a ghost, then the gdfos of all children will be
348
 
        updated accordingly.
349
 
        
350
 
        :param key: The node being added. If this is a duplicate, this is a
351
 
            no-op.
352
 
        :param parent_keys: The parents of the given node.
353
 
        :return: None (should we return if this was a ghost, etc?)
354
 
        """
355
 
        cdef PyObject *maybe_node
356
 
        cdef _KnownGraphNode node, parent_node, child_node
357
 
        cdef long parent_gdfo, next_gdfo
358
 
 
359
 
        maybe_node = PyDict_GetItem(self._nodes, key)
360
 
        if maybe_node != NULL:
361
 
            node = <_KnownGraphNode>maybe_node
362
 
            if node.parents is None:
363
 
                # We are filling in a ghost
364
 
                self._populate_parents(node, parent_keys)
365
 
                # We can't trust cached heads anymore
366
 
                self._known_heads.clear()
367
 
            else: # Ensure that the parent_key list matches
368
 
                existing_parent_keys = []
369
 
                for parent_node in node.parents:
370
 
                    existing_parent_keys.append(parent_node.key)
371
 
                # Make sure we use a list for the comparison, in case it was a
372
 
                # tuple, etc
373
 
                parent_keys = list(parent_keys)
374
 
                if existing_parent_keys == parent_keys:
375
 
                    # Exact match, nothing more to do
376
 
                    return
377
 
                else:
378
 
                    raise ValueError('Parent key mismatch, existing node %s'
379
 
                        ' has parents of %s not %s'
380
 
                        % (key, existing_parent_keys, parent_keys))
381
 
        else:
382
 
            node = _KnownGraphNode(key)
383
 
            PyDict_SetItem(self._nodes, key, node)
384
 
            self._populate_parents(node, parent_keys)
385
 
        parent_gdfo = 0
386
 
        for parent_node in node.parents:
387
 
            if parent_node.gdfo == -1:
388
 
                # This is a newly introduced ghost, so it gets gdfo of 1
389
 
                parent_node.gdfo = 1
390
 
            if parent_gdfo < parent_node.gdfo:
391
 
                parent_gdfo = parent_node.gdfo
392
 
        node.gdfo = parent_gdfo + 1
393
 
        # Now fill the gdfo to all children
394
 
        # Note that this loop is slightly inefficient, in that we may visit the
395
 
        # same child (and its decendents) more than once, however, it is
396
 
        # 'efficient' in that we only walk to nodes that would be updated,
397
 
        # rather than all nodes
398
 
        # We use a deque rather than a simple list stack, to go for BFD rather
399
 
        # than DFD. So that if a longer path is possible, we walk it before we
400
 
        # get to the final child
401
 
        pending = deque([node])
402
 
        pending_popleft = pending.popleft
403
 
        pending_append = pending.append
404
 
        while pending:
405
 
            node = pending_popleft()
406
 
            next_gdfo = node.gdfo + 1
407
 
            for child_node in node.children:
408
 
                if child_node.gdfo < next_gdfo:
409
 
                    # This child is being updated, we need to check its
410
 
                    # children
411
 
                    child_node.gdfo = next_gdfo
412
 
                    pending_append(child_node)
413
 
 
414
325
    def heads(self, keys):
415
326
        """Return the heads from amongst keys.
416
327
 
638
549
        #       shown a specific impact, yet.
639
550
        sorter = _MergeSorter(self, tip_key)
640
551
        return sorter.topo_order()
641
 
    
642
 
    def get_parent_keys(self, key):
643
 
        """Get the parents for a key
644
 
        
645
 
        Returns a list containg the parents keys. If the key is a ghost,
646
 
        None is returned. A KeyError will be raised if the key is not in
647
 
        the graph.
648
 
        
649
 
        :param keys: Key to check (eg revision_id)
650
 
        :return: A list of parents
651
 
        """
652
 
        return self._nodes[key].parent_keys 
653
 
 
654
 
    def get_child_keys(self, key):
655
 
        """Get the children for a key
656
 
        
657
 
        Returns a list containg the children keys. A KeyError will be raised
658
 
        if the key is not in the graph.
659
 
        
660
 
        :param keys: Key to check (eg revision_id)
661
 
        :return: A list of children
662
 
        """
663
 
        return self._nodes[key].child_keys    
664
552
 
665
553
 
666
554
cdef class _MergeSortNode:
703
591
            self._revno_first, self._revno_second, self._revno_last,
704
592
            self.is_first_child, self.seen_by_child)
705
593
 
706
 
    cdef int has_pending_parents(self): # cannot_raise
 
594
    cdef int has_pending_parents(self):
707
595
        if self.left_pending_parent is not None or self.pending_parents:
708
596
            return 1
709
597
        return 0