view mercurial/mpatch.c @ 1187:120aa5fc7ced

From mercurial-bounces@selenic.com Thu Sep 1 07:01:32 2005 Return-Path: <mercurial-bounces@selenic.com> X-Original-To: bos@serpentine.com Delivered-To: bos@serpentine.com Received: from waste.org (waste.org [216.27.176.166]) by demesne.serpentine.com (Postfix) with ESMTP id 3616A20B571 for <bos@serpentine.com>; Thu, 1 Sep 2005 07:01:32 -0700 (PDT) Received: from waste.org (localhost [127.0.0.1]) by waste.org (8.13.4/8.13.4/Debian-3) with ESMTP id j81DxodQ028829; Thu, 1 Sep 2005 08:59:51 -0500 Received: from web32904.mail.mud.yahoo.com (web32904.mail.mud.yahoo.com [68.142.206.51]) by waste.org (8.13.4/8.13.4/Debian-3) with SMTP id j81DxnNA028824 for <mercurial@selenic.com>; Thu, 1 Sep 2005 08:59:49 -0500 Received: (qmail 25859 invoked by uid 60001); 1 Sep 2005 13:59:17 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:Received:Date:From:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=O6sELrlCknW3M/gKVqijWs82e/CbDEum1sEitcuLKXaP9dHU175PszOqMgcSKykMY+BVXtcH3NeaXLM3FyBmqNkoPAvesezyFbgQsHSM1S028oOexybCKMvtGQJmz66hzd1fDb0QoPj1gCcGU2VDevQaOesSmo1xF9jJwy2LlLE= ; Message-ID: <20050901135917.25856.qmail@web32904.mail.mud.yahoo.com> Received: from [60.48.222.94] by web32904.mail.mud.yahoo.com via HTTP; Thu, 01 Sep 2005 06:59:17 PDT Date: Thu, 1 Sep 2005 06:59:17 -0700 (PDT) From: TK Soh <teekaysoh@yahoo.com> To: mercurial@selenic.com In-Reply-To: <20050828075808.GO27787@waste.org> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 X-Virus-Scanned: by amavisd-new Subject: Re: add -p to hg tip X-BeenThere: mercurial@selenic.com X-Mailman-Version: 2.1.5 Precedence: list List-Id: mercurial.selenic.com List-Unsubscribe: <http://selenic.com/mailman/listinfo/mercurial>, <mailto:mercurial-request@selenic.com?subject=unsubscribe> List-Archive: <http://www.selenic.com/pipermail/mercurial> List-Post: <mailto:mercurial@selenic.com> List-Help: <mailto:mercurial-request@selenic.com?subject=help> List-Subscribe: <http://selenic.com/mailman/listinfo/mercurial>, <mailto:mercurial-request@selenic.com?subject=subscribe> Sender: mercurial-bounces@selenic.com Errors-To: mercurial-bounces@selenic.com X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on demesne.serpentine.com X-Spam-Level: X-Spam-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.4 X-Evolution-Source: imap://bos@www.serpentine.com/ Content-Transfer-Encoding: 8bit
author bos@serpentine.internal.keyresearch.com
date Thu, 01 Sep 2005 07:47:26 -0700
parents e530637ea060
children 681c5c211b92
line wrap: on
line source

/*
 mpatch.c - efficient binary patching for Mercurial

 This implements a patch algorithm that's O(m + nlog n) where m is the
 size of the output and n is the number of patches.

 Given a list of binary patches, it unpacks each into a hunk list,
 then combines the hunk lists with a treewise recursion to form a
 single hunk list. This hunk list is then applied to the original
 text.

 The text (or binary) fragments are copied directly from their source
 Python objects into a preallocated output string to avoid the
 allocation of intermediate Python objects. Working memory is about 2x
 the total number of hunks.

 Copyright 2005 Matt Mackall <mpm@selenic.com>

 This software may be used and distributed according to the terms
 of the GNU General Public License, incorporated herein by reference.
*/

#include <Python.h>
#include <stdlib.h>
#include <string.h>
#ifdef _WIN32
#ifdef _MSC_VER
#define inline __inline
typedef unsigned long uint32_t;
#else
#include <stdint.h>
#endif
static uint32_t ntohl(uint32_t x)
{
	return ((x & 0x000000ffUL) << 24) |
		((x & 0x0000ff00UL) <<  8) |
		((x & 0x00ff0000UL) >>  8) |
		((x & 0xff000000UL) >> 24);
}
#else
#include <sys/types.h>
#include <arpa/inet.h>
#endif

static char mpatch_doc[] = "Efficient binary patching.";

struct frag {
	int start, end, len;
	char *data;
};

struct flist {
	struct frag *base, *head, *tail;
};

static struct flist *lalloc(int size)
{
	struct flist *a = NULL;

	a = malloc(sizeof(struct flist));
	if (a) {
		a->base = malloc(sizeof(struct frag) * size);
		if (!a->base) {
			free(a);
			a = NULL;
		} else
			a->head = a->tail = a->base;
	}
	return a;
}

static void lfree(struct flist *a)
{
	if (a) {
		free(a->base);
		free(a);
	}
}

static int lsize(struct flist *a)
{
	return a->tail - a->head;
}

/* move hunks in source that are less cut to dest, compensating
   for changes in offset. the last hunk may be split if necessary.
*/
static int gather(struct flist *dest, struct flist *src, int cut, int offset)
{
	struct frag *d = dest->tail, *s = src->head;
	int postend, c, l;

	while (s != src->tail) {
		if (s->start + offset >= cut)
			break; /* we've gone far enough */

		postend = offset + s->start + s->len;
		if (postend <= cut) {
			/* save this hunk */
			offset += s->start + s->len - s->end;
			*d++ = *s++;
		}
		else {
			/* break up this hunk */
			c = cut - offset;
			if (s->end < c)
				c = s->end;
			l = cut - offset - s->start;
			if (s->len < l)
				l = s->len;

			offset += s->start + l - c;

			d->start = s->start;
			d->end = c;
			d->len = l;
			d->data = s->data;
			d++;
			s->start = c;
			s->len = s->len - l;
			s->data = s->data + l;

			break;
		}
	}

	dest->tail = d;
	src->head = s;
	return offset;
}

/* like gather, but with no output list */
static int discard(struct flist *src, int cut, int offset)
{
	struct frag *s = src->head;
	int postend, c, l;

	while (s != src->tail) {
		if (s->start + offset >= cut)
			break;

		postend = offset + s->start + s->len;
		if (postend <= cut) {
			offset += s->start + s->len - s->end;
			s++;
		}
		else {
			c = cut - offset;
			if (s->end < c)
				c = s->end;
			l = cut - offset - s->start;
			if (s->len < l)
				l = s->len;

			offset += s->start + l - c;
			s->start = c;
			s->len = s->len - l;
			s->data = s->data + l;

			break;
		}
	}

	src->head = s;
	return offset;
}

/* combine hunk lists a and b, while adjusting b for offset changes in a/
   this deletes a and b and returns the resultant list. */
static struct flist *combine(struct flist *a, struct flist *b)
{
	struct flist *c = NULL;
	struct frag *bh, *ct;
	int offset = 0, post;

	if (a && b)
		c = lalloc((lsize(a) + lsize(b)) * 2);

	if (c) {

		for (bh = b->head; bh != b->tail; bh++) {
			/* save old hunks */
			offset = gather(c, a, bh->start, offset);

			/* discard replaced hunks */
			post = discard(a, bh->end, offset);

			/* insert new hunk */
			ct = c->tail;
			ct->start = bh->start - offset;
			ct->end = bh->end - post;
			ct->len = bh->len;
			ct->data = bh->data;
			c->tail++;
			offset = post;
		}

		/* hold on to tail from a */
		memcpy(c->tail, a->head, sizeof(struct frag) * lsize(a));
		c->tail += lsize(a);
	}

	lfree(a);
	lfree(b);
	return c;
}

/* decode a binary patch into a hunk list */
static struct flist *decode(char *bin, int len)
{
	struct flist *l;
	struct frag *lt;
	char *end = bin + len;
	char decode[12]; /* for dealing with alignment issues */

	/* assume worst case size, we won't have many of these lists */
	l = lalloc(len / 12);
	lt = l->tail;

	while (bin < end) {
		memcpy(decode, bin, 12);
		lt->start = ntohl(*(uint32_t *)decode);
		lt->end = ntohl(*(uint32_t *)(decode + 4));
		lt->len = ntohl(*(uint32_t *)(decode + 8));
		lt->data = bin + 12;
		bin += 12 + lt->len;
		lt++;
	}

	l->tail = lt;
	return l;
}

/* calculate the size of resultant text */
static int calcsize(int len, struct flist *l)
{
	int outlen = 0, last = 0;
	struct frag *f = l->head;

	while (f != l->tail) {
		outlen += f->start - last;
		last = f->end;
		outlen += f->len;
		f++;
	}

	outlen += len - last;
	return outlen;
}

static void apply(char *buf, char *orig, int len, struct flist *l)
{
	struct frag *f = l->head;
	int last = 0;
	char *p = buf;

	while (f != l->tail) {
		memcpy(p, orig + last, f->start - last);
		p += f->start - last;
		memcpy(p, f->data, f->len);
		last = f->end;
		p += f->len;
		f++;
	}
	memcpy(p, orig + last, len - last);
}

/* recursively generate a patch of all bins between start and end */
static struct flist *fold(PyObject *bins, int start, int end)
{
	int len;

	if (start + 1 == end) {
		/* trivial case, output a decoded list */
		PyObject *tmp = PyList_GetItem(bins, start);
		if (!tmp)
			return NULL;
		return decode(PyString_AsString(tmp), PyString_Size(tmp));
	}

	/* divide and conquer, memory management is elsewhere */
	len = (end - start) / 2;
	return combine(fold(bins, start, start + len),
		       fold(bins, start + len, end));
}

static PyObject *
patches(PyObject *self, PyObject *args)
{
	PyObject *text, *bins, *result;
	struct flist *patch;
	char *in, *out;
	int len, outlen;

	if (!PyArg_ParseTuple(args, "SO:mpatch", &text, &bins))
		return NULL;

	len = PyList_Size(bins);
	if (!len) {
		/* nothing to do */
		Py_INCREF(text);
		return text;
	}

	patch = fold(bins, 0, len);
	if (!patch)
		return PyErr_NoMemory();

	outlen = calcsize(PyString_Size(text), patch);
	result = PyString_FromStringAndSize(NULL, outlen);
	if (result) {
		in = PyString_AsString(text);
		out = PyString_AsString(result);
		apply(out, in, PyString_Size(text), patch);
	}

	lfree(patch);
	return result;
}

static PyMethodDef methods[] = {
	{"patches", patches, METH_VARARGS, "apply a series of patches\n"},
	{NULL, NULL}
};

PyMODINIT_FUNC
initmpatch(void)
{
	Py_InitModule3("mpatch", methods, mpatch_doc);
}