[git/git.git] / xdiff / xutils.c

/*
 *  LibXDiff by Davide Libenzi ( File Differential Library )
 *  Copyright (C) 2003	Davide Libenzi
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  Davide Libenzi <davidel@xmailserver.org>
 *
 */

#include "xinclude.h"


#define XDL_GUESS_NLINES 256


long xdl_bogosqrt(long n) {
	long i;

	/*
	 * Classical integer square root approximation using shifts.
	 */
	for (i = 1; n > 0; n >>= 2)
		i <<= 1;

	return i;
}


int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
		     xdemitcb_t *ecb) {
	int i = 2;
	mmbuffer_t mb[3];

	mb[0].ptr = (char *) pre;
	mb[0].size = psize;
	mb[1].ptr = (char *) rec;
	mb[1].size = size;
	if (size > 0 && rec[size - 1] != '\n') {
		mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
		mb[2].size = strlen(mb[2].ptr);
		i++;
	}
	if (ecb->outf(ecb->priv, mb, i) < 0) {

		return -1;
	}

	return 0;
}

void *xdl_mmfile_first(mmfile_t *mmf, long *size)
{
	*size = mmf->size;
	return mmf->ptr;
}


void *xdl_mmfile_next(mmfile_t *mmf, long *size)
{
	return NULL;
}


long xdl_mmfile_size(mmfile_t *mmf)
{
	return mmf->size;
}


int xdl_cha_init(chastore_t *cha, long isize, long icount) {

	cha->head = cha->tail = NULL;
	cha->isize = isize;
	cha->nsize = icount * isize;
	cha->ancur = cha->sncur = NULL;
	cha->scurr = 0;

	return 0;
}


void xdl_cha_free(chastore_t *cha) {
	chanode_t *cur, *tmp;

	for (cur = cha->head; (tmp = cur) != NULL;) {
		cur = cur->next;
		xdl_free(tmp);
	}
}


void *xdl_cha_alloc(chastore_t *cha) {
	chanode_t *ancur;
	void *data;

	if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
		if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {

			return NULL;
		}
		ancur->icurr = 0;
		ancur->next = NULL;
		if (cha->tail)
			cha->tail->next = ancur;
		if (!cha->head)
			cha->head = ancur;
		cha->tail = ancur;
		cha->ancur = ancur;
	}

	data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
	ancur->icurr += cha->isize;

	return data;
}


void *xdl_cha_first(chastore_t *cha) {
	chanode_t *sncur;

	if (!(cha->sncur = sncur = cha->head))
		return NULL;

	cha->scurr = 0;

	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
}


void *xdl_cha_next(chastore_t *cha) {
	chanode_t *sncur;

	if (!(sncur = cha->sncur))
		return NULL;
	cha->scurr += cha->isize;
	if (cha->scurr == sncur->icurr) {
		if (!(sncur = cha->sncur = sncur->next))
			return NULL;
		cha->scurr = 0;
	}

	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
}


long xdl_guess_lines(mmfile_t *mf) {
	long nl = 0, size, tsize = 0;
	char const *data, *cur, *top;

	if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
		for (top = data + size; nl < XDL_GUESS_NLINES;) {
			if (cur >= top) {
				tsize += (long) (cur - data);
				if (!(cur = data = xdl_mmfile_next(mf, &size)))
					break;
				top = data + size;
			}
			nl++;
			if (!(cur = memchr(cur, '\n', top - cur)))
				cur = top;
			else
				cur++;
		}
		tsize += (long) (cur - data);
	}

	if (nl && tsize)
		nl = xdl_mmfile_size(mf) / (tsize / nl);

	return nl + 1;
}

int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
{
	int i1, i2;

	if (flags & XDF_IGNORE_WHITESPACE) {
		for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
			if (isspace(l1[i1]))
				while (isspace(l1[i1]) && i1 < s1)
					i1++;
			else if (isspace(l2[i2]))
				while (isspace(l2[i2]) && i2 < s2)
					i2++;
			else if (l1[i1] != l2[i2])
				return l2[i2] - l1[i1];
		}
		if (i1 >= s1)
			return 1;
		else if (i2 >= s2)
			return -1;
	} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
		for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
			if (isspace(l1[i1])) {
				if (!isspace(l2[i2]))
					return -1;
				while (isspace(l1[i1]) && i1 < s1)
					i1++;
				while (isspace(l2[i2]) && i2 < s2)
					i2++;
			} else if (l1[i1] != l2[i2])
				return l2[i2] - l1[i1];
		}
		if (i1 >= s1)
			return 1;
		else if (i2 >= s2)
			return -1;
	} else
		return s1 == s2 && !memcmp(l1, l2, s1);

	return 0;
}

unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
	unsigned long ha = 5381;
	char const *ptr = *data;

	for (; ptr < top && *ptr != '\n'; ptr++) {
		if (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {
			while (ptr < top && isspace(*ptr) && ptr[1] != '\n')
				ptr++;
			if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
				ha += (ha << 5);
				ha ^= (unsigned long) ' ';
			}
			continue;
		}
		ha += (ha << 5);
		ha ^= (unsigned long) *ptr;
	}
	*data = ptr < top ? ptr + 1: ptr;

	return ha;
}


unsigned int xdl_hashbits(unsigned int size) {
	unsigned int val = 1, bits = 0;

	for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
	return bits ? bits: 1;
}


int xdl_num_out(char *out, long val) {
	char *ptr, *str = out;
	char buf[32];

	ptr = buf + sizeof(buf) - 1;
	*ptr = '\0';
	if (val < 0) {
		*--ptr = '-';
		val = -val;
	}
	for (; val && ptr > buf; val /= 10)
		*--ptr = "0123456789"[val % 10];
	if (*ptr)
		for (; *ptr; ptr++, str++)
			*str = *ptr;
	else
		*str++ = '0';
	*str = '\0';

	return str - out;
}


long xdl_atol(char const *str, char const **next) {
	long val, base;
	char const *top;

	for (top = str; XDL_ISDIGIT(*top); top++);
	if (next)
		*next = top;
	for (val = 0, base = 1, top--; top >= str; top--, base *= 10)
		val += base * (long)(*top - '0');
	return val;
}


int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
		      const char *func, long funclen, xdemitcb_t *ecb) {
	int nb = 0;
	mmbuffer_t mb;
	char buf[128];

	memcpy(buf, "@@ -", 4);
	nb += 4;

	nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);

	if (c1 != 1) {
		memcpy(buf + nb, ",", 1);
		nb += 1;

		nb += xdl_num_out(buf + nb, c1);
	}

	memcpy(buf + nb, " +", 2);
	nb += 2;

	nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);

	if (c2 != 1) {
		memcpy(buf + nb, ",", 1);
		nb += 1;

		nb += xdl_num_out(buf + nb, c2);
	}

	memcpy(buf + nb, " @@", 3);
	nb += 3;
	if (func && funclen) {
		buf[nb++] = ' ';
		if (funclen > sizeof(buf) - nb - 1)
			funclen = sizeof(buf) - nb - 1;
		memcpy(buf + nb, func, funclen);
		nb += funclen;
	}
	buf[nb++] = '\n';

	mb.ptr = buf;
	mb.size = nb;
	if (ecb->outf(ecb->priv, &mb, 1) < 0)
		return -1;

	return 0;
}
Commit	Line	Data
3443546f LT	1	/*
	2	* LibXDiff by Davide Libenzi ( File Differential Library )
	3	* Copyright (C) 2003 Davide Libenzi
	4	*
	5	* This library is free software; you can redistribute it and/or
	6	* modify it under the terms of the GNU Lesser General Public
	7	* License as published by the Free Software Foundation; either
	8	* version 2.1 of the License, or (at your option) any later version.
	9	*
	10	* This library is distributed in the hope that it will be useful,
	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	* Lesser General Public License for more details.
	14	*
	15	* You should have received a copy of the GNU Lesser General Public
	16	* License along with this library; if not, write to the Free Software
	17	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	18	*
	19	* Davide Libenzi <davidel@xmailserver.org>
	20	*
	21	*/
	22
	23	#include "xinclude.h"
	24
	25
	26
	27	#define XDL_GUESS_NLINES 256
	28
	29
	30
	31
ca557aff DL	32	long xdl_bogosqrt(long n) {
	33	long i;
	34
	35	/*
	36	* Classical integer square root approximation using shifts.
	37	*/
	38	for (i = 1; n > 0; n >>= 2)
	39	i <<= 1;
	40
	41	return i;
	42	}
	43
	44
3443546f LT	45	int xdl_emit_diffrec(char const rec, long size, char const pre, long psize,
3443546f LT	46	xdemitcb_t *ecb) {
d281786f	47	int i = 2;
621c53cc	48	mmbuffer_t mb[3];
3443546f LT	49
	50	mb[0].ptr = (char *) pre;
	51	mb[0].size = psize;
	52	mb[1].ptr = (char *) rec;
	53	mb[1].size = size;
d281786f JH	54	if (size > 0 && rec[size - 1] != '\n') {
d281786f JH	55	mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
621c53cc	56	mb[2].size = strlen(mb[2].ptr);
d281786f	57	i++;
621c53cc	58	}
621c53cc	59	if (ecb->outf(ecb->priv, mb, i) < 0) {
3443546f LT	60
	61	return -1;
	62	}
	63
	64	return 0;
	65	}
	66
	67	void xdl_mmfile_first(mmfile_t mmf, long *size)
	68	{
	69	*size = mmf->size;
	70	return mmf->ptr;
	71	}
	72
	73
	74	void xdl_mmfile_next(mmfile_t mmf, long *size)
	75	{
	76	return NULL;
	77	}
	78
	79
	80	long xdl_mmfile_size(mmfile_t *mmf)
	81	{
	82	return mmf->size;
	83	}
	84
	85
	86	int xdl_cha_init(chastore_t *cha, long isize, long icount) {
	87
	88	cha->head = cha->tail = NULL;
	89	cha->isize = isize;
	90	cha->nsize = icount * isize;
	91	cha->ancur = cha->sncur = NULL;
	92	cha->scurr = 0;
	93
	94	return 0;
	95	}
	96
	97
	98	void xdl_cha_free(chastore_t *cha) {
	99	chanode_t cur, tmp;
	100
	101	for (cur = cha->head; (tmp = cur) != NULL;) {
	102	cur = cur->next;
	103	xdl_free(tmp);
	104	}
	105	}
	106
	107
	108	void xdl_cha_alloc(chastore_t cha) {
	109	chanode_t *ancur;
	110	void *data;
	111
	112	if (!(ancur = cha->ancur) \|\| ancur->icurr == cha->nsize) {
	113	if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
	114
	115	return NULL;
	116	}
	117	ancur->icurr = 0;
	118	ancur->next = NULL;
	119	if (cha->tail)
	120	cha->tail->next = ancur;
	121	if (!cha->head)
	122	cha->head = ancur;
	123	cha->tail = ancur;
124	cha->ancur = ancur;
125	}
126
127	data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
128	ancur->icurr += cha->isize;
129
130	return data;
131	}
132
133
134	void xdl_cha_first(chastore_t cha) {
135	chanode_t *sncur;
136
137	if (!(cha->sncur = sncur = cha->head))
138	return NULL;
139
140	cha->scurr = 0;
141
142	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
143	}
144
145
146	void xdl_cha_next(chastore_t cha) {
147	chanode_t *sncur;
148
149	if (!(sncur = cha->sncur))
150	return NULL;
151	cha->scurr += cha->isize;
152	if (cha->scurr == sncur->icurr) {
153	if (!(sncur = cha->sncur = sncur->next))
154	return NULL;
155	cha->scurr = 0;
156	}
157
158	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
159	}
160
161
162	long xdl_guess_lines(mmfile_t *mf) {
163	long nl = 0, size, tsize = 0;
164	char const data, cur, *top;
165
166	if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
167	for (top = data + size; nl < XDL_GUESS_NLINES;) {
168	if (cur >= top) {
169	tsize += (long) (cur - data);
170	if (!(cur = data = xdl_mmfile_next(mf, &size)))
171	break;
172	top = data + size;
173	}
174	nl++;
175	if (!(cur = memchr(cur, '\n', top - cur)))
176	cur = top;
177	else
178	cur++;
179	}
180	tsize += (long) (cur - data);
181	}
182
183	if (nl && tsize)
184	nl = xdl_mmfile_size(mf) / (tsize / nl);
185
186	return nl + 1;
187	}
188
0d21efa5 JS	189	int xdl_recmatch(const char l1, long s1, const char l2, long s2, long flags)
	190	{
	191	int i1, i2;
	192
	193	if (flags & XDF_IGNORE_WHITESPACE) {
	194	for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
	195	if (isspace(l1[i1]))
	196	while (isspace(l1[i1]) && i1 < s1)
	197	i1++;
	198	else if (isspace(l2[i2]))
	199	while (isspace(l2[i2]) && i2 < s2)
	200	i2++;
	201	else if (l1[i1] != l2[i2])
	202	return l2[i2] - l1[i1];
	203	}
	204	if (i1 >= s1)
	205	return 1;
	206	else if (i2 >= s2)
	207	return -1;
	208	} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
	209	for (i1 = i2 = 0; i1 < s1 && i2 < s2; i1++, i2++) {
	210	if (isspace(l1[i1])) {
	211	if (!isspace(l2[i2]))
	212	return -1;
	213	while (isspace(l1[i1]) && i1 < s1)
	214	i1++;
	215	while (isspace(l2[i2]) && i2 < s2)
	216	i2++;
	217	} else if (l1[i1] != l2[i2])
	218	return l2[i2] - l1[i1];
	219	}
	220	if (i1 >= s1)
	221	return 1;
	222	else if (i2 >= s2)
	223	return -1;
	224	} else
	225	return s1 == s2 && !memcmp(l1, l2, s1);
	226
	227	return 0;
	228	}
3443546f	229
0d21efa5	230	unsigned long xdl_hash_record(char const *data, char const top, long flags) {
3443546f LT	231	unsigned long ha = 5381;
	232	char const ptr = data;
	233
	234	for (; ptr < top && *ptr != '\n'; ptr++) {
0d21efa5 JS	235	if (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {
	236	while (ptr < top && isspace(*ptr) && ptr[1] != '\n')
	237	ptr++;
	238	if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
	239	ha += (ha << 5);
	240	ha ^= (unsigned long) ' ';
	241	}
	242	continue;
	243	}
3443546f LT	244	ha += (ha << 5);
	245	ha ^= (unsigned long) *ptr;
	246	}
	247	*data = ptr < top ? ptr + 1: ptr;
	248
	249	return ha;
	250	}
	251
	252
	253	unsigned int xdl_hashbits(unsigned int size) {
	254	unsigned int val = 1, bits = 0;
	255
	256	for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
	257	return bits ? bits: 1;
	258	}
	259
	260
	261	int xdl_num_out(char *out, long val) {
	262	char ptr, str = out;
	263	char buf[32];
	264
	265	ptr = buf + sizeof(buf) - 1;
	266	*ptr = '\0';
	267	if (val < 0) {
	268	*--ptr = '-';
	269	val = -val;
	270	}
	271	for (; val && ptr > buf; val /= 10)
	272	*--ptr = "0123456789"[val % 10];
	273	if (*ptr)
	274	for (; *ptr; ptr++, str++)
	275	str = ptr;
	276	else
	277	*str++ = '0';
	278	*str = '\0';
	279
	280	return str - out;
	281	}
	282
	283
	284	long xdl_atol(char const str, char const *next) {
	285	long val, base;
	286	char const *top;
	287
	288	for (top = str; XDL_ISDIGIT(*top); top++);
	289	if (next)
	290	*next = top;
	291	for (val = 0, base = 1, top--; top >= str; top--, base *= 10)
	292	val += base * (long)(*top - '0');
	293	return val;
	294	}
	295
	296
acb72577 MW	297	int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
acb72577 MW	298	const char func, long funclen, xdemitcb_t ecb) {
3443546f LT	299	int nb = 0;
	300	mmbuffer_t mb;
	301	char buf[128];
	302
	303	memcpy(buf, "@@ -", 4);
	304	nb += 4;
	305
ca557aff	306	nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
3443546f	307
3ce8f089 JH	308	if (c1 != 1) {
	309	memcpy(buf + nb, ",", 1);
	310	nb += 1;
3443546f	311
3ce8f089 JH	312	nb += xdl_num_out(buf + nb, c1);
3ce8f089 JH	313	}
3443546f LT	314
	315	memcpy(buf + nb, " +", 2);
	316	nb += 2;
	317
ca557aff	318	nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
3443546f	319
3ce8f089 JH	320	if (c2 != 1) {
	321	memcpy(buf + nb, ",", 1);
	322	nb += 1;
3443546f	323
3ce8f089 JH	324	nb += xdl_num_out(buf + nb, c2);
3ce8f089 JH	325	}
3443546f	326
acb72577 MW	327	memcpy(buf + nb, " @@", 3);
	328	nb += 3;
	329	if (func && funclen) {
	330	buf[nb++] = ' ';
	331	if (funclen > sizeof(buf) - nb - 1)
	332	funclen = sizeof(buf) - nb - 1;
	333	memcpy(buf + nb, func, funclen);
	334	nb += funclen;
	335	}
	336	buf[nb++] = '\n';
3443546f LT	337
	338	mb.ptr = buf;
	339	mb.size = nb;
	340	if (ecb->outf(ecb->priv, &mb, 1) < 0)
	341	return -1;
	342
	343	return 0;
	344	}
	345