0000: 2f 2a 0a 2a 2a 20 43 6f 70 79 72 69 67 68 74 20 /*.** Copyright
0010: 28 63 29 20 32 30 30 37 20 44 2e 20 52 69 63 68 (c) 2007 D. Rich
0020: 61 72 64 20 48 69 70 70 0a 2a 2a 0a 2a 2a 20 54 ard Hipp.**.** T
0030: 68 69 73 20 70 72 6f 67 72 61 6d 20 69 73 20 66 his program is f
0040: 72 65 65 20 73 6f 66 74 77 61 72 65 3b 20 79 6f ree software; yo
0050: 75 20 63 61 6e 20 72 65 64 69 73 74 72 69 62 75 u can redistribu
0060: 74 65 20 69 74 20 61 6e 64 2f 6f 72 0a 2a 2a 20 te it and/or.**
0070: 6d 6f 64 69 66 79 20 69 74 20 75 6e 64 65 72 20 modify it under
0080: 74 68 65 20 74 65 72 6d 73 20 6f 66 20 74 68 65 the terms of the
0090: 20 47 4e 55 20 47 65 6e 65 72 61 6c 20 50 75 62 GNU General Pub
00a0: 6c 69 63 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 76 lic.** License v
00b0: 65 72 73 69 6f 6e 20 32 20 61 73 20 70 75 62 6c ersion 2 as publ
00c0: 69 73 68 65 64 20 62 79 20 74 68 65 20 46 72 65 ished by the Fre
00d0: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
00e0: 61 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 ation..**.** Thi
00f0: 73 20 70 72 6f 67 72 61 6d 20 69 73 20 64 69 73 s program is dis
0100: 74 72 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 tributed in the
0110: 68 6f 70 65 20 74 68 61 74 20 69 74 20 77 69 6c hope that it wil
0120: 6c 20 62 65 20 75 73 65 66 75 6c 2c 0a 2a 2a 20 l be useful,.**
0130: 62 75 74 20 57 49 54 48 4f 55 54 20 41 4e 59 20 but WITHOUT ANY
0140: 57 41 52 52 41 4e 54 59 3b 20 77 69 74 68 6f 75 WARRANTY; withou
0150: 74 20 65 76 65 6e 20 74 68 65 20 69 6d 70 6c 69 t even the impli
0160: 65 64 20 77 61 72 72 61 6e 74 79 20 6f 66 0a 2a ed warranty of.*
0170: 2a 20 4d 45 52 43 48 41 4e 54 41 42 49 4c 49 54 * MERCHANTABILIT
0180: 59 20 6f 72 20 46 49 54 4e 45 53 53 20 46 4f 52 Y or FITNESS FOR
0190: 20 41 20 50 41 52 54 49 43 55 4c 41 52 20 50 55 A PARTICULAR PU
01a0: 52 50 4f 53 45 2e 20 20 53 65 65 20 74 68 65 20 RPOSE. See the
01b0: 47 4e 55 0a 2a 2a 20 47 65 6e 65 72 61 6c 20 50 GNU.** General P
01c0: 75 62 6c 69 63 20 4c 69 63 65 6e 73 65 20 66 6f ublic License fo
01d0: 72 20 6d 6f 72 65 20 64 65 74 61 69 6c 73 2e 0a r more details..
01e0: 2a 2a 20 0a 2a 2a 20 59 6f 75 20 73 68 6f 75 6c ** .** You shoul
01f0: 64 20 68 61 76 65 20 72 65 63 65 69 76 65 64 20 d have received
0200: 61 20 63 6f 70 79 20 6f 66 20 74 68 65 20 47 4e a copy of the GN
0210: 55 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 U General Public
0220: 0a 2a 2a 20 4c 69 63 65 6e 73 65 20 61 6c 6f 6e .** License alon
0230: 67 20 77 69 74 68 20 74 68 69 73 20 6c 69 62 72 g with this libr
0240: 61 72 79 3b 20 69 66 20 6e 6f 74 2c 20 77 72 69 ary; if not, wri
0250: 74 65 20 74 6f 20 74 68 65 0a 2a 2a 20 46 72 65 te to the.** Fre
0260: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 e Software Found
0270: 61 74 69 6f 6e 2c 20 49 6e 63 2e 2c 20 35 39 20 ation, Inc., 59
0280: 54 65 6d 70 6c 65 20 50 6c 61 63 65 20 2d 20 53 Temple Place - S
0290: 75 69 74 65 20 33 33 30 2c 0a 2a 2a 20 42 6f 73 uite 330,.** Bos
02a0: 74 6f 6e 2c 20 4d 41 20 20 30 32 31 31 31 2d 31 ton, MA 02111-1
02b0: 33 30 37 2c 20 55 53 41 2e 0a 2a 2a 0a 2a 2a 20 307, USA..**.**
02c0: 41 75 74 68 6f 72 20 63 6f 6e 74 61 63 74 20 69 Author contact i
02d0: 6e 66 6f 72 6d 61 74 69 6f 6e 3a 0a 2a 2a 20 20 nformation:.**
02e0: 20 64 72 68 40 68 77 61 63 69 2e 63 6f 6d 0a 2a drh@hwaci.com.*
02f0: 2a 20 20 20 68 74 74 70 3a 2f 2f 77 77 77 2e 68 * http://www.h
0300: 77 61 63 69 2e 63 6f 6d 2f 64 72 68 2f 0a 2a 2a waci.com/drh/.**
0310: 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a .***************
0320: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0330: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0340: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0350: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0360: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 6d 6f 64 75 .**.** This modu
0370: 6c 65 20 69 6d 70 6c 65 6d 65 6e 74 73 20 61 20 le implements a
0380: 33 2d 77 61 79 20 6d 65 72 67 65 0a 2a 2f 0a 23 3-way merge.*/.#
0390: 69 6e 63 6c 75 64 65 20 22 63 6f 6e 66 69 67 2e include "config.
03a0: 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 6d 65 72 h".#include "mer
03b0: 67 65 33 2e 68 22 0a 0a 23 69 66 20 31 0a 23 20 ge3.h"..#if 1.#
03c0: 64 65 66 69 6e 65 20 44 45 42 55 47 31 28 58 29 define DEBUG1(X)
03d0: 20 58 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 6e X.#else.# defin
03e0: 65 20 44 45 42 55 47 31 28 58 29 0a 23 65 6e 64 e DEBUG1(X).#end
03f0: 69 66 0a 23 69 66 20 30 0a 23 64 65 66 69 6e 65 if.#if 0.#define
0400: 20 44 45 42 55 47 32 28 58 29 20 58 0a 2f 2a 0a DEBUG2(X) X./*.
0410: 2a 2a 20 46 6f 72 20 64 65 62 75 67 67 69 6e 67 ** For debugging
0420: 3a 0a 2a 2a 20 50 72 69 6e 74 20 31 36 20 63 68 :.** Print 16 ch
0430: 61 72 61 63 74 65 72 73 20 6f 66 20 74 65 78 74 aracters of text
0440: 20 66 72 6f 6d 20 7a 42 75 66 0a 2a 2f 0a 73 74 from zBuf.*/.st
0450: 61 74 69 63 20 63 6f 6e 73 74 20 63 68 61 72 20 atic const char
0460: 2a 70 72 69 6e 74 31 36 28 63 6f 6e 73 74 20 63 *print16(const c
0470: 68 61 72 20 2a 7a 29 7b 0a 20 20 69 6e 74 20 69 har *z){. int i
0480: 3b 0a 20 20 73 74 61 74 69 63 20 63 68 61 72 20 ;. static char
0490: 7a 42 75 66 5b 32 30 5d 3b 0a 20 20 66 6f 72 28 zBuf[20];. for(
04a0: 69 3d 30 3b 20 69 3c 31 36 3b 20 69 2b 2b 29 7b i=0; i<16; i++){
04b0: 0a 20 20 20 20 69 66 28 20 7a 5b 69 5d 3e 3d 30 . if( z[i]>=0
04c0: 78 32 30 20 26 26 20 7a 5b 69 5d 3c 3d 30 78 37 x20 && z[i]<=0x7
04d0: 65 20 29 7b 0a 20 20 20 20 20 20 7a 42 75 66 5b e ){. zBuf[
04e0: 69 5d 20 3d 20 7a 5b 69 5d 3b 0a 20 20 20 20 7d i] = z[i];. }
04f0: 65 6c 73 65 7b 0a 20 20 20 20 20 20 7a 42 75 66 else{. zBuf
0500: 5b 69 5d 20 3d 20 27 2e 27 3b 0a 20 20 20 20 7d [i] = '.';. }
0510: 0a 20 20 7d 0a 20 20 7a 42 75 66 5b 69 5d 20 3d . }. zBuf[i] =
0520: 20 30 3b 0a 20 20 72 65 74 75 72 6e 20 7a 42 75 0;. return zBu
0530: 66 3b 0a 7d 0a 23 65 6c 73 65 0a 23 20 64 65 66 f;.}.#else.# def
0540: 69 6e 65 20 44 45 42 55 47 32 28 58 29 0a 23 65 ine DEBUG2(X).#e
0550: 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 4d 75 73 74 ndif../*.** Must
0560: 20 62 65 20 61 20 33 32 2d 62 69 74 20 69 6e 74 be a 32-bit int
0570: 65 67 65 72 0a 2a 2f 0a 74 79 70 65 64 65 66 20 eger.*/.typedef
0580: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 75 33 32 unsigned int u32
0590: 3b 0a 0a 2f 2a 0a 2a 2a 20 4d 75 73 74 20 62 65 ;../*.** Must be
05a0: 20 61 20 31 36 2d 62 69 74 20 76 61 6c 75 65 20 a 16-bit value
05b0: 0a 2a 2f 0a 74 79 70 65 64 65 66 20 75 6e 73 69 .*/.typedef unsi
05c0: 67 6e 65 64 20 73 68 6f 72 74 20 69 6e 74 20 75 gned short int u
05d0: 31 36 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 77 16;../*.** The w
05e0: 69 64 74 68 20 6f 66 20 61 20 68 61 73 68 20 77 idth of a hash w
05f0: 69 6e 64 6f 77 20 69 6e 20 62 79 74 65 73 2e 20 indow in bytes.
0600: 20 54 68 65 20 61 6c 67 6f 72 69 74 68 6d 20 6f The algorithm o
0610: 6e 6c 79 20 77 6f 72 6b 73 20 69 66 20 74 68 69 nly works if thi
0620: 73 0a 2a 2a 20 69 73 20 61 20 70 6f 77 65 72 20 s.** is a power
0630: 6f 66 20 32 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 of 2..*/.#define
0640: 20 4e 48 41 53 48 20 31 36 0a 0a 2f 2a 0a 2a 2a NHASH 16../*.**
0650: 20 54 68 65 20 63 75 72 72 65 6e 74 20 73 74 61 The current sta
0660: 74 65 20 6f 66 20 74 68 65 20 72 6f 6c 6c 69 6e te of the rollin
0670: 67 20 68 61 73 68 2e 0a 2a 2a 0a 2a 2a 20 7a 5b g hash..**.** z[
0680: 5d 20 68 6f 6c 64 73 20 74 68 65 20 76 61 6c 75 ] holds the valu
0690: 65 73 20 74 68 61 74 20 68 61 76 65 20 62 65 65 es that have bee
06a0: 6e 20 68 61 73 68 65 64 2e 20 20 7a 5b 5d 20 69 n hashed. z[] i
06b0: 73 20 61 20 63 69 72 63 75 6c 61 72 20 62 75 66 s a circular buf
06c0: 66 65 72 2e 0a 2a 2a 20 7a 5b 69 5d 20 69 73 20 fer..** z[i] is
06d0: 74 68 65 20 66 69 72 73 74 20 65 6e 74 72 79 20 the first entry
06e0: 61 6e 64 20 7a 5b 28 69 2b 4e 48 41 53 48 2d 31 and z[(i+NHASH-1
06f0: 29 25 4e 48 41 53 48 5d 20 69 73 20 74 68 65 20 )%NHASH] is the
0700: 6c 61 73 74 20 65 6e 74 72 79 20 6f 66 20 0a 2a last entry of .*
0710: 2a 20 74 68 65 20 77 69 6e 64 6f 77 2e 0a 2a 2a * the window..**
0720: 0a 2a 2a 20 48 61 73 68 2e 61 20 69 73 20 74 68 .** Hash.a is th
0730: 65 20 73 75 6d 20 6f 66 20 61 6c 6c 20 65 6c 65 e sum of all ele
0740: 6d 65 6e 74 73 20 6f 66 20 68 61 73 68 2e 7a 5b ments of hash.z[
0750: 5d 2e 20 20 48 61 73 68 2e 62 20 69 73 20 61 20 ]. Hash.b is a
0760: 77 65 69 67 68 74 65 64 0a 2a 2a 20 73 75 6d 2e weighted.** sum.
0770: 20 20 48 61 73 68 2e 62 20 69 73 20 7a 5b 69 5d Hash.b is z[i]
0780: 2a 4e 48 41 53 48 20 2b 20 7a 5b 69 2b 31 5d 2a *NHASH + z[i+1]*
0790: 28 4e 48 41 53 48 2d 31 29 20 2b 20 2e 2e 2e 20 (NHASH-1) + ...
07a0: 2b 20 7a 5b 69 2b 4e 48 41 53 48 2d 31 5d 2a 31 + z[i+NHASH-1]*1
07b0: 2e 0a 2a 2a 20 28 45 61 63 68 20 69 6e 64 65 78 ..** (Each index
07c0: 20 66 6f 72 20 7a 5b 5d 20 73 68 6f 75 6c 64 20 for z[] should
07d0: 62 65 20 6d 6f 64 75 6c 65 20 4e 48 41 53 48 2c be module NHASH,
07e0: 20 6f 66 20 63 6f 75 72 73 65 2e 20 20 54 68 65 of course. The
07f0: 20 25 4e 48 41 53 48 20 6f 70 65 72 61 74 6f 72 %NHASH operator
0800: 0a 2a 2a 20 69 73 20 6f 6d 69 74 74 65 64 20 69 .** is omitted i
0810: 6e 20 74 68 65 20 70 72 69 6f 72 20 65 78 70 72 n the prior expr
0820: 65 73 73 69 6f 6e 20 66 6f 72 20 62 72 65 76 69 ession for brevi
0830: 74 79 2e 29 0a 2a 2f 0a 74 79 70 65 64 65 66 20 ty.).*/.typedef
0840: 73 74 72 75 63 74 20 68 61 73 68 20 68 61 73 68 struct hash hash
0850: 3b 0a 73 74 72 75 63 74 20 68 61 73 68 20 7b 0a ;.struct hash {.
0860: 20 20 75 31 36 20 61 2c 20 62 3b 20 20 20 20 20 u16 a, b;
0870: 20 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 /* Hash valu
0880: 65 73 20 2a 2f 0a 20 20 75 31 36 20 69 3b 20 20 es */. u16 i;
0890: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 74 61 /* Sta
08a0: 72 74 20 6f 66 20 74 68 65 20 68 61 73 68 20 77 rt of the hash w
08b0: 69 6e 64 6f 77 20 2a 2f 0a 20 20 63 68 61 72 20 indow */. char
08c0: 7a 5b 4e 48 41 53 48 5d 3b 20 20 20 20 2f 2a 20 z[NHASH]; /*
08d0: 54 68 65 20 76 61 6c 75 65 73 20 74 68 61 74 20 The values that
08e0: 68 61 76 65 20 62 65 65 6e 20 68 61 73 68 65 64 have been hashed
08f0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 49 6e */.};../*.** In
0900: 69 74 69 61 6c 69 7a 65 20 74 68 65 20 72 6f 6c itialize the rol
0910: 6c 69 6e 67 20 68 61 73 68 20 75 73 69 6e 67 20 ling hash using
0920: 74 68 65 20 66 69 72 73 74 20 4e 48 41 53 48 20 the first NHASH
0930: 63 68 61 72 61 63 74 65 72 73 20 6f 66 20 7a 5b characters of z[
0940: 5d 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 ].*/.static void
0950: 20 68 61 73 68 5f 69 6e 69 74 28 68 61 73 68 20 hash_init(hash
0960: 2a 70 48 61 73 68 2c 20 63 6f 6e 73 74 20 63 68 *pHash, const ch
0970: 61 72 20 2a 7a 29 7b 0a 20 20 75 31 36 20 61 2c ar *z){. u16 a,
0980: 20 62 2c 20 69 3b 0a 20 20 61 20 3d 20 62 20 3d b, i;. a = b =
0990: 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 0;. for(i=0; i
09a0: 3c 4e 48 41 53 48 3b 20 69 2b 2b 29 7b 0a 20 20 <NHASH; i++){.
09b0: 20 20 61 20 2b 3d 20 7a 5b 69 5d 3b 0a 20 20 20 a += z[i];.
09c0: 20 62 20 2b 3d 20 28 4e 48 41 53 48 2d 69 29 2a b += (NHASH-i)*
09d0: 7a 5b 69 5d 3b 0a 20 20 20 20 70 48 61 73 68 2d z[i];. pHash-
09e0: 3e 7a 5b 69 5d 20 3d 20 7a 5b 69 5d 3b 0a 20 20 >z[i] = z[i];.
09f0: 7d 0a 20 20 70 48 61 73 68 2d 3e 61 20 3d 20 61 }. pHash->a = a
0a00: 20 26 20 30 78 66 66 66 66 3b 0a 20 20 70 48 61 & 0xffff;. pHa
0a10: 73 68 2d 3e 62 20 3d 20 62 20 26 20 30 78 66 66 sh->b = b & 0xff
0a20: 66 66 3b 0a 20 20 70 48 61 73 68 2d 3e 69 20 3d ff;. pHash->i =
0a30: 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76 0;.}../*.** Adv
0a40: 61 6e 63 65 20 74 68 65 20 72 6f 6c 6c 69 6e 67 ance the rolling
0a50: 20 68 61 73 68 20 62 79 20 61 20 73 69 6e 67 6c hash by a singl
0a60: 65 20 63 68 61 72 61 63 74 65 72 20 22 63 22 0a e character "c".
0a70: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 68 */.static void h
0a80: 61 73 68 5f 6e 65 78 74 28 68 61 73 68 20 2a 70 ash_next(hash *p
0a90: 48 61 73 68 2c 20 69 6e 74 20 63 29 7b 0a 20 20 Hash, int c){.
0aa0: 75 31 36 20 6f 6c 64 20 3d 20 70 48 61 73 68 2d u16 old = pHash-
0ab0: 3e 7a 5b 70 48 61 73 68 2d 3e 69 5d 3b 0a 20 20 >z[pHash->i];.
0ac0: 70 48 61 73 68 2d 3e 7a 5b 70 48 61 73 68 2d 3e pHash->z[pHash->
0ad0: 69 5d 20 3d 20 63 3b 0a 20 20 70 48 61 73 68 2d i] = c;. pHash-
0ae0: 3e 69 20 3d 20 28 70 48 61 73 68 2d 3e 69 2b 31 >i = (pHash->i+1
0af0: 29 26 28 4e 48 41 53 48 2d 31 29 3b 0a 20 20 70 )&(NHASH-1);. p
0b00: 48 61 73 68 2d 3e 61 20 3d 20 70 48 61 73 68 2d Hash->a = pHash-
0b10: 3e 61 20 2d 20 6f 6c 64 20 2b 20 63 3b 0a 20 20 >a - old + c;.
0b20: 70 48 61 73 68 2d 3e 62 20 3d 20 70 48 61 73 68 pHash->b = pHash
0b30: 2d 3e 62 20 2d 20 4e 48 41 53 48 2a 6f 6c 64 20 ->b - NHASH*old
0b40: 2b 20 70 48 61 73 68 2d 3e 61 3b 0a 7d 0a 0a 2f + pHash->a;.}../
0b50: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 33 32 *.** Return a 32
0b60: 2d 62 69 74 20 68 61 73 68 20 76 61 6c 75 65 0a -bit hash value.
0b70: 2a 2f 0a 73 74 61 74 69 63 20 75 33 32 20 68 61 */.static u32 ha
0b80: 73 68 5f 33 32 62 69 74 28 68 61 73 68 20 2a 70 sh_32bit(hash *p
0b90: 48 61 73 68 29 7b 0a 20 20 72 65 74 75 72 6e 20 Hash){. return
0ba0: 28 70 48 61 73 68 2d 3e 61 20 26 20 30 78 66 66 (pHash->a & 0xff
0bb0: 66 66 29 20 7c 20 28 28 28 75 33 32 29 28 70 48 ff) | (((u32)(pH
0bc0: 61 73 68 2d 3e 62 20 26 20 30 78 66 66 66 66 29 ash->b & 0xffff)
0bd0: 29 3c 3c 31 36 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a )<<16);.}../*.**
0be0: 20 4d 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20 Maximum number
0bf0: 6f 66 20 6c 61 6e 64 6d 61 72 6b 73 20 74 6f 20 of landmarks to
0c00: 73 65 74 20 69 6e 20 74 68 65 20 73 6f 75 72 63 set in the sourc
0c10: 65 20 66 69 6c 65 2e 0a 2a 2f 0a 23 64 65 66 69 e file..*/.#defi
0c20: 6e 65 20 4d 58 5f 4c 41 4e 44 4d 41 52 4b 20 28 ne MX_LANDMARK (
0c30: 31 30 32 34 2a 31 32 38 29 0a 0a 2f 2a 0a 2a 2a 1024*128)../*.**
0c40: 20 41 20 6d 61 70 70 69 6e 67 20 73 74 72 75 63 A mapping struc
0c50: 74 75 72 65 20 69 73 20 75 73 65 64 20 74 6f 20 ture is used to
0c60: 72 65 63 6f 72 64 20 77 68 69 63 68 20 70 61 72 record which par
0c70: 74 73 20 6f 66 20 74 77 6f 0a 2a 2a 20 66 69 6c ts of two.** fil
0c80: 65 73 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 73 es contain the s
0c90: 61 6d 65 20 74 65 78 74 2e 20 20 54 68 65 72 65 ame text. There
0ca0: 20 61 72 65 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 are zero or mor
0cb0: 65 20 6d 61 70 70 69 6e 67 0a 2a 2a 20 65 6e 74 e mapping.** ent
0cc0: 72 69 65 73 20 69 6e 20 61 20 6d 61 70 70 69 6e ries in a mappin
0cd0: 67 2e 20 20 45 61 63 68 20 65 6e 74 72 79 20 6d g. Each entry m
0ce0: 61 70 73 20 61 20 73 65 67 6d 65 6e 74 20 6f 66 aps a segment of
0cf0: 20 74 65 78 74 20 69 6e 0a 2a 2a 20 74 68 65 20 text in.** the
0d00: 73 6f 75 72 63 65 20 66 69 6c 65 20 69 6e 74 6f source file into
0d10: 20 61 20 73 65 67 6d 65 6e 74 20 6f 66 20 74 68 a segment of th
0d20: 65 20 6f 75 74 70 75 74 20 66 69 6c 65 2e 0a 2a e output file..*
0d30: 2a 0a 2a 2a 20 20 20 20 20 66 72 6f 6d 46 69 72 *.** fromFir
0d40: 73 74 2e 2e 2e 66 72 6f 6d 4c 61 73 74 20 2d 3e st...fromLast ->
0d50: 20 20 74 6f 46 69 72 73 74 2e 2e 2e 74 6f 4c 61 toFirst...toLa
0d60: 73 74 0a 2a 2a 0a 2a 2a 20 45 78 74 72 61 20 74 st.**.** Extra t
0d70: 65 78 74 20 6d 69 67 68 74 20 62 65 20 69 6e 73 ext might be ins
0d80: 65 72 74 65 64 20 69 6e 20 74 68 65 20 6f 75 74 erted in the out
0d90: 70 75 74 20 66 69 6c 65 20 61 66 74 65 72 20 61 put file after a
0da0: 20 0a 2a 2a 20 6d 61 70 70 69 6e 67 2e 20 20 54 .** mapping. T
0db0: 68 65 20 6e 45 78 74 72 61 20 70 61 72 61 6d 65 he nExtra parame
0dc0: 74 65 72 20 72 65 63 6f 72 64 73 20 74 68 65 20 ter records the
0dd0: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 0a number of bytes.
0de0: 2a 2a 20 6f 66 20 65 78 74 72 61 20 74 65 78 74 ** of extra text
0df0: 20 74 6f 20 69 6e 73 65 72 74 2e 0a 2a 2f 0a 74 to insert..*/.t
0e00: 79 70 65 64 65 66 20 73 74 72 75 63 74 20 4d 61 ypedef struct Ma
0e10: 70 70 69 6e 67 20 4d 61 70 70 69 6e 67 3b 0a 73 pping Mapping;.s
0e20: 74 72 75 63 74 20 4d 61 70 70 69 6e 67 20 7b 0a truct Mapping {.
0e30: 20 20 69 6e 74 20 6e 4d 61 70 3b 0a 20 20 69 6e int nMap;. in
0e40: 74 20 6e 55 73 65 64 3b 0a 20 20 73 74 72 75 63 t nUsed;. struc
0e50: 74 20 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 t Mapping_entry
0e60: 7b 0a 20 20 20 20 69 6e 74 20 66 72 6f 6d 46 69 {. int fromFi
0e70: 72 73 74 2c 20 66 72 6f 6d 4c 61 73 74 3b 0a 20 rst, fromLast;.
0e80: 20 20 20 69 6e 74 20 74 6f 46 69 72 73 74 2c 20 int toFirst,
0e90: 74 6f 4c 61 73 74 3b 0a 20 20 20 20 69 6e 74 20 toLast;. int
0ea0: 6e 45 78 74 72 61 3b 0a 20 20 7d 20 2a 61 4d 61 nExtra;. } *aMa
0eb0: 70 3b 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 p;.};../*.** Fre
0ec0: 65 20 6d 61 6c 6c 6f 63 65 64 20 6d 65 6d 6f 72 e malloced memor
0ed0: 79 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 y associated wit
0ee0: 68 20 61 20 6d 61 70 70 69 6e 67 2e 0a 2a 2f 0a h a mapping..*/.
0ef0: 73 74 61 74 69 63 20 76 6f 69 64 20 4d 61 70 70 static void Mapp
0f00: 69 6e 67 43 6c 65 61 72 28 4d 61 70 70 69 6e 67 ingClear(Mapping
0f10: 20 2a 70 29 7b 0a 20 20 66 72 65 65 28 70 2d 3e *p){. free(p->
0f20: 61 4d 61 70 29 3b 0a 20 20 6d 65 6d 73 65 74 28 aMap);. memset(
0f30: 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 2a 70 29 p, 0, sizeof(*p)
0f40: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64 20 );.}../*.** Add
0f50: 61 6e 20 65 6e 74 72 79 20 74 6f 20 61 20 6d 61 an entry to a ma
0f60: 70 70 69 6e 67 20 73 74 72 75 63 74 75 72 65 2e pping structure.
0f70: 20 20 54 68 65 20 6d 61 70 70 69 6e 67 20 69 73 The mapping is
0f80: 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 2e 2e 2e :.**.** a...
0f90: 62 20 20 2d 3e 20 20 20 63 2e 2e 2e 64 0a 2a 2a b -> c...d.**
0fa0: 0a 2a 2a 20 54 68 65 20 6e 45 78 74 72 61 20 70 .** The nExtra p
0fb0: 61 72 61 6d 65 74 65 72 20 69 73 20 69 6e 69 74 arameter is init
0fc0: 69 61 6c 6c 79 20 7a 65 72 6f 2e 20 20 49 74 20 ially zero. It
0fd0: 77 69 6c 6c 20 62 65 20 63 68 61 6e 67 65 64 0a will be changed.
0fe0: 2a 2a 20 6c 61 74 65 72 20 69 66 20 6e 65 63 65 ** later if nece
0ff0: 73 73 61 72 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 ssary..*/.static
1000: 20 76 6f 69 64 20 4d 61 70 70 69 6e 67 49 6e 73 void MappingIns
1010: 65 72 74 28 4d 61 70 70 69 6e 67 20 2a 70 2c 20 ert(Mapping *p,
1020: 69 6e 74 20 61 2c 20 69 6e 74 20 62 2c 20 69 6e int a, int b, in
1030: 74 20 63 2c 20 69 6e 74 20 64 29 7b 0a 20 20 73 t c, int d){. s
1040: 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f 65 6e truct Mapping_en
1050: 74 72 79 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69 try *pEntry;. i
1060: 6e 74 20 69 3b 0a 20 20 66 6f 72 28 69 3d 30 2c nt i;. for(i=0,
1070: 20 70 45 6e 74 72 79 3d 70 2d 3e 61 4d 61 70 3b pEntry=p->aMap;
1080: 20 69 3c 70 2d 3e 6e 55 73 65 64 3b 20 69 2b 2b i<p->nUsed; i++
1090: 2c 20 70 45 6e 74 72 79 2b 2b 29 7b 0a 20 20 20 , pEntry++){.
10a0: 20 69 66 28 20 70 45 6e 74 72 79 2d 3e 66 72 6f if( pEntry->fro
10b0: 6d 46 69 72 73 74 3d 3d 61 20 26 26 20 70 45 6e mFirst==a && pEn
10c0: 74 72 79 2d 3e 66 72 6f 6d 4c 61 73 74 3d 3d 62 try->fromLast==b
10d0: 20 26 26 20 70 45 6e 74 72 79 2d 3e 74 6f 46 69 && pEntry->toFi
10e0: 72 73 74 3d 3d 63 20 29 7b 0a 20 20 20 20 20 20 rst==c ){.
10f0: 44 45 42 55 47 32 28 20 70 72 69 6e 74 66 28 22 DEBUG2( printf("
1100: 44 55 50 4c 49 43 41 54 45 3a 20 25 36 64 2e 2e DUPLICATE: %6d..
1110: 25 2d 36 64 20 25 36 64 2e 2e 25 64 5c 6e 22 2c %-6d %6d..%d\n",
1120: 20 61 2c 20 62 2c 20 63 2c 20 64 29 3b 20 29 0a a, b, c, d); ).
1130: 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 return;.
1140: 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d }. }. if( p-
1150: 3e 6e 55 73 65 64 3e 3d 70 2d 3e 6e 4d 61 70 20 >nUsed>=p->nMap
1160: 29 7b 0a 20 20 20 20 70 2d 3e 6e 4d 61 70 20 3d ){. p->nMap =
1170: 20 70 2d 3e 6e 4d 61 70 20 2a 20 32 20 2b 20 31 p->nMap * 2 + 1
1180: 30 3b 0a 20 20 20 20 70 2d 3e 61 4d 61 70 20 3d 0;. p->aMap =
1190: 20 72 65 61 6c 6c 6f 63 28 70 2d 3e 61 4d 61 70 realloc(p->aMap
11a0: 2c 20 70 2d 3e 6e 4d 61 70 2a 73 69 7a 65 6f 66 , p->nMap*sizeof
11b0: 28 70 2d 3e 61 4d 61 70 5b 30 5d 29 20 29 3b 0a (p->aMap[0]) );.
11c0: 20 20 20 20 69 66 28 20 70 2d 3e 61 4d 61 70 3d if( p->aMap=
11d0: 3d 30 20 29 20 65 78 69 74 28 31 29 3b 0a 20 20 =0 ) exit(1);.
11e0: 7d 0a 20 20 70 45 6e 74 72 79 20 3d 20 26 70 2d }. pEntry = &p-
11f0: 3e 61 4d 61 70 5b 70 2d 3e 6e 55 73 65 64 5d 3b >aMap[p->nUsed];
1200: 0a 20 20 70 45 6e 74 72 79 2d 3e 66 72 6f 6d 46 . pEntry->fromF
1210: 69 72 73 74 20 3d 20 61 3b 0a 20 20 70 45 6e 74 irst = a;. pEnt
1220: 72 79 2d 3e 66 72 6f 6d 4c 61 73 74 20 3d 20 62 ry->fromLast = b
1230: 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 74 6f 46 69 ;. pEntry->toFi
1240: 72 73 74 20 3d 20 63 3b 0a 20 20 70 45 6e 74 72 rst = c;. pEntr
1250: 79 2d 3e 74 6f 4c 61 73 74 20 3d 20 64 3b 0a 20 y->toLast = d;.
1260: 20 70 45 6e 74 72 79 2d 3e 6e 45 78 74 72 61 20 pEntry->nExtra
1270: 3d 20 30 3b 0a 20 20 70 2d 3e 6e 55 73 65 64 2b = 0;. p->nUsed+
1280: 2b 3b 0a 7d 0a 0a 44 45 42 55 47 31 28 0a 2f 2a +;.}..DEBUG1(./*
1290: 0a 2a 2a 20 46 6f 72 20 64 65 62 75 67 67 69 6e .** For debuggin
12a0: 67 20 70 75 72 70 6f 73 65 73 3a 0a 2a 2a 20 50 g purposes:.** P
12b0: 72 69 6e 74 20 74 68 65 20 63 6f 6e 74 65 6e 74 rint the content
12c0: 20 6f 66 20 61 20 6d 61 70 70 69 6e 67 2e 0a 2a of a mapping..*
12d0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 4d 61 /.static void Ma
12e0: 70 70 69 6e 67 50 72 69 6e 74 28 4d 61 70 70 69 ppingPrint(Mappi
12f0: 6e 67 20 2a 70 4d 61 70 29 7b 0a 20 20 69 6e 74 ng *pMap){. int
1300: 20 69 3b 0a 20 20 73 74 72 75 63 74 20 4d 61 70 i;. struct Map
1310: 70 69 6e 67 5f 65 6e 74 72 79 20 2a 70 3b 0a 20 ping_entry *p;.
1320: 20 66 6f 72 28 69 3d 30 2c 20 70 3d 70 4d 61 70 for(i=0, p=pMap
1330: 2d 3e 61 4d 61 70 3b 20 69 3c 70 4d 61 70 2d 3e ->aMap; i<pMap->
1340: 6e 55 73 65 64 3b 20 69 2b 2b 2c 20 70 2b 2b 29 nUsed; i++, p++)
1350: 7b 0a 20 20 20 20 70 72 69 6e 74 66 28 22 25 36 {. printf("%6
1360: 64 2e 2e 25 2d 36 64 20 25 36 64 2e 2e 25 2d 36 d..%-6d %6d..%-6
1370: 64 20 20 25 64 5c 6e 22 2c 0a 20 20 20 20 20 20 d %d\n",.
1380: 20 70 2d 3e 66 72 6f 6d 46 69 72 73 74 2c 20 70 p->fromFirst, p
1390: 2d 3e 66 72 6f 6d 4c 61 73 74 2c 0a 20 20 20 20 ->fromLast,.
13a0: 20 20 20 70 2d 3e 74 6f 46 69 72 73 74 2c 20 70 p->toFirst, p
13b0: 2d 3e 74 6f 4c 61 73 74 2c 20 70 2d 3e 6e 45 78 ->toLast, p->nEx
13c0: 74 72 61 29 3b 0a 20 20 7d 0a 7d 0a 29 0a 0a 2f tra);. }.}.)../
13d0: 2a 0a 2a 2a 20 52 65 6d 6f 76 65 20 64 65 6c 65 *.** Remove dele
13e0: 74 65 64 20 65 6e 74 72 69 65 73 20 66 72 6f 6d ted entries from
13f0: 20 61 20 6d 61 70 70 69 6e 67 2e 20 20 44 65 6c a mapping. Del
1400: 65 74 65 64 20 65 6e 74 69 65 73 20 68 61 76 65 eted enties have
1410: 20 0a 2a 2a 20 61 6e 20 66 72 6f 6d 46 69 72 73 .** an fromFirs
1420: 74 20 6f 66 20 6c 65 73 73 20 74 68 61 6e 20 30 t of less than 0
1430: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 ..*/.static void
1440: 20 4d 61 70 70 69 6e 67 50 75 72 67 65 44 65 6c MappingPurgeDel
1450: 65 74 65 64 45 6e 74 72 69 65 73 28 4d 61 70 70 etedEntries(Mapp
1460: 69 6e 67 20 2a 70 29 7b 0a 20 20 69 6e 74 20 69 ing *p){. int i
1470: 2c 20 6a 3b 0a 20 20 66 6f 72 28 69 3d 6a 3d 30 , j;. for(i=j=0
1480: 3b 20 69 3c 70 2d 3e 6e 55 73 65 64 3b 20 69 2b ; i<p->nUsed; i+
1490: 2b 29 7b 0a 20 20 20 20 69 66 28 20 70 2d 3e 61 +){. if( p->a
14a0: 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 72 73 74 Map[i].fromFirst
14b0: 3c 30 20 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 <0 ) continue;.
14c0: 20 20 20 69 66 28 20 6a 3c 69 20 29 7b 0a 20 20 if( j<i ){.
14d0: 20 20 20 20 70 2d 3e 61 4d 61 70 5b 6a 5d 20 3d p->aMap[j] =
14e0: 20 70 2d 3e 61 4d 61 70 5b 69 5d 3b 0a 20 20 20 p->aMap[i];.
14f0: 20 7d 0a 20 20 20 20 6a 2b 2b 3b 0a 20 20 7d 0a }. j++;. }.
1500: 20 20 70 2d 3e 6e 55 73 65 64 20 3d 20 6a 3b 0a p->nUsed = j;.
1510: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 61 72 69 }../*.** Compari
1520: 73 6f 6e 73 20 66 75 6e 63 74 69 6f 6e 73 20 75 sons functions u
1530: 73 65 64 20 66 6f 72 20 73 6f 72 74 69 6e 67 20 sed for sorting
1540: 65 6c 65 6d 65 6e 74 73 20 6f 66 20 61 20 4d 61 elements of a Ma
1550: 70 70 69 6e 67 0a 2a 2f 0a 73 74 61 74 69 63 20 pping.*/.static
1560: 69 6e 74 20 69 6e 74 41 62 73 28 69 6e 74 20 78 int intAbs(int x
1570: 29 7b 20 72 65 74 75 72 6e 20 78 3c 30 20 3f 20 ){ return x<0 ?
1580: 2d 78 20 3a 20 78 3b 20 7d 0a 73 74 61 74 69 63 -x : x; }.static
1590: 20 69 6e 74 20 63 6f 6d 70 61 72 65 53 69 7a 65 int compareSize
15a0: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 61 2c 20 (const void *a,
15b0: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 62 29 7b 0a const void *b){.
15c0: 20 20 63 6f 6e 73 74 20 73 74 72 75 63 74 20 4d const struct M
15d0: 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a 41 20 apping_entry *A
15e0: 3d 20 28 63 6f 6e 73 74 20 73 74 72 75 63 74 20 = (const struct
15f0: 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 2a 29 61 Mapping_entry*)a
1600: 3b 0a 20 20 63 6f 6e 73 74 20 73 74 72 75 63 74 ;. const struct
1610: 20 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a Mapping_entry *
1620: 42 20 3d 20 28 63 6f 6e 73 74 20 73 74 72 75 63 B = (const struc
1630: 74 20 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 2a t Mapping_entry*
1640: 29 62 3b 0a 20 20 69 6e 74 20 72 63 3b 0a 20 20 )b;. int rc;.
1650: 72 63 20 3d 20 28 42 2d 3e 66 72 6f 6d 4c 61 73 rc = (B->fromLas
1660: 74 20 2d 20 42 2d 3e 66 72 6f 6d 46 69 72 73 74 t - B->fromFirst
1670: 29 20 2d 20 28 41 2d 3e 66 72 6f 6d 4c 61 73 74 ) - (A->fromLast
1680: 20 2d 20 41 2d 3e 66 72 6f 6d 46 69 72 73 74 29 - A->fromFirst)
1690: 3b 0a 20 20 69 66 28 20 72 63 3d 3d 30 20 29 7b ;. if( rc==0 ){
16a0: 0a 20 20 20 20 72 63 20 3d 20 69 6e 74 41 62 73 . rc = intAbs
16b0: 28 41 2d 3e 74 6f 46 69 72 73 74 20 2d 20 41 2d (A->toFirst - A-
16c0: 3e 66 72 6f 6d 46 69 72 73 74 29 20 2d 0a 20 20 >fromFirst) -.
16d0: 20 20 20 20 20 20 20 20 20 20 20 20 69 6e 74 41 intA
16e0: 62 73 28 42 2d 3e 74 6f 46 69 72 73 74 20 2d 20 bs(B->toFirst -
16f0: 42 2d 3e 66 72 6f 6d 46 69 72 73 74 29 3b 0a 20 B->fromFirst);.
1700: 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a }. return rc;.
1710: 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 63 6f 6d }.static int com
1720: 70 61 72 65 46 72 6f 6d 28 63 6f 6e 73 74 20 76 pareFrom(const v
1730: 6f 69 64 20 2a 61 2c 20 63 6f 6e 73 74 20 76 6f oid *a, const vo
1740: 69 64 20 2a 62 29 7b 0a 20 20 63 6f 6e 73 74 20 id *b){. const
1750: 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f 65 struct Mapping_e
1760: 6e 74 72 79 20 2a 41 20 3d 20 28 63 6f 6e 73 74 ntry *A = (const
1770: 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f struct Mapping_
1780: 65 6e 74 72 79 2a 29 61 3b 0a 20 20 63 6f 6e 73 entry*)a;. cons
1790: 74 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 t struct Mapping
17a0: 5f 65 6e 74 72 79 20 2a 42 20 3d 20 28 63 6f 6e _entry *B = (con
17b0: 73 74 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e st struct Mappin
17c0: 67 5f 65 6e 74 72 79 2a 29 62 3b 0a 20 20 72 65 g_entry*)b;. re
17d0: 74 75 72 6e 20 41 2d 3e 66 72 6f 6d 46 69 72 73 turn A->fromFirs
17e0: 74 20 2d 20 42 2d 3e 66 72 6f 6d 46 69 72 73 74 t - B->fromFirst
17f0: 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 63 ;.}.static int c
1800: 6f 6d 70 61 72 65 54 6f 28 63 6f 6e 73 74 20 76 ompareTo(const v
1810: 6f 69 64 20 2a 61 2c 20 63 6f 6e 73 74 20 76 6f oid *a, const vo
1820: 69 64 20 2a 62 29 7b 0a 20 20 63 6f 6e 73 74 20 id *b){. const
1830: 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f 65 struct Mapping_e
1840: 6e 74 72 79 20 2a 41 20 3d 20 28 63 6f 6e 73 74 ntry *A = (const
1850: 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f struct Mapping_
1860: 65 6e 74 72 79 2a 29 61 3b 0a 20 20 63 6f 6e 73 entry*)a;. cons
1870: 74 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 t struct Mapping
1880: 5f 65 6e 74 72 79 20 2a 42 20 3d 20 28 63 6f 6e _entry *B = (con
1890: 73 74 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e st struct Mappin
18a0: 67 5f 65 6e 74 72 79 2a 29 62 3b 0a 20 20 72 65 g_entry*)b;. re
18b0: 74 75 72 6e 20 41 2d 3e 74 6f 46 69 72 73 74 20 turn A->toFirst
18c0: 2d 20 42 2d 3e 74 6f 46 69 72 73 74 3b 0a 7d 0a - B->toFirst;.}.
18d0: 0a 2f 2a 0a 2a 2a 20 52 6f 75 74 69 6e 65 73 20 ./*.** Routines
18e0: 66 6f 72 20 73 6f 72 74 69 6e 67 20 74 68 65 20 for sorting the
18f0: 65 6e 74 72 69 65 73 20 6f 66 20 61 20 6d 61 70 entries of a map
1900: 70 69 6e 67 2e 20 20 53 6f 72 74 53 69 7a 65 20 ping. SortSize
1910: 73 6f 72 74 73 0a 2a 2a 20 74 68 65 20 65 6e 74 sorts.** the ent
1920: 72 69 65 73 20 69 6e 20 6f 72 64 65 72 20 6f 66 ries in order of
1930: 20 64 65 63 72 65 61 73 69 6e 67 20 73 69 7a 65 decreasing size
1940: 20 28 6c 61 72 67 65 73 74 20 66 69 72 73 74 2e (largest first.
1950: 29 20 20 0a 2a 2a 20 53 6f 72 74 46 72 6f 6d 20 ) .** SortFrom
1960: 61 6e 64 20 53 6f 72 74 54 6f 20 73 6f 72 74 20 and SortTo sort
1970: 74 68 65 20 65 6e 74 72 69 65 73 20 69 6e 20 6f the entries in o
1980: 72 64 65 72 20 6f 66 20 69 6e 63 72 65 61 73 69 rder of increasi
1990: 6e 67 0a 2a 2a 20 66 72 6f 6d 46 69 72 73 74 20 ng.** fromFirst
19a0: 61 6e 64 20 74 6f 46 69 72 73 74 2e 0a 2a 2f 0a and toFirst..*/.
19b0: 73 74 61 74 69 63 20 76 6f 69 64 20 4d 61 70 70 static void Mapp
19c0: 69 6e 67 53 6f 72 74 53 69 7a 65 28 4d 61 70 70 ingSortSize(Mapp
19d0: 69 6e 67 20 2a 70 29 7b 0a 20 20 71 73 6f 72 74 ing *p){. qsort
19e0: 28 70 2d 3e 61 4d 61 70 2c 20 70 2d 3e 6e 55 73 (p->aMap, p->nUs
19f0: 65 64 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 61 4d ed, sizeof(p->aM
1a00: 61 70 5b 30 5d 29 2c 20 63 6f 6d 70 61 72 65 53 ap[0]), compareS
1a10: 69 7a 65 29 3b 0a 7d 0a 73 74 61 74 69 63 20 76 ize);.}.static v
1a20: 6f 69 64 20 4d 61 70 70 69 6e 67 53 6f 72 74 46 oid MappingSortF
1a30: 72 6f 6d 28 4d 61 70 70 69 6e 67 20 2a 70 29 7b rom(Mapping *p){
1a40: 0a 20 20 71 73 6f 72 74 28 70 2d 3e 61 4d 61 70 . qsort(p->aMap
1a50: 2c 20 70 2d 3e 6e 55 73 65 64 2c 20 73 69 7a 65 , p->nUsed, size
1a60: 6f 66 28 70 2d 3e 61 4d 61 70 5b 30 5d 29 2c 20 of(p->aMap[0]),
1a70: 63 6f 6d 70 61 72 65 46 72 6f 6d 29 3b 0a 7d 0a compareFrom);.}.
1a80: 73 74 61 74 69 63 20 76 6f 69 64 20 4d 61 70 70 static void Mapp
1a90: 69 6e 67 53 6f 72 74 54 6f 28 4d 61 70 70 69 6e ingSortTo(Mappin
1aa0: 67 20 2a 70 29 7b 0a 20 20 71 73 6f 72 74 28 70 g *p){. qsort(p
1ab0: 2d 3e 61 4d 61 70 2c 20 70 2d 3e 6e 55 73 65 64 ->aMap, p->nUsed
1ac0: 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 61 4d 61 70 , sizeof(p->aMap
1ad0: 5b 30 5d 29 2c 20 63 6f 6d 70 61 72 65 54 6f 29 [0]), compareTo)
1ae0: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 ;.}../*.** Initi
1af0: 61 6c 69 7a 65 20 70 4d 61 70 20 74 6f 20 63 6f alize pMap to co
1b00: 6e 74 61 69 6e 20 61 20 73 65 74 20 6f 66 20 73 ntain a set of s
1b10: 69 6d 69 6c 61 72 69 74 69 65 73 20 62 65 74 77 imilarities betw
1b20: 65 65 6e 20 74 77 6f 20 66 69 6c 65 73 2e 0a 2a een two files..*
1b30: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 4d 61 /.static void Ma
1b40: 70 70 69 6e 67 49 6e 69 74 28 0a 20 20 63 6f 6e ppingInit(. con
1b50: 73 74 20 63 68 61 72 20 2a 7a 53 72 63 2c 20 20 st char *zSrc,
1b60: 20 20 20 20 2f 2a 20 54 68 65 20 73 6f 75 72 63 /* The sourc
1b70: 65 20 6f 72 20 70 61 74 74 65 72 6e 20 66 69 6c e or pattern fil
1b80: 65 20 2a 2f 0a 20 20 69 6e 74 20 6c 65 6e 53 72 e */. int lenSr
1b90: 63 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a c, /*
1ba0: 20 4c 65 6e 67 74 68 20 6f 66 20 74 68 65 20 73 Length of the s
1bb0: 6f 75 72 63 65 20 66 69 6c 65 20 2a 2f 0a 20 20 ource file */.
1bc0: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 4f 75 74 const char *zOut
1bd0: 2c 20 20 20 20 20 20 2f 2a 20 54 68 65 20 74 61 , /* The ta
1be0: 72 67 65 74 20 66 69 6c 65 20 2a 2f 0a 20 20 69 rget file */. i
1bf0: 6e 74 20 6c 65 6e 4f 75 74 2c 20 20 20 20 20 20 nt lenOut,
1c00: 20 20 20 20 20 20 2f 2a 20 4c 65 6e 67 74 68 20 /* Length
1c10: 6f 66 20 74 68 65 20 74 61 72 67 65 74 20 66 69 of the target fi
1c20: 6c 65 20 2a 2f 0a 20 20 4d 61 70 70 69 6e 67 20 le */. Mapping
1c30: 2a 70 4d 61 70 20 20 20 20 20 20 20 20 20 20 2f *pMap /
1c40: 2a 20 57 72 69 74 65 20 74 68 65 20 6d 61 70 20 * Write the map
1c50: 6f 66 20 73 69 6d 69 6c 61 72 69 65 73 20 68 65 of similaries he
1c60: 72 65 20 2a 2f 0a 29 7b 0a 20 20 69 6e 74 20 69 re */.){. int i
1c70: 2c 20 6a 2c 20 62 61 73 65 2c 20 70 72 65 66 69 , j, base, prefi
1c80: 78 3b 0a 20 20 69 6e 74 20 63 68 61 6e 67 65 73 x;. int changes
1c90: 3b 0a 20 20 68 61 73 68 20 68 3b 0a 20 20 69 6e ;. hash h;. in
1ca0: 74 20 2a 63 6f 6c 6c 69 64 65 3b 0a 20 20 69 6e t *collide;. in
1cb0: 74 20 6f 72 69 67 4c 65 6e 4f 75 74 20 3d 20 6c t origLenOut = l
1cc0: 65 6e 4f 75 74 3b 0a 20 20 73 74 72 75 63 74 20 enOut;. struct
1cd0: 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a 61 Mapping_entry *a
1ce0: 4d 61 70 3b 0a 20 20 69 6e 74 20 6c 61 6e 64 6d Map;. int landm
1cf0: 61 72 6b 5b 4d 58 5f 4c 41 4e 44 4d 41 52 4b 5d ark[MX_LANDMARK]
1d00: 3b 0a 0a 20 20 2f 2a 0a 20 20 2a 2a 20 49 6e 69 ;.. /*. ** Ini
1d10: 74 69 61 6c 69 7a 65 20 74 68 65 20 6d 61 70 0a tialize the map.
1d20: 20 20 2a 2f 0a 20 20 6d 65 6d 73 65 74 28 70 4d */. memset(pM
1d30: 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 2a 70 ap, 0, sizeof(*p
1d40: 4d 61 70 29 29 3b 0a 0a 20 20 2f 2a 0a 20 20 2a Map));.. /*. *
1d50: 2a 20 46 69 6e 64 20 63 6f 6d 6d 6f 6e 20 70 72 * Find common pr
1d60: 65 66 69 78 20 61 6e 64 20 73 75 66 66 69 78 0a efix and suffix.
1d70: 20 20 2a 2f 0a 20 20 69 66 28 20 6c 65 6e 53 72 */. if( lenSr
1d80: 63 3c 3d 4e 48 41 53 48 20 7c 7c 20 6c 65 6e 4f c<=NHASH || lenO
1d90: 75 74 3c 3d 4e 48 41 53 48 20 29 7b 0a 20 20 20 ut<=NHASH ){.
1da0: 20 4d 61 70 70 69 6e 67 49 6e 73 65 72 74 28 70 MappingInsert(p
1db0: 4d 61 70 2c 20 30 2c 20 30 2c 20 30 2c 20 30 29 Map, 0, 0, 0, 0)
1dc0: 3b 0a 20 20 20 20 67 6f 74 6f 20 61 64 64 5f 6e ;. goto add_n
1dd0: 65 78 74 72 61 3b 0a 20 20 7d 0a 20 20 66 6f 72 extra;. }. for
1de0: 28 69 3d 30 3b 20 69 3c 6c 65 6e 53 72 63 20 26 (i=0; i<lenSrc &
1df0: 26 20 69 3c 6c 65 6e 4f 75 74 20 26 26 20 7a 53 & i<lenOut && zS
1e00: 72 63 5b 69 5d 3d 3d 7a 4f 75 74 5b 69 5d 3b 20 rc[i]==zOut[i];
1e10: 69 2b 2b 29 7b 7d 0a 20 20 69 66 28 20 69 3e 3d i++){}. if( i>=
1e20: 4e 48 41 53 48 20 29 7b 0a 20 20 20 20 4d 61 70 NHASH ){. Map
1e30: 70 69 6e 67 49 6e 73 65 72 74 28 70 4d 61 70 2c pingInsert(pMap,
1e40: 20 30 2c 20 69 2d 31 2c 20 30 2c 20 69 2d 31 29 0, i-1, 0, i-1)
1e50: 3b 0a 20 20 20 20 6c 65 6e 53 72 63 20 2d 3d 20 ;. lenSrc -=
1e60: 69 3b 0a 20 20 20 20 7a 53 72 63 20 2b 3d 20 69 i;. zSrc += i
1e70: 3b 0a 20 20 20 20 6c 65 6e 4f 75 74 20 2d 3d 20 ;. lenOut -=
1e80: 69 3b 0a 20 20 20 20 7a 4f 75 74 20 2b 3d 20 69 i;. zOut += i
1e90: 3b 0a 20 20 20 20 69 66 28 20 6c 65 6e 53 72 63 ;. if( lenSrc
1ea0: 3c 3d 30 20 7c 7c 20 6c 65 6e 4f 75 74 3c 3d 30 <=0 || lenOut<=0
1eb0: 20 29 20 67 6f 74 6f 20 61 64 64 5f 6e 65 78 74 ) goto add_next
1ec0: 72 61 3b 0a 20 20 20 20 70 72 65 66 69 78 20 3d ra;. prefix =
1ed0: 20 69 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 i;. }else{.
1ee0: 20 70 72 65 66 69 78 20 3d 20 30 3b 0a 20 20 7d prefix = 0;. }
1ef0: 0a 20 20 66 6f 72 28 69 3d 31 3b 20 69 3c 3d 6c . for(i=1; i<=l
1f00: 65 6e 53 72 63 20 26 26 20 69 3c 3d 6c 65 6e 4f enSrc && i<=lenO
1f10: 75 74 20 26 26 20 7a 53 72 63 5b 6c 65 6e 53 72 ut && zSrc[lenSr
1f20: 63 2d 69 5d 3d 3d 7a 4f 75 74 5b 6c 65 6e 4f 75 c-i]==zOut[lenOu
1f30: 74 2d 69 5d 3b 20 69 2b 2b 29 7b 7d 0a 20 20 69 t-i]; i++){}. i
1f40: 66 28 20 69 3e 4e 48 41 53 48 20 29 7b 0a 20 20 f( i>NHASH ){.
1f50: 20 20 4d 61 70 70 69 6e 67 49 6e 73 65 72 74 28 MappingInsert(
1f60: 70 4d 61 70 2c 20 70 72 65 66 69 78 2b 6c 65 6e pMap, prefix+len
1f70: 53 72 63 2d 69 2b 31 2c 20 70 72 65 66 69 78 2b Src-i+1, prefix+
1f80: 6c 65 6e 53 72 63 2d 31 2c 0a 20 20 20 20 20 20 lenSrc-1,.
1f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1fa0: 20 20 70 72 65 66 69 78 2b 6c 65 6e 4f 75 74 2d prefix+lenOut-
1fb0: 69 2b 31 2c 20 70 72 65 66 69 78 2b 6c 65 6e 4f i+1, prefix+lenO
1fc0: 75 74 2d 31 29 3b 0a 20 20 20 20 6c 65 6e 53 72 ut-1);. lenSr
1fd0: 63 20 2d 3d 20 69 3b 0a 20 20 20 20 6c 65 6e 4f c -= i;. lenO
1fe0: 75 74 20 2d 3d 20 69 3b 0a 20 20 7d 0a 0a 20 20 ut -= i;. }..
1ff0: 2f 2a 20 49 66 20 74 68 65 20 73 6f 75 72 63 65 /* If the source
2000: 20 66 69 6c 65 20 69 73 20 76 65 72 79 20 73 6d file is very sm
2010: 61 6c 6c 2c 20 69 74 20 6d 65 61 6e 73 20 74 68 all, it means th
2020: 61 74 20 77 65 20 68 61 76 65 20 6e 6f 0a 20 20 at we have no.
2030: 2a 2a 20 63 68 61 6e 63 65 20 6f 66 20 65 76 65 ** chance of eve
2040: 72 20 66 69 6e 64 69 6e 67 20 61 6e 79 20 6d 61 r finding any ma
2050: 74 63 68 65 73 2e 20 20 57 65 20 63 61 6e 20 6c tches. We can l
2060: 65 61 76 65 20 65 61 72 6c 79 2e 0a 20 20 2a 2f eave early.. */
2070: 0a 20 20 69 66 28 20 6c 65 6e 53 72 63 3c 3d 4e . if( lenSrc<=N
2080: 48 41 53 48 20 29 20 67 6f 74 6f 20 61 64 64 5f HASH ) goto add_
2090: 6e 65 78 74 72 61 3b 0a 0a 20 20 2f 2a 20 43 6f nextra;.. /* Co
20a0: 6d 70 75 74 65 20 74 68 65 20 68 61 73 68 20 74 mpute the hash t
20b0: 61 62 6c 65 20 75 73 65 64 20 74 6f 20 6c 6f 63 able used to loc
20c0: 61 74 65 20 6d 61 74 63 68 69 6e 67 20 73 65 63 ate matching sec
20d0: 74 69 6f 6e 73 20 69 6e 20 74 68 65 0a 20 20 2a tions in the. *
20e0: 2a 20 73 6f 75 72 63 65 20 66 69 6c 65 2e 0a 20 * source file..
20f0: 20 2a 2f 0a 20 20 63 6f 6c 6c 69 64 65 20 3d 20 */. collide =
2100: 6d 61 6c 6c 6f 63 28 20 6c 65 6e 53 72 63 2a 73 malloc( lenSrc*s
2110: 69 7a 65 6f 66 28 69 6e 74 29 2f 4e 48 41 53 48 izeof(int)/NHASH
2120: 20 29 3b 0a 20 20 69 66 28 20 63 6f 6c 6c 69 64 );. if( collid
2130: 65 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 e==0 ) return;.
2140: 20 6d 65 6d 73 65 74 28 6c 61 6e 64 6d 61 72 6b memset(landmark
2150: 2c 20 2d 31 2c 20 73 69 7a 65 6f 66 28 6c 61 6e , -1, sizeof(lan
2160: 64 6d 61 72 6b 29 29 3b 0a 20 20 6d 65 6d 73 65 dmark));. memse
2170: 74 28 63 6f 6c 6c 69 64 65 2c 20 2d 31 2c 20 6c t(collide, -1, l
2180: 65 6e 53 72 63 2a 73 69 7a 65 6f 66 28 69 6e 74 enSrc*sizeof(int
2190: 29 2f 4e 48 41 53 48 20 29 3b 0a 20 20 66 6f 72 )/NHASH );. for
21a0: 28 69 3d 30 3b 20 69 3c 6c 65 6e 53 72 63 2d 4e (i=0; i<lenSrc-N
21b0: 48 41 53 48 3b 20 69 2b 3d 4e 48 41 53 48 29 7b HASH; i+=NHASH){
21c0: 0a 20 20 20 20 69 6e 74 20 68 76 3b 0a 20 20 20 . int hv;.
21d0: 20 68 61 73 68 5f 69 6e 69 74 28 26 68 2c 20 26 hash_init(&h, &
21e0: 7a 53 72 63 5b 69 5d 29 3b 0a 20 20 20 20 68 76 zSrc[i]);. hv
21f0: 20 3d 20 68 61 73 68 5f 33 32 62 69 74 28 26 68 = hash_32bit(&h
2200: 29 20 26 20 28 4d 58 5f 4c 41 4e 44 4d 41 52 4b ) & (MX_LANDMARK
2210: 2d 31 29 3b 0a 20 20 20 20 63 6f 6c 6c 69 64 65 -1);. collide
2220: 5b 69 2f 4e 48 41 53 48 5d 20 3d 20 6c 61 6e 64 [i/NHASH] = land
2230: 6d 61 72 6b 5b 68 76 5d 3b 0a 20 20 20 20 6c 61 mark[hv];. la
2240: 6e 64 6d 61 72 6b 5b 68 76 5d 20 3d 20 69 2f 4e ndmark[hv] = i/N
2250: 48 41 53 48 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 HASH;. }.. /*
2260: 42 65 67 69 6e 20 73 63 61 6e 6e 69 6e 67 20 74 Begin scanning t
2270: 68 65 20 74 61 72 67 65 74 20 66 69 6c 65 20 61 he target file a
2280: 6e 64 20 67 65 6e 65 72 61 74 69 6e 67 20 6d 61 nd generating ma
2290: 70 70 69 6e 67 73 2e 20 20 49 6e 20 74 68 69 73 ppings. In this
22a0: 0a 20 20 2a 2a 20 73 74 65 70 2c 20 77 65 20 67 . ** step, we g
22b0: 65 6e 65 72 61 74 65 20 61 73 20 6d 61 6e 79 20 enerate as many
22c0: 6d 61 70 70 69 6e 67 20 65 6e 74 72 69 65 73 20 mapping entries
22d0: 69 73 20 77 65 20 63 61 6e 2e 20 20 4d 61 6e 79 is we can. Many
22e0: 20 6f 66 20 74 68 65 73 65 0a 20 20 2a 2a 20 65 of these. ** e
22f0: 6e 74 72 69 65 73 20 6d 69 67 68 74 20 6f 76 65 ntries might ove
2300: 72 6c 61 70 2e 20 20 54 68 65 20 6f 76 65 72 6c rlap. The overl
2310: 61 70 70 69 6e 67 20 65 6e 74 72 69 65 73 20 61 apping entries a
2320: 72 65 20 72 65 6d 6f 76 65 64 20 62 79 0a 20 20 re removed by.
2330: 2a 2a 20 74 68 65 20 6c 6f 6f 70 20 74 68 65 20 ** the loop the
2340: 66 6f 6c 6c 6f 77 73 2e 0a 20 20 2a 2f 0a 20 20 follows.. */.
2350: 62 61 73 65 20 3d 20 30 3b 20 20 20 20 2f 2a 20 base = 0; /*
2360: 57 65 20 68 61 76 65 20 61 6c 72 65 61 64 79 20 We have already
2370: 63 68 65 63 6b 65 64 20 65 76 65 72 79 74 68 69 checked everythi
2380: 6e 67 20 62 65 66 6f 72 65 20 7a 4f 75 74 5b 62 ng before zOut[b
2390: 61 73 65 5d 20 2a 2f 0a 20 20 77 68 69 6c 65 28 ase] */. while(
23a0: 20 62 61 73 65 3c 6c 65 6e 4f 75 74 2d 4e 48 41 base<lenOut-NHA
23b0: 53 48 20 29 7b 0a 20 20 20 20 69 6e 74 20 69 53 SH ){. int iS
23c0: 72 63 2c 20 69 42 6c 6f 63 6b 2c 20 6e 65 78 74 rc, iBlock, next
23d0: 42 61 73 65 2c 20 6e 65 78 74 42 61 73 65 49 3b Base, nextBaseI;
23e0: 0a 20 20 20 20 68 61 73 68 5f 69 6e 69 74 28 26 . hash_init(&
23f0: 68 2c 20 26 7a 4f 75 74 5b 62 61 73 65 5d 29 3b h, &zOut[base]);
2400: 0a 20 20 20 20 69 20 3d 20 30 3b 20 20 20 20 20 . i = 0;
2410: 2f 2a 20 54 72 79 69 6e 67 20 74 6f 20 6d 61 74 /* Trying to mat
2420: 63 68 20 61 20 6c 61 6e 64 6d 61 72 6b 20 61 67 ch a landmark ag
2430: 61 69 6e 73 74 20 7a 4f 75 74 5b 62 61 73 65 2b ainst zOut[base+
2440: 69 5d 20 2a 2f 0a 20 20 20 20 6e 65 78 74 42 61 i] */. nextBa
2450: 73 65 49 20 3d 20 4e 48 41 53 48 3b 0a 20 20 20 seI = NHASH;.
2460: 20 6e 65 78 74 42 61 73 65 20 3d 20 62 61 73 65 nextBase = base
2470: 3b 0a 20 20 20 20 77 68 69 6c 65 28 31 29 7b 0a ;. while(1){.
2480: 20 20 20 20 20 20 69 6e 74 20 68 76 3b 0a 0a 20 int hv;..
2490: 20 20 20 20 20 68 76 20 3d 20 68 61 73 68 5f 33 hv = hash_3
24a0: 32 62 69 74 28 26 68 29 20 26 20 28 4d 58 5f 4c 2bit(&h) & (MX_L
24b0: 41 4e 44 4d 41 52 4b 2d 31 29 3b 0a 20 20 20 20 ANDMARK-1);.
24c0: 20 20 44 45 42 55 47 32 28 20 70 72 69 6e 74 66 DEBUG2( printf
24d0: 28 22 4c 4f 4f 4b 49 4e 47 3a 20 25 64 2b 25 64 ("LOOKING: %d+%d
24e0: 2b 25 64 3d 25 64 20 5b 25 73 5d 5c 6e 22 2c 0a +%d=%d [%s]\n",.
24f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72 pr
2500: 65 66 69 78 2c 62 61 73 65 2c 69 2c 70 72 65 66 efix,base,i,pref
2510: 69 78 2b 62 61 73 65 2b 69 2c 20 70 72 69 6e 74 ix+base+i, print
2520: 31 36 28 26 7a 4f 75 74 5b 62 61 73 65 2b 69 5d 16(&zOut[base+i]
2530: 29 29 3b 20 29 0a 20 20 20 20 20 20 69 42 6c 6f )); ). iBlo
2540: 63 6b 20 3d 20 6c 61 6e 64 6d 61 72 6b 5b 68 76 ck = landmark[hv
2550: 5d 3b 0a 20 20 20 20 20 20 77 68 69 6c 65 28 20 ];. while(
2560: 69 42 6c 6f 63 6b 3e 3d 30 20 29 7b 0a 20 20 20 iBlock>=0 ){.
2570: 20 20 20 20 20 2f 2a 0a 20 20 20 20 20 20 20 20 /*.
2580: 2a 2a 20 54 68 65 20 68 61 73 68 20 77 69 6e 64 ** The hash wind
2590: 6f 77 20 68 61 73 20 69 64 65 6e 74 69 66 69 65 ow has identifie
25a0: 64 20 61 20 70 6f 74 65 6e 74 69 61 6c 20 6d 61 d a potential ma
25b0: 74 63 68 20 61 67 61 69 6e 73 74 20 0a 20 20 20 tch against .
25c0: 20 20 20 20 20 2a 2a 20 6c 61 6e 64 6d 61 72 6b ** landmark
25d0: 20 62 6c 6f 63 6b 20 69 42 6c 6f 63 6b 2e 20 20 block iBlock.
25e0: 42 75 74 20 77 65 20 6e 65 65 64 20 74 6f 20 69 But we need to i
25f0: 6e 76 65 73 74 69 67 61 74 65 20 66 75 72 74 68 nvestigate furth
2600: 65 72 2e 0a 20 20 20 20 20 20 20 20 2a 2a 20 0a er.. ** .
2610: 20 20 20 20 20 20 20 20 2a 2a 20 4c 6f 6f 6b 20 ** Look
2620: 66 6f 72 20 61 20 72 65 67 69 6f 6e 20 69 6e 20 for a region in
2630: 7a 4f 75 74 20 74 68 61 74 20 6d 61 74 63 68 65 zOut that matche
2640: 73 20 7a 53 72 63 2e 20 41 6e 63 68 6f 72 20 74 s zSrc. Anchor t
2650: 68 65 20 73 65 61 72 63 68 0a 20 20 20 20 20 20 he search.
2660: 20 20 2a 2a 20 61 74 20 7a 53 72 63 5b 69 53 72 ** at zSrc[iSr
2670: 63 5d 20 61 6e 64 20 7a 4f 75 74 5b 62 61 73 65 c] and zOut[base
2680: 2b 69 5d 2e 0a 20 20 20 20 20 20 20 20 2a 2a 0a +i].. **.
2690: 20 20 20 20 20 20 20 20 2a 2a 20 53 65 74 20 63 ** Set c
26a0: 6e 74 20 65 71 75 61 6c 20 74 6f 20 74 68 65 20 nt equal to the
26b0: 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 20 6d 61 length of the ma
26c0: 74 63 68 20 61 6e 64 20 73 65 74 20 6f 66 73 74 tch and set ofst
26d0: 20 73 6f 20 74 68 61 74 0a 20 20 20 20 20 20 20 so that.
26e0: 20 2a 2a 20 7a 53 72 63 5b 6f 66 73 74 5d 20 69 ** zSrc[ofst] i
26f0: 73 20 74 68 65 20 66 69 72 73 74 20 65 6c 65 6d s the first elem
2700: 65 6e 74 20 6f 66 20 74 68 65 20 6d 61 74 63 68 ent of the match
2710: 2e 20 0a 20 20 20 20 20 20 20 20 2a 2f 0a 20 20 . . */.
2720: 20 20 20 20 20 20 69 6e 74 20 63 6e 74 2c 20 6f int cnt, o
2730: 66 73 74 53 72 63 3b 0a 20 20 20 20 20 20 20 20 fstSrc;.
2740: 69 6e 74 20 6a 2c 20 6b 2c 20 78 2c 20 79 3b 0a int j, k, x, y;.
2750: 0a 20 20 20 20 20 20 20 20 2f 2a 20 42 65 67 69 . /* Begi
2760: 6e 6e 69 6e 67 20 61 74 20 69 53 72 63 2c 20 6d nning at iSrc, m
2770: 61 74 63 68 20 66 6f 72 77 61 72 64 73 20 61 73 atch forwards as
2780: 20 66 61 72 20 61 73 20 77 65 20 63 61 6e 2e 20 far as we can.
2790: 20 6a 20 63 6f 75 6e 74 73 0a 20 20 20 20 20 20 j counts.
27a0: 20 20 2a 2a 20 74 68 65 20 6e 75 6d 62 65 72 20 ** the number
27b0: 6f 66 20 63 68 61 72 61 63 74 65 72 73 20 74 68 of characters th
27c0: 61 74 20 6d 61 74 63 68 20 2a 2f 0a 20 20 20 20 at match */.
27d0: 20 20 20 20 69 53 72 63 20 3d 20 69 42 6c 6f 63 iSrc = iBloc
27e0: 6b 2a 4e 48 41 53 48 3b 0a 20 20 20 20 20 20 20 k*NHASH;.
27f0: 20 66 6f 72 28 6a 3d 30 2c 20 78 3d 69 53 72 63 for(j=0, x=iSrc
2800: 2c 20 79 3d 62 61 73 65 2b 69 3b 20 78 3c 6c 65 , y=base+i; x<le
2810: 6e 53 72 63 20 26 26 20 79 3c 6c 65 6e 4f 75 74 nSrc && y<lenOut
2820: 3b 20 6a 2b 2b 2c 20 78 2b 2b 2c 20 79 2b 2b 29 ; j++, x++, y++)
2830: 7b 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 {. if(
2840: 7a 53 72 63 5b 78 5d 21 3d 7a 4f 75 74 5b 79 5d zSrc[x]!=zOut[y]
2850: 20 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 ) break;.
2860: 20 20 7d 0a 20 20 20 20 20 20 20 20 6a 2d 2d 3b }. j--;
2870: 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 42 65 67 .. /* Beg
2880: 69 6e 6e 69 6e 67 20 61 74 20 69 53 72 63 2d 31 inning at iSrc-1
2890: 2c 20 6d 61 74 63 68 20 62 61 63 6b 77 61 72 64 , match backward
28a0: 73 20 61 73 20 66 61 72 20 61 73 20 77 65 20 63 s as far as we c
28b0: 61 6e 2e 20 20 6b 20 63 6f 75 6e 74 73 0a 20 20 an. k counts.
28c0: 20 20 20 20 20 20 2a 2a 20 74 68 65 20 6e 75 6d ** the num
28d0: 62 65 72 20 6f 66 20 63 68 61 72 61 63 74 65 72 ber of character
28e0: 73 20 74 68 61 74 20 6d 61 74 63 68 20 2a 2f 0a s that match */.
28f0: 20 20 20 20 20 20 20 20 66 6f 72 28 6b 3d 31 3b for(k=1;
2900: 20 6b 3c 69 53 72 63 20 26 26 20 6b 3c 3d 62 61 k<iSrc && k<=ba
2910: 73 65 2b 69 3b 20 6b 2b 2b 29 7b 0a 20 20 20 20 se+i; k++){.
2920: 20 20 20 20 20 20 69 66 28 20 7a 53 72 63 5b 69 if( zSrc[i
2930: 53 72 63 2d 6b 5d 21 3d 7a 4f 75 74 5b 62 61 73 Src-k]!=zOut[bas
2940: 65 2b 69 2d 6b 5d 20 29 20 62 72 65 61 6b 3b 0a e+i-k] ) break;.
2950: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 }.
2960: 20 20 6b 2d 2d 3b 0a 0a 20 20 20 20 20 20 20 20 k--;..
2970: 2f 2a 20 43 6f 6d 70 75 74 65 20 74 68 65 20 6f /* Compute the o
2980: 66 66 73 65 74 20 61 6e 64 20 73 69 7a 65 20 6f ffset and size o
2990: 66 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20 72 f the matching r
29a0: 65 67 69 6f 6e 20 7a 53 72 63 20 2a 2f 0a 20 20 egion zSrc */.
29b0: 20 20 20 20 20 20 6f 66 73 74 53 72 63 20 3d 20 ofstSrc =
29c0: 69 53 72 63 2d 6b 3b 0a 20 20 20 20 20 20 20 20 iSrc-k;.
29d0: 63 6e 74 20 3d 20 6a 2b 6b 2b 31 3b 0a 20 20 20 cnt = j+k+1;.
29e0: 20 20 20 20 20 44 45 42 55 47 32 28 20 70 72 69 DEBUG2( pri
29f0: 6e 74 66 28 22 4d 41 54 43 48 20 25 64 20 62 79 ntf("MATCH %d by
2a00: 74 65 73 20 61 74 20 53 52 43 5b 25 64 2e 2e 25 tes at SRC[%d..%
2a10: 64 5d 3a 20 5b 25 73 5d 5c 6e 22 2c 0a 20 20 20 d]: [%s]\n",.
2a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 63 6e cn
2a30: 74 2c 20 6f 66 73 74 53 72 63 2c 20 6f 66 73 74 t, ofstSrc, ofst
2a40: 53 72 63 2b 63 6e 74 2d 31 2c 20 70 72 69 6e 74 Src+cnt-1, print
2a50: 31 36 28 26 7a 53 72 63 5b 6f 66 73 74 53 72 63 16(&zSrc[ofstSrc
2a60: 5d 29 29 3b 20 29 0a 20 20 20 20 20 20 20 20 69 ])); ). i
2a70: 66 28 20 63 6e 74 3e 4e 48 41 53 48 20 29 7b 0a f( cnt>NHASH ){.
2a80: 20 20 20 20 20 20 20 20 20 20 69 6e 74 20 6f 66 int of
2a90: 73 74 4f 75 74 20 3d 20 62 61 73 65 2b 69 2d 6b stOut = base+i-k
2aa0: 3b 0a 20 20 20 20 20 20 20 20 20 20 44 45 42 55 ;. DEBU
2ab0: 47 32 28 20 70 72 69 6e 74 66 28 22 43 4f 50 59 G2( printf("COPY
2ac0: 20 25 36 64 2e 2e 25 2d 36 64 20 25 36 64 2e 2e %6d..%-6d %6d..
2ad0: 25 64 5c 6e 22 2c 0a 20 20 20 20 20 20 20 20 20 %d\n",.
2ae0: 20 20 20 70 72 65 66 69 78 2b 6f 66 73 74 53 72 prefix+ofstSr
2af0: 63 2c 20 70 72 65 66 69 78 2b 6f 66 73 74 53 72 c, prefix+ofstSr
2b00: 63 2b 63 6e 74 2d 31 2c 0a 20 20 20 20 20 20 20 c+cnt-1,.
2b10: 20 20 20 20 20 70 72 65 66 69 78 2b 6f 66 73 74 prefix+ofst
2b20: 4f 75 74 2c 20 70 72 65 66 69 78 2b 6f 66 73 74 Out, prefix+ofst
2b30: 4f 75 74 2b 63 6e 74 2d 31 29 3b 20 29 0a 20 20 Out+cnt-1); ).
2b40: 20 20 20 20 20 20 20 20 4d 61 70 70 69 6e 67 49 MappingI
2b50: 6e 73 65 72 74 28 70 4d 61 70 2c 0a 20 20 20 20 nsert(pMap,.
2b60: 20 20 20 20 20 20 20 20 70 72 65 66 69 78 2b 6f prefix+o
2b70: 66 73 74 53 72 63 2c 20 70 72 65 66 69 78 2b 6f fstSrc, prefix+o
2b80: 66 73 74 53 72 63 2b 63 6e 74 2d 31 2c 0a 20 20 fstSrc+cnt-1,.
2b90: 20 20 20 20 20 20 20 20 20 20 70 72 65 66 69 78 prefix
2ba0: 2b 6f 66 73 74 4f 75 74 2c 20 70 72 65 66 69 78 +ofstOut, prefix
2bb0: 2b 6f 66 73 74 4f 75 74 2b 63 6e 74 2d 31 29 3b +ofstOut+cnt-1);
2bc0: 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 6e . if( n
2bd0: 65 78 74 42 61 73 65 20 3c 20 6f 66 73 74 4f 75 extBase < ofstOu
2be0: 74 2b 63 6e 74 2d 31 20 29 7b 0a 20 20 20 20 20 t+cnt-1 ){.
2bf0: 20 20 20 20 20 20 20 6e 65 78 74 42 61 73 65 20 nextBase
2c00: 3d 20 6f 66 73 74 4f 75 74 2b 63 6e 74 2d 31 3b = ofstOut+cnt-1;
2c10: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e 65 78 . nex
2c20: 74 42 61 73 65 49 20 3d 20 69 2b 4e 48 41 53 48 tBaseI = i+NHASH
2c30: 3b 0a 20 20 20 20 20 20 20 20 20 20 7d 0a 20 20 ;. }.
2c40: 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 }..
2c50: 20 2f 2a 20 43 68 65 63 6b 20 74 68 65 20 6e 65 /* Check the ne
2c60: 78 74 20 6d 61 74 63 68 69 6e 67 20 62 6c 6f 63 xt matching bloc
2c70: 6b 20 2a 2f 0a 20 20 20 20 20 20 20 20 69 42 6c k */. iBl
2c80: 6f 63 6b 20 3d 20 63 6f 6c 6c 69 64 65 5b 69 42 ock = collide[iB
2c90: 6c 6f 63 6b 5d 3b 0a 20 20 20 20 20 20 7d 0a 0a lock];. }..
2ca0: 20 20 20 20 20 20 2f 2a 20 49 66 20 77 65 20 66 /* If we f
2cb0: 6f 75 6e 64 20 61 20 6d 61 74 63 68 2c 20 74 68 ound a match, th
2cc0: 65 6e 20 6a 75 6d 70 20 6f 75 74 20 74 6f 20 74 en jump out to t
2cd0: 68 65 20 6f 75 74 65 72 20 6c 6f 6f 70 20 61 6e he outer loop an
2ce0: 64 20 62 65 67 69 6e 0a 20 20 20 20 20 20 2a 2a d begin. **
2cf0: 20 61 20 6e 65 77 20 63 79 63 6c 65 2e 0a 20 20 a new cycle..
2d00: 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 */. if(
2d10: 20 6e 65 78 74 42 61 73 65 3e 62 61 73 65 20 26 nextBase>base &
2d20: 26 20 69 3e 3d 6e 65 78 74 42 61 73 65 49 20 29 & i>=nextBaseI )
2d30: 7b 0a 20 20 20 20 20 20 20 20 62 61 73 65 20 3d {. base =
2d40: 20 6e 65 78 74 42 61 73 65 3b 0a 20 20 20 20 20 nextBase;.
2d50: 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 break;.
2d60: 7d 0a 0a 20 20 20 20 20 20 2f 2a 20 41 64 76 61 }.. /* Adva
2d70: 6e 63 65 20 74 68 65 20 68 61 73 68 20 62 79 20 nce the hash by
2d80: 6f 6e 65 20 63 68 61 72 61 63 74 65 72 2e 20 20 one character.
2d90: 4b 65 65 70 20 6c 6f 6f 6b 69 6e 67 20 66 6f 72 Keep looking for
2da0: 20 61 20 6d 61 74 63 68 20 2a 2f 0a 20 20 20 20 a match */.
2db0: 20 20 69 66 28 20 62 61 73 65 2b 69 2b 4e 48 41 if( base+i+NHA
2dc0: 53 48 3e 3d 6c 65 6e 4f 75 74 20 29 7b 0a 20 20 SH>=lenOut ){.
2dd0: 20 20 20 20 20 20 62 61 73 65 20 3d 20 6c 65 6e base = len
2de0: 4f 75 74 3b 0a 20 20 20 20 20 20 20 20 62 72 65 Out;. bre
2df0: 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ak;. }.
2e00: 20 20 68 61 73 68 5f 6e 65 78 74 28 26 68 2c 20 hash_next(&h,
2e10: 7a 4f 75 74 5b 62 61 73 65 2b 69 2b 4e 48 41 53 zOut[base+i+NHAS
2e20: 48 5d 29 3b 0a 20 20 20 20 20 20 69 2b 2b 3b 0a H]);. i++;.
2e30: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 66 72 65 65 }. }. free
2e40: 28 63 6f 6c 6c 69 64 65 29 3b 0a 23 69 66 20 30 (collide);.#if 0
2e50: 0a 20 20 44 45 42 55 47 31 28 0a 20 20 20 70 72 . DEBUG1(. pr
2e60: 69 6e 74 66 28 22 61 66 74 65 72 20 63 72 65 61 intf("after crea
2e70: 74 69 6f 6e 3a 5c 6e 22 29 3b 0a 20 20 20 4d 61 tion:\n");. Ma
2e80: 70 70 69 6e 67 50 72 69 6e 74 28 70 4d 61 70 29 ppingPrint(pMap)
2e90: 3b 0a 20 20 29 0a 23 65 6e 64 69 66 0a 0a 20 20 ;. ).#endif..
2ea0: 2f 2a 20 49 6e 20 74 68 69 73 20 73 74 65 70 2c /* In this step,
2eb0: 20 77 65 20 77 69 6c 6c 20 72 65 6d 6f 76 65 20 we will remove
2ec0: 6f 76 65 72 6c 61 70 70 69 6e 67 20 65 6e 74 72 overlapping entr
2ed0: 69 65 73 20 66 72 6f 6d 20 74 68 65 20 6d 61 70 ies from the map
2ee0: 70 69 6e 67 2e 0a 20 20 2a 2a 0a 20 20 2a 2a 20 ping.. **. **
2ef0: 57 65 20 75 73 65 20 61 20 67 72 65 65 64 79 20 We use a greedy
2f00: 61 6c 67 6f 72 69 74 68 6d 2e 20 20 53 65 6c 65 algorithm. Sele
2f10: 63 74 20 74 68 65 20 6c 61 72 67 65 73 74 20 6d ct the largest m
2f20: 61 70 70 69 6e 67 20 66 69 72 73 74 20 61 6e 64 apping first and
2f30: 0a 20 20 2a 2a 20 72 65 6d 6f 76 65 20 61 6c 6c . ** remove all
2f40: 20 6f 76 65 72 6c 61 70 70 69 6e 67 20 6d 61 70 overlapping map
2f50: 70 69 6e 67 73 2e 20 20 54 68 65 6e 20 74 61 6b pings. Then tak
2f60: 65 20 74 68 65 20 6e 65 78 74 20 6c 61 72 67 65 e the next large
2f70: 73 74 0a 20 20 2a 2a 20 6d 61 70 70 69 6e 67 20 st. ** mapping
2f80: 61 6e 64 20 72 65 6d 6f 76 65 20 6f 74 68 65 72 and remove other
2f90: 73 20 74 68 61 74 20 6f 76 65 72 6c 61 70 20 77 s that overlap w
2fa0: 69 74 68 20 69 74 2e 20 20 4b 65 65 70 20 67 6f ith it. Keep go
2fb0: 69 6e 67 20 75 6e 74 69 6c 0a 20 20 2a 2a 20 61 ing until. ** a
2fc0: 6c 6c 20 6d 61 70 70 69 6e 67 73 20 68 61 76 65 ll mappings have
2fd0: 20 62 65 65 6e 20 70 72 6f 63 65 73 73 65 64 2e been processed.
2fe0: 0a 20 20 2a 2f 0a 20 20 4d 61 70 70 69 6e 67 53 . */. MappingS
2ff0: 6f 72 74 53 69 7a 65 28 70 4d 61 70 29 3b 0a 20 ortSize(pMap);.
3000: 20 64 6f 7b 0a 20 20 20 20 63 68 61 6e 67 65 73 do{. changes
3010: 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d = 0;. for(i=
3020: 30 3b 20 69 3c 70 4d 61 70 2d 3e 6e 55 73 65 64 0; i<pMap->nUsed
3030: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 69 6e ; i++){. in
3040: 74 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 30 t sortNeeded = 0
3050: 3b 0a 20 20 20 20 20 20 69 6e 74 20 70 75 72 67 ;. int purg
3060: 65 4e 65 65 64 65 64 20 3d 20 30 3b 0a 20 20 20 eNeeded = 0;.
3070: 20 20 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e struct Mappin
3080: 67 5f 65 6e 74 72 79 20 2a 70 41 3b 0a 20 20 20 g_entry *pA;.
3090: 20 20 20 70 41 20 3d 20 26 70 4d 61 70 2d 3e 61 pA = &pMap->a
30a0: 4d 61 70 5b 69 5d 3b 0a 20 20 20 20 20 20 66 6f Map[i];. fo
30b0: 72 28 6a 3d 69 2b 31 3b 20 6a 3c 70 4d 61 70 2d r(j=i+1; j<pMap-
30c0: 3e 6e 55 73 65 64 3b 20 6a 2b 2b 29 7b 0a 20 20 >nUsed; j++){.
30d0: 20 20 20 20 20 20 69 6e 74 20 64 69 66 66 3b 0a int diff;.
30e0: 20 20 20 20 20 20 20 20 73 74 72 75 63 74 20 4d struct M
30f0: 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a 70 42 apping_entry *pB
3100: 3b 0a 20 20 20 20 20 20 20 20 70 42 20 3d 20 26 ;. pB = &
3110: 70 4d 61 70 2d 3e 61 4d 61 70 5b 6a 5d 3b 0a 20 pMap->aMap[j];.
3120: 20 20 20 20 20 20 20 69 66 28 20 70 42 2d 3e 66 if( pB->f
3130: 72 6f 6d 4c 61 73 74 3c 70 41 2d 3e 66 72 6f 6d romLast<pA->from
3140: 46 69 72 73 74 20 7c 7c 20 70 42 2d 3e 66 72 6f First || pB->fro
3150: 6d 46 69 72 73 74 3e 70 41 2d 3e 66 72 6f 6d 4c mFirst>pA->fromL
3160: 61 73 74 20 29 7b 0a 20 20 20 20 20 20 20 20 20 ast ){.
3170: 20 2f 2a 20 4e 6f 20 6f 76 65 72 6c 61 70 2e 20 /* No overlap.
3180: 20 44 6f 20 6e 6f 74 68 69 6e 67 20 2a 2f 0a 20 Do nothing */.
3190: 20 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 28 }else if(
31a0: 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 3e 3d pB->fromFirst>=
31b0: 70 41 2d 3e 66 72 6f 6d 46 69 72 73 74 20 26 26 pA->fromFirst &&
31c0: 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 3c 3d 70 pB->fromLast<=p
31d0: 41 2d 3e 66 72 6f 6d 4c 61 73 74 20 29 7b 0a 20 A->fromLast ){.
31e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 42 20 69 73 /* B is
31f0: 20 63 6f 6e 74 61 69 6e 65 64 20 65 6e 74 69 72 contained entir
3200: 65 6c 79 20 77 69 74 68 69 6e 20 41 2e 20 20 44 ely within A. D
3210: 72 6f 70 20 42 20 2a 2f 0a 20 20 20 20 20 20 20 rop B */.
3220: 20 20 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 pB->fromFirst
3230: 20 3d 20 2d 31 3b 0a 20 20 20 20 20 20 20 20 20 = -1;.
3240: 20 70 75 72 67 65 4e 65 65 64 65 64 20 3d 20 31 purgeNeeded = 1
3250: 3b 0a 20 20 20 20 20 20 20 20 20 20 63 6f 6e 74 ;. cont
3260: 69 6e 75 65 3b 0a 20 20 20 20 20 20 20 20 7d 65 inue;. }e
3270: 6c 73 65 20 69 66 28 20 70 42 2d 3e 66 72 6f 6d lse if( pB->from
3280: 46 69 72 73 74 3c 70 41 2d 3e 66 72 6f 6d 46 69 First<pA->fromFi
3290: 72 73 74 20 29 7b 0a 20 20 20 20 20 20 20 20 20 rst ){.
32a0: 20 2f 2a 20 54 68 65 20 74 61 69 6c 20 42 20 6f /* The tail B o
32b0: 76 65 72 6c 61 70 73 20 74 68 65 20 68 65 61 64 verlaps the head
32c0: 20 6f 66 20 41 20 2a 2f 0a 20 20 20 20 20 20 20 of A */.
32d0: 20 20 20 61 73 73 65 72 74 28 20 70 42 2d 3e 66 assert( pB->f
32e0: 72 6f 6d 4c 61 73 74 3e 3d 70 41 2d 3e 66 72 6f romLast>=pA->fro
32f0: 6d 46 69 72 73 74 20 26 26 20 70 42 2d 3e 66 72 mFirst && pB->fr
3300: 6f 6d 4c 61 73 74 3c 3d 70 41 2d 3e 66 72 6f 6d omLast<=pA->from
3310: 4c 61 73 74 20 29 3b 0a 20 20 20 20 20 20 20 20 Last );.
3320: 20 20 64 69 66 66 20 3d 20 70 42 2d 3e 66 72 6f diff = pB->fro
3330: 6d 4c 61 73 74 20 2b 20 31 20 2d 20 70 41 2d 3e mLast + 1 - pA->
3340: 66 72 6f 6d 46 69 72 73 74 3b 0a 20 20 20 20 20 fromFirst;.
3350: 20 20 20 20 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 pB->fromLas
3360: 74 20 2d 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 t -= diff;.
3370: 20 20 20 20 20 70 42 2d 3e 74 6f 4c 61 73 74 20 pB->toLast
3380: 2d 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 -= diff;.
3390: 20 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 sortNeeded =
33a0: 31 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73 65 1;. }else
33b0: 7b 0a 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 {. /* T
33c0: 68 65 20 68 65 61 64 20 6f 66 20 42 20 6f 76 65 he head of B ove
33d0: 72 6c 61 70 73 20 74 68 65 20 74 61 69 6c 20 6f rlaps the tail o
33e0: 66 20 41 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 f A */.
33f0: 20 61 73 73 65 72 74 28 20 70 42 2d 3e 66 72 6f assert( pB->fro
3400: 6d 46 69 72 73 74 3c 3d 70 41 2d 3e 66 72 6f 6d mFirst<=pA->from
3410: 4c 61 73 74 20 26 26 20 70 42 2d 3e 66 72 6f 6d Last && pB->from
3420: 4c 61 73 74 3e 70 41 2d 3e 66 72 6f 6d 4c 61 73 Last>pA->fromLas
3430: 74 20 29 3b 0a 20 20 20 20 20 20 20 20 20 20 64 t );. d
3440: 69 66 66 20 3d 20 70 41 2d 3e 66 72 6f 6d 4c 61 iff = pA->fromLa
3450: 73 74 20 2b 20 31 20 2d 20 70 42 2d 3e 66 72 6f st + 1 - pB->fro
3460: 6d 46 69 72 73 74 3b 0a 20 20 20 20 20 20 20 20 mFirst;.
3470: 20 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 20 pB->fromFirst
3480: 2b 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 += diff;.
3490: 20 20 20 70 42 2d 3e 74 6f 46 69 72 73 74 20 2b pB->toFirst +
34a0: 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 20 = diff;.
34b0: 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 31 sortNeeded = 1
34c0: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 ;. }.
34d0: 20 20 20 20 69 66 28 20 70 42 2d 3e 74 6f 4c 61 if( pB->toLa
34e0: 73 74 3c 70 41 2d 3e 74 6f 46 69 72 73 74 20 7c st<pA->toFirst |
34f0: 7c 20 70 42 2d 3e 74 6f 46 69 72 73 74 3e 70 41 | pB->toFirst>pA
3500: 2d 3e 74 6f 4c 61 73 74 20 29 7b 0a 20 20 20 20 ->toLast ){.
3510: 20 20 20 20 20 20 2f 2a 20 4e 6f 20 6f 76 65 72 /* No over
3520: 6c 61 70 2e 20 20 44 6f 20 6e 6f 74 68 69 6e 67 lap. Do nothing
3530: 20 2a 2f 0a 20 20 20 20 20 20 20 20 7d 65 6c 73 */. }els
3540: 65 20 69 66 28 20 70 42 2d 3e 74 6f 46 69 72 73 e if( pB->toFirs
3550: 74 3e 3d 70 41 2d 3e 74 6f 46 69 72 73 74 20 26 t>=pA->toFirst &
3560: 26 20 70 42 2d 3e 74 6f 4c 61 73 74 3c 3d 70 41 & pB->toLast<=pA
3570: 2d 3e 74 6f 4c 61 73 74 20 29 7b 0a 20 20 20 20 ->toLast ){.
3580: 20 20 20 20 20 20 2f 2a 20 42 20 69 73 20 63 6f /* B is co
3590: 6e 74 61 69 6e 65 64 20 65 6e 74 69 72 65 6c 79 ntained entirely
35a0: 20 77 69 74 68 69 6e 20 41 2e 20 20 44 72 6f 70 within A. Drop
35b0: 20 42 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 B */.
35c0: 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 20 3d 20 pB->fromFirst =
35d0: 2d 31 3b 0a 20 20 20 20 20 20 20 20 20 20 70 75 -1;. pu
35e0: 72 67 65 4e 65 65 64 65 64 20 3d 20 31 3b 0a 20 rgeNeeded = 1;.
35f0: 20 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 28 }else if(
3600: 20 70 42 2d 3e 74 6f 46 69 72 73 74 3c 70 41 2d pB->toFirst<pA-
3610: 3e 74 6f 46 69 72 73 74 20 29 7b 0a 20 20 20 20 >toFirst ){.
3620: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 74 61 69 /* The tai
3630: 6c 20 6f 66 20 42 20 6f 76 65 72 6c 61 70 73 20 l of B overlaps
3640: 74 68 65 20 68 65 61 64 20 6f 66 20 41 20 2a 2f the head of A */
3650: 0a 20 20 20 20 20 20 20 20 20 20 61 73 73 65 72 . asser
3660: 74 28 20 70 42 2d 3e 74 6f 4c 61 73 74 3e 3d 70 t( pB->toLast>=p
3670: 41 2d 3e 74 6f 46 69 72 73 74 20 26 26 20 70 42 A->toFirst && pB
3680: 2d 3e 74 6f 4c 61 73 74 3c 3d 70 41 2d 3e 74 6f ->toLast<=pA->to
3690: 4c 61 73 74 20 29 3b 0a 20 20 20 20 20 20 20 20 Last );.
36a0: 20 20 64 69 66 66 20 3d 20 70 42 2d 3e 74 6f 4c diff = pB->toL
36b0: 61 73 74 20 2b 20 31 20 2d 20 70 41 2d 3e 74 6f ast + 1 - pA->to
36c0: 46 69 72 73 74 3b 0a 20 20 20 20 20 20 20 20 20 First;.
36d0: 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 20 2d 3d pB->fromLast -=
36e0: 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 20 20 diff;.
36f0: 20 70 42 2d 3e 74 6f 4c 61 73 74 20 2d 3d 20 64 pB->toLast -= d
3700: 69 66 66 3b 0a 20 20 20 20 20 20 20 20 20 20 73 iff;. s
3710: 6f 72 74 4e 65 65 64 65 64 20 3d 20 31 3b 0a 20 ortNeeded = 1;.
3720: 20 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 }else{.
3730: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68 /* The h
3740: 65 61 64 20 6f 66 20 42 20 6f 76 65 72 6c 61 70 ead of B overlap
3750: 73 20 74 68 65 20 74 61 69 6c 20 6f 66 20 41 20 s the tail of A
3760: 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 61 73 73 */. ass
3770: 65 72 74 28 20 70 42 2d 3e 74 6f 46 69 72 73 74 ert( pB->toFirst
3780: 3c 3d 70 41 2d 3e 74 6f 4c 61 73 74 20 26 26 20 <=pA->toLast &&
3790: 70 42 2d 3e 74 6f 4c 61 73 74 3e 70 41 2d 3e 74 pB->toLast>pA->t
37a0: 6f 4c 61 73 74 20 29 3b 0a 20 20 20 20 20 20 20 oLast );.
37b0: 20 20 20 64 69 66 66 20 3d 20 70 41 2d 3e 74 6f diff = pA->to
37c0: 4c 61 73 74 20 2b 20 31 20 2d 20 70 42 2d 3e 74 Last + 1 - pB->t
37d0: 6f 46 69 72 73 74 3b 0a 20 20 20 20 20 20 20 20 oFirst;.
37e0: 20 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 20 pB->fromFirst
37f0: 2b 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 += diff;.
3800: 20 20 20 70 42 2d 3e 74 6f 46 69 72 73 74 20 2b pB->toFirst +
3810: 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 20 20 = diff;.
3820: 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 31 sortNeeded = 1
3830: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 ;. }.
3840: 20 20 7d 0a 20 20 20 20 20 20 69 66 28 20 70 75 }. if( pu
3850: 72 67 65 4e 65 65 64 65 64 20 29 7b 0a 20 20 20 rgeNeeded ){.
3860: 20 20 20 20 20 4d 61 70 70 69 6e 67 50 75 72 67 MappingPurg
3870: 65 44 65 6c 65 74 65 64 45 6e 74 72 69 65 73 28 eDeletedEntries(
3880: 70 4d 61 70 29 3b 0a 20 20 20 20 20 20 20 20 2f pMap);. /
3890: 2a 20 63 68 61 6e 67 65 73 2b 2b 3b 20 2a 2f 0a * changes++; */.
38a0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 69 66 }. if
38b0: 28 20 73 6f 72 74 4e 65 65 64 65 64 20 26 26 20 ( sortNeeded &&
38c0: 69 3c 70 4d 61 70 2d 3e 6e 55 73 65 64 2d 32 20 i<pMap->nUsed-2
38d0: 29 7b 0a 20 20 20 20 20 20 20 20 4d 61 70 70 69 ){. Mappi
38e0: 6e 67 53 6f 72 74 53 69 7a 65 28 70 4d 61 70 29 ngSortSize(pMap)
38f0: 3b 0a 20 20 20 20 20 20 20 20 2f 2a 20 63 68 61 ;. /* cha
3900: 6e 67 65 73 2b 2b 3b 20 2a 2f 0a 20 20 20 20 20 nges++; */.
3910: 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 77 68 69 6c }. }. }whil
3920: 65 28 20 63 68 61 6e 67 65 73 20 29 3b 0a 20 20 e( changes );.
3930: 0a 20 20 2f 2a 20 46 69 6e 61 6c 20 73 74 65 70 . /* Final step
3940: 3a 20 20 41 72 72 61 6e 67 65 20 74 68 65 20 6d : Arrange the m
3950: 61 70 70 69 6e 67 20 65 6e 74 69 72 65 73 20 73 apping entires s
3960: 6f 20 74 68 61 74 20 74 68 65 79 20 61 72 65 20 o that they are
3970: 69 6e 20 74 68 65 0a 20 20 2a 2a 20 6f 72 64 65 in the. ** orde
3980: 72 20 6f 66 20 74 68 65 20 6f 75 74 70 75 74 20 r of the output
3990: 66 69 6c 65 2e 20 20 54 68 65 6e 20 66 69 6c 6c file. Then fill
39a0: 20 69 6e 20 74 68 65 20 6e 45 78 74 72 61 20 76 in the nExtra v
39b0: 61 6c 75 65 73 2e 0a 20 20 2a 2f 0a 61 64 64 5f alues.. */.add_
39c0: 6e 65 78 74 72 61 3a 0a 20 20 4d 61 70 70 69 6e nextra:. Mappin
39d0: 67 53 6f 72 74 54 6f 28 70 4d 61 70 29 3b 0a 20 gSortTo(pMap);.
39e0: 20 61 4d 61 70 20 3d 20 70 4d 61 70 2d 3e 61 4d aMap = pMap->aM
39f0: 61 70 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 ap;. for(i=0; i
3a00: 3c 70 4d 61 70 2d 3e 6e 55 73 65 64 2d 31 3b 20 <pMap->nUsed-1;
3a10: 69 2b 2b 29 7b 0a 20 20 20 20 61 4d 61 70 5b 69 i++){. aMap[i
3a20: 5d 2e 6e 45 78 74 72 61 20 3d 20 61 4d 61 70 5b ].nExtra = aMap[
3a30: 69 2b 31 5d 2e 74 6f 46 69 72 73 74 20 2d 20 61 i+1].toFirst - a
3a40: 4d 61 70 5b 69 5d 2e 74 6f 4c 61 73 74 20 2d 20 Map[i].toLast -
3a50: 31 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 4d 61 1;. }. if( pMa
3a60: 70 2d 3e 6e 55 73 65 64 3e 30 20 26 26 20 6f 72 p->nUsed>0 && or
3a70: 69 67 4c 65 6e 4f 75 74 20 3e 20 61 4d 61 70 5b igLenOut > aMap[
3a80: 69 5d 2e 74 6f 4c 61 73 74 2b 31 20 29 7b 0a 20 i].toLast+1 ){.
3a90: 20 20 20 61 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 aMap[i].nExtr
3aa0: 61 20 3d 20 6f 72 69 67 4c 65 6e 4f 75 74 20 2d a = origLenOut -
3ab0: 20 61 4d 61 70 5b 69 5d 2e 74 6f 4c 61 73 74 20 aMap[i].toLast
3ac0: 2d 20 31 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a - 1;. }.}../*.*
3ad0: 2a 20 54 72 61 6e 73 6c 61 74 65 20 61 6e 20 69 * Translate an i
3ae0: 6e 64 65 78 20 69 6e 74 6f 20 61 20 66 69 6c 65 ndex into a file
3af0: 20 75 73 69 6e 67 20 61 20 6d 61 70 70 69 6e 67 using a mapping
3b00: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 61 70 70 ..**.** The mapp
3b10: 69 6e 67 20 22 70 22 20 73 68 6f 77 73 20 68 6f ing "p" shows ho
3b20: 77 20 62 6c 6f 63 6b 73 20 69 6e 20 74 68 65 20 w blocks in the
3b30: 69 6e 70 75 74 20 66 69 6c 65 20 6d 61 70 20 69 input file map i
3b40: 6e 74 6f 20 62 6c 6f 63 6b 73 0a 2a 2a 20 6f 66 nto blocks.** of
3b50: 20 74 68 65 20 6f 75 74 70 75 74 20 66 69 6c 65 the output file
3b60: 2e 20 20 54 68 65 20 69 6e 64 65 78 20 69 46 72 . The index iFr
3b70: 6f 6d 20 69 73 20 61 6e 20 69 6e 64 65 78 20 69 om is an index i
3b80: 6e 74 6f 20 74 68 65 20 69 6e 70 75 74 20 66 69 nto the input fi
3b90: 6c 65 2e 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74 le..** This rout
3ba0: 69 6e 65 20 72 65 74 75 72 6e 73 20 74 68 65 20 ine returns the
3bb0: 69 6e 64 65 78 20 69 6e 74 6f 20 74 68 65 20 6f index into the o
3bc0: 75 74 70 75 74 20 66 69 6c 65 20 6f 66 20 74 68 utput file of th
3bd0: 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 0a e corresponding.
3be0: 2a 2a 20 63 68 61 72 61 63 74 65 72 2e 0a 2a 2a ** character..**
3bf0: 0a 2a 2a 20 49 66 20 70 49 6e 73 65 72 74 65 64 .** If pInserted
3c00: 21 3d 30 20 61 6e 64 20 69 46 72 6f 6d 20 70 6f !=0 and iFrom po
3c10: 69 6e 74 73 20 74 6f 20 74 68 65 20 6c 61 73 74 ints to the last
3c20: 20 63 68 61 72 61 63 74 65 72 20 62 65 66 6f 72 character befor
3c30: 65 20 61 0a 2a 2a 20 69 6e 73 65 72 74 20 69 6e e a.** insert in
3c40: 20 74 68 65 20 6f 75 74 70 75 74 20 66 69 6c 65 the output file
3c50: 2c 20 74 68 65 6e 20 74 68 65 20 72 65 74 75 72 , then the retur
3c60: 6e 20 76 61 6c 75 65 20 69 73 20 61 64 6a 75 73 n value is adjus
3c70: 74 65 64 20 66 6f 72 77 61 72 64 0a 2a 2a 20 73 ted forward.** s
3c80: 6f 20 74 68 61 74 20 69 74 20 70 6f 69 6e 74 73 o that it points
3c90: 20 74 6f 20 74 68 65 20 65 6e 64 20 6f 66 20 74 to the end of t
3ca0: 68 65 20 69 6e 73 65 72 74 69 6f 6e 20 61 6e 64 he insertion and
3cb0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a the number of.*
3cc0: 2a 20 62 79 74 65 73 20 69 6e 73 65 72 74 65 64 * bytes inserted
3cd0: 20 69 73 20 77 72 69 74 74 65 6e 20 69 6e 74 6f is written into
3ce0: 20 2a 70 49 6e 73 65 72 74 65 64 2e 20 20 49 66 *pInserted. If
3cf0: 20 70 49 6e 73 65 72 74 65 64 3d 3d 30 20 74 68 pInserted==0 th
3d00: 65 6e 0a 2a 2a 20 69 46 72 6f 6d 20 61 6c 77 61 en.** iFrom alwa
3d10: 79 73 20 6d 61 70 73 20 64 69 72 65 63 74 6c 79 ys maps directly
3d20: 20 69 6e 20 74 68 65 20 63 6f 72 72 65 73 70 6f in the correspo
3d30: 6e 64 69 6e 67 20 6f 75 74 70 75 74 20 66 69 6c nding output fil
3d40: 65 0a 2a 2a 20 69 6e 64 65 78 20 72 65 67 61 72 e.** index regar
3d50: 64 6c 65 73 73 20 6f 66 20 77 68 65 74 68 65 72 dless of whether
3d60: 20 6f 72 20 6e 6f 74 20 69 74 20 70 6f 69 6e 74 or not it point
3d70: 73 20 74 6f 20 74 68 65 20 6c 61 73 74 20 63 68 s to the last ch
3d80: 61 72 61 63 74 65 72 0a 2a 2a 20 62 65 66 6f 72 aracter.** befor
3d90: 65 20 61 6e 20 69 6e 73 65 72 74 69 6f 6e 2e 0a e an insertion..
3da0: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 4d 61 */.static int Ma
3db0: 70 70 69 6e 67 54 72 61 6e 73 6c 61 74 65 28 4d ppingTranslate(M
3dc0: 61 70 70 69 6e 67 20 2a 70 2c 20 69 6e 74 20 69 apping *p, int i
3dd0: 46 72 6f 6d 2c 20 69 6e 74 20 2a 70 49 6e 73 65 From, int *pInse
3de0: 72 74 65 64 29 7b 0a 20 20 69 6e 74 20 69 3b 0a rted){. int i;.
3df0: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 2d 3e for(i=0; i<p->
3e00: 6e 55 73 65 64 3b 20 69 2b 2b 29 7b 0a 20 20 20 nUsed; i++){.
3e10: 20 69 66 28 20 69 46 72 6f 6d 3e 70 2d 3e 61 4d if( iFrom>p->aM
3e20: 61 70 5b 69 5d 2e 66 72 6f 6d 4c 61 73 74 20 29 ap[i].fromLast )
3e30: 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 69 continue;. i
3e40: 66 28 20 69 46 72 6f 6d 3c 3d 70 2d 3e 61 4d 61 f( iFrom<=p->aMa
3e50: 70 5b 69 5d 2e 66 72 6f 6d 46 69 72 73 74 20 29 p[i].fromFirst )
3e60: 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 70 {. return p
3e70: 2d 3e 61 4d 61 70 5b 69 5d 2e 74 6f 46 69 72 73 ->aMap[i].toFirs
3e80: 74 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 t;. }. if(
3e90: 20 70 49 6e 73 65 72 74 65 64 20 26 26 20 69 46 pInserted && iF
3ea0: 72 6f 6d 3d 3d 70 2d 3e 61 4d 61 70 5b 69 5d 2e rom==p->aMap[i].
3eb0: 66 72 6f 6d 4c 61 73 74 20 29 7b 0a 20 20 20 20 fromLast ){.
3ec0: 20 20 69 6e 74 20 6e 20 3d 20 70 2d 3e 61 4d 61 int n = p->aMa
3ed0: 70 5b 69 5d 2e 6e 45 78 74 72 61 3b 0a 20 20 20 p[i].nExtra;.
3ee0: 20 20 20 2a 70 49 6e 73 65 72 74 65 64 20 3d 20 *pInserted =
3ef0: 6e 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 n;. return
3f00: 70 2d 3e 61 4d 61 70 5b 69 5d 2e 74 6f 4c 61 73 p->aMap[i].toLas
3f10: 74 20 2b 20 6e 3b 0a 20 20 20 20 7d 65 6c 73 65 t + n;. }else
3f20: 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 70 {. return p
3f30: 2d 3e 61 4d 61 70 5b 69 5d 2e 74 6f 46 69 72 73 ->aMap[i].toFirs
3f40: 74 20 2b 20 69 46 72 6f 6d 20 2d 20 70 2d 3e 61 t + iFrom - p->a
3f50: 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 72 73 74 Map[i].fromFirst
3f60: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 2d ;. }. }. i-
3f70: 2d 3b 0a 20 20 72 65 74 75 72 6e 20 70 2d 3e 61 -;. return p->a
3f80: 4d 61 70 5b 69 5d 2e 74 6f 4c 61 73 74 20 2b 20 Map[i].toLast +
3f90: 70 2d 3e 61 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 p->aMap[i].nExtr
3fa0: 61 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 44 6f 20 61 a;.}../*.** Do a
3fb0: 20 74 68 72 65 65 2d 77 61 79 20 6d 65 72 67 65 three-way merge
3fc0: 2e 20 20 49 6e 69 74 69 61 6c 69 7a 65 20 70 4f . Initialize pO
3fd0: 75 74 20 74 6f 20 63 6f 6e 74 61 69 6e 20 74 68 ut to contain th
3fe0: 65 20 72 65 73 75 6c 74 2e 0a 2a 2f 0a 76 6f 69 e result..*/.voi
3ff0: 64 20 62 6c 6f 62 5f 6d 65 72 67 65 28 42 6c 6f d blob_merge(Blo
4000: 62 20 2a 70 50 69 76 6f 74 2c 20 42 6c 6f 62 20 b *pPivot, Blob
4010: 2a 70 56 31 2c 20 42 6c 6f 62 20 2a 70 56 32 2c *pV1, Blob *pV2,
4020: 20 42 6c 6f 62 20 2a 70 4f 75 74 29 7b 0a 20 20 Blob *pOut){.
4030: 4d 61 70 70 69 6e 67 20 6d 61 70 31 2c 20 6d 61 Mapping map1, ma
4040: 70 32 2c 20 6d 61 70 33 3b 0a 20 20 69 6e 74 20 p2, map3;. int
4050: 69 2c 20 6a 3b 0a 20 20 63 6f 6e 73 74 20 63 68 i, j;. const ch
4060: 61 72 20 2a 7a 56 31 2c 20 2a 7a 56 32 3b 0a 20 ar *zV1, *zV2;.
4070: 20 62 6c 6f 62 5f 7a 65 72 6f 28 70 4f 75 74 29 blob_zero(pOut)
4080: 3b 0a 20 20 4d 61 70 70 69 6e 67 49 6e 69 74 28 ;. MappingInit(
4090: 0a 20 20 20 20 62 6c 6f 62 5f 62 75 66 66 65 72 . blob_buffer
40a0: 28 70 50 69 76 6f 74 29 2c 20 62 6c 6f 62 5f 73 (pPivot), blob_s
40b0: 69 7a 65 28 70 50 69 76 6f 74 29 2c 0a 20 20 20 ize(pPivot),.
40c0: 20 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 56 31 blob_buffer(pV1
40d0: 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 70 56 31 ), blob_size(pV1
40e0: 29 2c 0a 20 20 20 20 26 6d 61 70 31 29 3b 0a 20 ),. &map1);.
40f0: 20 4d 61 70 70 69 6e 67 53 6f 72 74 46 72 6f 6d MappingSortFrom
4100: 28 26 6d 61 70 31 29 3b 0a 20 20 44 45 42 55 47 (&map1);. DEBUG
4110: 31 28 20 0a 20 20 20 20 70 72 69 6e 74 66 28 22 1( . printf("
4120: 6d 61 70 31 2d 66 69 6e 61 6c 3a 5c 6e 22 29 3b map1-final:\n");
4130: 0a 20 20 20 20 4d 61 70 70 69 6e 67 50 72 69 6e . MappingPrin
4140: 74 28 26 6d 61 70 31 29 3b 0a 20 20 29 0a 20 20 t(&map1);. ).
4150: 4d 61 70 70 69 6e 67 49 6e 69 74 28 0a 20 20 20 MappingInit(.
4160: 20 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 50 69 blob_buffer(pPi
4170: 76 6f 74 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 vot), blob_size(
4180: 70 50 69 76 6f 74 29 2c 0a 20 20 20 20 62 6c 6f pPivot),. blo
4190: 62 5f 62 75 66 66 65 72 28 70 56 32 29 2c 20 62 b_buffer(pV2), b
41a0: 6c 6f 62 5f 73 69 7a 65 28 70 56 32 29 2c 0a 20 lob_size(pV2),.
41b0: 20 20 20 26 6d 61 70 32 29 3b 0a 20 20 44 45 42 &map2);. DEB
41c0: 55 47 31 28 0a 20 20 20 20 70 72 69 6e 74 66 28 UG1(. printf(
41d0: 22 6d 61 70 32 2d 66 69 6e 61 6c 3a 5c 6e 22 29 "map2-final:\n")
41e0: 3b 0a 20 20 20 20 4d 61 70 70 69 6e 67 50 72 69 ;. MappingPri
41f0: 6e 74 28 26 6d 61 70 32 29 3b 0a 20 20 29 0a 20 nt(&map2);. ).
4200: 20 4d 61 70 70 69 6e 67 49 6e 69 74 28 0a 20 20 MappingInit(.
4210: 20 20 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 56 blob_buffer(pV
4220: 31 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 70 56 1), blob_size(pV
4230: 31 29 2c 0a 20 20 20 20 62 6c 6f 62 5f 62 75 66 1),. blob_buf
4240: 66 65 72 28 70 56 32 29 2c 20 62 6c 6f 62 5f 73 fer(pV2), blob_s
4250: 69 7a 65 28 70 56 32 29 2c 0a 20 20 20 20 26 6d ize(pV2),. &m
4260: 61 70 33 29 3b 0a 20 20 44 45 42 55 47 31 28 0a ap3);. DEBUG1(.
4270: 20 20 20 20 70 72 69 6e 74 66 28 22 6d 61 70 33 printf("map3
4280: 2d 66 69 6e 61 6c 3a 5c 6e 22 29 3b 0a 20 20 20 -final:\n");.
4290: 20 4d 61 70 70 69 6e 67 50 72 69 6e 74 28 26 6d MappingPrint(&m
42a0: 61 70 33 29 3b 0a 20 20 29 0a 20 20 7a 56 31 20 ap3);. ). zV1
42b0: 3d 20 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 56 = blob_buffer(pV
42c0: 31 29 3b 0a 20 20 7a 56 32 20 3d 20 62 6c 6f 62 1);. zV2 = blob
42d0: 5f 62 75 66 66 65 72 28 70 56 32 29 3b 0a 20 20 _buffer(pV2);.
42e0: 69 66 28 20 6d 61 70 31 2e 61 4d 61 70 5b 30 5d if( map1.aMap[0]
42f0: 2e 74 6f 46 69 72 73 74 3e 30 20 29 7b 0a 20 20 .toFirst>0 ){.
4300: 20 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f blob_append(pO
4310: 75 74 2c 20 7a 56 31 2c 20 6d 61 70 31 2e 61 4d ut, zV1, map1.aM
4320: 61 70 5b 30 5d 2e 74 6f 46 69 72 73 74 29 3b 0a ap[0].toFirst);.
4330: 20 20 20 20 44 45 42 55 47 31 28 20 70 72 69 6e DEBUG1( prin
4340: 74 66 28 22 49 4e 53 45 52 54 20 25 64 20 62 79 tf("INSERT %d by
4350: 74 65 73 20 66 72 6f 6d 20 56 31 5b 30 2e 2e 25 tes from V1[0..%
4360: 64 5d 5c 6e 22 2c 0a 20 20 20 20 20 20 20 20 20 d]\n",.
4370: 20 20 20 6d 61 70 31 2e 61 4d 61 70 5b 30 5d 2e map1.aMap[0].
4380: 74 6f 46 69 72 73 74 2c 20 6d 61 70 31 2e 61 4d toFirst, map1.aM
4390: 61 70 5b 30 5d 2e 74 6f 46 69 72 73 74 2d 31 29 ap[0].toFirst-1)
43a0: 3b 20 29 0a 20 20 7d 0a 20 20 69 66 28 20 6d 61 ; ). }. if( ma
43b0: 70 32 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 69 72 p2.aMap[0].toFir
43c0: 73 74 3e 30 20 29 7b 0a 20 20 20 20 62 6c 6f 62 st>0 ){. blob
43d0: 5f 61 70 70 65 6e 64 28 70 4f 75 74 2c 20 7a 56 _append(pOut, zV
43e0: 32 2c 20 6d 61 70 32 2e 61 4d 61 70 5b 30 5d 2e 2, map2.aMap[0].
43f0: 74 6f 46 69 72 73 74 29 3b 0a 20 20 20 20 44 45 toFirst);. DE
4400: 42 55 47 31 28 20 70 72 69 6e 74 66 28 22 49 4e BUG1( printf("IN
4410: 53 45 52 54 20 25 64 20 62 79 74 65 73 20 66 72 SERT %d bytes fr
4420: 6f 6d 20 56 32 5b 30 2e 2e 25 64 5d 5c 6e 22 2c om V2[0..%d]\n",
4430: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6d 61 70 . map
4440: 32 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 69 72 73 2.aMap[0].toFirs
4450: 74 2c 20 6d 61 70 32 2e 61 4d 61 70 5b 30 5d 2e t, map2.aMap[0].
4460: 74 6f 46 69 72 73 74 2d 31 29 3b 20 29 0a 20 20 toFirst-1); ).
4470: 7d 0a 20 20 66 6f 72 28 69 3d 6a 3d 30 3b 20 69 }. for(i=j=0; i
4480: 3c 6d 61 70 32 2e 6e 55 73 65 64 3b 20 69 2b 2b <map2.nUsed; i++
4490: 29 7b 0a 20 20 20 20 69 6e 74 20 69 46 69 72 73 ){. int iFirs
44a0: 74 2c 20 69 4c 61 73 74 2c 20 6e 49 6e 73 65 72 t, iLast, nInser
44b0: 74 2c 20 69 54 61 69 6c 3b 0a 20 20 20 20 73 74 t, iTail;. st
44c0: 72 75 63 74 20 4d 61 70 70 69 6e 67 5f 65 6e 74 ruct Mapping_ent
44d0: 72 79 20 2a 70 20 3d 20 26 6d 61 70 32 2e 61 4d ry *p = &map2.aM
44e0: 61 70 5b 69 5d 3b 0a 20 20 20 20 77 68 69 6c 65 ap[i];. while
44f0: 28 20 6a 3c 6d 61 70 33 2e 6e 55 73 65 64 2d 31 ( j<map3.nUsed-1
4500: 20 26 26 20 6d 61 70 33 2e 61 4d 61 70 5b 6a 2b && map3.aMap[j+
4510: 31 5d 2e 74 6f 46 69 72 73 74 3e 70 2d 3e 74 6f 1].toFirst>p->to
4520: 46 69 72 73 74 20 29 7b 20 6a 2b 2b 3b 20 7d 0a First ){ j++; }.
4530: 20 20 20 20 44 45 42 55 47 31 28 0a 20 20 20 20 DEBUG1(.
4540: 20 20 70 72 69 6e 74 66 28 22 6d 61 70 32 3a 20 printf("map2:
4550: 25 36 64 2e 2e 25 2d 36 64 20 25 36 64 2e 2e 25 %6d..%-6d %6d..%
4560: 2d 36 64 20 20 25 64 5c 6e 22 2c 0a 20 20 20 20 -6d %d\n",.
4570: 20 20 20 20 70 2d 3e 66 72 6f 6d 46 69 72 73 74 p->fromFirst
4580: 2c 20 70 2d 3e 66 72 6f 6d 4c 61 73 74 2c 20 70 , p->fromLast, p
4590: 2d 3e 74 6f 46 69 72 73 74 2c 20 70 2d 3e 74 6f ->toFirst, p->to
45a0: 4c 61 73 74 2c 20 70 2d 3e 6e 45 78 74 72 61 29 Last, p->nExtra)
45b0: 3b 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 ;. printf("
45c0: 6d 61 70 33 3a 20 20 20 20 20 20 20 6a 3d 25 2d map3: j=%-
45d0: 36 64 20 25 36 64 2e 2e 25 2d 36 64 5c 6e 22 2c 6d %6d..%-6d\n",
45e0: 20 6a 2c 20 6d 61 70 33 2e 61 4d 61 70 5b 6a 5d j, map3.aMap[j]
45f0: 2e 74 6f 46 69 72 73 74 2c 0a 20 20 20 20 20 20 .toFirst,.
4600: 20 20 6d 61 70 33 2e 61 4d 61 70 5b 6a 5d 2e 74 map3.aMap[j].t
4610: 6f 4c 61 73 74 29 3b 0a 20 20 20 20 29 3b 0a 20 oLast);. );.
4620: 20 20 20 69 54 61 69 6c 20 3d 20 70 2d 3e 74 6f iTail = p->to
4630: 4c 61 73 74 20 2b 20 70 2d 3e 6e 45 78 74 72 61 Last + p->nExtra
4640: 3b 0a 20 20 20 20 69 66 28 20 69 3c 6d 61 70 32 ;. if( i<map2
4650: 2e 6e 55 73 65 64 2d 31 20 26 26 0a 20 20 20 20 .nUsed-1 &&.
4660: 20 20 20 20 20 6d 61 70 33 2e 61 4d 61 70 5b 6a map3.aMap[j
4670: 5d 2e 74 6f 46 69 72 73 74 3c 3d 70 2d 3e 74 6f ].toFirst<=p->to
4680: 46 69 72 73 74 20 26 26 20 6d 61 70 33 2e 61 4d First && map3.aM
4690: 61 70 5b 6a 5d 2e 74 6f 4c 61 73 74 3e 3d 69 54 ap[j].toLast>=iT
46a0: 61 69 6c 20 29 7b 0a 20 20 20 20 20 20 62 6c 6f ail ){. blo
46b0: 62 5f 61 70 70 65 6e 64 28 70 4f 75 74 2c 20 26 b_append(pOut, &
46c0: 7a 56 32 5b 70 2d 3e 74 6f 46 69 72 73 74 5d 2c zV2[p->toFirst],
46d0: 20 69 54 61 69 6c 20 2d 20 70 2d 3e 74 6f 46 69 iTail - p->toFi
46e0: 72 73 74 20 2b 20 31 29 3b 0a 20 20 20 20 20 20 rst + 1);.
46f0: 44 45 42 55 47 31 28 0a 20 20 20 20 20 20 20 20 DEBUG1(.
4700: 70 72 69 6e 74 66 28 22 43 4f 50 59 20 25 64 20 printf("COPY %d
4710: 62 79 74 65 73 20 66 72 6f 6d 20 56 32 5b 25 64 bytes from V2[%d
4720: 2e 2e 25 64 5d 5c 6e 22 2c 20 69 54 61 69 6c 20 ..%d]\n", iTail
4730: 2d 20 70 2d 3e 74 6f 46 69 72 73 74 2b 31 2c 0a - p->toFirst+1,.
4740: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
4750: 70 2d 3e 74 6f 46 69 72 73 74 2c 20 69 54 61 69 p->toFirst, iTai
4760: 6c 29 3b 0a 20 20 20 20 20 20 29 0a 20 20 20 20 l);. ).
4770: 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 20 20 20 20 continue;.
4780: 7d 0a 20 20 20 20 69 46 69 72 73 74 20 3d 20 4d }. iFirst = M
4790: 61 70 70 69 6e 67 54 72 61 6e 73 6c 61 74 65 28 appingTranslate(
47a0: 26 6d 61 70 31 2c 20 70 2d 3e 66 72 6f 6d 46 69 &map1, p->fromFi
47b0: 72 73 74 2c 20 30 29 3b 0a 20 20 20 20 69 4c 61 rst, 0);. iLa
47c0: 73 74 20 3d 20 4d 61 70 70 69 6e 67 54 72 61 6e st = MappingTran
47d0: 73 6c 61 74 65 28 26 6d 61 70 31 2c 20 70 2d 3e slate(&map1, p->
47e0: 66 72 6f 6d 4c 61 73 74 2c 20 26 6e 49 6e 73 65 fromLast, &nInse
47f0: 72 74 29 3b 0a 20 20 20 20 62 6c 6f 62 5f 61 70 rt);. blob_ap
4800: 70 65 6e 64 28 70 4f 75 74 2c 20 26 7a 56 31 5b pend(pOut, &zV1[
4810: 69 46 69 72 73 74 5d 2c 20 69 4c 61 73 74 20 2d iFirst], iLast -
4820: 20 69 46 69 72 73 74 20 2b 20 31 29 3b 0a 20 20 iFirst + 1);.
4830: 20 20 44 45 42 55 47 31 28 0a 20 20 20 20 20 20 DEBUG1(.
4840: 70 72 69 6e 74 66 28 22 43 4f 50 59 20 25 64 20 printf("COPY %d
4850: 62 79 74 65 73 20 66 72 6f 6d 20 56 31 5b 25 64 bytes from V1[%d
4860: 2e 2e 25 64 5d 5c 6e 22 2c 20 69 4c 61 73 74 2d ..%d]\n", iLast-
4870: 69 46 69 72 73 74 2b 31 2c 20 69 46 69 72 73 74 iFirst+1, iFirst
4880: 2c 20 69 4c 61 73 74 29 3b 0a 20 20 20 20 29 0a , iLast);. ).
4890: 20 20 20 20 69 66 28 20 70 2d 3e 6e 45 78 74 72 if( p->nExtr
48a0: 61 3e 30 20 29 7b 0a 20 20 20 20 20 20 69 66 28 a>0 ){. if(
48b0: 20 70 2d 3e 6e 45 78 74 72 61 3d 3d 6e 49 6e 73 p->nExtra==nIns
48c0: 65 72 74 20 26 26 0a 20 20 20 20 20 20 20 20 20 ert &&.
48d0: 20 6d 65 6d 63 6d 70 28 26 7a 56 32 5b 70 2d 3e memcmp(&zV2[p->
48e0: 74 6f 4c 61 73 74 2b 31 5d 2c 20 26 7a 56 31 5b toLast+1], &zV1[
48f0: 69 4c 61 73 74 2d 6e 49 6e 73 65 72 74 2b 31 5d iLast-nInsert+1]
4900: 2c 20 6e 49 6e 73 65 72 74 29 3d 3d 30 20 29 7b , nInsert)==0 ){
4910: 0a 20 20 20 20 20 20 20 20 2f 2a 20 4f 6d 69 74 . /* Omit
4920: 20 61 20 64 75 70 6c 69 63 61 74 65 20 69 6e 73 a duplicate ins
4930: 65 72 74 20 2a 2f 0a 20 20 20 20 20 20 20 20 44 ert */. D
4940: 45 42 55 47 31 28 20 70 72 69 6e 74 66 28 22 4f EBUG1( printf("O
4950: 4d 49 54 20 64 75 70 6c 69 63 61 74 65 20 69 6e MIT duplicate in
4960: 73 65 72 74 5c 6e 22 29 3b 20 29 0a 20 20 20 20 sert\n"); ).
4970: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 }else{.
4980: 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 blob_append(pOu
4990: 74 2c 20 26 7a 56 32 5b 70 2d 3e 74 6f 4c 61 73 t, &zV2[p->toLas
49a0: 74 2b 31 5d 2c 20 70 2d 3e 6e 45 78 74 72 61 29 t+1], p->nExtra)
49b0: 3b 0a 20 20 20 20 20 20 20 20 44 45 42 55 47 31 ;. DEBUG1
49c0: 28 0a 20 20 20 20 20 20 20 20 20 20 70 72 69 6e (. prin
49d0: 74 66 28 22 49 4e 53 45 52 54 20 25 64 20 62 79 tf("INSERT %d by
49e0: 74 65 73 20 66 72 6f 6d 20 56 32 5b 25 64 2e 2e tes from V2[%d..
49f0: 25 64 5d 5c 6e 22 2c 0a 20 20 20 20 20 20 20 20 %d]\n",.
4a00: 20 20 20 20 20 20 20 20 20 20 70 2d 3e 6e 45 78 p->nEx
4a10: 74 72 61 2c 20 70 2d 3e 74 6f 4c 61 73 74 2b 31 tra, p->toLast+1
4a20: 2c 20 70 2d 3e 74 6f 4c 61 73 74 2b 70 2d 3e 6e , p->toLast+p->n
4a30: 45 78 74 72 61 29 3b 0a 20 20 20 20 20 20 20 20 Extra);.
4a40: 29 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a ). }. }.
4a50: 20 20 7d 0a 20 20 4d 61 70 70 69 6e 67 43 6c 65 }. MappingCle
4a60: 61 72 28 26 6d 61 70 31 29 3b 0a 20 20 4d 61 70 ar(&map1);. Map
4a70: 70 69 6e 67 43 6c 65 61 72 28 26 6d 61 70 32 29 pingClear(&map2)
4a80: 3b 0a 20 20 4d 61 70 70 69 6e 67 43 6c 65 61 72 ;. MappingClear
4a90: 28 26 6d 61 70 33 29 3b 0a 7d 0a 0a 2f 2a 0a 2a (&map3);.}../*.*
4aa0: 2a 20 43 4f 4d 4d 41 4e 44 3a 20 20 74 65 73 74 * COMMAND: test
4ab0: 2d 33 2d 77 61 79 2d 6d 65 72 67 65 0a 2a 2a 0a -3-way-merge.**.
4ac0: 2a 2a 20 43 6f 6d 62 69 6e 65 20 63 68 61 6e 67 ** Combine chang
4ad0: 65 20 69 6e 20 67 6f 69 6e 67 20 66 72 6f 6d 20 e in going from
4ae0: 50 49 56 4f 54 2d 3e 56 45 52 53 49 4f 4e 31 20 PIVOT->VERSION1
4af0: 77 69 74 68 20 74 68 65 20 63 68 61 6e 67 65 20 with the change
4b00: 67 6f 69 6e 67 0a 2a 2a 20 66 72 6f 6d 20 50 49 going.** from PI
4b10: 56 4f 54 2d 3e 56 45 52 53 49 4f 4e 32 20 61 6e VOT->VERSION2 an
4b20: 64 20 77 72 69 74 65 20 74 68 65 20 63 6f 6d 62 d write the comb
4b30: 69 6e 65 64 20 63 68 61 6e 67 65 73 20 69 6e 74 ined changes int
4b40: 6f 20 4d 45 52 47 45 44 2e 0a 2a 2f 0a 76 6f 69 o MERGED..*/.voi
4b50: 64 20 64 65 6c 74 61 5f 33 77 61 79 6d 65 72 67 d delta_3waymerg
4b60: 65 5f 63 6d 64 28 76 6f 69 64 29 7b 0a 20 20 42 e_cmd(void){. B
4b70: 6c 6f 62 20 70 69 76 6f 74 2c 20 76 31 2c 20 76 lob pivot, v1, v
4b80: 32 2c 20 6d 65 72 67 65 64 3b 0a 20 20 69 66 28 2, merged;. if(
4b90: 20 67 2e 61 72 67 63 21 3d 36 20 29 7b 0a 20 20 g.argc!=6 ){.
4ba0: 20 20 66 70 72 69 6e 74 66 28 73 74 64 65 72 72 fprintf(stderr
4bb0: 2c 22 55 73 61 67 65 3a 20 25 73 20 25 73 20 50 ,"Usage: %s %s P
4bc0: 49 56 4f 54 20 56 31 20 56 32 20 4d 45 52 47 45 IVOT V1 V2 MERGE
4bd0: 44 5c 6e 22 2c 20 67 2e 61 72 67 76 5b 30 5d 2c D\n", g.argv[0],
4be0: 20 67 2e 61 72 67 76 5b 31 5d 29 3b 0a 20 20 20 g.argv[1]);.
4bf0: 20 65 78 69 74 28 31 29 3b 0a 20 20 7d 0a 20 20 exit(1);. }.
4c00: 69 66 28 20 62 6c 6f 62 5f 72 65 61 64 5f 66 72 if( blob_read_fr
4c10: 6f 6d 5f 66 69 6c 65 28 26 70 69 76 6f 74 2c 20 om_file(&pivot,
4c20: 67 2e 61 72 67 76 5b 32 5d 29 3c 30 20 29 7b 0a g.argv[2])<0 ){.
4c30: 20 20 20 20 66 70 72 69 6e 74 66 28 73 74 64 65 fprintf(stde
4c40: 72 72 2c 22 63 61 6e 6e 6f 74 20 72 65 61 64 20 rr,"cannot read
4c50: 25 73 5c 6e 22 2c 20 67 2e 61 72 67 76 5b 32 5d %s\n", g.argv[2]
4c60: 29 3b 0a 20 20 20 20 65 78 69 74 28 31 29 3b 0a );. exit(1);.
4c70: 20 20 7d 0a 20 20 69 66 28 20 62 6c 6f 62 5f 72 }. if( blob_r
4c80: 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 76 ead_from_file(&v
4c90: 31 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3c 30 20 1, g.argv[3])<0
4ca0: 29 7b 0a 20 20 20 20 66 70 72 69 6e 74 66 28 73 ){. fprintf(s
4cb0: 74 64 65 72 72 2c 22 63 61 6e 6e 6f 74 20 72 65 tderr,"cannot re
4cc0: 61 64 20 25 73 5c 6e 22 2c 20 67 2e 61 72 67 76 ad %s\n", g.argv
4cd0: 5b 33 5d 29 3b 0a 20 20 20 20 65 78 69 74 28 31 [3]);. exit(1
4ce0: 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20 62 6c 6f );. }. if( blo
4cf0: 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 b_read_from_file
4d00: 28 26 76 32 2c 20 67 2e 61 72 67 76 5b 34 5d 29 (&v2, g.argv[4])
4d10: 3c 30 20 29 7b 0a 20 20 20 20 66 70 72 69 6e 74 <0 ){. fprint
4d20: 66 28 73 74 64 65 72 72 2c 22 63 61 6e 6e 6f 74 f(stderr,"cannot
4d30: 20 72 65 61 64 20 25 73 5c 6e 22 2c 20 67 2e 61 read %s\n", g.a
4d40: 72 67 76 5b 34 5d 29 3b 0a 20 20 20 20 65 78 69 rgv[4]);. exi
4d50: 74 28 31 29 3b 0a 20 20 7d 0a 20 20 62 6c 6f 62 t(1);. }. blob
4d60: 5f 6d 65 72 67 65 28 26 70 69 76 6f 74 2c 20 26 _merge(&pivot, &
4d70: 76 31 2c 20 26 76 32 2c 20 26 6d 65 72 67 65 64 v1, &v2, &merged
4d80: 29 3b 0a 20 20 69 66 28 20 62 6c 6f 62 5f 77 72 );. if( blob_wr
4d90: 69 74 65 5f 74 6f 5f 66 69 6c 65 28 26 6d 65 72 ite_to_file(&mer
4da0: 67 65 64 2c 20 67 2e 61 72 67 76 5b 35 5d 29 3c ged, g.argv[5])<
4db0: 62 6c 6f 62 5f 73 69 7a 65 28 26 6d 65 72 67 65 blob_size(&merge
4dc0: 64 29 20 29 7b 0a 20 20 20 20 66 70 72 69 6e 74 d) ){. fprint
4dd0: 66 28 73 74 64 65 72 72 2c 22 63 61 6e 6e 6f 74 f(stderr,"cannot
4de0: 20 77 72 69 74 65 20 25 73 5c 6e 22 2c 20 67 2e write %s\n", g.
4df0: 61 72 67 76 5b 34 5d 29 3b 0a 20 20 20 20 65 78 argv[4]);. ex
4e00: 69 74 28 31 29 3b 0a 20 20 7d 0a 20 20 62 6c 6f it(1);. }. blo
4e10: 62 5f 72 65 73 65 74 28 26 70 69 76 6f 74 29 3b b_reset(&pivot);
4e20: 0a 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 76 . blob_reset(&v
4e30: 31 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 73 65 74 1);. blob_reset
4e40: 28 26 76 32 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 (&v2);. blob_re
4e50: 73 65 74 28 26 6d 65 72 67 65 64 29 3b 0a 7d 0a set(&merged);.}.
4e60: 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 3a ../*.** COMMAND:
4e70: 20 20 74 65 73 74 2d 6d 61 70 70 69 6e 67 0a 2a test-mapping.*
4e80: 2f 0a 76 6f 69 64 20 6d 61 70 70 69 6e 67 5f 74 /.void mapping_t
4e90: 65 73 74 28 76 6f 69 64 29 7b 0a 20 20 69 6e 74 est(void){. int
4ea0: 20 69 3b 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 i;. const char
4eb0: 20 2a 7a 61 2c 20 2a 7a 62 3b 0a 20 20 42 6c 6f *za, *zb;. Blo
4ec0: 62 20 61 2c 20 62 3b 0a 20 20 4d 61 70 70 69 6e b a, b;. Mappin
4ed0: 67 20 6d 61 70 3b 0a 20 20 69 66 28 20 67 2e 61 g map;. if( g.a
4ee0: 72 67 63 21 3d 34 20 29 7b 0a 20 20 20 20 75 73 rgc!=4 ){. us
4ef0: 61 67 65 28 22 46 49 4c 45 31 20 46 49 4c 45 32 age("FILE1 FILE2
4f00: 22 29 3b 0a 20 20 7d 0a 20 20 62 6c 6f 62 5f 72 ");. }. blob_r
4f10: 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 61 ead_from_file(&a
4f20: 2c 20 67 2e 61 72 67 76 5b 32 5d 29 3b 0a 20 20 , g.argv[2]);.
4f30: 62 6c 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 blob_read_from_f
4f40: 69 6c 65 28 26 62 2c 20 67 2e 61 72 67 76 5b 33 ile(&b, g.argv[3
4f50: 5d 29 3b 0a 20 20 6d 65 6d 73 65 74 28 26 6d 61 ]);. memset(&ma
4f60: 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 6d 61 70 p, 0, sizeof(map
4f70: 29 29 3b 0a 20 20 4d 61 70 70 69 6e 67 49 6e 69 ));. MappingIni
4f80: 74 28 62 6c 6f 62 5f 62 75 66 66 65 72 28 26 61 t(blob_buffer(&a
4f90: 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 26 61 29 ), blob_size(&a)
4fa0: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,.
4fb0: 62 6c 6f 62 5f 62 75 66 66 65 72 28 26 62 29 2c blob_buffer(&b),
4fc0: 20 62 6c 6f 62 5f 73 69 7a 65 28 26 62 29 2c 0a blob_size(&b),.
4fd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 26 6d &m
4fe0: 61 70 29 3b 0a 20 20 44 45 42 55 47 31 28 0a 20 ap);. DEBUG1(.
4ff0: 20 20 20 70 72 69 6e 74 66 28 22 6d 61 70 2d 66 printf("map-f
5000: 69 6e 61 6c 3a 5c 6e 22 29 3b 0a 20 20 20 20 4d inal:\n");. M
5010: 61 70 70 69 6e 67 50 72 69 6e 74 28 26 6d 61 70 appingPrint(&map
5020: 29 3b 0a 20 20 29 0a 20 20 7a 61 20 3d 20 62 6c );. ). za = bl
5030: 6f 62 5f 62 75 66 66 65 72 28 26 61 29 3b 0a 20 ob_buffer(&a);.
5040: 20 7a 62 20 3d 20 62 6c 6f 62 5f 62 75 66 66 65 zb = blob_buffe
5050: 72 28 26 62 29 3b 0a 20 20 66 6f 72 28 69 3d 30 r(&b);. for(i=0
5060: 3b 20 69 3c 6d 61 70 2e 6e 55 73 65 64 3b 20 69 ; i<map.nUsed; i
5070: 2b 2b 29 7b 0a 20 20 20 20 70 72 69 6e 74 66 28 ++){. printf(
5080: 22 3d 3d 3d 3d 3d 3d 3d 20 25 36 64 2e 2e 25 2d "======= %6d..%-
5090: 36 64 20 25 36 64 2e 2e 25 2d 36 64 20 25 64 5c 6d %6d..%-6d %d\
50a0: 6e 22 2c 20 0a 20 20 20 20 20 20 20 20 20 6d 61 n", . ma
50b0: 70 2e 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 p.aMap[i].fromFi
50c0: 72 73 74 2c 20 6d 61 70 2e 61 4d 61 70 5b 69 5d rst, map.aMap[i]
50d0: 2e 66 72 6f 6d 4c 61 73 74 2c 0a 20 20 20 20 20 .fromLast,.
50e0: 20 20 20 20 6d 61 70 2e 61 4d 61 70 5b 69 5d 2e map.aMap[i].
50f0: 74 6f 46 69 72 73 74 2c 20 6d 61 70 2e 61 4d 61 toFirst, map.aMa
5100: 70 5b 69 5d 2e 74 6f 4c 61 73 74 2c 0a 20 20 20 p[i].toLast,.
5110: 20 20 20 20 20 20 6d 61 70 2e 61 4d 61 70 5b 69 map.aMap[i
5120: 5d 2e 6e 45 78 74 72 61 29 3b 0a 20 20 20 20 70 ].nExtra);. p
5130: 72 69 6e 74 66 28 22 25 2e 2a 73 5c 6e 22 2c 20 rintf("%.*s\n",
5140: 6d 61 70 2e 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d map.aMap[i].from
5150: 4c 61 73 74 20 2d 20 6d 61 70 2e 61 4d 61 70 5b Last - map.aMap[
5160: 69 5d 2e 66 72 6f 6d 46 69 72 73 74 20 2b 20 31 i].fromFirst + 1
5170: 2c 20 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 , .
5180: 20 20 20 20 20 20 20 20 26 7a 61 5b 6d 61 70 2e &za[map.
5190: 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 72 73 aMap[i].fromFirs
51a0: 74 5d 29 3b 0a 20 20 20 20 69 66 28 20 6d 61 70 t]);. if( map
51b0: 2e 61 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 61 20 .aMap[i].nExtra
51c0: 29 7b 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 ){. printf(
51d0: 22 3d 3d 3d 3d 3d 3d 3d 20 45 58 54 52 41 3a 5c "======= EXTRA:\
51e0: 6e 22 29 3b 0a 20 20 20 20 20 20 70 72 69 6e 74 n");. print
51f0: 66 28 22 25 2e 2a 73 5c 6e 22 2c 20 6d 61 70 2e f("%.*s\n", map.
5200: 61 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 61 2c 20 aMap[i].nExtra,
5210: 26 7a 62 5b 6d 61 70 2e 61 4d 61 70 5b 69 5d 2e &zb[map.aMap[i].
5220: 74 6f 4c 61 73 74 2b 31 5d 29 3b 0a 20 20 20 20 toLast+1]);.
5230: 7d 0a 20 20 7d 0a 7d 0a }. }.}.