~bzr-pqm/bzr/bzr.dev

Viewing changes to bzrlib/_known_graph_pyx.pyx

Committer: Vincent Ladeuil
Date: 2009-06-18 09:51:38 UTC
mto: This revision was merged to the branch mainline in revision 4466.
Revision ID: v.ladeuil+lp@free.fr-20090618095138-rha25usmqwsfwoxv

Simple Pyrex version for the new heads() method.

* tools/time_graph.py:
Also display parent_map loading.

* bzrlib/_known_graph_pyx.pyx:
(KnownGraph.heads): pyrex version faster by ~20% than the previous
pyrex version, without using linears dominators. Strictly speaking
linear dominators breaks the algorithm as jumping from one node to
its dominator may miss a candidate. Trying to compensate that
seems to cost more than the benefits it provides :-/ Their use
will surely come back later.

files modified:
bzrlib/_known_graph_py.py

bzrlib/_known_graph_pyx.pyx

tools/time_graph.py

Show diffs side-by-side

added added

removed removed

bzrlib/_known_graph_pyx.pyx

364

This is done by searching the ancestries of each key. Any key that is

365

reachable from another key is not returned; all the others are.

366

367

This operation scales with the relative depth between any two keys. It

368

uses gdfo to avoid walking all ancestry.

369

370

:param keys: An iterable of keys.

371

:return: A set of the heads. Note that as a set there is no ordering

372

information. Callers will need to filter their input to create

373

order if they need it.

374

"""

375

cdef PyObject *maybe_node

376

cdef PyObject *maybe_heads

377

cdef PyObject *temp_node

378

cdef _KnownGraphNode node

379

380

heads_key = PyFrozenSet_New(keys)

381

maybe_heads = PyDict_GetItem(self._known_heads, heads_key)

382

if maybe_heads != NULL:

383

return <object>maybe_heads

384

# Not cached, compute it ourselves

385

candidate_nodes = {}

386

nodes = self._nodes

387

for key in keys:

388

maybe_node = PyDict_GetItem(nodes, key)

389

if maybe_node == NULL:

390

raise KeyError('key %s not in nodes' % (key,))

391

PyDict_SetItem(candidate_nodes, key, <object>maybe_node)

392

if revision.NULL_REVISION in candidate_nodes:

393

# NULL_REVISION is only a head if it is the only entry

394

candidate_nodes.pop(revision.NULL_REVISION)

395

if not candidate_nodes:

396

return set([revision.NULL_REVISION])

397

# The keys changed, so recalculate heads_key

398

heads_key = PyFrozenSet_New(candidate_nodes)

399

if len(candidate_nodes) < 2:

400

return heads_key

401

402

seen = set()

403

pending = []

404

cdef Py_ssize_t pos

405

pos = 0

406

min_gdfo = None

407

while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):

408

node = <_KnownGraphNode>temp_node

409

if node.parents is not None:

410

pending.extend(node.parents)

411

if min_gdfo is None or node.gdfo < min_gdfo:

412

min_gdfo = node.gdfo

413

nodes = self._nodes

414

while pending:

415

node = pending.pop()

416

if node.key in seen:

417

# node already appears in some ancestry

418

continue

419

seen.add(node.key)

420

if node.gdfo <= min_gdfo:

421

continue

422

if node.parents:

423

pending.extend(node.parents)

424

heads = heads_key.difference(seen)

425

if self.do_cache:

426

self._known_heads[heads_key] = heads

427

return heads

428

429

def xheads(self, keys):

430

"""Return the heads from amongst keys.

431

432

This is done by searching the ancestries of each key. Any key that is

433

reachable from another key is not returned; all the others are.

434

367

435

This operation scales with the relative depth between any two keys. If

368

436

any two keys are completely disconnected all ancestry of both sides

369

437

will be retrieved.

Older »