← 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: Canonical.com Patch Queue Manager
  • Date: 2010-03-02 08:49:07 UTC
  • mfrom: (5067.1.1 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20100302084907-z4r0yoa4ldspjz82
(vila) Resolve --take-this or --take-other correctly rename kept file

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 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
54
55
import gc
55
56
 
56
57
from bzrlib import errors, revision
88
89
                PyList_Append(keys, child.key)
89
90
            return keys
90
91
 
 
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
    
91
104
    cdef clear_references(self):
92
105
        self.parents = None
93
106
        self.children = None
180
193
    """This is a class which assumes we already know the full graph."""
181
194
 
182
195
    cdef public object _nodes
183
 
    cdef object _known_heads
 
196
    cdef public object _known_heads
184
197
    cdef public int do_cache
185
198
 
186
199
    def __init__(self, parent_map, do_cache=True):
220
233
            node = <_KnownGraphNode>temp_node
221
234
        return node
222
235
 
 
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
 
223
258
    def _initialize_nodes(self, parent_map):
224
259
        """Populate self._nodes.
225
260
 
230
265
          child keys,
231
266
        """
232
267
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
233
 
        cdef Py_ssize_t pos, pos2, num_parent_keys
 
268
        cdef Py_ssize_t pos
234
269
        cdef _KnownGraphNode node
235
270
        cdef _KnownGraphNode parent_node
236
271
 
241
276
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
242
277
            key = <object>temp_key
243
278
            parent_keys = <object>temp_parent_keys
244
 
            num_parent_keys = len(parent_keys)
245
279
            node = self._get_or_create_node(key)
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
 
280
            self._populate_parents(node, parent_keys)
262
281
 
263
282
    def _find_tails(self):
264
283
        cdef PyObject *temp_node
322
341
                    # anymore
323
342
                    child.seen = 0
324
343
 
 
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
 
325
414
    def heads(self, keys):
326
415
        """Return the heads from amongst keys.
327
416
 
549
638
        #       shown a specific impact, yet.
550
639
        sorter = _MergeSorter(self, tip_key)
551
640
        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    
552
664
 
553
665
 
554
666
cdef class _MergeSortNode:
591
703
            self._revno_first, self._revno_second, self._revno_last,
592
704
            self.is_first_child, self.seen_by_child)
593
705
 
594
 
    cdef int has_pending_parents(self):
 
706
    cdef int has_pending_parents(self): # cannot_raise
595
707
        if self.left_pending_parent is not None or self.pending_parents:
596
708
            return 1
597
709
        return 0