~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

• browse files at revision 4801
• compare with another revision
• download diff
• download tarball
• view history from revision 4801

• reverse the comparison (4801 to 4964)
• stop comparing with revision 4964

Show diffs side-by-side

added

removed

bzrlib/_known_graph_pyx.pyx

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

193

192

    """This is a class which assumes we already know the full graph."""

194

193

 

195

194

    cdef public object _nodes

196

 

    cdef public object _known_heads

 

195

    cdef object _known_heads

197

196

    cdef public int do_cache

198

197

 

199

198

    def __init__(self, parent_map, do_cache=True):

233

232

            node = <_KnownGraphNode>temp_node

234

233

        return node

235

234

 

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

235

    def _initialize_nodes(self, parent_map):

259

236

        """Populate self._nodes.

260

237

 

265

242

          child keys,

266

243

        """

267

244

        cdef PyObject *temp_key, *temp_parent_keys, *temp_node

268

 

        cdef Py_ssize_t pos

 

245

        cdef Py_ssize_t pos, pos2, num_parent_keys

269

246

        cdef _KnownGraphNode node

270

247

        cdef _KnownGraphNode parent_node

271

248

 

276

253

        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):

277

254

            key = <object>temp_key

278

255

            parent_keys = <object>temp_parent_keys

 

256

            num_parent_keys = len(parent_keys)

279

257

            node = self._get_or_create_node(key)

280

 

            self._populate_parents(node, parent_keys)

 

258

            # We know how many parents, so we pre allocate the tuple

 

259

            parent_nodes = PyTuple_New(num_parent_keys)

 

260

            for pos2 from 0 <= pos2 < num_parent_keys:

 

261

                # Note: it costs us 10ms out of 40ms to lookup all of these

 

262

                #       parents, it doesn't seem to be an allocation overhead,

 

263

                #       but rather a lookup overhead. There doesn't seem to be

 

264

                #       a way around it, and that is one reason why

 

265

                #       KnownGraphNode maintains a direct pointer to the parent

 

266

                #       node.

 

267

                # We use [] because parent_keys may be a tuple or list

 

268

                parent_node = self._get_or_create_node(parent_keys[pos2])

 

269

                # PyTuple_SET_ITEM will steal a reference, so INCREF first

 

270

                Py_INCREF(parent_node)

 

271

                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)

 

272

                PyList_Append(parent_node.children, node)

 

273

            node.parents = parent_nodes

281

274

 

282

275

    def _find_tails(self):

283

276

        cdef PyObject *temp_node

341

334

                    # anymore

342

335

                    child.seen = 0

343

336

 

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

337

    def heads(self, keys):

415

338

        """Return the heads from amongst keys.

416

339

 

703

626

            self._revno_first, self._revno_second, self._revno_last,

704

627

            self.is_first_child, self.seen_by_child)

705

628

 

706

 

    cdef int has_pending_parents(self): # cannot_raise

 

629

    cdef int has_pending_parents(self):

707

630

        if self.left_pending_parent is not None or self.pending_parents:

708

631

            return 1

709

632

        return 0

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1