X-Git-Url: https://asedeno.scripts.mit.edu/gitweb/?a=blobdiff_plain;f=diff-delta.c;h=464ac3ffc0a45e95637e2cecdf97b3d39e5c7933;hb=452c6d506b1a6dcf24d4ceaa592afc39c1c1a60e;hp=3a737da68c8cadb900ffe5b44973d9193fbca83f;hpb=843366961cf14aad6490fbeb30f7b98f37f8833a;p=git.git diff --git a/diff-delta.c b/diff-delta.c index 3a737da68..464ac3ffc 100644 --- a/diff-delta.c +++ b/diff-delta.c @@ -1,21 +1,14 @@ /* * diff-delta.c: generate a delta between two buffers * - * Many parts of this file have been lifted from LibXDiff version 0.10. - * http://www.xmailserver.org/xdiff-lib.html + * This code was greatly inspired by parts of LibXDiff from Davide Libenzi + * http://www.xmailserver.org/xdiff-lib.html * - * LibXDiff was written by Davide Libenzi - * Copyright (C) 2003 Davide Libenzi + * Rewritten for GIT by Nicolas Pitre , (C) 2005-2007 * - * Many mods for GIT usage by Nicolas Pitre , (C) 2005. - * - * This file is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * Use of this within git automatically means that the LGPL - * licensing gets turned into GPLv2 within this project. + * This code is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. */ #include "git-compat-util.h" @@ -122,10 +115,15 @@ static const unsigned int U[256] = { struct index_entry { const unsigned char *ptr; unsigned int val; - struct index_entry *next; +}; + +struct unpacked_index_entry { + struct index_entry entry; + struct unpacked_index_entry *next; }; struct delta_index { + unsigned long memsize; const void *src_buf; unsigned long src_size; unsigned int hash_mask; @@ -137,7 +135,8 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize) unsigned int i, hsize, hmask, entries, prev_val, *hash_count; const unsigned char *data, *buffer = buf; struct delta_index *index; - struct index_entry *entry, **hash; + struct unpacked_index_entry *entry, **hash; + struct index_entry *packed_entry, **packed_hash; void *mem; unsigned long memsize; @@ -154,27 +153,21 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize) hmask = hsize - 1; /* allocate lookup index */ - memsize = sizeof(*index) + - sizeof(*hash) * hsize + + memsize = sizeof(*hash) * hsize + sizeof(*entry) * entries; mem = malloc(memsize); if (!mem) return NULL; - index = mem; - mem = index + 1; hash = mem; mem = hash + hsize; entry = mem; - index->src_buf = buf; - index->src_size = bufsize; - index->hash_mask = hmask; memset(hash, 0, hsize * sizeof(*hash)); /* allocate an array to count hash entries */ hash_count = calloc(hsize, sizeof(*hash_count)); if (!hash_count) { - free(index); + free(hash); return NULL; } @@ -188,12 +181,13 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize) val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT]; if (val == prev_val) { /* keep the lowest of consecutive identical blocks */ - entry[-1].ptr = data + RABIN_WINDOW; + entry[-1].entry.ptr = data + RABIN_WINDOW; + --entries; } else { prev_val = val; i = val & hmask; - entry->ptr = data + RABIN_WINDOW; - entry->val = val; + entry->entry.ptr = data + RABIN_WINDOW; + entry->entry.val = val; entry->next = hash[i]; hash[i] = entry++; hash_count[i]++; @@ -213,20 +207,84 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize) * the reference buffer. */ for (i = 0; i < hsize; i++) { - if (hash_count[i] < HASH_LIMIT) + int acc; + + if (hash_count[i] <= HASH_LIMIT) continue; + + /* We leave exactly HASH_LIMIT entries in the bucket */ + entries -= hash_count[i] - HASH_LIMIT; + entry = hash[i]; + acc = 0; + + /* + * Assume that this loop is gone through exactly + * HASH_LIMIT times and is entered and left with + * acc==0. So the first statement in the loop + * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT + * to the accumulator, and the inner loop consequently + * is run (hash_count[i]-HASH_LIMIT) times, removing + * one element from the list each time. Since acc + * balances out to 0 at the final run, the inner loop + * body can't be left with entry==NULL. So we indeed + * encounter entry==NULL in the outer loop only. + */ do { - struct index_entry *keep = entry; - int skip = hash_count[i] / HASH_LIMIT / 2; - do { - entry = entry->next; - } while(--skip && entry); - keep->next = entry; - } while(entry); + acc += hash_count[i] - HASH_LIMIT; + if (acc > 0) { + struct unpacked_index_entry *keep = entry; + do { + entry = entry->next; + acc -= HASH_LIMIT; + } while (acc > 0); + keep->next = entry->next; + } + entry = entry->next; + } while (entry); } free(hash_count); + /* + * Now create the packed index in array form + * rather than linked lists. + */ + memsize = sizeof(*index) + + sizeof(*packed_hash) * (hsize+1) + + sizeof(*packed_entry) * entries; + mem = malloc(memsize); + if (!mem) { + free(hash); + return NULL; + } + + index = mem; + index->memsize = memsize; + index->src_buf = buf; + index->src_size = bufsize; + index->hash_mask = hmask; + + mem = index->hash; + packed_hash = mem; + mem = packed_hash + (hsize+1); + packed_entry = mem; + + for (i = 0; i < hsize; i++) { + /* + * Coalesce all entries belonging to one linked list + * into consecutive array entries. + */ + packed_hash[i] = packed_entry; + for (entry = hash[i]; entry; entry = entry->next) + *packed_entry++ = entry->entry; + } + + /* Sentinel value to indicate the length of the last hash bucket */ + packed_hash[hsize] = packed_entry; + + assert(packed_entry - (struct index_entry *)mem == entries); + free(hash); + return index; } @@ -235,6 +293,14 @@ void free_delta_index(struct delta_index *index) free(index); } +unsigned long sizeof_delta_index(struct delta_index *index) +{ + if (index) + return index->memsize; + else + return 0; +} + /* * The maximum size for any opcode sequence, including the initial header * plus Rabin window plus biggest copy. @@ -299,7 +365,7 @@ create_delta(const struct delta_index *index, val ^= U[data[-RABIN_WINDOW]]; val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT]; i = val & index->hash_mask; - for (entry = index->hash[i]; entry; entry = entry->next) { + for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) { const unsigned char *ref = entry->ptr; const unsigned char *src = data; unsigned int ref_size = ref_top - ref; @@ -395,7 +461,7 @@ create_delta(const struct delta_index *index, outsize = max_size + MAX_OP_SIZE + 1; if (max_size && outpos > max_size) break; - out = xrealloc(out, outsize); + out = realloc(out, outsize); if (!out) { free(tmp); return NULL;