Documentation: remove backslash before ~ in fast-import manual

diff --git a/diff-delta.c b/diff-delta.c
index 7f8a60de18584fa18dba71a454a6f2300674f47f..464ac3ffc0a45e95637e2cecdf97b3d39e5c7933 100644 (file)
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -4,7 +4,7 @@
  * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
  * http://www.xmailserver.org/xdiff-lib.html
  *
- * Rewritten for GIT by Nicolas Pitre <nico@cam.org>, (C) 2005-2007
+ * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
  *
  * 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
@@ -207,31 +207,52 @@ 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 unpacked_index_entry *keep = entry;
-                       int skip = hash_count[i] / HASH_LIMIT;
-                       do {
-                               --entries;
-                               entry = entry->next;
-                       } while(--skip && entry);
-                       ++entries;
-                       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 */
-
+       /*
+        * 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;
@@ -243,24 +264,24 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
        index->src_size = bufsize;
        index->hash_mask = hmask;
 
-       mem = index + 1;
+       mem = index->hash;
        packed_hash = mem;
        mem = packed_hash + (hsize+1);
        packed_entry = mem;
 
-       /* Coalesce all entries belonging to one linked list into
-        * consecutive array entries */
-
        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 */
-
+       /* 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);