← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Andrew Bennetts
  • Date: 2011-02-14 12:03:05 UTC
  • mto: This revision was merged to the branch mainline in revision 5664.
  • Revision ID: andrew.bennetts@canonical.com-20110214120305-7l7iu1h6f13voeo7
Add release note.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
4
4
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
5
5
 * http://www.xmailserver.org/xdiff-lib.html
6
6
 *
7
 
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 
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
10
 * This program is free software; you can redistribute it and/or modify
280
280
        if (fit_in_old) {
281
281
            // fprintf(stderr, "Fit all %d entries into old index\n",
282
282
            //                 copied_count);
283
 
            /*
284
 
             * No need to allocate a new buffer, but return old_index ptr so
285
 
             * callers can distinguish this from an OOM failure.
286
 
             */
287
 
            return old_index;
 
283
            /* No need to allocate a new buffer */
 
284
            return NULL;
288
285
        } else {
289
286
            // fprintf(stderr, "Fit only %d entries into old index,"
290
287
            //                 " reallocating\n", copied_count);
373
370
}
374
371
 
375
372
 
376
 
delta_result
 
373
struct delta_index *
377
374
create_delta_index(const struct source_info *src,
378
 
                   struct delta_index *old,
379
 
                   struct delta_index **fresh)
 
375
                   struct delta_index *old)
380
376
{
381
377
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
382
378
    unsigned int total_num_entries;
387
383
    unsigned long memsize;
388
384
 
389
385
    if (!src->buf || !src->size)
390
 
        return DELTA_SOURCE_EMPTY;
 
386
        return NULL;
391
387
    buffer = src->buf;
392
388
 
393
389
    /* Determine index hash size.  Note that indexing skips the
412
408
          sizeof(*entry) * total_num_entries;
413
409
    mem = malloc(memsize);
414
410
    if (!mem)
415
 
        return DELTA_OUT_OF_MEMORY;
 
411
        return NULL;
416
412
    hash = mem;
417
413
    mem = hash + hsize;
418
414
    entry = mem;
423
419
    hash_count = calloc(hsize, sizeof(*hash_count));
424
420
    if (!hash_count) {
425
421
        free(hash);
426
 
        return DELTA_OUT_OF_MEMORY;
 
422
        return NULL;
427
423
    }
428
424
 
429
425
    /* then populate the index for the new data */
454
450
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
455
451
                                           total_num_entries);
456
452
    free(hash_count);
 
453
    if (old) {
 
454
        old->last_src = src;
 
455
    }
457
456
    index = pack_delta_index(hash, hsize, total_num_entries, old);
458
457
    free(hash);
459
 
    /* pack_delta_index only returns NULL on malloc failure */
460
458
    if (!index) {
461
 
        return DELTA_OUT_OF_MEMORY;
 
459
        return NULL;
462
460
    }
463
461
    index->last_src = src;
464
 
    *fresh = index;
465
 
    return DELTA_OK;
 
462
    return index;
466
463
}
467
464
 
468
465
/* Take some entries, and put them into a custom hash.
682
679
    }
683
680
}
684
681
 
685
 
delta_result
 
682
struct delta_index *
686
683
create_delta_index_from_delta(const struct source_info *src,
687
 
                              struct delta_index *old_index,
688
 
                              struct delta_index **fresh)
 
684
                              struct delta_index *old_index)
689
685
{
690
686
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
691
687
    unsigned int hash_offset;
694
690
    struct delta_index *new_index;
695
691
    struct index_entry *entry, *entries;
696
692
 
697
 
    if (!old_index)
698
 
        return DELTA_INDEX_NEEDED;
699
693
    if (!src->buf || !src->size)
700
 
        return DELTA_SOURCE_EMPTY;
 
694
        return NULL;
701
695
    buffer = src->buf;
702
696
    top = buffer + src->size;
703
697
 
713
707
    /* allocate an array to hold whatever entries we find */
714
708
    entries = malloc(sizeof(*entry) * max_num_entries);
715
709
    if (!entries) /* malloc failure */
716
 
        return DELTA_OUT_OF_MEMORY;
 
710
        return NULL;
717
711
 
718
712
    /* then populate the index for the new data */
719
713
    prev_val = ~0;
780
774
        }
781
775
    }
782
776
    if (data != top) {
783
 
        /* The source_info data passed was corrupted or otherwise invalid */
 
777
        /* Something was wrong with this delta */
784
778
        free(entries);
785
 
        return DELTA_SOURCE_BAD;
 
779
        return NULL;
786
780
    }
787
781
    if (num_entries == 0) {
788
782
        /** Nothing to index **/
789
783
        free(entries);
790
 
        *fresh = old_index;
791
 
        return DELTA_OK;
 
784
        return NULL;
792
785
    }
 
786
    assert(old_index != NULL);
793
787
    old_index->last_src = src;
794
788
    /* See if we can fill in these values into the holes in the array */
795
789
    entry = entries;
847
841
        new_index = create_index_from_old_and_new_entries(old_index,
848
842
            entry, num_entries);
849
843
    } else {
850
 
        new_index = old_index;
 
844
        new_index = NULL;
851
845
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
852
846
    }
853
847
    free(entries);
854
 
    /* create_index_from_old_and_new_entries returns NULL on malloc failure */
855
 
    if (!new_index)
856
 
        return DELTA_OUT_OF_MEMORY;
857
 
    *fresh = new_index;
858
 
    return DELTA_OK;
 
848
    return new_index;
859
849
}
860
850
 
861
851
void free_delta_index(struct delta_index *index)
878
868
 */
879
869
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
880
870
 
881
 
delta_result
 
871
void *
882
872
create_delta(const struct delta_index *index,
883
873
             const void *trg_buf, unsigned long trg_size,
884
 
             unsigned long *delta_size, unsigned long max_size,
885
 
             void **delta_data)
 
874
             unsigned long *delta_size, unsigned long max_size)
886
875
{
887
876
    unsigned int i, outpos, outsize, moff, val;
888
877
    int msize;
893
882
    unsigned long source_size;
894
883
 
895
884
    if (!trg_buf || !trg_size)
896
 
        return DELTA_BUFFER_EMPTY;
 
885
        return NULL;
897
886
    if (index == NULL)
898
 
        return DELTA_INDEX_NEEDED;
 
887
        return NULL;
899
888
 
900
889
    outpos = 0;
901
890
    outsize = 8192;
903
892
        outsize = max_size + MAX_OP_SIZE + 1;
904
893
    out = malloc(outsize);
905
894
    if (!out)
906
 
        return DELTA_OUT_OF_MEMORY;
 
895
        return NULL;
907
896
 
908
897
    source_size = index->last_src->size + index->last_src->agg_offset;
909
898
 
1082
1071
            out = realloc(out, outsize);
1083
1072
            if (!out) {
1084
1073
                free(tmp);
1085
 
                return DELTA_OUT_OF_MEMORY;
 
1074
                return NULL;
1086
1075
            }
1087
1076
        }
1088
1077
    }
1092
1081
 
1093
1082
    if (max_size && outpos > max_size) {
1094
1083
        free(out);
1095
 
        return DELTA_SIZE_TOO_BIG;
 
1084
        return NULL;
1096
1085
    }
1097
1086
 
1098
1087
    *delta_size = outpos;
1099
 
    *delta_data = out;
1100
 
    return DELTA_OK;
 
1088
    return out;
1101
1089
}
1102
1090
 
1103
1091
/* vim: et ts=4 sw=4 sts=4