/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2017-06-10 00:52:08 UTC
  • mfrom: (6675 work)
  • mto: (6670.4.8 move-bzr)
  • mto: This revision was merged to the branch mainline in revision 6681.
  • Revision ID: jelmer@jelmer.uk-20170610005208-dthx80fkolfpsenj
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/btree_index.py
44
44
    BytesIO,
45
45
    map,
46
46
    range,
 
47
    viewitems,
 
48
    viewkeys,
 
49
    viewvalues,
47
50
    )
48
51
 
49
52
 
529
532
            will be returned, and every match that is in the index will be
530
533
            returned.
531
534
        """
532
 
        # XXX: To much duplication with the GraphIndex class; consider finding
533
 
        # a good place to pull out the actual common logic.
534
535
        keys = set(keys)
535
536
        if not keys:
536
537
            return
541
542
                yield (self,) + node[1:]
542
543
        if self._key_length == 1:
543
544
            for key in keys:
544
 
                # sanity check
545
 
                if key[0] is None:
546
 
                    raise errors.BadIndexKey(key)
547
 
                if len(key) != self._key_length:
548
 
                    raise errors.BadIndexKey(key)
 
545
                index._sanity_check_key(self, key)
549
546
                try:
550
547
                    node = self._nodes[key]
551
548
                except KeyError:
555
552
                else:
556
553
                    yield self, key, node[1]
557
554
            return
558
 
        for key in keys:
559
 
            # sanity check
560
 
            if key[0] is None:
561
 
                raise errors.BadIndexKey(key)
562
 
            if len(key) != self._key_length:
563
 
                raise errors.BadIndexKey(key)
564
 
            # find what it refers to:
565
 
            key_dict = self._get_nodes_by_key()
566
 
            elements = list(key)
567
 
            # find the subdict to return
568
 
            try:
569
 
                while len(elements) and elements[0] is not None:
570
 
                    key_dict = key_dict[elements[0]]
571
 
                    elements.pop(0)
572
 
            except KeyError:
573
 
                # a non-existant lookup.
574
 
                continue
575
 
            if len(elements):
576
 
                dicts = [key_dict]
577
 
                while dicts:
578
 
                    key_dict = dicts.pop(-1)
579
 
                    # can't be empty or would not exist
580
 
                    item, value = next(key_dict.iteritems())
581
 
                    if isinstance(value, dict):
582
 
                        # push keys
583
 
                        dicts.extend(key_dict.itervalues())
584
 
                    else:
585
 
                        # yield keys
586
 
                        for value in key_dict.itervalues():
587
 
                            yield (self, ) + tuple(value)
588
 
            else:
589
 
                yield (self, ) + key_dict
 
555
        nodes_by_key = self._get_nodes_by_key()
 
556
        for entry in index._iter_entries_prefix(self, nodes_by_key, keys):
 
557
            yield entry
590
558
 
591
559
    def _get_nodes_by_key(self):
592
560
        if self._nodes_by_key is None:
593
561
            nodes_by_key = {}
594
562
            if self.reference_lists:
595
 
                for key, (references, value) in self._nodes.iteritems():
 
563
                for key, (references, value) in viewitems(self._nodes):
596
564
                    key_dict = nodes_by_key
597
565
                    for subkey in key[:-1]:
598
566
                        key_dict = key_dict.setdefault(subkey, {})
599
567
                    key_dict[key[-1]] = key, value, references
600
568
            else:
601
 
                for key, (references, value) in self._nodes.iteritems():
 
569
                for key, (references, value) in viewitems(self._nodes):
602
570
                    key_dict = nodes_by_key
603
571
                    for subkey in key[:-1]:
604
572
                        key_dict = key_dict.setdefault(subkey, {})
940
908
 
941
909
    def _get_offsets_to_cached_pages(self):
942
910
        """Determine what nodes we already have cached."""
943
 
        cached_offsets = set(self._internal_node_cache.keys())
 
911
        cached_offsets = set(self._internal_node_cache)
 
912
        # cache may be dict or LRUCache, keys() is the common method
944
913
        cached_offsets.update(self._leaf_node_cache.keys())
945
914
        if self._root_node is not None:
946
915
            cached_offsets.add(0)
979
948
    def _cache_leaf_values(self, nodes):
980
949
        """Cache directly from key => value, skipping the btree."""
981
950
        if self._leaf_value_cache is not None:
982
 
            for node in nodes.itervalues():
 
951
            for node in viewvalues(nodes):
983
952
                for key, value in node.all_items():
984
953
                    if key in self._leaf_value_cache:
985
954
                        # Don't add the rest of the keys, we've seen this node
1395
1364
                    key_dict[key[-1]] = key_value
1396
1365
        if self._key_length == 1:
1397
1366
            for key in keys:
1398
 
                # sanity check
1399
 
                if key[0] is None:
1400
 
                    raise errors.BadIndexKey(key)
1401
 
                if len(key) != self._key_length:
1402
 
                    raise errors.BadIndexKey(key)
 
1367
                index._sanity_check_key(self, key)
1403
1368
                try:
1404
1369
                    if self.node_ref_lists:
1405
1370
                        value, node_refs = nodes[key]
1409
1374
                except KeyError:
1410
1375
                    pass
1411
1376
            return
1412
 
        for key in keys:
1413
 
            # sanity check
1414
 
            if key[0] is None:
1415
 
                raise errors.BadIndexKey(key)
1416
 
            if len(key) != self._key_length:
1417
 
                raise errors.BadIndexKey(key)
1418
 
            # find what it refers to:
1419
 
            key_dict = nodes_by_key
1420
 
            elements = list(key)
1421
 
            # find the subdict whose contents should be returned.
1422
 
            try:
1423
 
                while len(elements) and elements[0] is not None:
1424
 
                    key_dict = key_dict[elements[0]]
1425
 
                    elements.pop(0)
1426
 
            except KeyError:
1427
 
                # a non-existant lookup.
1428
 
                continue
1429
 
            if len(elements):
1430
 
                dicts = [key_dict]
1431
 
                while dicts:
1432
 
                    key_dict = dicts.pop(-1)
1433
 
                    # can't be empty or would not exist
1434
 
                    item, value = next(key_dict.iteritems())
1435
 
                    if isinstance(value, dict):
1436
 
                        # push keys
1437
 
                        dicts.extend(key_dict.itervalues())
1438
 
                    else:
1439
 
                        # yield keys
1440
 
                        for value in key_dict.itervalues():
1441
 
                            # each value is the key:value:node refs tuple
1442
 
                            # ready to yield.
1443
 
                            yield (self, ) + value
1444
 
            else:
1445
 
                # the last thing looked up was a terminal element
1446
 
                yield (self, ) + key_dict
 
1377
        for entry in index._iter_entries_prefix(self, nodes_by_key, keys):
 
1378
            yield entry
1447
1379
 
1448
1380
    def key_count(self):
1449
1381
        """Return an estimate of the number of keys in this index.