Mercurial > hg > pyhgsh
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); }