diffcore-delta.c

   1 #include "cache.h"
   2 #include "diff.h"
   3 #include "diffcore.h"
   4
   5 struct linehash {
   6         unsigned long bytes;
   7         unsigned long hash;
   8 };
   9
  10 static unsigned long hash_extended_line(const unsigned char **buf_p,
  11                                         unsigned long left)
  12 {
  13         /* An extended line is zero or more whitespace letters (including LF)
  14          * followed by one non whitespace letter followed by zero or more
  15          * non LF, and terminated with by a LF (or EOF).
  16          */
  17         const unsigned char *bol = *buf_p;
  18         const unsigned char *buf = bol;
  19         unsigned long hashval = 0;
  20         while (left) {
  21                 unsigned c = *buf++;
  22                 if (!c)
  23                         goto binary;
  24                 left--;
  25                 if (' ' < c) {
  26                         hashval = c;
  27                         break;
  28                 }
  29         }
  30         while (left) {
  31                 unsigned c = *buf++;
  32                 if (!c)
  33                         goto binary;
  34                 left--;
  35                 if (c == '\n')
  36                         break;
  37                 if (' ' < c)
  38                         hashval = hashval * 11 + c;
  39         }
  40         *buf_p = buf;
  41         return hashval;
  42
  43  binary:
  44         *buf_p = NULL;
  45         return 0;
  46 }
  47
  48 static int linehash_compare(const void *a_, const void *b_)
  49 {
  50         struct linehash *a = (struct linehash *) a_;
  51         struct linehash *b = (struct linehash *) b_;
  52         if (a->hash < b->hash) return -1;
  53         if (a->hash > b->hash) return 1;
  54         return 0;
  55 }
  56
  57 static struct linehash *hash_lines(const unsigned char *buf,
  58                                    unsigned long size)
  59 {
  60         const unsigned char *eobuf = buf + size;
  61         struct linehash *line = NULL;
  62         int alloc = 0, used = 0;
  63
  64         while (buf < eobuf) {
  65                 const unsigned char *ptr = buf;
  66                 unsigned long hash = hash_extended_line(&buf, eobuf-ptr);
  67                 if (!buf) {
  68                         free(line);
  69                         return NULL;
  70                 }
  71                 if (alloc <= used) {
  72                         alloc = alloc_nr(alloc);
  73                         line = xrealloc(line, sizeof(*line) * alloc);
  74                 }
  75                 line[used].bytes = buf - ptr;
  76                 line[used].hash = hash;
  77                 used++;
  78         }
  79         qsort(line, used, sizeof(*line), linehash_compare);
  80
  81         /* Terminate the list */
  82         if (alloc <= used)
  83                 line = xrealloc(line, sizeof(*line) * (used+1));
  84         line[used].bytes = line[used].hash = 0;
  85         return line;
  86 }
  87
  88 int diffcore_count_changes(void *src, unsigned long src_size,
  89                            void *dst, unsigned long dst_size,
  90                            unsigned long delta_limit,
  91                            unsigned long *src_copied,
  92                            unsigned long *literal_added)
  93 {
  94         struct linehash *src_lines, *dst_lines;
  95         unsigned long sc, la;
  96
  97         src_lines = hash_lines(src, src_size);
  98         if (!src_lines)
  99                 return -1;
 100         dst_lines = hash_lines(dst, dst_size);
 101         if (!dst_lines) {
 102                 free(src_lines);
 103                 return -1;
 104         }
 105         sc = la = 0;
 106         while (src_lines->bytes && dst_lines->bytes) {
 107                 int cmp = linehash_compare(src_lines, dst_lines);
 108                 if (!cmp) {
 109                         sc += src_lines->bytes;
 110                         src_lines++;
 111                         dst_lines++;
 112                         continue;
 113                 }
 114                 if (cmp < 0) {
 115                         src_lines++;
 116                         continue;
 117                 }
 118                 la += dst_lines->bytes;
 119                 dst_lines++;
 120         }
 121         while (dst_lines->bytes) {
 122                 la += dst_lines->bytes;
 123                 dst_lines++;
 124         }
 125         *src_copied = sc;
 126         *literal_added = la;
 127         return 0;
 128 }