~bzr-pqm/bzr/bzr.dev

Committer: John Arbash Meinel
Date: 2009-03-19 04:02:18 UTC
mto: (3735.2.157 brisbane-core)
mto: This revision was merged to the branch mainline in revision 4280.
Revision ID: john@arbash-meinel.com-20090319040218-pqex5298ifl1ds54

Fix a bug when there is more than one entry (increment out_entry).
Also make the mini_hsize always the same size as hsize.
Otherwise we end up walking the same nodes over and over again.
This way, we only walk nodes when we are going to be inserting them.

files modified:
bzrlib/diff-delta.c

Show diffs side-by-side

added added

removed removed

bzrlib/diff-delta.c

528

529

struct index_entry_linked_list **

530

_put_entries_into_hash(struct index_entry *entries, unsigned int num_entries,

531

unsigned int *out_hsize)

531

unsigned int hsize)

532

{

533

unsigned int i, hsize, hmask, memsize;

533

unsigned int i, hash_offset, hmask, memsize;

534

struct index_entry *entry, *last_entry;

535

struct index_entry_linked_list *out_entry, **hash;

536

void *mem;

537

538

/* Avoid getting collisions, as it makes the code faster, and this will be

539

* a temp buffer anyway.

540

541

hsize = num_entries * 2;

542

for (i = 4; (1u << i) < hsize && i < 31; i++);

543

hsize = 1 << i;

544

if (hsize > *out_hsize) {

545

hsize = *out_hsize;

546

}

547

538

hmask = hsize - 1;

548

*out_hsize = hsize;

549

539

550

540

memsize = sizeof(*hash) * hsize +

551

541

sizeof(*out_entry) * num_entries;

563

553

564

554

last_entry = entries + num_entries;

565

555

for (entry = entries + num_entries - 1; entry >= entries; --entry) {

566

i = entry->val & hmask;

556

hash_offset = entry->val & hmask;

567

557

out_entry->p_entry = entry;

568

out_entry->next = hash[i];

558

out_entry->next = hash[hash_offset];

569

559

/* TODO: Remove entries that have identical vals, or at least filter

570

560

* the map a little bit.

571

561

* if (hash[i] != NULL) {

572

562

* }

573

563

574

hash[i] = out_entry;

564

hash[hash_offset] = out_entry;

565

++out_entry;

575

566

}

576

567

return hash;

577

568

}

589

580

void *mem;

590

581

unsigned long memsize;

591

582

struct index_entry_linked_list *unpacked_entry, **mini_hash;

592

unsigned int mini_hsize, mini_hmask;

593

583

594

584

/* Determine index hash size. Note that indexing skips the

595

585

first byte to allow for optimizing the Rabin's polynomial

632

622

mem = packed_hash + (hsize+1);

633

623

packed_entry = mem;

634

624

635

mini_hsize = hsize;

636

mini_hash = _put_entries_into_hash(entries, num_entries, &mini_hsize);

625

mini_hash = _put_entries_into_hash(entries, num_entries, hsize);

637

626

if (mini_hash == NULL) {

638

627

free(index);

639

628

return NULL;

640

629

}

641

mini_hmask = mini_hsize - 1;

642

assert(mini_hmask <= hmask);

643

630

last_entry = entries + num_entries;

644

631

for (i = 0; i < hsize; i++) {

645

632

692

679

* entries, the tradeoff is a malloc, 1 pass over the entries, copying

693

680

* them into a sorted buffer, and a free() when done,

694

681

695

for (unpacked_entry = mini_hash[i & mini_hmask];

682

for (unpacked_entry = mini_hash[i];

696

683

unpacked_entry;

697

684

unpacked_entry = unpacked_entry->next) {

698

if ((unpacked_entry->p_entry->val & hmask) == i) {

699

*packed_entry++ = *(unpacked_entry->p_entry);

700

}

685

assert((unpacked_entry->p_entry->val & hmask) == i);

686

*packed_entry++ = *(unpacked_entry->p_entry);

701

687

}

702

688

/* Now insert some extra nulls */

703

689

for (j = 0; j < EXTRA_NULLS; ++j) {

Older »