mercurial/mpatch.c
author mpm@selenic.com
Fri, 20 May 2005 19:19:25 -0800
changeset 127 44538462d3c8
parent 82 7ed96baa7caa
child 128 d6afb6dbf9f2
permissions -rw-r--r--
Fix braindamaged import in mdiff.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     1
/*
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     2
 mpatch.c - efficient binary patching for Mercurial
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     3
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     4
 This implements a patch algorithm that's O(m + nlog n) where m is the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     5
 size of the output and n is the number of patches.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     6
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     7
 Given a list of binary patches, it unpacks each into a hunk list,
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     8
 then combines the hunk lists with a treewise recursion to form a
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     9
 single hunk list. This hunk list is then applied to the original
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    10
 text.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    11
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    12
 The text (or binary) fragments are copied directly from their source
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    13
 Python objects into a preallocated output string to avoid the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    14
 allocation of intermediate Python objects. Working memory is about 2x
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    15
 the total number of hunks.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    16
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    17
 Copyright 2005 Matt Mackall <mpm@selenic.com>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    18
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    19
 This software may be used and distributed according to the terms
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    20
 of the GNU General Public License, incorporated herein by reference.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    21
*/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    22
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    23
#include <Python.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    24
#include <stdlib.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    25
#include <string.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    26
#include <netinet/in.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    27
#include <sys/types.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    28
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    29
static char mpatch_doc[] = "Efficient binary patching.";
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    30
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    31
struct frag {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    32
	int start, end, len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    33
	char *data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    34
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    35
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    36
struct flist {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    37
	struct frag *base, *head, *tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    38
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    39
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    40
static struct flist *lalloc(int size)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    41
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    42
	struct flist *a;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    43
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    44
	a = malloc(sizeof(struct flist));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    45
	a->head = a->tail = a->base = malloc(sizeof(struct frag) * size);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    46
	return a;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    47
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    48
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    49
static void lfree(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    50
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    51
	free(a->base);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    52
	free(a);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    53
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    54
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    55
static int lsize(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    56
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    57
	return a->tail - a->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    58
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    59
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    60
/* move hunks in source that are less cut to dest, compensating
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    61
   for changes in offset. the last hunk may be split if necessary.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    62
*/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    63
static int gather(struct flist *dest, struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    64
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    65
	struct frag *d = dest->tail, *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    66
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    67
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    68
	while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    69
		if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
    70
			break; /* we've gone far enough */
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    71
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    72
		postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    73
		if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    74
			/* save this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    75
			offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    76
			*d++ = *s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    77
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    78
		else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    79
			/* break up this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    80
			c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    81
			if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    82
				c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    83
			l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    84
			if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    85
				l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    86
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    87
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    88
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    89
			d->start = s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    90
			d->end = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    91
			d->len = l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    92
			d->data = s->data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    93
			d++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    94
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    95
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    96
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    97
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
    98
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    99
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   100
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   101
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   102
	dest->tail = d;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   103
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   104
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   105
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   106
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   107
/* like gather, but with no output list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   108
static int discard(struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   109
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   110
	struct frag *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   111
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   112
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   113
	while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   114
		if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   115
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   116
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   117
		postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   118
		if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   119
			offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   120
			s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   121
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   122
		else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   123
			c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   124
			if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   125
				c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   126
			l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   127
			if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   128
				l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   129
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   130
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   131
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   132
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   133
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   134
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   135
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   136
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   137
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   138
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   139
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   140
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   141
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   142
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   143
/* combine hunk lists a and b, while adjusting b for offset changes in a/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   144
   this deletes a and b and returns the resultant list. */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   145
static struct flist *combine(struct flist *a, struct flist *b)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   146
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   147
	struct flist *c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   148
	struct frag *bh = b->head, *ct;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   149
	int offset = 0, post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   150
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   151
	c = lalloc((lsize(a) + lsize(b)) * 2);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   152
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   153
	while (bh != b->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   154
		/* save old hunks */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   155
		offset = gather(c, a, bh->start, offset);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   156
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   157
		/* discard replaced hunks */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   158
		post = discard(a, bh->end, offset);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   159
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   160
		/* insert new hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   161
		ct = c->tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   162
		ct->start = bh->start - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   163
		ct->end = bh->end - post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   164
		ct->len = bh->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   165
		ct->data = bh->data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   166
		c->tail++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   167
		bh++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   168
		offset = post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   169
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   170
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   171
	/* hold on to tail from a */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   172
	memcpy(c->tail, a->head, sizeof(struct frag) * lsize(a));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   173
	c->tail += lsize(a);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   174
	lfree(a);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   175
	lfree(b);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   176
	return c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   177
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   178
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   179
/* decode a binary patch into a hunk list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   180
static struct flist *decode(char *bin, int len)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   181
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   182
	struct flist *l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   183
	struct frag *lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   184
	char *end = bin + len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   185
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   186
	/* assume worst case size, we won't have many of these lists */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   187
	l = lalloc(len / 12);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   188
	lt = l->tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   189
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   190
	while (bin < end) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   191
		lt->start = ntohl(*(uint32_t *)bin);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   192
		lt->end = ntohl(*(uint32_t *)(bin + 4));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   193
		lt->len = ntohl(*(uint32_t *)(bin + 8));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   194
		lt->data = bin + 12;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   195
		bin += 12 + lt->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   196
		lt++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   197
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   198
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   199
	l->tail = lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   200
	return l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   201
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   202
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   203
/* calculate the size of resultant text */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   204
static int calcsize(int len, struct flist *l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   205
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   206
	int outlen = 0, last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   207
	struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   208
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   209
	while (f != l->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   210
		outlen += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   211
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   212
		outlen += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   213
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   214
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   215
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   216
	outlen += len - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   217
	return outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   218
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   219
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   220
static void apply(char *buf, char *orig, int len, struct flist *l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   221
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   222
	struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   223
	int last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   224
	char *p = buf;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   225
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   226
	while (f != l->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   227
		memcpy(p, orig + last, f->start - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   228
		p += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   229
		memcpy(p, f->data, f->len);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   230
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   231
		p += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   232
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   233
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   234
	memcpy(p, orig + last, len - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   235
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   236
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   237
/* recursively generate a patch of all bins between start and end */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   238
static struct flist *fold(PyObject *bins, int start, int end)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   239
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   240
	int len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   241
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   242
	if (start + 1 == end) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   243
		/* trivial case, output a decoded list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   244
		PyObject *tmp = PyList_GetItem(bins, start);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   245
		return decode(PyString_AsString(tmp), PyString_Size(tmp));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   246
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   247
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   248
	/* divide and conquer, memory management is elsewhere */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   249
	len = (end - start) / 2;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   250
	return combine(fold(bins, start, start + len),
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   251
		       fold(bins, start + len, end));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   252
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   253
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   254
static PyObject *
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   255
patches(PyObject *self, PyObject *args)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   256
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   257
	PyObject *text, *bins, *result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   258
	struct flist *patch;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   259
	char *in, *out;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   260
	int len, outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   261
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   262
	if (!PyArg_ParseTuple(args, "OO:mpatch", &text, &bins))
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   263
		return NULL;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   264
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   265
	len = PyList_Size(bins);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   266
	if (!len) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   267
		/* nothing to do */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   268
		Py_INCREF(text);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   269
		return text;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   270
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   271
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   272
	patch = fold(bins, 0, len);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   273
	outlen = calcsize(PyString_Size(text), patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   274
	result = PyString_FromStringAndSize(NULL, outlen);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   275
	in = PyString_AsString(text);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   276
	out = PyString_AsString(result);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   277
	apply(out, in, PyString_Size(text), patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   278
	lfree(patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   279
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   280
	return result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   281
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   282
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   283
static PyMethodDef methods[] = {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   284
	{"patches", patches, METH_VARARGS, "apply a series of patches\n"},
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   285
	{NULL, NULL}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   286
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   287
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   288
PyMODINIT_FUNC
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   289
initmpatch(void)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   290
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   291
	Py_InitModule3("mpatch", methods, mpatch_doc);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   292
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   293