← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
7
7
 * Rewritten for GIT by Nicolas Pitre <nico@cam.org>, (C) 2005-2007
8
8
 * Adapted for Bazaar by John Arbash Meinel <john@arbash-meinel.com> (C) 2009
9
9
 *
10
 
 * This code is free software; you can redistribute it and/or modify
11
 
 * it under the terms of the GNU General Public License version 2 as
12
 
 * published by the Free Software Foundation.
 
10
 * This program is free software; you can redistribute it and/or modify
 
11
 * it under the terms of the GNU General Public License as published by
 
12
 * the Free Software Foundation; either version 2 of the License, or
 
13
 * (at your option) any later version.
 
14
 *
 
15
 * NB: The version in GIT is 'version 2 of the Licence only', however Nicolas
 
16
 * has granted permission for use under 'version 2 or later' in private email
 
17
 * to Robert Collins and Karl Fogel on the 6th April 2009.
13
18
 */
14
19
 
15
20
#include <stdio.h>
683
688
    const unsigned char *data, *buffer, *top;
684
689
    unsigned char cmd;
685
690
    struct delta_index *new_index;
686
 
    struct index_entry *entry, *entries, *old_entry;
 
691
    struct index_entry *entry, *entries;
687
692
 
688
693
    if (!src->buf || !src->size)
689
694
        return NULL;
708
713
    prev_val = ~0;
709
714
    data = buffer;
710
715
    /* target size */
711
 
    get_delta_hdr_size(&data, top);
 
716
    /* get_delta_hdr_size doesn't mutate the content, just moves the
 
717
     * start-of-data pointer, so it is safe to do the cast.
 
718
     */
 
719
    get_delta_hdr_size((unsigned char**)&data, top);
712
720
    entry = entries; /* start at the first slot */
713
721
    num_entries = 0; /* calculate the real number of entries */
714
722
    while (data < top) {
781
789
    entry = entries;
782
790
    num_inserted = 0;
783
791
    for (; num_entries > 0; --num_entries, ++entry) {
 
792
        struct index_entry *next_bucket_entry, *cur_entry, *bucket_first_entry;
784
793
        hash_offset = (entry->val & old_index->hash_mask);
785
794
        /* The basic structure is a hash => packed_entries that fit in that
786
795
         * hash bucket. Things are structured such that the hash-pointers are
789
798
         * forward. If there are no NULL targets, then we know because
790
799
         * entry->ptr will not be NULL.
791
800
         */
792
 
        old_entry = old_index->hash[hash_offset + 1];
793
 
        old_entry--;
794
 
        while (old_entry->ptr == NULL
795
 
               && old_entry >= old_index->hash[hash_offset]) {
796
 
            old_entry--;
 
801
        // The start of the next bucket, this may point past the end of the
 
802
        // entry table if hash_offset is the last bucket.
 
803
        next_bucket_entry = old_index->hash[hash_offset + 1];
 
804
        // First entry in this bucket
 
805
        bucket_first_entry = old_index->hash[hash_offset];
 
806
        cur_entry = next_bucket_entry - 1;
 
807
        while (cur_entry->ptr == NULL && cur_entry >= bucket_first_entry) {
 
808
            cur_entry--;
797
809
        }
798
 
        old_entry++;
799
 
        if (old_entry->ptr != NULL
800
 
            || old_entry >= old_index->hash[hash_offset + 1]) {
 
810
        // cur_entry now either points at the first NULL, or it points to
 
811
        // next_bucket_entry if there were no blank spots.
 
812
        cur_entry++;
 
813
        if (cur_entry >= next_bucket_entry || cur_entry->ptr != NULL) {
801
814
            /* There is no room for this entry, we have to resize */
802
815
            // char buff[128];
803
816
            // get_text(buff, entry->ptr);
814
827
            break;
815
828
        }
816
829
        num_inserted++;
817
 
        *old_entry = *entry;
 
830
        *cur_entry = *entry;
818
831
        /* For entries which we *do* manage to insert into old_index, we don't
819
832
         * want them double copied into the final output.
820
833
         */
840
853
    free(index);
841
854
}
842
855
 
843
 
unsigned long sizeof_delta_index(struct delta_index *index)
 
856
unsigned long
 
857
sizeof_delta_index(struct delta_index *index)
844
858
{
845
859
    if (index)
846
860
        return index->memsize;
859
873
             const void *trg_buf, unsigned long trg_size,
860
874
             unsigned long *delta_size, unsigned long max_size)
861
875
{
862
 
    unsigned int i, outpos, outsize, moff, msize, val;
 
876
    unsigned int i, outpos, outsize, moff, val;
 
877
    int msize;
863
878
    const struct source_info *msource;
864
879
    int inscnt;
865
880
    const unsigned char *ref_data, *ref_top, *data, *top;
930
945
                 entry++) {
931
946
                const unsigned char *ref;
932
947
                const unsigned char *src;
933
 
                unsigned int ref_size;
 
948
                int ref_size;
934
949
                if (entry->val != val)
935
950
                    continue;
936
951
                ref = entry->ptr;
943
958
                 * match more bytes with this location that we have already
944
959
                 * matched.
945
960
                 */
946
 
                if (ref_size > top - src)
 
961
                if (ref_size > (top - src))
947
962
                    ref_size = top - src;
948
963
                if (ref_size <= msize)
949
964
                    break;
950
965
                /* See how many bytes actually match at this location. */
951
966
                while (ref_size-- && *src++ == *ref)
952
967
                    ref++;
953
 
                if (msize < ref - entry->ptr) {
 
968
                if (msize < (ref - entry->ptr)) {
954
969
                    /* this is our best match so far */
955
970
                    msize = ref - entry->ptr;
956
971
                    msource = entry->src;