← 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 18:05:44 UTC
  • mto: (0.17.31 trunk)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090303180544-mfgw9jsndwiwj047
Change the internals to allow delta indexes to be expanded with new source data.
Now when adding a new source, the old index entries are included in the new structure.
This generally seems to be better than having multiple indexes, as it improves the
efficiency of the internal hash map, and avoids extra iterating.
Bring back the _FAST flag. At the moment, with _FAST=True, doing bzr pack is about
37s rather than 1min, and gives 9.7MB texts, rather than 8.2MB or so.
So at the moment, it is still a useful flag to have.

Show diffs side-by-side

added added

removed removed

Lines of Context:
diff-delta.c
129
129
        unsigned int hash_mask; /* val & hash_mask gives the hash index for a given
130
130
                                                           entry */
131
131
        unsigned int num_entries; /* The total number of entries in this index */
 
132
        struct index_entry *last_entry; /* Pointer to the last valid entry */
132
133
        struct index_entry *hash[];
133
134
};
134
135
 
193
194
 
194
195
static struct delta_index *
195
196
pack_delta_index(struct unpacked_index_entry **hash, unsigned int hsize,
196
 
                                 unsigned int entries)
 
197
                                 unsigned int num_entries)
197
198
{
198
199
        unsigned int i, memsize;
199
200
        struct unpacked_index_entry *entry;
206
207
         */
207
208
        memsize = sizeof(*index)
208
209
                + sizeof(*packed_hash) * (hsize+1)
209
 
                + sizeof(*packed_entry) * entries;
 
210
                + sizeof(*packed_entry) * num_entries;
210
211
        mem = malloc(memsize);
211
212
        if (!mem) {
212
213
                return NULL;
215
216
        index = mem;
216
217
        index->memsize = memsize;
217
218
        index->hash_mask = hsize - 1;
218
 
        index->num_entries = entries;
 
219
        index->num_entries = num_entries;
219
220
 
220
221
        mem = index->hash;
221
222
        packed_hash = mem;
235
236
        /* Sentinel value to indicate the length of the last hash bucket */
236
237
        packed_hash[hsize] = packed_entry;
237
238
 
238
 
        assert(packed_entry - (struct index_entry *)mem == entries);
 
239
        assert(packed_entry - (struct index_entry *)mem == num_entries);
 
240
        index->last_entry = (packed_entry - 1);
239
241
        return index;
240
242
}
241
243
 
242
 
 
243
 
struct delta_index * create_delta_index(const struct source_info *src)
244
 
{
245
 
        unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
 
244
void include_entries_from_index(struct unpacked_index_entry **hash,
 
245
                                                                unsigned int *hash_count,
 
246
                                                                unsigned int hsize,
 
247
                                                                struct unpacked_index_entry *entry,
 
248
                                                                const struct delta_index *old)
 
249
{
 
250
        unsigned int i, hmask, masked_val;
 
251
        struct index_entry *old_entry;
 
252
 
 
253
        hmask = hsize - 1;
 
254
        /* Iterate backwards through the existing entries
 
255
         * This is so that matches early in the file end up being the first pointer
 
256
         * in the linked list.
 
257
         */
 
258
        for (old_entry = old->last_entry, i = 0; i < old->num_entries;
 
259
                 i++, old_entry--) {
 
260
                masked_val = old_entry->val & hmask;
 
261
                entry->entry = *old_entry;
 
262
                entry->next = hash[masked_val];
 
263
                hash[masked_val] = entry++;
 
264
                hash_count[masked_val]++;
 
265
        }
 
266
}
 
267
 
 
268
 
 
269
struct delta_index * create_delta_index(const struct source_info *src,
 
270
                                                                                const struct delta_index *old)
 
271
{
 
272
        unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
 
273
        unsigned int total_num_entries;
246
274
        const unsigned char *data, *buffer;
247
275
        struct delta_index *index;
248
276
        struct unpacked_index_entry *entry, **hash;
256
284
        /* Determine index hash size.  Note that indexing skips the
257
285
           first byte to allow for optimizing the Rabin's polynomial
258
286
           initialization in create_delta(). */
259
 
        entries = (src->size - 1)  / RABIN_WINDOW;
260
 
        hsize = entries / 4;
 
287
        num_entries = (src->size - 1)  / RABIN_WINDOW;
 
288
        if (old != NULL)
 
289
                total_num_entries = num_entries + old->num_entries;
 
290
        else
 
291
                total_num_entries = num_entries;
 
292
        hsize = total_num_entries / 4;
261
293
        for (i = 4; (1u << i) < hsize && i < 31; i++);
262
294
        hsize = 1 << i;
263
295
        hmask = hsize - 1;
264
296
 
265
297
        /* allocate lookup index */
266
298
        memsize = sizeof(*hash) * hsize +
267
 
                  sizeof(*entry) * entries;
 
299
                  sizeof(*entry) * total_num_entries;
268
300
        mem = malloc(memsize);
269
301
        if (!mem)
270
302
                return NULL;
274
306
 
275
307
        memset(hash, 0, hsize * sizeof(*hash));
276
308
 
277
 
        /* allocate an array to count hash entries */
 
309
        /* allocate an array to count hash num_entries */
278
310
        hash_count = calloc(hsize, sizeof(*hash_count));
279
311
        if (!hash_count) {
280
312
                free(hash);
281
313
                return NULL;
282
314
        }
283
315
 
284
 
        /* then populate the index */
 
316
        /* then populate the index for the new data */
285
317
        prev_val = ~0;
286
 
        for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
 
318
        for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
287
319
                 data >= buffer;
288
320
                 data -= RABIN_WINDOW) {
289
321
                unsigned int val = 0;
292
324
                if (val == prev_val) {
293
325
                        /* keep the lowest of consecutive identical blocks */
294
326
                        entry[-1].entry.ptr = data + RABIN_WINDOW;
295
 
                        --entries;
 
327
                        --num_entries;
 
328
                        --total_num_entries;
296
329
                } else {
297
330
                        prev_val = val;
298
331
                        i = val & hmask;
304
337
                        hash_count[i]++;
305
338
                }
306
339
        }
 
340
        /* If we have an existing delta_index, we want to bring its info into the
 
341
         * new structure. We assume that the existing structure's objects all occur
 
342
         * before the new source, so they get first precedence in the index.
 
343
         */
 
344
        if (old != NULL)
 
345
                include_entries_from_index(hash, hash_count, hsize, entry, old);
307
346
 
308
 
        entries = limit_hash_buckets(hash, hash_count, hsize, entries);
 
347
        total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
 
348
                                                                                   total_num_entries);
309
349
        free(hash_count);
310
 
        index = pack_delta_index(hash, hsize, entries);
 
350
        index = pack_delta_index(hash, hsize, total_num_entries);
311
351
        index->src = src;
312
352
        free(hash);
313
353
        if (!index) {
347
387
        int inscnt;
348
388
        const unsigned char *ref_data, *ref_top, *data, *top;
349
389
        unsigned char *out;
 
390
        unsigned long source_size;
350
391
 
351
392
        if (!trg_buf || !trg_size)
352
393
                return NULL;
370
411
        }
371
412
        assert(i <= index->src->size + index->src->agg_offset);
372
413
        i = index->src->size + index->src->agg_offset;
 
414
        source_size = i;
373
415
        while (i >= 0x80) {
374
416
                out[outpos++] = i | 0x80;
375
417
                i >>= 7;
507
549
                        /* moff is the offset in the local structure, for encoding, we need
508
550
                         * to push it into the global offset
509
551
                         */
 
552
                        assert(moff < msource->size);
510
553
                        moff += msource->agg_offset;
 
554
                        assert(moff + msize <= source_size);
511
555
                        if (moff & 0x000000ff)
512
556
                                out[outpos++] = moff >> 0,  i |= 0x01;
513
557
                        if (moff & 0x0000ff00)