/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: John Arbash Meinel
  • Date: 2011-04-22 14:12:22 UTC
  • mfrom: (5809 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5836.
  • Revision ID: john@arbash-meinel.com-20110422141222-nx2j0hbkihcb8j16
Merge newer bzr.dev and resolve conflicts.
Try to write some documentation about how the _dirblock_state works.
Fix up the tests so that they pass again.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
220
220
    unsigned int i, j, hmask, memsize, fit_in_old, copied_count;
221
221
    struct unpacked_index_entry *entry;
222
222
    struct delta_index *index;
223
 
    struct index_entry *packed_entry, **packed_hash, *old_entry;
 
223
    struct index_entry *packed_entry, **packed_hash, *old_entry, *copy_from;
224
224
    struct index_entry null_entry = {0};
225
225
    void *mem;
226
226
 
334
334
             * old_index->hash_mask? Would it make any real difference?
335
335
             */
336
336
            j = i & old_index->hash_mask;
 
337
            copy_from = old_index->hash[j];
337
338
            for (old_entry = old_index->hash[j];
338
339
                 old_entry < old_index->hash[j + 1] && old_entry->ptr != NULL;
339
340
                 old_entry++) {
375
376
delta_result
376
377
create_delta_index(const struct source_info *src,
377
378
                   struct delta_index *old,
378
 
                   struct delta_index **fresh,
379
 
                   int max_bytes_to_index)
 
379
                   struct delta_index **fresh)
380
380
{
381
381
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
382
 
    unsigned int total_num_entries, stride, max_entries;
 
382
    unsigned int total_num_entries;
383
383
    const unsigned char *data, *buffer;
384
384
    struct delta_index *index;
385
385
    struct unpacked_index_entry *entry, **hash;
391
391
    buffer = src->buf;
392
392
 
393
393
    /* Determine index hash size.  Note that indexing skips the
394
 
       first byte so we subtract 1 to get the edge cases right.
395
 
     */
396
 
    stride = RABIN_WINDOW;
 
394
       first byte to allow for optimizing the Rabin's polynomial
 
395
       initialization in create_delta(). */
397
396
    num_entries = (src->size - 1)  / RABIN_WINDOW;
398
 
    if (max_bytes_to_index > 0) {
399
 
        max_entries = (unsigned int) (max_bytes_to_index / RABIN_WINDOW);
400
 
        if (num_entries > max_entries) {
401
 
            /* Limit the max number of matching entries. This reduces the 'best'
402
 
             * possible match, but means we don't consume all of ram.
403
 
             */
404
 
            num_entries = max_entries;
405
 
            stride = (src->size - 1) / num_entries;
406
 
        }
407
 
    }
408
397
    if (old != NULL)
409
398
        total_num_entries = num_entries + old->num_entries;
410
399
    else
439
428
 
440
429
    /* then populate the index for the new data */
441
430
    prev_val = ~0;
442
 
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
 
431
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
443
432
         data >= buffer;
444
 
         data -= stride) {
 
433
         data -= RABIN_WINDOW) {
445
434
        unsigned int val = 0;
446
435
        for (i = 1; i <= RABIN_WINDOW; i++)
447
436
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
487
476
                       unsigned int hsize)
488
477
{
489
478
    unsigned int hash_offset, hmask, memsize;
490
 
    struct index_entry *entry;
 
479
    struct index_entry *entry, *last_entry;
491
480
    struct index_entry_linked_list *out_entry, **hash;
492
481
    void *mem;
493
482
 
507
496
    /* We know that entries are in the order we want in the output, but they
508
497
     * aren't "grouped" by hash bucket yet.
509
498
     */
 
499
    last_entry = entries + num_entries;
510
500
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
511
501
        hash_offset = entry->val & hmask;
512
502
        out_entry->p_entry = entry;
531
521
    unsigned int i, j, hsize, hmask, total_num_entries;
532
522
    struct delta_index *index;
533
523
    struct index_entry *entry, *packed_entry, **packed_hash;
534
 
    struct index_entry null_entry = {0};
 
524
    struct index_entry *last_entry, null_entry = {0};
535
525
    void *mem;
536
526
    unsigned long memsize;
537
527
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
582
572
        free(index);
583
573
        return NULL;
584
574
    }
 
575
    last_entry = entries + num_entries;
585
576
    for (i = 0; i < hsize; i++) {
586
577
        /*
587
578
         * Coalesce all entries belonging in one hash bucket
719
710
 
720
711
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
721
712
 
722
 
    if (!max_num_entries) {
723
 
        *fresh = old_index;
724
 
        return DELTA_OK;
725
 
    }
726
 
 
727
713
    /* allocate an array to hold whatever entries we find */
728
714
    entries = malloc(sizeof(*entry) * max_num_entries);
729
715
    if (!entries) /* malloc failure */
904
890
    int inscnt;
905
891
    const unsigned char *ref_data, *ref_top, *data, *top;
906
892
    unsigned char *out;
 
893
    unsigned long source_size;
907
894
 
908
895
    if (!trg_buf || !trg_size)
909
896
        return DELTA_BUFFER_EMPTY;
918
905
    if (!out)
919
906
        return DELTA_OUT_OF_MEMORY;
920
907
 
 
908
    source_size = index->last_src->size + index->last_src->agg_offset;
 
909
 
921
910
    /* store target buffer size */
922
911
    i = trg_size;
923
912
    while (i >= 0x80) {
1049
1038
             */
1050
1039
            assert(moff < msource->size);
1051
1040
            moff += msource->agg_offset;
1052
 
            assert(moff + msize
1053
 
                <= index->last_src->size + index->last_src->agg_offset);
 
1041
            assert(moff + msize <= source_size);
1054
1042
            if (moff & 0x000000ff)
1055
1043
                out[outpos++] = moff >> 0,  i |= 0x01;
1056
1044
            if (moff & 0x0000ff00)
1112
1100
    return DELTA_OK;
1113
1101
}
1114
1102
 
1115
 
 
1116
 
int
1117
 
get_entry_summary(const struct delta_index *index, int pos,
1118
 
                  unsigned int *text_offset, unsigned int *hash_val)
1119
 
{
1120
 
    int hsize;
1121
 
    const struct index_entry *entry;
1122
 
    const struct index_entry *start_of_entries;
1123
 
    unsigned int offset;
1124
 
    if (pos < 0 || text_offset == NULL || hash_val == NULL
1125
 
        || index == NULL)
1126
 
    {
1127
 
        return 0;
1128
 
    }
1129
 
    hsize = index->hash_mask + 1;
1130
 
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
1131
 
    entry = start_of_entries + pos;
1132
 
    if (entry > index->last_entry) {
1133
 
        return 0;
1134
 
    }
1135
 
    if (entry->ptr == NULL) {
1136
 
        *text_offset = 0;
1137
 
        *hash_val = 0;
1138
 
    } else {
1139
 
        offset = entry->src->agg_offset;
1140
 
        offset += (entry->ptr - ((unsigned char *)entry->src->buf));
1141
 
        *text_offset = offset;
1142
 
        *hash_val = entry->val;
1143
 
    }
1144
 
    return 1;
1145
 
}
1146
 
 
1147
 
 
1148
 
int
1149
 
get_hash_offset(const struct delta_index *index, int pos,
1150
 
                unsigned int *entry_offset)
1151
 
{
1152
 
    int hsize;
1153
 
    const struct index_entry *entry;
1154
 
    const struct index_entry *start_of_entries;
1155
 
    if (pos < 0 || index == NULL || entry_offset == NULL)
1156
 
    {
1157
 
        return 0;
1158
 
    }
1159
 
    hsize = index->hash_mask + 1;
1160
 
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
1161
 
    if (pos >= hsize) {
1162
 
        return 0;
1163
 
    }
1164
 
    entry = index->hash[pos];
1165
 
    if (entry == NULL) {
1166
 
        *entry_offset = -1;
1167
 
    } else {
1168
 
        *entry_offset = (entry - start_of_entries);
1169
 
    }
1170
 
    return 1;
1171
 
}
1172
 
 
1173
 
 
1174
 
unsigned int
1175
 
rabin_hash(const unsigned char *data)
1176
 
{
1177
 
    int i;
1178
 
    unsigned int val = 0;
1179
 
    for (i = 0; i < RABIN_WINDOW; i++)
1180
 
        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
1181
 
    return val;
1182
 
}
1183
 
 
1184
1103
/* vim: et ts=4 sw=4 sts=4
1185
1104
 */