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
xdl_bogosqrt(long n)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
xdl_emit_diffrec(char const * rec,long size,char const * pre,long psize,xdemitcb_t * ecb)45 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
46 xdemitcb_t *ecb) {
47 int i = 2;
48 mmbuffer_t mb[3];
49
50 mb[0].ptr = (char *) pre;
51 mb[0].size = psize;
52 mb[1].ptr = (char *) rec;
53 mb[1].size = size;
54 if (size > 0 && rec[size - 1] != '\n') {
55 mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
56 mb[2].size = strlen(mb[2].ptr);
57 i++;
58 }
59 if (ecb->outf(ecb->priv, mb, i) < 0) {
60
61 return -1;
62 }
63
64 return 0;
65 }
66
67
xdl_init_mmfile(mmfile_t * mmf,long bsize,unsigned long flags)68 int xdl_init_mmfile(mmfile_t *mmf, long bsize, unsigned long flags) {
69
70 mmf->flags = flags;
71 mmf->head = mmf->tail = NULL;
72 mmf->bsize = bsize;
73 mmf->fsize = 0;
74 mmf->rcur = mmf->wcur = NULL;
75 mmf->rpos = 0;
76
77 return 0;
78 }
79
80
xdl_free_mmfile(mmfile_t * mmf)81 void xdl_free_mmfile(mmfile_t *mmf) {
82 mmblock_t *cur, *tmp;
83
84 for (cur = mmf->head; (tmp = cur) != NULL;) {
85 cur = cur->next;
86 xdl_free(tmp);
87 }
88 }
89
90
xdl_mmfile_iscompact(mmfile_t * mmf)91 int xdl_mmfile_iscompact(mmfile_t *mmf) {
92
93 return mmf->head == mmf->tail;
94 }
95
96
xdl_seek_mmfile(mmfile_t * mmf,long off)97 int xdl_seek_mmfile(mmfile_t *mmf, long off) {
98 long bsize;
99
100 if (xdl_mmfile_first(mmf, &bsize)) {
101 do {
102 if (off < bsize) {
103 mmf->rpos = off;
104 return 0;
105 }
106 off -= bsize;
107 } while (xdl_mmfile_next(mmf, &bsize));
108 }
109
110 return -1;
111 }
112
113
xdl_read_mmfile(mmfile_t * mmf,void * data,long size)114 long xdl_read_mmfile(mmfile_t *mmf, void *data, long size) {
115 long rsize, csize;
116 char *ptr = data;
117 mmblock_t *rcur;
118
119 for (rsize = 0, rcur = mmf->rcur; rcur && rsize < size;) {
120 if (mmf->rpos >= rcur->size) {
121 if (!(mmf->rcur = rcur = rcur->next))
122 break;
123 mmf->rpos = 0;
124 }
125 csize = XDL_MIN(size - rsize, rcur->size - mmf->rpos);
126 memcpy(ptr, rcur->ptr + mmf->rpos, csize);
127 rsize += csize;
128 ptr += csize;
129 mmf->rpos += csize;
130 }
131
132 return rsize;
133 }
134
135
xdl_write_mmfile(mmfile_t * mmf,void const * data,long size)136 long xdl_write_mmfile(mmfile_t *mmf, void const *data, long size) {
137 long wsize, bsize, csize;
138 mmblock_t *wcur;
139
140 for (wsize = 0; wsize < size;) {
141 wcur = mmf->wcur;
142 if (wcur && (wcur->flags & XDL_MMB_READONLY))
143 return wsize;
144 if (!wcur || wcur->size == wcur->bsize ||
145 (mmf->flags & XDL_MMF_ATOMIC && wcur->size + size > wcur->bsize)) {
146 bsize = XDL_MAX(mmf->bsize, size);
147 if (!(wcur = (mmblock_t *) xdl_malloc(sizeof(mmblock_t) + bsize))) {
148
149 return wsize;
150 }
151 wcur->flags = 0;
152 wcur->ptr = (char *) wcur + sizeof(mmblock_t);
153 wcur->size = 0;
154 wcur->bsize = bsize;
155 wcur->next = NULL;
156 if (!mmf->head)
157 mmf->head = wcur;
158 if (mmf->tail)
159 mmf->tail->next = wcur;
160 mmf->tail = wcur;
161 mmf->wcur = wcur;
162 }
163 csize = XDL_MIN(size - wsize, wcur->bsize - wcur->size);
164 memcpy(wcur->ptr + wcur->size, (char const *) data + wsize, csize);
165 wsize += csize;
166 wcur->size += csize;
167 mmf->fsize += csize;
168 }
169
170 return size;
171 }
172
173
xdl_writem_mmfile(mmfile_t * mmf,mmbuffer_t * mb,int nbuf)174 long xdl_writem_mmfile(mmfile_t *mmf, mmbuffer_t *mb, int nbuf) {
175 int i;
176 long size;
177 char *data;
178
179 for (i = 0, size = 0; i < nbuf; i++)
180 size += mb[i].size;
181 if (!(data = (char *) xdl_mmfile_writeallocate(mmf, size)))
182 return -1;
183 for (i = 0; i < nbuf; i++) {
184 memcpy(data, mb[i].ptr, mb[i].size);
185 data += mb[i].size;
186 }
187
188 return size;
189 }
190
191
xdl_mmfile_writeallocate(mmfile_t * mmf,long size)192 void *xdl_mmfile_writeallocate(mmfile_t *mmf, long size) {
193 long bsize;
194 mmblock_t *wcur;
195 char *blk;
196
197 if (!(wcur = mmf->wcur) || wcur->size + size > wcur->bsize) {
198 bsize = XDL_MAX(mmf->bsize, size);
199 if (!(wcur = (mmblock_t *) xdl_malloc(sizeof(mmblock_t) + bsize))) {
200
201 return NULL;
202 }
203 wcur->flags = 0;
204 wcur->ptr = (char *) wcur + sizeof(mmblock_t);
205 wcur->size = 0;
206 wcur->bsize = bsize;
207 wcur->next = NULL;
208 if (!mmf->head)
209 mmf->head = wcur;
210 if (mmf->tail)
211 mmf->tail->next = wcur;
212 mmf->tail = wcur;
213 mmf->wcur = wcur;
214 }
215
216 blk = wcur->ptr + wcur->size;
217 wcur->size += size;
218 mmf->fsize += size;
219
220 return blk;
221 }
222
223
xdl_mmfile_ptradd(mmfile_t * mmf,char * ptr,long size,unsigned long flags)224 long xdl_mmfile_ptradd(mmfile_t *mmf, char *ptr, long size, unsigned long flags) {
225 mmblock_t *wcur;
226
227 if (!(wcur = (mmblock_t *) xdl_malloc(sizeof(mmblock_t)))) {
228
229 return -1;
230 }
231 wcur->flags = flags;
232 wcur->ptr = ptr;
233 wcur->size = wcur->bsize = size;
234 wcur->next = NULL;
235 if (!mmf->head)
236 mmf->head = wcur;
237 if (mmf->tail)
238 mmf->tail->next = wcur;
239 mmf->tail = wcur;
240 mmf->wcur = wcur;
241
242 mmf->fsize += size;
243
244 return size;
245 }
246
247
xdl_copy_mmfile(mmfile_t * mmf,long size,xdemitcb_t * ecb)248 long xdl_copy_mmfile(mmfile_t *mmf, long size, xdemitcb_t *ecb) {
249 long rsize, csize;
250 mmblock_t *rcur;
251 mmbuffer_t mb;
252
253 for (rsize = 0, rcur = mmf->rcur; rcur && rsize < size;) {
254 if (mmf->rpos >= rcur->size) {
255 if (!(mmf->rcur = rcur = rcur->next))
256 break;
257 mmf->rpos = 0;
258 }
259 csize = XDL_MIN(size - rsize, rcur->size - mmf->rpos);
260 mb.ptr = rcur->ptr + mmf->rpos;
261 mb.size = csize;
262 if (ecb->outf(ecb->priv, &mb, 1) < 0) {
263
264 return rsize;
265 }
266 rsize += csize;
267 mmf->rpos += csize;
268 }
269
270 return rsize;
271 }
272
273
xdl_mmfile_first(mmfile_t * mmf,long * size)274 void *xdl_mmfile_first(mmfile_t *mmf, long *size) {
275
276 if (!(mmf->rcur = mmf->head))
277 return NULL;
278
279 *size = mmf->rcur->size;
280
281 return mmf->rcur->ptr;
282 }
283
284
xdl_mmfile_next(mmfile_t * mmf,long * size)285 void *xdl_mmfile_next(mmfile_t *mmf, long *size) {
286
287 if (!mmf->rcur || !(mmf->rcur = mmf->rcur->next))
288 return NULL;
289
290 *size = mmf->rcur->size;
291
292 return mmf->rcur->ptr;
293 }
294
295
xdl_mmfile_size(mmfile_t * mmf)296 long xdl_mmfile_size(mmfile_t *mmf) {
297
298 return mmf->fsize;
299 }
300
301
xdl_mmfile_cmp(mmfile_t * mmf1,mmfile_t * mmf2)302 int xdl_mmfile_cmp(mmfile_t *mmf1, mmfile_t *mmf2) {
303 int cres;
304 long size, bsize1, bsize2, size1, size2;
305 char const *blk1, *cur1, *top1;
306 char const *blk2, *cur2, *top2;
307
308 if ((cur1 = blk1 = xdl_mmfile_first(mmf1, &bsize1)) != NULL)
309 top1 = blk1 + bsize1;
310 if ((cur2 = blk2 = xdl_mmfile_first(mmf2, &bsize2)) != NULL)
311 top2 = blk2 + bsize2;
312 if (!cur1) {
313 if (!cur2 || xdl_mmfile_size(mmf2) == 0)
314 return 0;
315 return -*cur2;
316 } else if (!cur2)
317 return xdl_mmfile_size(mmf1) ? *cur1: 0;
318 for (;;) {
319 if (cur1 >= top1) {
320 if ((cur1 = blk1 = xdl_mmfile_next(mmf1, &bsize1)) != NULL)
321 top1 = blk1 + bsize1;
322 }
323 if (cur2 >= top2) {
324 if ((cur2 = blk2 = xdl_mmfile_next(mmf2, &bsize2)) != NULL)
325 top2 = blk2 + bsize2;
326 }
327 if (!cur1) {
328 if (!cur2)
329 break;
330 return -*cur2;
331 } else if (!cur2)
332 return *cur1;
333 size1 = top1 - cur1;
334 size2 = top2 - cur2;
335 size = XDL_MIN(size1, size2);
336 if ((cres = memcmp(cur1, cur2, size)) != 0)
337 return cres;
338 cur1 += size;
339 cur2 += size;
340 }
341
342 return 0;
343 }
344
345
xdl_mmfile_compact(mmfile_t * mmfo,mmfile_t * mmfc,long bsize,unsigned long flags)346 int xdl_mmfile_compact(mmfile_t *mmfo, mmfile_t *mmfc, long bsize, unsigned long flags) {
347 long fsize = xdl_mmfile_size(mmfo), size;
348 char *data;
349 char const *blk;
350
351 if (xdl_init_mmfile(mmfc, bsize, flags) < 0) {
352
353 return -1;
354 }
355 if (!(data = (char *) xdl_mmfile_writeallocate(mmfc, fsize))) {
356
357 xdl_free_mmfile(mmfc);
358 return -1;
359 }
360 if ((blk = (char const *) xdl_mmfile_first(mmfo, &size)) != NULL) {
361 do {
362 memcpy(data, blk, size);
363 data += size;
364 } while ((blk = (char const *) xdl_mmfile_next(mmfo, &size)) != NULL);
365 }
366
367 return 0;
368 }
369
370
xdl_mmfile_outf(void * priv,mmbuffer_t * mb,int nbuf)371 int xdl_mmfile_outf(void *priv, mmbuffer_t *mb, int nbuf) {
372 mmfile_t *mmf = priv;
373
374 if (xdl_writem_mmfile(mmf, mb, nbuf) < 0) {
375
376 return -1;
377 }
378
379 return 0;
380 }
381
382
xdl_cha_init(chastore_t * cha,long isize,long icount)383 int xdl_cha_init(chastore_t *cha, long isize, long icount) {
384
385 cha->head = cha->tail = NULL;
386 cha->isize = isize;
387 cha->nsize = icount * isize;
388 cha->ancur = cha->sncur = NULL;
389 cha->scurr = 0;
390
391 return 0;
392 }
393
394
xdl_cha_free(chastore_t * cha)395 void xdl_cha_free(chastore_t *cha) {
396 chanode_t *cur, *tmp;
397
398 for (cur = cha->head; (tmp = cur) != NULL;) {
399 cur = cur->next;
400 xdl_free(tmp);
401 }
402 }
403
404
xdl_cha_alloc(chastore_t * cha)405 void *xdl_cha_alloc(chastore_t *cha) {
406 chanode_t *ancur;
407 void *data;
408
409 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
410 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
411
412 return NULL;
413 }
414 ancur->icurr = 0;
415 ancur->next = NULL;
416 if (cha->tail)
417 cha->tail->next = ancur;
418 if (!cha->head)
419 cha->head = ancur;
420 cha->tail = ancur;
421 cha->ancur = ancur;
422 }
423
424 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
425 ancur->icurr += cha->isize;
426
427 return data;
428 }
429
430
xdl_cha_first(chastore_t * cha)431 void *xdl_cha_first(chastore_t *cha) {
432 chanode_t *sncur;
433
434 if (!(cha->sncur = sncur = cha->head))
435 return NULL;
436
437 cha->scurr = 0;
438
439 return (char *) sncur + sizeof(chanode_t) + cha->scurr;
440 }
441
442
xdl_cha_next(chastore_t * cha)443 void *xdl_cha_next(chastore_t *cha) {
444 chanode_t *sncur;
445
446 if (!(sncur = cha->sncur))
447 return NULL;
448 cha->scurr += cha->isize;
449 if (cha->scurr == sncur->icurr) {
450 if (!(sncur = cha->sncur = sncur->next))
451 return NULL;
452 cha->scurr = 0;
453 }
454
455 return (char *) sncur + sizeof(chanode_t) + cha->scurr;
456 }
457
458
xdl_guess_lines(mmfile_t * mf)459 long xdl_guess_lines(mmfile_t *mf) {
460 long nl = 0, size, tsize = 0;
461 char const *data, *cur, *top;
462
463 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
464 for (top = data + size; nl < XDL_GUESS_NLINES;) {
465 if (cur >= top) {
466 tsize += (long) (cur - data);
467 if (!(cur = data = xdl_mmfile_next(mf, &size)))
468 break;
469 top = data + size;
470 }
471 nl++;
472 if (!(cur = memchr(cur, '\n', top - cur)))
473 cur = top;
474 else
475 cur++;
476 }
477 tsize += (long) (cur - data);
478 }
479
480 if (nl && tsize)
481 nl = xdl_mmfile_size(mf) / (tsize / nl);
482
483 return nl + 1;
484 }
485
486
xdl_hash_record(char const ** data,char const * top)487 unsigned long xdl_hash_record(char const **data, char const *top) {
488 unsigned long ha = 5381;
489 char const *ptr = *data;
490
491 for (; ptr < top && *ptr != '\n'; ptr++) {
492 ha += (ha << 5);
493 ha ^= (unsigned long) *ptr;
494 }
495 *data = ptr < top ? ptr + 1: ptr;
496
497 return ha;
498 }
499
500
xdl_hashbits(unsigned int size)501 unsigned int xdl_hashbits(unsigned int size) {
502 unsigned int val = 1, bits = 0;
503
504 for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
505 return bits ? bits: 1;
506 }
507
508
xdl_num_out(char * out,long val)509 int xdl_num_out(char *out, long val) {
510 char *ptr, *str = out;
511 char buf[32];
512
513 ptr = buf + sizeof(buf) - 1;
514 *ptr = '\0';
515 if (val < 0) {
516 *--ptr = '-';
517 val = -val;
518 }
519 for (; val && ptr > buf; val /= 10)
520 *--ptr = "0123456789"[val % 10];
521 if (*ptr)
522 for (; *ptr; ptr++, str++)
523 *str = *ptr;
524 else
525 *str++ = '0';
526 *str = '\0';
527
528 return str - out;
529 }
530
531
xdl_atol(char const * str,char const ** next)532 long xdl_atol(char const *str, char const **next) {
533 long val, base;
534 char const *top;
535
536 for (top = str; XDL_ISDIGIT(*top); top++);
537 if (next)
538 *next = top;
539 for (val = 0, base = 1, top--; top >= str; top--, base *= 10)
540 val += base * (long)(*top - '0');
541 return val;
542 }
543
544
xdl_emit_hunk_hdr(long s1,long c1,long s2,long c2,xdemitcb_t * ecb)545 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, xdemitcb_t *ecb) {
546 int nb = 0;
547 mmbuffer_t mb;
548 char buf[128];
549
550 memcpy(buf, "@@ -", 4);
551 nb += 4;
552
553 nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
554
555 memcpy(buf + nb, ",", 1);
556 nb += 1;
557
558 nb += xdl_num_out(buf + nb, c1);
559
560 memcpy(buf + nb, " +", 2);
561 nb += 2;
562
563 nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
564
565 memcpy(buf + nb, ",", 1);
566 nb += 1;
567
568 nb += xdl_num_out(buf + nb, c2);
569
570 memcpy(buf + nb, " @@\n", 4);
571 nb += 4;
572
573 mb.ptr = buf;
574 mb.size = nb;
575 if (ecb->outf(ecb->priv, &mb, 1) < 0)
576 return -1;
577
578 return 0;
579 }
580
581