/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 bzrlib/diff-delta.c

  • Committer: Vincent Ladeuil
  • Date: 2012-01-18 14:09:19 UTC
  • mto: This revision was merged to the branch mainline in revision 6468.
  • Revision ID: v.ladeuil+lp@free.fr-20120118140919-rlvdrhpc0nq1lbwi
Change set/remove to require a lock for the branch config files.

This means that tests (or any plugin for that matter) do not requires an
explicit lock on the branch anymore to change a single option. This also
means the optimisation becomes "opt-in" and as such won't be as
spectacular as it may be and/or harder to get right (nothing fails
anymore).

This reduces the diff by ~300 lines.

Code/tests that were updating more than one config option is still taking
a lock to at least avoid some IOs and demonstrate the benefits through
the decreased number of hpss calls.

The duplication between BranchStack and BranchOnlyStack will be removed
once the same sharing is in place for local config files, at which point
the Stack class itself may be able to host the changes.

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@cam.org>, (C) 2005-2007
 
7
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (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
 
            /* No need to allocate a new buffer */
284
 
            return NULL;
 
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;
285
288
        } else {
286
289
            // fprintf(stderr, "Fit only %d entries into old index,"
287
290
            //                 " reallocating\n", copied_count);
370
373
}
371
374
 
372
375
 
373
 
struct delta_index *
 
376
delta_result
374
377
create_delta_index(const struct source_info *src,
375
 
                   struct delta_index *old)
 
378
                   struct delta_index *old,
 
379
                   struct delta_index **fresh,
 
380
                   int max_bytes_to_index)
376
381
{
377
382
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
378
 
    unsigned int total_num_entries;
 
383
    unsigned int total_num_entries, stride, max_entries;
379
384
    const unsigned char *data, *buffer;
380
385
    struct delta_index *index;
381
386
    struct unpacked_index_entry *entry, **hash;
383
388
    unsigned long memsize;
384
389
 
385
390
    if (!src->buf || !src->size)
386
 
        return NULL;
 
391
        return DELTA_SOURCE_EMPTY;
387
392
    buffer = src->buf;
388
393
 
389
394
    /* Determine index hash size.  Note that indexing skips the
390
 
       first byte to allow for optimizing the Rabin's polynomial
391
 
       initialization in create_delta(). */
 
395
       first byte so we subtract 1 to get the edge cases right.
 
396
     */
 
397
    stride = RABIN_WINDOW;
392
398
    num_entries = (src->size - 1)  / RABIN_WINDOW;
 
399
    if (max_bytes_to_index > 0) {
 
400
        max_entries = (unsigned int) (max_bytes_to_index / RABIN_WINDOW);
 
401
        if (num_entries > max_entries) {
 
402
            /* Limit the max number of matching entries. This reduces the 'best'
 
403
             * possible match, but means we don't consume all of ram.
 
404
             */
 
405
            num_entries = max_entries;
 
406
            stride = (src->size - 1) / num_entries;
 
407
        }
 
408
    }
393
409
    if (old != NULL)
394
410
        total_num_entries = num_entries + old->num_entries;
395
411
    else
408
424
          sizeof(*entry) * total_num_entries;
409
425
    mem = malloc(memsize);
410
426
    if (!mem)
411
 
        return NULL;
 
427
        return DELTA_OUT_OF_MEMORY;
412
428
    hash = mem;
413
429
    mem = hash + hsize;
414
430
    entry = mem;
419
435
    hash_count = calloc(hsize, sizeof(*hash_count));
420
436
    if (!hash_count) {
421
437
        free(hash);
422
 
        return NULL;
 
438
        return DELTA_OUT_OF_MEMORY;
423
439
    }
424
440
 
425
441
    /* then populate the index for the new data */
426
442
    prev_val = ~0;
427
 
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
 
443
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
428
444
         data >= buffer;
429
 
         data -= RABIN_WINDOW) {
 
445
         data -= stride) {
430
446
        unsigned int val = 0;
431
447
        for (i = 1; i <= RABIN_WINDOW; i++)
432
448
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
450
466
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
451
467
                                           total_num_entries);
452
468
    free(hash_count);
453
 
    if (old) {
454
 
        old->last_src = src;
455
 
    }
456
469
    index = pack_delta_index(hash, hsize, total_num_entries, old);
457
470
    free(hash);
 
471
    /* pack_delta_index only returns NULL on malloc failure */
458
472
    if (!index) {
459
 
        return NULL;
 
473
        return DELTA_OUT_OF_MEMORY;
460
474
    }
461
475
    index->last_src = src;
462
 
    return index;
 
476
    *fresh = index;
 
477
    return DELTA_OK;
463
478
}
464
479
 
465
480
/* Take some entries, and put them into a custom hash.
473
488
                       unsigned int hsize)
474
489
{
475
490
    unsigned int hash_offset, hmask, memsize;
476
 
    struct index_entry *entry, *last_entry;
 
491
    struct index_entry *entry;
477
492
    struct index_entry_linked_list *out_entry, **hash;
478
493
    void *mem;
479
494
 
493
508
    /* We know that entries are in the order we want in the output, but they
494
509
     * aren't "grouped" by hash bucket yet.
495
510
     */
496
 
    last_entry = entries + num_entries;
497
511
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
498
512
        hash_offset = entry->val & hmask;
499
513
        out_entry->p_entry = entry;
518
532
    unsigned int i, j, hsize, hmask, total_num_entries;
519
533
    struct delta_index *index;
520
534
    struct index_entry *entry, *packed_entry, **packed_hash;
521
 
    struct index_entry *last_entry, null_entry = {0};
 
535
    struct index_entry null_entry = {0};
522
536
    void *mem;
523
537
    unsigned long memsize;
524
538
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
569
583
        free(index);
570
584
        return NULL;
571
585
    }
572
 
    last_entry = entries + num_entries;
573
586
    for (i = 0; i < hsize; i++) {
574
587
        /*
575
588
         * Coalesce all entries belonging in one hash bucket
679
692
    }
680
693
}
681
694
 
682
 
struct delta_index *
 
695
delta_result
683
696
create_delta_index_from_delta(const struct source_info *src,
684
 
                              struct delta_index *old_index)
 
697
                              struct delta_index *old_index,
 
698
                              struct delta_index **fresh)
685
699
{
686
700
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
687
701
    unsigned int hash_offset;
690
704
    struct delta_index *new_index;
691
705
    struct index_entry *entry, *entries;
692
706
 
 
707
    if (!old_index)
 
708
        return DELTA_INDEX_NEEDED;
693
709
    if (!src->buf || !src->size)
694
 
        return NULL;
 
710
        return DELTA_SOURCE_EMPTY;
695
711
    buffer = src->buf;
696
712
    top = buffer + src->size;
697
713
 
704
720
 
705
721
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
706
722
 
 
723
    if (!max_num_entries) {
 
724
        *fresh = old_index;
 
725
        return DELTA_OK;
 
726
    }
 
727
 
707
728
    /* allocate an array to hold whatever entries we find */
708
729
    entries = malloc(sizeof(*entry) * max_num_entries);
709
730
    if (!entries) /* malloc failure */
710
 
        return NULL;
 
731
        return DELTA_OUT_OF_MEMORY;
711
732
 
712
733
    /* then populate the index for the new data */
713
734
    prev_val = ~0;
774
795
        }
775
796
    }
776
797
    if (data != top) {
777
 
        /* Something was wrong with this delta */
 
798
        /* The source_info data passed was corrupted or otherwise invalid */
778
799
        free(entries);
779
 
        return NULL;
 
800
        return DELTA_SOURCE_BAD;
780
801
    }
781
802
    if (num_entries == 0) {
782
803
        /** Nothing to index **/
783
804
        free(entries);
784
 
        return NULL;
 
805
        *fresh = old_index;
 
806
        return DELTA_OK;
785
807
    }
786
 
    assert(old_index != NULL);
787
808
    old_index->last_src = src;
788
809
    /* See if we can fill in these values into the holes in the array */
789
810
    entry = entries;
841
862
        new_index = create_index_from_old_and_new_entries(old_index,
842
863
            entry, num_entries);
843
864
    } else {
844
 
        new_index = NULL;
 
865
        new_index = old_index;
845
866
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
846
867
    }
847
868
    free(entries);
848
 
    return new_index;
 
869
    /* create_index_from_old_and_new_entries returns NULL on malloc failure */
 
870
    if (!new_index)
 
871
        return DELTA_OUT_OF_MEMORY;
 
872
    *fresh = new_index;
 
873
    return DELTA_OK;
849
874
}
850
875
 
851
876
void free_delta_index(struct delta_index *index)
853
878
    free(index);
854
879
}
855
880
 
856
 
unsigned long sizeof_delta_index(struct delta_index *index)
 
881
unsigned long
 
882
sizeof_delta_index(struct delta_index *index)
857
883
{
858
884
    if (index)
859
885
        return index->memsize;
867
893
 */
868
894
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
869
895
 
870
 
void *
 
896
delta_result
871
897
create_delta(const struct delta_index *index,
872
898
             const void *trg_buf, unsigned long trg_size,
873
 
             unsigned long *delta_size, unsigned long max_size)
 
899
             unsigned long *delta_size, unsigned long max_size,
 
900
             void **delta_data)
874
901
{
875
 
    unsigned int i, outpos, outsize, moff, msize, val;
 
902
    unsigned int i, outpos, outsize, moff, val;
 
903
    int msize;
876
904
    const struct source_info *msource;
877
905
    int inscnt;
878
906
    const unsigned char *ref_data, *ref_top, *data, *top;
880
908
    unsigned long source_size;
881
909
 
882
910
    if (!trg_buf || !trg_size)
883
 
        return NULL;
 
911
        return DELTA_BUFFER_EMPTY;
884
912
    if (index == NULL)
885
 
        return NULL;
 
913
        return DELTA_INDEX_NEEDED;
886
914
 
887
915
    outpos = 0;
888
916
    outsize = 8192;
890
918
        outsize = max_size + MAX_OP_SIZE + 1;
891
919
    out = malloc(outsize);
892
920
    if (!out)
893
 
        return NULL;
 
921
        return DELTA_OUT_OF_MEMORY;
894
922
 
895
923
    source_size = index->last_src->size + index->last_src->agg_offset;
896
924
 
943
971
                 entry++) {
944
972
                const unsigned char *ref;
945
973
                const unsigned char *src;
946
 
                unsigned int ref_size;
 
974
                int ref_size;
947
975
                if (entry->val != val)
948
976
                    continue;
949
977
                ref = entry->ptr;
956
984
                 * match more bytes with this location that we have already
957
985
                 * matched.
958
986
                 */
959
 
                if (ref_size > top - src)
 
987
                if (ref_size > (top - src))
960
988
                    ref_size = top - src;
961
989
                if (ref_size <= msize)
962
990
                    break;
963
991
                /* See how many bytes actually match at this location. */
964
992
                while (ref_size-- && *src++ == *ref)
965
993
                    ref++;
966
 
                if (msize < ref - entry->ptr) {
 
994
                if (msize < (ref - entry->ptr)) {
967
995
                    /* this is our best match so far */
968
996
                    msize = ref - entry->ptr;
969
997
                    msource = entry->src;
1069
1097
            out = realloc(out, outsize);
1070
1098
            if (!out) {
1071
1099
                free(tmp);
1072
 
                return NULL;
 
1100
                return DELTA_OUT_OF_MEMORY;
1073
1101
            }
1074
1102
        }
1075
1103
    }
1079
1107
 
1080
1108
    if (max_size && outpos > max_size) {
1081
1109
        free(out);
1082
 
        return NULL;
 
1110
        return DELTA_SIZE_TOO_BIG;
1083
1111
    }
1084
1112
 
1085
1113
    *delta_size = outpos;
1086
 
    return out;
 
1114
    *delta_data = out;
 
1115
    return DELTA_OK;
 
1116
}
 
1117
 
 
1118
 
 
1119
int
 
1120
get_entry_summary(const struct delta_index *index, int pos,
 
1121
                  unsigned int *text_offset, unsigned int *hash_val)
 
1122
{
 
1123
    int hsize;
 
1124
    const struct index_entry *entry;
 
1125
    const struct index_entry *start_of_entries;
 
1126
    unsigned int offset;
 
1127
    if (pos < 0 || text_offset == NULL || hash_val == NULL
 
1128
        || index == NULL)
 
1129
    {
 
1130
        return 0;
 
1131
    }
 
1132
    hsize = index->hash_mask + 1;
 
1133
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
 
1134
    entry = start_of_entries + pos;
 
1135
    if (entry > index->last_entry) {
 
1136
        return 0;
 
1137
    }
 
1138
    if (entry->ptr == NULL) {
 
1139
        *text_offset = 0;
 
1140
        *hash_val = 0;
 
1141
    } else {
 
1142
        offset = entry->src->agg_offset;
 
1143
        offset += (entry->ptr - ((unsigned char *)entry->src->buf));
 
1144
        *text_offset = offset;
 
1145
        *hash_val = entry->val;
 
1146
    }
 
1147
    return 1;
 
1148
}
 
1149
 
 
1150
 
 
1151
int
 
1152
get_hash_offset(const struct delta_index *index, int pos,
 
1153
                unsigned int *entry_offset)
 
1154
{
 
1155
    int hsize;
 
1156
    const struct index_entry *entry;
 
1157
    const struct index_entry *start_of_entries;
 
1158
    if (pos < 0 || index == NULL || entry_offset == NULL)
 
1159
    {
 
1160
        return 0;
 
1161
    }
 
1162
    hsize = index->hash_mask + 1;
 
1163
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
 
1164
    if (pos >= hsize) {
 
1165
        return 0;
 
1166
    }
 
1167
    entry = index->hash[pos];
 
1168
    if (entry == NULL) {
 
1169
        *entry_offset = -1;
 
1170
    } else {
 
1171
        *entry_offset = (entry - start_of_entries);
 
1172
    }
 
1173
    return 1;
 
1174
}
 
1175
 
 
1176
 
 
1177
unsigned int
 
1178
rabin_hash(const unsigned char *data)
 
1179
{
 
1180
    int i;
 
1181
    unsigned int val = 0;
 
1182
    for (i = 0; i < RABIN_WINDOW; i++)
 
1183
        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 
1184
    return val;
1087
1185
}
1088
1186
 
1089
1187
/* vim: et ts=4 sw=4 sts=4