← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: John Arbash Meinel
  • Date: 2011-04-20 15:06:17 UTC
  • mto: This revision was merged to the branch mainline in revision 5836.
  • Revision ID: john@arbash-meinel.com-20110420150617-i41caxgemg32tq1r
Start adding tests that _worth_saving_limit works as expected.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
376
376
delta_result
377
377
create_delta_index(const struct source_info *src,
378
378
                   struct delta_index *old,
379
 
                   struct delta_index **fresh,
380
 
                   int max_bytes_to_index)
 
379
                   struct delta_index **fresh)
381
380
{
382
381
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
383
 
    unsigned int total_num_entries, stride, max_entries;
 
382
    unsigned int total_num_entries;
384
383
    const unsigned char *data, *buffer;
385
384
    struct delta_index *index;
386
385
    struct unpacked_index_entry *entry, **hash;
392
391
    buffer = src->buf;
393
392
 
394
393
    /* Determine index hash size.  Note that indexing skips the
395
 
       first byte so we subtract 1 to get the edge cases right.
396
 
     */
397
 
    stride = RABIN_WINDOW;
 
394
       first byte to allow for optimizing the Rabin's polynomial
 
395
       initialization in create_delta(). */
398
396
    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
 
    }
409
397
    if (old != NULL)
410
398
        total_num_entries = num_entries + old->num_entries;
411
399
    else
440
428
 
441
429
    /* then populate the index for the new data */
442
430
    prev_val = ~0;
443
 
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
 
431
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
444
432
         data >= buffer;
445
 
         data -= stride) {
 
433
         data -= RABIN_WINDOW) {
446
434
        unsigned int val = 0;
447
435
        for (i = 1; i <= RABIN_WINDOW; i++)
448
436
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
488
476
                       unsigned int hsize)
489
477
{
490
478
    unsigned int hash_offset, hmask, memsize;
491
 
    struct index_entry *entry;
 
479
    struct index_entry *entry, *last_entry;
492
480
    struct index_entry_linked_list *out_entry, **hash;
493
481
    void *mem;
494
482
 
508
496
    /* We know that entries are in the order we want in the output, but they
509
497
     * aren't "grouped" by hash bucket yet.
510
498
     */
 
499
    last_entry = entries + num_entries;
511
500
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
512
501
        hash_offset = entry->val & hmask;
513
502
        out_entry->p_entry = entry;
532
521
    unsigned int i, j, hsize, hmask, total_num_entries;
533
522
    struct delta_index *index;
534
523
    struct index_entry *entry, *packed_entry, **packed_hash;
535
 
    struct index_entry null_entry = {0};
 
524
    struct index_entry *last_entry, null_entry = {0};
536
525
    void *mem;
537
526
    unsigned long memsize;
538
527
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
583
572
        free(index);
584
573
        return NULL;
585
574
    }
 
575
    last_entry = entries + num_entries;
586
576
    for (i = 0; i < hsize; i++) {
587
577
        /*
588
578
         * Coalesce all entries belonging in one hash bucket
720
710
 
721
711
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
722
712
 
723
 
    if (!max_num_entries) {
724
 
        *fresh = old_index;
725
 
        return DELTA_OK;
726
 
    }
727
 
 
728
713
    /* allocate an array to hold whatever entries we find */
729
714
    entries = malloc(sizeof(*entry) * max_num_entries);
730
715
    if (!entries) /* malloc failure */
1115
1100
    return DELTA_OK;
1116
1101
}
1117
1102
 
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;
1185
 
}
1186
 
 
1187
1103
/* vim: et ts=4 sw=4 sts=4
1188
1104
 */