← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/chk_map.py

Teach CHKMap how to iter items in 2-tuple keyspaces.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/chk_map.py
102
102
        return stream.next().get_bytes_as('fulltext')
103
103
 
104
104
    @classmethod
105
 
    def from_dict(klass, store, initial_value, maximum_size=0):
 
105
    def from_dict(klass, store, initial_value, maximum_size=0, key_width=1):
106
106
        """Create a CHKMap in store with initial_value as the content.
107
107
        
108
108
        :param store: The store to record initial_value in, a VersionedFiles
111
111
            must be bytestrings.
112
112
        :param maximum_size: The maximum_size rule to apply to nodes. This
113
113
            determines the size at which no new data is added to a single node.
 
114
        :param key_width: The number of elements in each key_tuple being stored
 
115
            in this map.
114
116
        :return: The root chk of te resulting CHKMap.
115
117
        """
116
118
        result = CHKMap(store, None)
117
119
        result._root_node.set_maximum_size(maximum_size)
 
120
        result._root_node._key_width = key_width
118
121
        delta = []
119
122
        for key, value in initial_value.items():
120
123
            delta.append((None, key, value))
425
428
        return result
426
429
 
427
430
    def iteritems(self, store, key_filter=None):
 
431
        """Iterate over items in the node.
 
432
 
 
433
        :param key_filter: A filter to apply to the node. It should be a
 
434
            list/set/dict or similar repeatedly iterable container.
 
435
        """
428
436
        if key_filter is not None:
 
437
            # Adjust the filter - short elements go to a prefix filter. Would this
 
438
            # be cleaner explicitly? That would be no harder for InternalNode..
 
439
            # XXX: perhaps defaultdict? Profiling<rinse and repeat>
 
440
            filters = {}
 
441
            for key in key_filter:
 
442
                length_filter = filters.setdefault(len(key), set())
 
443
                length_filter.add(key)
 
444
            filters = filters.items()
429
445
            for item in self._items.iteritems():
430
 
                if item[0] in key_filter:
431
 
                    yield item
 
446
                for length, length_filter in filters:
 
447
                    if item[0][:length] in length_filter:
 
448
                        yield item
 
449
                        break
432
450
        else:
433
451
            for item in self._items.iteritems():
434
452
                yield item
597
615
                else:
598
616
                    nodes.append(node)
599
617
        else:
600
 
            serialised_filter = set([self._serialised_key(key) for key in
601
 
                key_filter])
 
618
            # XXX defaultdict ?
 
619
            length_filters = {}
 
620
            for key in key_filter:
 
621
                serialised_key = self._serialised_prefix_filter(key)
 
622
                length_filter = length_filters.setdefault(len(serialised_key),
 
623
                    set())
 
624
                length_filter.add(serialised_key)
 
625
            length_filters = length_filters.items()
602
626
            for prefix, node in self._items.iteritems():
603
 
                if prefix in serialised_filter:
604
 
                    if type(node) == tuple:
605
 
                        keys[node] = prefix
606
 
                    else:
607
 
                        nodes.append(node)
 
627
                for length, length_filter in length_filters:
 
628
                    if prefix[:length] in length_filter:
 
629
                        if type(node) == tuple:
 
630
                            keys[node] = prefix
 
631
                        else:
 
632
                            nodes.append(node)
 
633
                        break
608
634
        if keys:
609
635
            # demand load some pages.
610
636
            stream = store.get_record_stream(keys, 'unordered', True)
685
711
        """Return the serialised key for key in this node."""
686
712
        return ('\x00'.join(key) + '\x00'*self._node_width)[:self._node_width]
687
713
 
 
714
    def _serialised_prefix_filter(self, key):
 
715
        """Serialise key for use as a prefix filter in iteritems."""
 
716
        if len(key) == self._key_width:
 
717
            return self._serialised_key(key)
 
718
        return '\x00'.join(key)[:self._node_width]
 
719
 
688
720
    def _split(self, offset):
689
721
        """Split this node into smaller nodes starting at offset.
690
722