← Back to branch summary

~mbp/bzr/257217-sighup

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-08-27 22:09:35 UTC
  • mfrom: (5361.3.8 2.3-dirstate-index)
  • Revision ID: pqm@pqm.ubuntu.com-20100827220935-gwk3320p99ggl80n
(jameinel) use StaticTuple for dirstate and don't use sets in _id_index for
 improved memory use (John A Meinel)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/dirstate.py
220
220
    inventory,
221
221
    lock,
222
222
    osutils,
 
223
    static_tuple,
223
224
    trace,
224
225
    )
225
226
 
548
549
           self._ensure_block(block_index, entry_index, utf8path)
549
550
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
550
551
        if self._id_index:
551
 
            self._id_index.setdefault(entry_key[2], set()).add(entry_key)
 
552
            self._add_to_id_index(self._id_index, entry_key)
552
553
 
553
554
    def _bisect(self, paths):
554
555
        """Bisect through the disk structure for specific rows.
1566
1567
            return
1567
1568
        id_index = self._get_id_index()
1568
1569
        for file_id in new_ids:
1569
 
            for key in id_index.get(file_id, []):
 
1570
            for key in id_index.get(file_id, ()):
1570
1571
                block_i, entry_i, d_present, f_present = \
1571
1572
                    self._get_block_entry_index(key[0], key[1], tree_index)
1572
1573
                if not f_present:
1980
1981
                                          ' tree_index, file_id and path')
1981
1982
            return entry
1982
1983
        else:
1983
 
            possible_keys = self._get_id_index().get(fileid_utf8, None)
 
1984
            possible_keys = self._get_id_index().get(fileid_utf8, ())
1984
1985
            if not possible_keys:
1985
1986
                return None, None
1986
1987
            for key in possible_keys:
2143
2144
                yield entry
2144
2145
 
2145
2146
    def _get_id_index(self):
2146
 
        """Get an id index of self._dirblocks."""
 
2147
        """Get an id index of self._dirblocks.
 
2148
        
 
2149
        This maps from file_id => [(directory, name, file_id)] entries where
 
2150
        that file_id appears in one of the trees.
 
2151
        """
2147
2152
        if self._id_index is None:
2148
2153
            id_index = {}
2149
2154
            for key, tree_details in self._iter_entries():
2150
 
                id_index.setdefault(key[2], set()).add(key)
 
2155
                self._add_to_id_index(id_index, key)
2151
2156
            self._id_index = id_index
2152
2157
        return self._id_index
2153
2158
 
 
2159
    def _add_to_id_index(self, id_index, entry_key):
 
2160
        """Add this entry to the _id_index mapping."""
 
2161
        # This code used to use a set for every entry in the id_index. However,
 
2162
        # it is *rare* to have more than one entry. So a set is a large
 
2163
        # overkill. And even when we do, we won't ever have more than the
 
2164
        # number of parent trees. Which is still a small number (rarely >2). As
 
2165
        # such, we use a simple tuple, and do our own uniqueness checks. While
 
2166
        # the 'in' check is O(N) since N is nicely bounded it shouldn't ever
 
2167
        # cause quadratic failure.
 
2168
        # TODO: This should use StaticTuple
 
2169
        file_id = entry_key[2]
 
2170
        entry_key = static_tuple.StaticTuple.from_sequence(entry_key)
 
2171
        if file_id not in id_index:
 
2172
            id_index[file_id] = static_tuple.StaticTuple(entry_key,)
 
2173
        else:
 
2174
            entry_keys = id_index[file_id]
 
2175
            if entry_key not in entry_keys:
 
2176
                id_index[file_id] = entry_keys + (entry_key,)
 
2177
 
 
2178
    def _remove_from_id_index(self, id_index, entry_key):
 
2179
        """Remove this entry from the _id_index mapping.
 
2180
 
 
2181
        It is an programming error to call this when the entry_key is not
 
2182
        already present.
 
2183
        """
 
2184
        file_id = entry_key[2]
 
2185
        entry_keys = list(id_index[file_id])
 
2186
        entry_keys.remove(entry_key)
 
2187
        id_index[file_id] = static_tuple.StaticTuple.from_sequence(entry_keys)
 
2188
 
2154
2189
    def _get_output_lines(self, lines):
2155
2190
        """Format lines for final output.
2156
2191
 
2414
2449
                continue
2415
2450
            by_path[entry[0]] = [entry[1][0]] + \
2416
2451
                [DirState.NULL_PARENT_DETAILS] * parent_count
2417
 
            id_index[entry[0][2]] = set([entry[0]])
 
2452
            # TODO: Possibly inline this, since we know it isn't present yet
 
2453
            #       id_index[entry[0][2]] = (entry[0],)
 
2454
            self._add_to_id_index(id_index, entry[0])
2418
2455
 
2419
2456
        # now the parent trees:
2420
2457
        for tree_index, tree in enumerate(parent_trees):
2442
2479
                new_entry_key = (dirname, basename, file_id)
2443
2480
                # tree index consistency: All other paths for this id in this tree
2444
2481
                # index must point to the correct path.
2445
 
                for entry_key in id_index.setdefault(file_id, set()):
 
2482
                for entry_key in id_index.get(file_id, ()):
2446
2483
                    # TODO:PROFILING: It might be faster to just update
2447
2484
                    # rather than checking if we need to, and then overwrite
2448
2485
                    # the one we are located at.
2454
2491
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2455
2492
                # by path consistency: Insert into an existing path record (trivial), or
2456
2493
                # add a new one with relocation pointers for the other tree indexes.
2457
 
                if new_entry_key in id_index[file_id]:
 
2494
                entry_keys = id_index.get(file_id, ())
 
2495
                if new_entry_key in entry_keys:
2458
2496
                    # there is already an entry where this data belongs, just insert it.
2459
2497
                    by_path[new_entry_key][tree_index] = \
2460
2498
                        self._inv_entry_to_details(entry)
2465
2503
                    new_details = []
2466
2504
                    for lookup_index in xrange(tree_index):
2467
2505
                        # boundary case: this is the first occurence of file_id
2468
 
                        # so there are no id_indexs, possibly take this out of
 
2506
                        # so there are no id_indexes, possibly take this out of
2469
2507
                        # the loop?
2470
 
                        if not len(id_index[file_id]):
 
2508
                        if not len(entry_keys):
2471
2509
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2472
2510
                        else:
2473
2511
                            # grab any one entry, use it to find the right path.
2474
2512
                            # TODO: optimise this to reduce memory use in highly
2475
2513
                            # fragmented situations by reusing the relocation
2476
2514
                            # records.
2477
 
                            a_key = iter(id_index[file_id]).next()
 
2515
                            a_key = iter(entry_keys).next()
2478
2516
                            if by_path[a_key][lookup_index][0] in ('r', 'a'):
2479
2517
                                # its a pointer or missing statement, use it as is.
2480
2518
                                new_details.append(by_path[a_key][lookup_index])
2485
2523
                    new_details.append(self._inv_entry_to_details(entry))
2486
2524
                    new_details.extend(new_location_suffix)
2487
2525
                    by_path[new_entry_key] = new_details
2488
 
                    id_index[file_id].add(new_entry_key)
 
2526
                    self._add_to_id_index(id_index, new_entry_key)
2489
2527
        # --- end generation of full tree mappings
2490
2528
 
2491
2529
        # sort and output all the entries
2673
2711
            block[1].pop(entry_index)
2674
2712
            # if we have an id_index in use, remove this key from it for this id.
2675
2713
            if self._id_index is not None:
2676
 
                self._id_index[current_old[0][2]].remove(current_old[0])
 
2714
                self._remove_from_id_index(self._id_index, current_old[0])
2677
2715
        # update all remaining keys for this id to record it as absent. The
2678
2716
        # existing details may either be the record we are marking as deleted
2679
2717
        # (if there were other trees with the id present at this path), or may
2748
2786
                    else:
2749
2787
                        break
2750
2788
            # new entry, synthesis cross reference here,
2751
 
            existing_keys = id_index.setdefault(key[2], set())
 
2789
            existing_keys = id_index.get(key[2], ())
2752
2790
            if not existing_keys:
2753
2791
                # not currently in the state, simplest case
2754
2792
                new_entry = key, [new_details] + self._empty_parent_info()
2785
2823
                    # loop.
2786
2824
                    other_entry = other_block[other_entry_index]
2787
2825
                    other_entry[1][0] = ('r', path_utf8, 0, False, '')
2788
 
                    self._maybe_remove_row(other_block, other_entry_index,
2789
 
                        id_index)
 
2826
                    if self._maybe_remove_row(other_block, other_entry_index,
 
2827
                                              id_index):
 
2828
                        # If the row holding this was removed, we need to
 
2829
                        # recompute where this entry goes
 
2830
                        entry_index, _ = self._find_entry_index(key, block)
2790
2831
 
2791
2832
                # This loop:
2792
2833
                # adds a tuple to the new details for each column
2794
2835
                #  - or by creating a new pointer to the right row inside that column
2795
2836
                num_present_parents = self._num_present_parents()
2796
2837
                if num_present_parents:
 
2838
                    # TODO: This re-evaluates the existing_keys set, do we need
 
2839
                    #       to do that ourselves?
2797
2840
                    other_key = list(existing_keys)[0]
2798
2841
                for lookup_index in xrange(1, num_present_parents + 1):
2799
2842
                    # grab any one entry, use it to find the right path.
2818
2861
                        pointer_path = osutils.pathjoin(*other_key[0:2])
2819
2862
                        new_entry[1].append(('r', pointer_path, 0, False, ''))
2820
2863
            block.insert(entry_index, new_entry)
2821
 
            existing_keys.add(key)
 
2864
            self._add_to_id_index(id_index, key)
2822
2865
        else:
2823
2866
            # Does the new state matter?
2824
2867
            block[entry_index][1][0] = new_details
2833
2876
            # converted to relocated.
2834
2877
            if path_utf8 is None:
2835
2878
                raise AssertionError('no path')
2836
 
            for entry_key in id_index.setdefault(key[2], set()):
 
2879
            existing_keys = id_index[key[2]]
 
2880
            if key not in existing_keys:
 
2881
                raise AssertionError('We found the entry in the blocks, but'
 
2882
                    ' the key is not in the id_index.'
 
2883
                    ' key: %s, existing_keys: %s' % (key, existing_keys))
 
2884
            for entry_key in id_index[key[2]]:
2837
2885
                # TODO:PROFILING: It might be faster to just update
2838
2886
                # rather than checking if we need to, and then overwrite
2839
2887
                # the one we are located at.
2863
2911
        """Remove index if it is absent or relocated across the row.
2864
2912
        
2865
2913
        id_index is updated accordingly.
 
2914
        :return: True if we removed the row, False otherwise
2866
2915
        """
2867
2916
        present_in_row = False
2868
2917
        entry = block[index]
2872
2921
                break
2873
2922
        if not present_in_row:
2874
2923
            block.pop(index)
2875
 
            id_index[entry[0][2]].remove(entry[0])
 
2924
            self._remove_from_id_index(id_index, entry[0])
 
2925
            return True
 
2926
        return False
2876
2927
 
2877
2928
    def _validate(self):
2878
2929
        """Check that invariants on the dirblock are correct.
3020
3071
                        raise AssertionError(
3021
3072
                            'file_id %r did not match entry key %s'
3022
3073
                            % (file_id, entry_key))
 
3074
                if len(entry_keys) != len(set(entry_keys)):
 
3075
                    raise AssertionError(
 
3076
                        'id_index contained non-unique data for %s'
 
3077
                        % (entry_keys,))
3023
3078
 
3024
3079
    def _wipe_state(self):
3025
3080
        """Forget all state information about the dirstate."""