← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to diff-delta.c

  • Committer: John Arbash Meinel
  • Date: 2009-03-03 21:07:21 UTC
  • mto: (0.17.31 trunk)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090303210721-m25wehoeo3jxsz11
When adding new entries to the delta index, use memcpy
rather than copying them one by one.

Show diffs side-by-side

added added

removed removed

Lines of Context:
diff-delta.c
11
11
 * published by the Free Software Foundation.
12
12
 */
13
13
 
 
14
#include <stdio.h>
14
15
#include "delta.h"
15
16
#include <assert.h>
16
17
 
270
271
        }
271
272
}
272
273
 
 
274
struct delta_index *
 
275
create_index_from_old_and_hash(const struct delta_index *old,
 
276
                                                           struct unpacked_index_entry **hash,
 
277
                                                           unsigned int hsize,
 
278
                                                           unsigned int num_entries)
 
279
{
 
280
        unsigned int i, memsize, total_num_entries;
 
281
        struct unpacked_index_entry *entry;
 
282
        struct delta_index *index;
 
283
        struct index_entry *packed_entry, **packed_hash, *old_entry;
 
284
        size_t to_copy;
 
285
        void *mem;
 
286
        /*
 
287
         * Now create the packed index in array form
 
288
         * rather than linked lists.
 
289
         */
 
290
        total_num_entries = num_entries + old->num_entries;
 
291
        memsize = sizeof(*index)
 
292
                + sizeof(*packed_hash) * (hsize+1)
 
293
                + sizeof(*packed_entry) * total_num_entries;
 
294
        mem = malloc(memsize);
 
295
        if (!mem) {
 
296
                return NULL;
 
297
        }
 
298
 
 
299
        index = mem;
 
300
        index->memsize = memsize;
 
301
        index->hash_mask = hsize - 1;
 
302
        index->num_entries = total_num_entries;
 
303
 
 
304
        mem = index->hash;
 
305
        packed_hash = mem;
 
306
        mem = packed_hash + (hsize+1);
 
307
        packed_entry = mem;
 
308
 
 
309
        fprintf(stderr, "copying %d entries, adding %d\n",
 
310
                old->num_entries, num_entries);
 
311
        to_copy = 0;
 
312
        for (i = 0; i < hsize; i++) {
 
313
                /*
 
314
                 * Coalesce all entries belonging to one linked list
 
315
                 * into consecutive array entries.
 
316
                 * The entries in old all come before the entries in hash.
 
317
                 */
 
318
                packed_hash[i] = packed_entry;
 
319
                old_entry = old->hash[i];
 
320
                to_copy = (old->hash[i+1] - old_entry);
 
321
                if (to_copy > 0) {
 
322
                        memcpy(packed_entry, old_entry, to_copy * sizeof(struct index_entry));
 
323
                        packed_entry += to_copy;
 
324
                }
 
325
                for (entry = hash[i]; entry; entry = entry->next)
 
326
                        *packed_entry++ = entry->entry;
 
327
        }
 
328
 
 
329
        /* Sentinel value to indicate the length of the last hash bucket */
 
330
        packed_hash[hsize] = packed_entry;
 
331
 
 
332
        assert(packed_entry - (struct index_entry *)mem == total_num_entries);
 
333
        index->last_entry = (packed_entry - 1);
 
334
        return index;
 
335
}
 
336
 
273
337
 
274
338
struct delta_index * create_delta_index(const struct source_info *src,
275
339
                                                                                const struct delta_index *old)
432
496
                cmd = *data++;
433
497
                if (cmd & 0x80) {
434
498
                        /* Copy instruction, skip it */
435
 
                        const unsigned char *start = data;
436
499
                        if (cmd & 0x01) data++;
437
500
                        if (cmd & 0x02) data++;
438
501
                        if (cmd & 0x04) data++;
494
557
                free(hash_count);
495
558
                return NULL;
496
559
        }
 
560
        if (num_entries == 0) {
 
561
                /** Nothing to index **/
 
562
                return NULL;
 
563
        }
497
564
        if (old != NULL) {
498
 
                total_num_entries = num_entries + old->num_entries;
499
 
                include_entries_from_index(hash, hash_count, hsize, entry, old);
 
565
                if (hmask == old->hash_mask) {
 
566
                        /* The total hash table size didn't change, which means that
 
567
                         * entries will end up in the same pages. We can do bulk-copying to
 
568
                         * get the final output
 
569
                         */
 
570
                        index = create_index_from_old_and_hash(old, hash, hsize,
 
571
                                                                                                   num_entries);
 
572
                        free(hash_count);
 
573
                        free(hash);
 
574
                        if (!index) {
 
575
                                return NULL;
 
576
                        }
 
577
                        index->last_src = src;
 
578
                        return index;
 
579
                } else {
 
580
                        total_num_entries = num_entries + old->num_entries;
 
581
                        include_entries_from_index(hash, hash_count, hsize, entry, old);
 
582
                }
500
583
        } else {
501
584
                total_num_entries = num_entries;
502
585
        }
505
588
                                                                                   total_num_entries);
506
589
        free(hash_count);
507
590
        index = pack_delta_index(hash, hsize, total_num_entries);
508
 
        index->last_src = src;
509
591
        free(hash);
510
592
        if (!index) {
511
593
                return NULL;
512
594
        }
 
595
        index->last_src = src;
513
596
        return index;
514
597
}
515
598