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 30 0a 23 20 ge3.h"..#if 0.#
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 68 61 73 68 20 68 3b 0a 20 20 69 x;. hash h;. i
1c90: 6e 74 20 2a 63 6f 6c 6c 69 64 65 3b 0a 20 20 69 nt *collide;. i
1ca0: 6e 74 20 6f 72 69 67 4c 65 6e 4f 75 74 20 3d 20 nt origLenOut =
1cb0: 6c 65 6e 4f 75 74 3b 0a 20 20 73 74 72 75 63 74 lenOut;. struct
1cc0: 20 4d 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a Mapping_entry *
1cd0: 61 4d 61 70 3b 0a 20 20 69 6e 74 20 6c 61 6e 64 aMap;. int land
1ce0: 6d 61 72 6b 5b 4d 58 5f 4c 41 4e 44 4d 41 52 4b mark[MX_LANDMARK
1cf0: 5d 3b 0a 0a 20 20 2f 2a 0a 20 20 2a 2a 20 49 6e ];.. /*. ** In
1d00: 69 74 69 61 6c 69 7a 65 20 74 68 65 20 6d 61 70 itialize the map
1d10: 0a 20 20 2a 2f 0a 20 20 6d 65 6d 73 65 74 28 70 . */. memset(p
1d20: 4d 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 2a Map, 0, sizeof(*
1d30: 70 4d 61 70 29 29 3b 0a 0a 20 20 2f 2a 0a 20 20 pMap));.. /*.
1d40: 2a 2a 20 46 69 6e 64 20 63 6f 6d 6d 6f 6e 20 70 ** Find common p
1d50: 72 65 66 69 78 20 61 6e 64 20 73 75 66 66 69 78 refix and suffix
1d60: 0a 20 20 2a 2f 0a 20 20 69 66 28 20 6c 65 6e 53 . */. if( lenS
1d70: 72 63 3c 3d 4e 48 41 53 48 20 7c 7c 20 6c 65 6e rc<=NHASH || len
1d80: 4f 75 74 3c 3d 4e 48 41 53 48 20 29 7b 0a 20 20 Out<=NHASH ){.
1d90: 20 20 4d 61 70 70 69 6e 67 49 6e 73 65 72 74 28 MappingInsert(
1da0: 70 4d 61 70 2c 20 30 2c 20 30 2c 20 30 2c 20 30 pMap, 0, 0, 0, 0
1db0: 29 3b 0a 20 20 20 20 67 6f 74 6f 20 61 64 64 5f );. goto add_
1dc0: 6e 65 78 74 72 61 3b 0a 20 20 7d 0a 20 20 66 6f nextra;. }. fo
1dd0: 72 28 69 3d 30 3b 20 69 3c 6c 65 6e 53 72 63 20 r(i=0; i<lenSrc
1de0: 26 26 20 69 3c 6c 65 6e 4f 75 74 20 26 26 20 7a && i<lenOut && z
1df0: 53 72 63 5b 69 5d 3d 3d 7a 4f 75 74 5b 69 5d 3b Src[i]==zOut[i];
1e00: 20 69 2b 2b 29 7b 7d 0a 20 20 69 66 28 20 69 3e i++){}. if( i>
1e10: 3d 4e 48 41 53 48 20 29 7b 0a 20 20 20 20 4d 61 =NHASH ){. Ma
1e20: 70 70 69 6e 67 49 6e 73 65 72 74 28 70 4d 61 70 ppingInsert(pMap
1e30: 2c 20 30 2c 20 69 2d 31 2c 20 30 2c 20 69 2d 31 , 0, i-1, 0, i-1
1e40: 29 3b 0a 20 20 20 20 6c 65 6e 53 72 63 20 2d 3d );. lenSrc -=
1e50: 20 69 3b 0a 20 20 20 20 7a 53 72 63 20 2b 3d 20 i;. zSrc +=
1e60: 69 3b 0a 20 20 20 20 6c 65 6e 4f 75 74 20 2d 3d i;. lenOut -=
1e70: 20 69 3b 0a 20 20 20 20 7a 4f 75 74 20 2b 3d 20 i;. zOut +=
1e80: 69 3b 0a 20 20 20 20 69 66 28 20 6c 65 6e 53 72 i;. if( lenSr
1e90: 63 3c 3d 30 20 7c 7c 20 6c 65 6e 4f 75 74 3c 3d c<=0 || lenOut<=
1ea0: 30 20 29 20 67 6f 74 6f 20 61 64 64 5f 6e 65 78 0 ) goto add_nex
1eb0: 74 72 61 3b 0a 20 20 20 20 70 72 65 66 69 78 20 tra;. prefix
1ec0: 3d 20 69 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 = i;. }else{.
1ed0: 20 20 70 72 65 66 69 78 20 3d 20 30 3b 0a 20 20 prefix = 0;.
1ee0: 7d 0a 20 20 66 6f 72 28 69 3d 31 3b 20 69 3c 3d }. for(i=1; i<=
1ef0: 6c 65 6e 53 72 63 20 26 26 20 69 3c 3d 6c 65 6e lenSrc && i<=len
1f00: 4f 75 74 20 26 26 20 7a 53 72 63 5b 6c 65 6e 53 Out && zSrc[lenS
1f10: 72 63 2d 69 5d 3d 3d 7a 4f 75 74 5b 6c 65 6e 4f rc-i]==zOut[lenO
1f20: 75 74 2d 69 5d 3b 20 69 2b 2b 29 7b 7d 0a 20 20 ut-i]; i++){}.
1f30: 69 66 28 20 69 3e 4e 48 41 53 48 20 29 7b 0a 20 if( i>NHASH ){.
1f40: 20 20 20 4d 61 70 70 69 6e 67 49 6e 73 65 72 74 MappingInsert
1f50: 28 70 4d 61 70 2c 20 70 72 65 66 69 78 2b 6c 65 (pMap, prefix+le
1f60: 6e 53 72 63 2d 69 2b 31 2c 20 70 72 65 66 69 78 nSrc-i+1, prefix
1f70: 2b 6c 65 6e 53 72 63 2d 31 2c 0a 20 20 20 20 20 +lenSrc-1,.
1f80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1f90: 20 20 20 70 72 65 66 69 78 2b 6c 65 6e 4f 75 74 prefix+lenOut
1fa0: 2d 69 2b 31 2c 20 70 72 65 66 69 78 2b 6c 65 6e -i+1, prefix+len
1fb0: 4f 75 74 2d 31 29 3b 0a 20 20 20 20 6c 65 6e 53 Out-1);. lenS
1fc0: 72 63 20 2d 3d 20 69 3b 0a 20 20 20 20 6c 65 6e rc -= i;. len
1fd0: 4f 75 74 20 2d 3d 20 69 3b 0a 20 20 7d 0a 0a 20 Out -= i;. }..
1fe0: 20 2f 2a 20 49 66 20 74 68 65 20 73 6f 75 72 63 /* If the sourc
1ff0: 65 20 66 69 6c 65 20 69 73 20 76 65 72 79 20 73 e file is very s
2000: 6d 61 6c 6c 2c 20 69 74 20 6d 65 61 6e 73 20 74 mall, it means t
2010: 68 61 74 20 77 65 20 68 61 76 65 20 6e 6f 0a 20 hat we have no.
2020: 20 2a 2a 20 63 68 61 6e 63 65 20 6f 66 20 65 76 ** chance of ev
2030: 65 72 20 66 69 6e 64 69 6e 67 20 61 6e 79 20 6d er finding any m
2040: 61 74 63 68 65 73 2e 20 20 57 65 20 63 61 6e 20 atches. We can
2050: 6c 65 61 76 65 20 65 61 72 6c 79 2e 0a 20 20 2a leave early.. *
2060: 2f 0a 20 20 69 66 28 20 6c 65 6e 53 72 63 3c 3d /. if( lenSrc<=
2070: 4e 48 41 53 48 20 29 20 67 6f 74 6f 20 61 64 64 NHASH ) goto add
2080: 5f 6e 65 78 74 72 61 3b 0a 0a 20 20 2f 2a 20 43 _nextra;.. /* C
2090: 6f 6d 70 75 74 65 20 74 68 65 20 68 61 73 68 20 ompute the hash
20a0: 74 61 62 6c 65 20 75 73 65 64 20 74 6f 20 6c 6f table used to lo
20b0: 63 61 74 65 20 6d 61 74 63 68 69 6e 67 20 73 65 cate matching se
20c0: 63 74 69 6f 6e 73 20 69 6e 20 74 68 65 0a 20 20 ctions in the.
20d0: 2a 2a 20 73 6f 75 72 63 65 20 66 69 6c 65 2e 0a ** source file..
20e0: 20 20 2a 2f 0a 20 20 63 6f 6c 6c 69 64 65 20 3d */. collide =
20f0: 20 6d 61 6c 6c 6f 63 28 20 6c 65 6e 53 72 63 2a malloc( lenSrc*
2100: 73 69 7a 65 6f 66 28 69 6e 74 29 2f 4e 48 41 53 sizeof(int)/NHAS
2110: 48 20 29 3b 0a 20 20 69 66 28 20 63 6f 6c 6c 69 H );. if( colli
2120: 64 65 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a de==0 ) return;.
2130: 20 20 6d 65 6d 73 65 74 28 6c 61 6e 64 6d 61 72 memset(landmar
2140: 6b 2c 20 2d 31 2c 20 73 69 7a 65 6f 66 28 6c 61 k, -1, sizeof(la
2150: 6e 64 6d 61 72 6b 29 29 3b 0a 20 20 6d 65 6d 73 ndmark));. mems
2160: 65 74 28 63 6f 6c 6c 69 64 65 2c 20 2d 31 2c 20 et(collide, -1,
2170: 6c 65 6e 53 72 63 2a 73 69 7a 65 6f 66 28 69 6e lenSrc*sizeof(in
2180: 74 29 2f 4e 48 41 53 48 20 29 3b 0a 20 20 66 6f t)/NHASH );. fo
2190: 72 28 69 3d 30 3b 20 69 3c 6c 65 6e 53 72 63 2d r(i=0; i<lenSrc-
21a0: 4e 48 41 53 48 3b 20 69 2b 3d 4e 48 41 53 48 29 NHASH; i+=NHASH)
21b0: 7b 0a 20 20 20 20 69 6e 74 20 68 76 3b 0a 20 20 {. int hv;.
21c0: 20 20 68 61 73 68 5f 69 6e 69 74 28 26 68 2c 20 hash_init(&h,
21d0: 26 7a 53 72 63 5b 69 5d 29 3b 0a 20 20 20 20 68 &zSrc[i]);. h
21e0: 76 20 3d 20 68 61 73 68 5f 33 32 62 69 74 28 26 v = hash_32bit(&
21f0: 68 29 20 26 20 28 4d 58 5f 4c 41 4e 44 4d 41 52 h) & (MX_LANDMAR
2200: 4b 2d 31 29 3b 0a 20 20 20 20 63 6f 6c 6c 69 64 K-1);. collid
2210: 65 5b 69 2f 4e 48 41 53 48 5d 20 3d 20 6c 61 6e e[i/NHASH] = lan
2220: 64 6d 61 72 6b 5b 68 76 5d 3b 0a 20 20 20 20 6c dmark[hv];. l
2230: 61 6e 64 6d 61 72 6b 5b 68 76 5d 20 3d 20 69 2f andmark[hv] = i/
2240: 4e 48 41 53 48 3b 0a 20 20 7d 0a 0a 20 20 2f 2a NHASH;. }.. /*
2250: 20 42 65 67 69 6e 20 73 63 61 6e 6e 69 6e 67 20 Begin scanning
2260: 74 68 65 20 74 61 72 67 65 74 20 66 69 6c 65 20 the target file
2270: 61 6e 64 20 67 65 6e 65 72 61 74 69 6e 67 20 6d and generating m
2280: 61 70 70 69 6e 67 73 2e 20 20 49 6e 20 74 68 69 appings. In thi
2290: 73 0a 20 20 2a 2a 20 73 74 65 70 2c 20 77 65 20 s. ** step, we
22a0: 67 65 6e 65 72 61 74 65 20 61 73 20 6d 61 6e 79 generate as many
22b0: 20 6d 61 70 70 69 6e 67 20 65 6e 74 72 69 65 73 mapping entries
22c0: 20 69 73 20 77 65 20 63 61 6e 2e 20 20 4d 61 6e is we can. Man
22d0: 79 20 6f 66 20 74 68 65 73 65 0a 20 20 2a 2a 20 y of these. **
22e0: 65 6e 74 72 69 65 73 20 6d 69 67 68 74 20 6f 76 entries might ov
22f0: 65 72 6c 61 70 2e 20 20 54 68 65 20 6f 76 65 72 erlap. The over
2300: 6c 61 70 70 69 6e 67 20 65 6e 74 72 69 65 73 20 lapping entries
2310: 61 72 65 20 72 65 6d 6f 76 65 64 20 62 79 0a 20 are removed by.
2320: 20 2a 2a 20 74 68 65 20 6c 6f 6f 70 20 74 68 65 ** the loop the
2330: 20 66 6f 6c 6c 6f 77 73 2e 0a 20 20 2a 2f 0a 20 follows.. */.
2340: 20 62 61 73 65 20 3d 20 30 3b 20 20 20 20 2f 2a base = 0; /*
2350: 20 57 65 20 68 61 76 65 20 61 6c 72 65 61 64 79 We have already
2360: 20 63 68 65 63 6b 65 64 20 65 76 65 72 79 74 68 checked everyth
2370: 69 6e 67 20 62 65 66 6f 72 65 20 7a 4f 75 74 5b ing before zOut[
2380: 62 61 73 65 5d 20 2a 2f 0a 20 20 77 68 69 6c 65 base] */. while
2390: 28 20 62 61 73 65 3c 6c 65 6e 4f 75 74 2d 4e 48 ( base<lenOut-NH
23a0: 41 53 48 20 29 7b 0a 20 20 20 20 69 6e 74 20 69 ASH ){. int i
23b0: 53 72 63 2c 20 69 42 6c 6f 63 6b 2c 20 6e 65 78 Src, iBlock, nex
23c0: 74 42 61 73 65 2c 20 6e 65 78 74 42 61 73 65 49 tBase, nextBaseI
23d0: 3b 0a 20 20 20 20 68 61 73 68 5f 69 6e 69 74 28 ;. hash_init(
23e0: 26 68 2c 20 26 7a 4f 75 74 5b 62 61 73 65 5d 29 &h, &zOut[base])
23f0: 3b 0a 20 20 20 20 69 20 3d 20 30 3b 20 20 20 20 ;. i = 0;
2400: 20 2f 2a 20 54 72 79 69 6e 67 20 74 6f 20 6d 61 /* Trying to ma
2410: 74 63 68 20 61 20 6c 61 6e 64 6d 61 72 6b 20 61 tch a landmark a
2420: 67 61 69 6e 73 74 20 7a 4f 75 74 5b 62 61 73 65 gainst zOut[base
2430: 2b 69 5d 20 2a 2f 0a 20 20 20 20 6e 65 78 74 42 +i] */. nextB
2440: 61 73 65 49 20 3d 20 4e 48 41 53 48 3b 0a 20 20 aseI = NHASH;.
2450: 20 20 6e 65 78 74 42 61 73 65 20 3d 20 62 61 73 nextBase = bas
2460: 65 3b 0a 20 20 20 20 77 68 69 6c 65 28 31 29 7b e;. while(1){
2470: 0a 20 20 20 20 20 20 69 6e 74 20 68 76 3b 0a 0a . int hv;..
2480: 20 20 20 20 20 20 68 76 20 3d 20 68 61 73 68 5f hv = hash_
2490: 33 32 62 69 74 28 26 68 29 20 26 20 28 4d 58 5f 32bit(&h) & (MX_
24a0: 4c 41 4e 44 4d 41 52 4b 2d 31 29 3b 0a 20 20 20 LANDMARK-1);.
24b0: 20 20 20 44 45 42 55 47 32 28 20 70 72 69 6e 74 DEBUG2( print
24c0: 66 28 22 4c 4f 4f 4b 49 4e 47 3a 20 25 64 2b 25 f("LOOKING: %d+%
24d0: 64 2b 25 64 3d 25 64 20 5b 25 73 5d 5c 6e 22 2c d+%d=%d [%s]\n",
24e0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 70 . p
24f0: 72 65 66 69 78 2c 62 61 73 65 2c 69 2c 70 72 65 refix,base,i,pre
2500: 66 69 78 2b 62 61 73 65 2b 69 2c 20 70 72 69 6e fix+base+i, prin
2510: 74 31 36 28 26 7a 4f 75 74 5b 62 61 73 65 2b 69 t16(&zOut[base+i
2520: 5d 29 29 3b 20 29 0a 20 20 20 20 20 20 69 42 6c ])); ). iBl
2530: 6f 63 6b 20 3d 20 6c 61 6e 64 6d 61 72 6b 5b 68 ock = landmark[h
2540: 76 5d 3b 0a 20 20 20 20 20 20 77 68 69 6c 65 28 v];. while(
2550: 20 69 42 6c 6f 63 6b 3e 3d 30 20 29 7b 0a 20 20 iBlock>=0 ){.
2560: 20 20 20 20 20 20 2f 2a 0a 20 20 20 20 20 20 20 /*.
2570: 20 2a 2a 20 54 68 65 20 68 61 73 68 20 77 69 6e ** The hash win
2580: 64 6f 77 20 68 61 73 20 69 64 65 6e 74 69 66 69 dow has identifi
2590: 65 64 20 61 20 70 6f 74 65 6e 74 69 61 6c 20 6d ed a potential m
25a0: 61 74 63 68 20 61 67 61 69 6e 73 74 20 0a 20 20 atch against .
25b0: 20 20 20 20 20 20 2a 2a 20 6c 61 6e 64 6d 61 72 ** landmar
25c0: 6b 20 62 6c 6f 63 6b 20 69 42 6c 6f 63 6b 2e 20 k block iBlock.
25d0: 20 42 75 74 20 77 65 20 6e 65 65 64 20 74 6f 20 But we need to
25e0: 69 6e 76 65 73 74 69 67 61 74 65 20 66 75 72 74 investigate furt
25f0: 68 65 72 2e 0a 20 20 20 20 20 20 20 20 2a 2a 20 her.. **
2600: 0a 20 20 20 20 20 20 20 20 2a 2a 20 4c 6f 6f 6b . ** Look
2610: 20 66 6f 72 20 61 20 72 65 67 69 6f 6e 20 69 6e for a region in
2620: 20 7a 4f 75 74 20 74 68 61 74 20 6d 61 74 63 68 zOut that match
2630: 65 73 20 7a 53 72 63 2e 20 41 6e 63 68 6f 72 20 es zSrc. Anchor
2640: 74 68 65 20 73 65 61 72 63 68 0a 20 20 20 20 20 the search.
2650: 20 20 20 2a 2a 20 61 74 20 7a 53 72 63 5b 69 53 ** at zSrc[iS
2660: 72 63 5d 20 61 6e 64 20 7a 4f 75 74 5b 62 61 73 rc] and zOut[bas
2670: 65 2b 69 5d 2e 0a 20 20 20 20 20 20 20 20 2a 2a e+i].. **
2680: 0a 20 20 20 20 20 20 20 20 2a 2a 20 53 65 74 20 . ** Set
2690: 63 6e 74 20 65 71 75 61 6c 20 74 6f 20 74 68 65 cnt equal to the
26a0: 20 6c 65 6e 67 74 68 20 6f 66 20 74 68 65 20 6d length of the m
26b0: 61 74 63 68 20 61 6e 64 20 73 65 74 20 6f 66 73 atch and set ofs
26c0: 74 20 73 6f 20 74 68 61 74 0a 20 20 20 20 20 20 t so that.
26d0: 20 20 2a 2a 20 7a 53 72 63 5b 6f 66 73 74 5d 20 ** zSrc[ofst]
26e0: 69 73 20 74 68 65 20 66 69 72 73 74 20 65 6c 65 is the first ele
26f0: 6d 65 6e 74 20 6f 66 20 74 68 65 20 6d 61 74 63 ment of the matc
2700: 68 2e 20 0a 20 20 20 20 20 20 20 20 2a 2f 0a 20 h. . */.
2710: 20 20 20 20 20 20 20 69 6e 74 20 63 6e 74 2c 20 int cnt,
2720: 6f 66 73 74 53 72 63 3b 0a 20 20 20 20 20 20 20 ofstSrc;.
2730: 20 69 6e 74 20 6a 2c 20 6b 2c 20 78 2c 20 79 3b int j, k, x, y;
2740: 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 42 65 67 .. /* Beg
2750: 69 6e 6e 69 6e 67 20 61 74 20 69 53 72 63 2c 20 inning at iSrc,
2760: 6d 61 74 63 68 20 66 6f 72 77 61 72 64 73 20 61 match forwards a
2770: 73 20 66 61 72 20 61 73 20 77 65 20 63 61 6e 2e s far as we can.
2780: 20 20 6a 20 63 6f 75 6e 74 73 0a 20 20 20 20 20 j counts.
2790: 20 20 20 2a 2a 20 74 68 65 20 6e 75 6d 62 65 72 ** the number
27a0: 20 6f 66 20 63 68 61 72 61 63 74 65 72 73 20 74 of characters t
27b0: 68 61 74 20 6d 61 74 63 68 20 2a 2f 0a 20 20 20 hat match */.
27c0: 20 20 20 20 20 69 53 72 63 20 3d 20 69 42 6c 6f iSrc = iBlo
27d0: 63 6b 2a 4e 48 41 53 48 3b 0a 20 20 20 20 20 20 ck*NHASH;.
27e0: 20 20 66 6f 72 28 6a 3d 30 2c 20 78 3d 69 53 72 for(j=0, x=iSr
27f0: 63 2c 20 79 3d 62 61 73 65 2b 69 3b 20 78 3c 6c c, y=base+i; x<l
2800: 65 6e 53 72 63 20 26 26 20 79 3c 6c 65 6e 4f 75 enSrc && y<lenOu
2810: 74 3b 20 6a 2b 2b 2c 20 78 2b 2b 2c 20 79 2b 2b t; j++, x++, y++
2820: 29 7b 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 ){. if(
2830: 20 7a 53 72 63 5b 78 5d 21 3d 7a 4f 75 74 5b 79 zSrc[x]!=zOut[y
2840: 5d 20 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 ] ) break;.
2850: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 6a 2d 2d }. j--
2860: 3b 0a 0a 20 20 20 20 20 20 20 20 2f 2a 20 42 65 ;.. /* Be
2870: 67 69 6e 6e 69 6e 67 20 61 74 20 69 53 72 63 2d ginning at iSrc-
2880: 31 2c 20 6d 61 74 63 68 20 62 61 63 6b 77 61 72 1, match backwar
2890: 64 73 20 61 73 20 66 61 72 20 61 73 20 77 65 20 ds as far as we
28a0: 63 61 6e 2e 20 20 6b 20 63 6f 75 6e 74 73 0a 20 can. k counts.
28b0: 20 20 20 20 20 20 20 2a 2a 20 74 68 65 20 6e 75 ** the nu
28c0: 6d 62 65 72 20 6f 66 20 63 68 61 72 61 63 74 65 mber of characte
28d0: 72 73 20 74 68 61 74 20 6d 61 74 63 68 20 2a 2f rs that match */
28e0: 0a 20 20 20 20 20 20 20 20 66 6f 72 28 6b 3d 31 . for(k=1
28f0: 3b 20 6b 3c 69 53 72 63 20 26 26 20 6b 3c 3d 62 ; k<iSrc && k<=b
2900: 61 73 65 2b 69 3b 20 6b 2b 2b 29 7b 0a 20 20 20 ase+i; k++){.
2910: 20 20 20 20 20 20 20 69 66 28 20 7a 53 72 63 5b if( zSrc[
2920: 69 53 72 63 2d 6b 5d 21 3d 7a 4f 75 74 5b 62 61 iSrc-k]!=zOut[ba
2930: 73 65 2b 69 2d 6b 5d 20 29 20 62 72 65 61 6b 3b se+i-k] ) break;
2940: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 . }.
2950: 20 20 20 6b 2d 2d 3b 0a 0a 20 20 20 20 20 20 20 k--;..
2960: 20 2f 2a 20 43 6f 6d 70 75 74 65 20 74 68 65 20 /* Compute the
2970: 6f 66 66 73 65 74 20 61 6e 64 20 73 69 7a 65 20 offset and size
2980: 6f 66 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20 of the matching
2990: 72 65 67 69 6f 6e 20 7a 53 72 63 20 2a 2f 0a 20 region zSrc */.
29a0: 20 20 20 20 20 20 20 6f 66 73 74 53 72 63 20 3d ofstSrc =
29b0: 20 69 53 72 63 2d 6b 3b 0a 20 20 20 20 20 20 20 iSrc-k;.
29c0: 20 63 6e 74 20 3d 20 6a 2b 6b 2b 31 3b 0a 20 20 cnt = j+k+1;.
29d0: 20 20 20 20 20 20 44 45 42 55 47 32 28 20 70 72 DEBUG2( pr
29e0: 69 6e 74 66 28 22 4d 41 54 43 48 20 25 64 20 62 intf("MATCH %d b
29f0: 79 74 65 73 20 61 74 20 53 52 43 5b 25 64 2e 2e ytes at SRC[%d..
2a00: 25 64 5d 3a 20 5b 25 73 5d 5c 6e 22 2c 0a 20 20 %d]: [%s]\n",.
2a10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 63 c
2a20: 6e 74 2c 20 6f 66 73 74 53 72 63 2c 20 6f 66 73 nt, ofstSrc, ofs
2a30: 74 53 72 63 2b 63 6e 74 2d 31 2c 20 70 72 69 6e tSrc+cnt-1, prin
2a40: 74 31 36 28 26 7a 53 72 63 5b 6f 66 73 74 53 72 t16(&zSrc[ofstSr
2a50: 63 5d 29 29 3b 20 29 0a 20 20 20 20 20 20 20 20 c])); ).
2a60: 69 66 28 20 63 6e 74 3e 4e 48 41 53 48 20 29 7b if( cnt>NHASH ){
2a70: 0a 20 20 20 20 20 20 20 20 20 20 69 6e 74 20 6f . int o
2a80: 66 73 74 4f 75 74 20 3d 20 62 61 73 65 2b 69 2d fstOut = base+i-
2a90: 6b 3b 0a 20 20 20 20 20 20 20 20 20 20 44 45 42 k;. DEB
2aa0: 55 47 32 28 20 70 72 69 6e 74 66 28 22 43 4f 50 UG2( printf("COP
2ab0: 59 20 25 36 64 2e 2e 25 2d 36 64 20 25 36 64 2e Y %6d..%-6d %6d.
2ac0: 2e 25 64 5c 6e 22 2c 0a 20 20 20 20 20 20 20 20 .%d\n",.
2ad0: 20 20 20 20 70 72 65 66 69 78 2b 6f 66 73 74 53 prefix+ofstS
2ae0: 72 63 2c 20 70 72 65 66 69 78 2b 6f 66 73 74 53 rc, prefix+ofstS
2af0: 72 63 2b 63 6e 74 2d 31 2c 0a 20 20 20 20 20 20 rc+cnt-1,.
2b00: 20 20 20 20 20 20 70 72 65 66 69 78 2b 6f 66 73 prefix+ofs
2b10: 74 4f 75 74 2c 20 70 72 65 66 69 78 2b 6f 66 73 tOut, prefix+ofs
2b20: 74 4f 75 74 2b 63 6e 74 2d 31 29 3b 20 29 0a 20 tOut+cnt-1); ).
2b30: 20 20 20 20 20 20 20 20 20 4d 61 70 70 69 6e 67 Mapping
2b40: 49 6e 73 65 72 74 28 70 4d 61 70 2c 0a 20 20 20 Insert(pMap,.
2b50: 20 20 20 20 20 20 20 20 20 70 72 65 66 69 78 2b prefix+
2b60: 6f 66 73 74 53 72 63 2c 20 70 72 65 66 69 78 2b ofstSrc, prefix+
2b70: 6f 66 73 74 53 72 63 2b 63 6e 74 2d 31 2c 0a 20 ofstSrc+cnt-1,.
2b80: 20 20 20 20 20 20 20 20 20 20 20 70 72 65 66 69 prefi
2b90: 78 2b 6f 66 73 74 4f 75 74 2c 20 70 72 65 66 69 x+ofstOut, prefi
2ba0: 78 2b 6f 66 73 74 4f 75 74 2b 63 6e 74 2d 31 29 x+ofstOut+cnt-1)
2bb0: 3b 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 ;. if(
2bc0: 6e 65 78 74 42 61 73 65 20 3c 20 6f 66 73 74 4f nextBase < ofstO
2bd0: 75 74 2b 63 6e 74 2d 31 20 29 7b 0a 20 20 20 20 ut+cnt-1 ){.
2be0: 20 20 20 20 20 20 20 20 6e 65 78 74 42 61 73 65 nextBase
2bf0: 20 3d 20 6f 66 73 74 4f 75 74 2b 63 6e 74 2d 31 = ofstOut+cnt-1
2c00: 3b 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e 65 ;. ne
2c10: 78 74 42 61 73 65 49 20 3d 20 69 2b 4e 48 41 53 xtBaseI = i+NHAS
2c20: 48 3b 0a 20 20 20 20 20 20 20 20 20 20 7d 0a 20 H;. }.
2c30: 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 }..
2c40: 20 20 2f 2a 20 43 68 65 63 6b 20 74 68 65 20 6e /* Check the n
2c50: 65 78 74 20 6d 61 74 63 68 69 6e 67 20 62 6c 6f ext matching blo
2c60: 63 6b 20 2a 2f 0a 20 20 20 20 20 20 20 20 69 42 ck */. iB
2c70: 6c 6f 63 6b 20 3d 20 63 6f 6c 6c 69 64 65 5b 69 lock = collide[i
2c80: 42 6c 6f 63 6b 5d 3b 0a 20 20 20 20 20 20 7d 0a Block];. }.
2c90: 0a 20 20 20 20 20 20 2f 2a 20 49 66 20 77 65 20 . /* If we
2ca0: 66 6f 75 6e 64 20 61 20 6d 61 74 63 68 2c 20 74 found a match, t
2cb0: 68 65 6e 20 6a 75 6d 70 20 6f 75 74 20 74 6f 20 hen jump out to
2cc0: 74 68 65 20 6f 75 74 65 72 20 6c 6f 6f 70 20 61 the outer loop a
2cd0: 6e 64 20 62 65 67 69 6e 0a 20 20 20 20 20 20 2a nd begin. *
2ce0: 2a 20 61 20 6e 65 77 20 63 79 63 6c 65 2e 0a 20 * a new cycle..
2cf0: 20 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 69 66 */. if
2d00: 28 20 6e 65 78 74 42 61 73 65 3e 62 61 73 65 20 ( nextBase>base
2d10: 26 26 20 69 3e 3d 6e 65 78 74 42 61 73 65 49 20 && i>=nextBaseI
2d20: 29 7b 0a 20 20 20 20 20 20 20 20 62 61 73 65 20 ){. base
2d30: 3d 20 6e 65 78 74 42 61 73 65 3b 0a 20 20 20 20 = nextBase;.
2d40: 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 break;.
2d50: 20 7d 0a 0a 20 20 20 20 20 20 2f 2a 20 41 64 76 }.. /* Adv
2d60: 61 6e 63 65 20 74 68 65 20 68 61 73 68 20 62 79 ance the hash by
2d70: 20 6f 6e 65 20 63 68 61 72 61 63 74 65 72 2e 20 one character.
2d80: 20 4b 65 65 70 20 6c 6f 6f 6b 69 6e 67 20 66 6f Keep looking fo
2d90: 72 20 61 20 6d 61 74 63 68 20 2a 2f 0a 20 20 20 r a match */.
2da0: 20 20 20 69 66 28 20 62 61 73 65 2b 69 2b 4e 48 if( base+i+NH
2db0: 41 53 48 3e 3d 6c 65 6e 4f 75 74 20 29 7b 0a 20 ASH>=lenOut ){.
2dc0: 20 20 20 20 20 20 20 62 61 73 65 20 3d 20 6c 65 base = le
2dd0: 6e 4f 75 74 3b 0a 20 20 20 20 20 20 20 20 62 72 nOut;. br
2de0: 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 eak;. }.
2df0: 20 20 20 68 61 73 68 5f 6e 65 78 74 28 26 68 2c hash_next(&h,
2e00: 20 7a 4f 75 74 5b 62 61 73 65 2b 69 2b 4e 48 41 zOut[base+i+NHA
2e10: 53 48 5d 29 3b 0a 20 20 20 20 20 20 69 2b 2b 3b SH]);. i++;
2e20: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 66 72 65 . }. }. fre
2e30: 65 28 63 6f 6c 6c 69 64 65 29 3b 0a 20 20 44 45 e(collide);. DE
2e40: 42 55 47 31 28 0a 20 20 20 70 72 69 6e 74 66 28 BUG1(. printf(
2e50: 22 61 66 74 65 72 20 63 72 65 61 74 69 6f 6e 3a "after creation:
2e60: 5c 6e 22 29 3b 0a 20 20 20 4d 61 70 70 69 6e 67 \n");. Mapping
2e70: 50 72 69 6e 74 28 70 4d 61 70 29 3b 0a 20 20 29 Print(pMap);. )
2e80: 0a 0a 20 20 2f 2a 20 49 6e 20 74 68 69 73 20 73 .. /* In this s
2e90: 74 65 70 2c 20 77 65 20 77 69 6c 6c 20 72 65 6d tep, we will rem
2ea0: 6f 76 65 20 6f 76 65 72 6c 61 70 70 69 6e 67 20 ove overlapping
2eb0: 65 6e 74 72 69 65 73 20 66 72 6f 6d 20 74 68 65 entries from the
2ec0: 20 6d 61 70 70 69 6e 67 2e 0a 20 20 2a 2a 0a 20 mapping.. **.
2ed0: 20 2a 2a 20 57 65 20 75 73 65 20 61 20 67 72 65 ** We use a gre
2ee0: 65 64 79 20 61 6c 67 6f 72 69 74 68 6d 2e 20 20 edy algorithm.
2ef0: 53 65 6c 65 63 74 20 74 68 65 20 6c 61 72 67 65 Select the large
2f00: 73 74 20 6d 61 70 70 69 6e 67 20 66 69 72 73 74 st mapping first
2f10: 20 61 6e 64 0a 20 20 2a 2a 20 72 65 6d 6f 76 65 and. ** remove
2f20: 20 61 6c 6c 20 6f 76 65 72 6c 61 70 70 69 6e 67 all overlapping
2f30: 20 6d 61 70 70 69 6e 67 73 2e 20 20 54 68 65 6e mappings. Then
2f40: 20 74 61 6b 65 20 74 68 65 20 6e 65 78 74 20 6c take the next l
2f50: 61 72 67 65 73 74 0a 20 20 2a 2a 20 6d 61 70 70 argest. ** mapp
2f60: 69 6e 67 20 61 6e 64 20 72 65 6d 6f 76 65 20 6f ing and remove o
2f70: 74 68 65 72 73 20 74 68 61 74 20 6f 76 65 72 6c thers that overl
2f80: 61 70 20 77 69 74 68 20 69 74 2e 20 20 4b 65 65 ap with it. Kee
2f90: 70 20 67 6f 69 6e 67 20 75 6e 74 69 6c 0a 20 20 p going until.
2fa0: 2a 2a 20 61 6c 6c 20 6d 61 70 70 69 6e 67 73 20 ** all mappings
2fb0: 68 61 76 65 20 62 65 65 6e 20 70 72 6f 63 65 73 have been proces
2fc0: 73 65 64 2e 0a 20 20 2a 2f 0a 20 20 4d 61 70 70 sed.. */. Mapp
2fd0: 69 6e 67 53 6f 72 74 53 69 7a 65 28 70 4d 61 70 ingSortSize(pMap
2fe0: 29 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c );. for(i=0; i<
2ff0: 70 4d 61 70 2d 3e 6e 55 73 65 64 3b 20 69 2b 2b pMap->nUsed; i++
3000: 29 7b 0a 20 20 20 20 69 6e 74 20 73 6f 72 74 4e ){. int sortN
3010: 65 65 64 65 64 20 3d 20 30 3b 0a 20 20 20 20 69 eeded = 0;. i
3020: 6e 74 20 70 75 72 67 65 4e 65 65 64 65 64 20 3d nt purgeNeeded =
3030: 20 30 3b 0a 20 20 20 20 73 74 72 75 63 74 20 4d 0;. struct M
3040: 61 70 70 69 6e 67 5f 65 6e 74 72 79 20 2a 70 41 apping_entry *pA
3050: 3b 0a 20 20 20 20 70 41 20 3d 20 26 70 4d 61 70 ;. pA = &pMap
3060: 2d 3e 61 4d 61 70 5b 69 5d 3b 0a 20 20 20 20 66 ->aMap[i];. f
3070: 6f 72 28 6a 3d 69 2b 31 3b 20 6a 3c 70 4d 61 70 or(j=i+1; j<pMap
3080: 2d 3e 6e 55 73 65 64 3b 20 6a 2b 2b 29 7b 0a 20 ->nUsed; j++){.
3090: 20 20 20 20 20 69 6e 74 20 64 69 66 66 3b 0a 20 int diff;.
30a0: 20 20 20 20 20 73 74 72 75 63 74 20 4d 61 70 70 struct Mapp
30b0: 69 6e 67 5f 65 6e 74 72 79 20 2a 70 42 3b 0a 20 ing_entry *pB;.
30c0: 20 20 20 20 20 70 42 20 3d 20 26 70 4d 61 70 2d pB = &pMap-
30d0: 3e 61 4d 61 70 5b 6a 5d 3b 0a 20 20 20 20 20 20 >aMap[j];.
30e0: 69 66 28 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 if( pB->fromLast
30f0: 3c 70 41 2d 3e 66 72 6f 6d 46 69 72 73 74 20 7c <pA->fromFirst |
3100: 7c 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 3e | pB->fromFirst>
3110: 70 41 2d 3e 66 72 6f 6d 4c 61 73 74 20 29 7b 0a pA->fromLast ){.
3120: 20 20 20 20 20 20 20 20 2f 2a 20 4e 6f 20 6f 76 /* No ov
3130: 65 72 6c 61 70 2e 20 20 44 6f 20 6e 6f 74 68 69 erlap. Do nothi
3140: 6e 67 20 2a 2f 0a 20 20 20 20 20 20 7d 65 6c 73 ng */. }els
3150: 65 20 69 66 28 20 70 42 2d 3e 66 72 6f 6d 46 69 e if( pB->fromFi
3160: 72 73 74 3e 3d 70 41 2d 3e 66 72 6f 6d 46 69 72 rst>=pA->fromFir
3170: 73 74 20 26 26 20 70 42 2d 3e 66 72 6f 6d 4c 61 st && pB->fromLa
3180: 73 74 3c 3d 70 41 2d 3e 66 72 6f 6d 4c 61 73 74 st<=pA->fromLast
3190: 20 29 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 42 ){. /* B
31a0: 20 69 73 20 63 6f 6e 74 61 69 6e 65 64 20 65 6e is contained en
31b0: 74 69 72 65 6c 79 20 77 69 74 68 69 6e 20 41 2e tirely within A.
31c0: 20 20 44 72 6f 70 20 42 20 2a 2f 0a 20 20 20 20 Drop B */.
31d0: 20 20 20 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 pB->fromFirs
31e0: 74 20 3d 20 2d 31 3b 0a 20 20 20 20 20 20 20 20 t = -1;.
31f0: 70 75 72 67 65 4e 65 65 64 65 64 20 3d 20 31 3b purgeNeeded = 1;
3200: 0a 20 20 20 20 20 20 20 20 63 6f 6e 74 69 6e 75 . continu
3210: 65 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 e;. }else i
3220: 66 28 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 f( pB->fromFirst
3230: 3c 70 41 2d 3e 66 72 6f 6d 46 69 72 73 74 20 29 <pA->fromFirst )
3240: 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 {. /* The
3250: 20 74 61 69 6c 20 42 20 6f 76 65 72 6c 61 70 73 tail B overlaps
3260: 20 74 68 65 20 68 65 61 64 20 6f 66 20 41 20 2a the head of A *
3270: 2f 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 74 /. assert
3280: 28 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 3e 3d ( pB->fromLast>=
3290: 70 41 2d 3e 66 72 6f 6d 46 69 72 73 74 20 26 26 pA->fromFirst &&
32a0: 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 3c 3d 70 pB->fromLast<=p
32b0: 41 2d 3e 66 72 6f 6d 4c 61 73 74 20 29 3b 0a 20 A->fromLast );.
32c0: 20 20 20 20 20 20 20 64 69 66 66 20 3d 20 70 42 diff = pB
32d0: 2d 3e 66 72 6f 6d 4c 61 73 74 20 2b 20 31 20 2d ->fromLast + 1 -
32e0: 20 70 41 2d 3e 66 72 6f 6d 46 69 72 73 74 3b 0a pA->fromFirst;.
32f0: 20 20 20 20 20 20 20 20 70 42 2d 3e 66 72 6f 6d pB->from
3300: 4c 61 73 74 20 2d 3d 20 64 69 66 66 3b 0a 20 20 Last -= diff;.
3310: 20 20 20 20 20 20 70 42 2d 3e 74 6f 4c 61 73 74 pB->toLast
3320: 20 2d 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 20 -= diff;.
3330: 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 31 sortNeeded = 1
3340: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 ;. }else{.
3350: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68 65 /* The he
3360: 61 64 20 6f 66 20 42 20 6f 76 65 72 6c 61 70 73 ad of B overlaps
3370: 20 74 68 65 20 74 61 69 6c 20 6f 66 20 41 20 2a the tail of A *
3380: 2f 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 74 /. assert
3390: 28 20 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 3c ( pB->fromFirst<
33a0: 3d 70 41 2d 3e 66 72 6f 6d 4c 61 73 74 20 26 26 =pA->fromLast &&
33b0: 20 70 42 2d 3e 66 72 6f 6d 4c 61 73 74 3e 70 41 pB->fromLast>pA
33c0: 2d 3e 66 72 6f 6d 4c 61 73 74 20 29 3b 0a 20 20 ->fromLast );.
33d0: 20 20 20 20 20 20 64 69 66 66 20 3d 20 70 41 2d diff = pA-
33e0: 3e 66 72 6f 6d 4c 61 73 74 20 2b 20 31 20 2d 20 >fromLast + 1 -
33f0: 70 42 2d 3e 66 72 6f 6d 46 69 72 73 74 3b 0a 20 pB->fromFirst;.
3400: 20 20 20 20 20 20 20 70 42 2d 3e 66 72 6f 6d 46 pB->fromF
3410: 69 72 73 74 20 2b 3d 20 64 69 66 66 3b 0a 20 20 irst += diff;.
3420: 20 20 20 20 20 20 70 42 2d 3e 74 6f 46 69 72 73 pB->toFirs
3430: 74 20 2b 3d 20 64 69 66 66 3b 0a 20 20 20 20 20 t += diff;.
3440: 20 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d 20 sortNeeded =
3450: 31 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 1;. }.
3460: 20 69 66 28 20 70 42 2d 3e 74 6f 4c 61 73 74 3c if( pB->toLast<
3470: 70 41 2d 3e 74 6f 46 69 72 73 74 20 7c 7c 20 70 pA->toFirst || p
3480: 42 2d 3e 74 6f 46 69 72 73 74 3e 70 41 2d 3e 74 B->toFirst>pA->t
3490: 6f 4c 61 73 74 20 29 7b 0a 20 20 20 20 20 20 20 oLast ){.
34a0: 20 2f 2a 20 4e 6f 20 6f 76 65 72 6c 61 70 2e 20 /* No overlap.
34b0: 20 44 6f 20 6e 6f 74 68 69 6e 67 20 2a 2f 0a 20 Do nothing */.
34c0: 20 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20 70 }else if( p
34d0: 42 2d 3e 74 6f 46 69 72 73 74 3e 3d 70 41 2d 3e B->toFirst>=pA->
34e0: 74 6f 46 69 72 73 74 20 26 26 20 70 42 2d 3e 74 toFirst && pB->t
34f0: 6f 4c 61 73 74 3c 3d 70 41 2d 3e 74 6f 4c 61 73 oLast<=pA->toLas
3500: 74 20 29 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 t ){. /*
3510: 42 20 69 73 20 63 6f 6e 74 61 69 6e 65 64 20 65 B is contained e
3520: 6e 74 69 72 65 6c 79 20 77 69 74 68 69 6e 20 41 ntirely within A
3530: 2e 20 20 44 72 6f 70 20 42 20 2a 2f 0a 20 20 20 . Drop B */.
3540: 20 20 20 20 20 70 42 2d 3e 66 72 6f 6d 46 69 72 pB->fromFir
3550: 73 74 20 3d 20 2d 31 3b 0a 20 20 20 20 20 20 20 st = -1;.
3560: 20 70 75 72 67 65 4e 65 65 64 65 64 20 3d 20 31 purgeNeeded = 1
3570: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 20 69 66 ;. }else if
3580: 28 20 70 42 2d 3e 74 6f 46 69 72 73 74 3c 70 41 ( pB->toFirst<pA
3590: 2d 3e 74 6f 46 69 72 73 74 20 29 7b 0a 20 20 20 ->toFirst ){.
35a0: 20 20 20 20 20 2f 2a 20 54 68 65 20 74 61 69 6c /* The tail
35b0: 20 6f 66 20 42 20 6f 76 65 72 6c 61 70 73 20 74 of B overlaps t
35c0: 68 65 20 68 65 61 64 20 6f 66 20 41 20 2a 2f 0a he head of A */.
35d0: 20 20 20 20 20 20 20 20 61 73 73 65 72 74 28 20 assert(
35e0: 70 42 2d 3e 74 6f 4c 61 73 74 3e 3d 70 41 2d 3e pB->toLast>=pA->
35f0: 74 6f 46 69 72 73 74 20 26 26 20 70 42 2d 3e 74 toFirst && pB->t
3600: 6f 4c 61 73 74 3c 3d 70 41 2d 3e 74 6f 4c 61 73 oLast<=pA->toLas
3610: 74 20 29 3b 0a 20 20 20 20 20 20 20 20 64 69 66 t );. dif
3620: 66 20 3d 20 70 42 2d 3e 74 6f 4c 61 73 74 20 2b f = pB->toLast +
3630: 20 31 20 2d 20 70 41 2d 3e 74 6f 46 69 72 73 74 1 - pA->toFirst
3640: 3b 0a 20 20 20 20 20 20 20 20 70 42 2d 3e 66 72 ;. pB->fr
3650: 6f 6d 4c 61 73 74 20 2d 3d 20 64 69 66 66 3b 0a omLast -= diff;.
3660: 20 20 20 20 20 20 20 20 70 42 2d 3e 74 6f 4c 61 pB->toLa
3670: 73 74 20 2d 3d 20 64 69 66 66 3b 0a 20 20 20 20 st -= diff;.
3680: 20 20 20 20 73 6f 72 74 4e 65 65 64 65 64 20 3d sortNeeded =
3690: 20 31 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 1;. }else{
36a0: 0a 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 . /* The
36b0: 68 65 61 64 20 6f 66 20 42 20 6f 76 65 72 6c 61 head of B overla
36c0: 70 73 20 74 68 65 20 74 61 69 6c 20 6f 66 20 41 ps the tail of A
36d0: 20 2a 2f 0a 20 20 20 20 20 20 20 20 61 73 73 65 */. asse
36e0: 72 74 28 20 70 42 2d 3e 74 6f 46 69 72 73 74 3c rt( pB->toFirst<
36f0: 3d 70 41 2d 3e 74 6f 4c 61 73 74 20 26 26 20 70 =pA->toLast && p
3700: 42 2d 3e 74 6f 4c 61 73 74 3e 70 41 2d 3e 74 6f B->toLast>pA->to
3710: 4c 61 73 74 20 29 3b 0a 20 20 20 20 20 20 20 20 Last );.
3720: 64 69 66 66 20 3d 20 70 41 2d 3e 74 6f 4c 61 73 diff = pA->toLas
3730: 74 20 2b 20 31 20 2d 20 70 42 2d 3e 74 6f 46 69 t + 1 - pB->toFi
3740: 72 73 74 3b 0a 20 20 20 20 20 20 20 20 70 42 2d rst;. pB-
3750: 3e 66 72 6f 6d 46 69 72 73 74 20 2b 3d 20 64 69 >fromFirst += di
3760: 66 66 3b 0a 20 20 20 20 20 20 20 20 70 42 2d 3e ff;. pB->
3770: 74 6f 46 69 72 73 74 20 2b 3d 20 64 69 66 66 3b toFirst += diff;
3780: 0a 20 20 20 20 20 20 20 20 73 6f 72 74 4e 65 65 . sortNee
3790: 64 65 64 20 3d 20 31 3b 0a 20 20 20 20 20 20 7d ded = 1;. }
37a0: 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20 70 . }. if( p
37b0: 75 72 67 65 4e 65 65 64 65 64 20 29 7b 0a 20 20 urgeNeeded ){.
37c0: 20 20 20 20 4d 61 70 70 69 6e 67 50 75 72 67 65 MappingPurge
37d0: 44 65 6c 65 74 65 64 45 6e 74 72 69 65 73 28 70 DeletedEntries(p
37e0: 4d 61 70 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 Map);. }.
37f0: 69 66 28 20 73 6f 72 74 4e 65 65 64 65 64 20 26 if( sortNeeded &
3800: 26 20 69 3c 70 4d 61 70 2d 3e 6e 55 73 65 64 2d & i<pMap->nUsed-
3810: 32 20 29 7b 0a 20 20 20 20 20 20 4d 61 70 70 69 2 ){. Mappi
3820: 6e 67 53 6f 72 74 53 69 7a 65 28 70 4d 61 70 29 ngSortSize(pMap)
3830: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f ;. }. }.. /
3840: 2a 20 46 69 6e 61 6c 20 73 74 65 70 3a 20 20 41 * Final step: A
3850: 72 72 61 6e 67 65 20 74 68 65 20 6d 61 70 70 69 rrange the mappi
3860: 6e 67 20 65 6e 74 69 72 65 73 20 73 6f 20 74 68 ng entires so th
3870: 61 74 20 74 68 65 79 20 61 72 65 20 69 6e 20 74 at they are in t
3880: 68 65 0a 20 20 2a 2a 20 6f 72 64 65 72 20 6f 66 he. ** order of
3890: 20 74 68 65 20 6f 75 74 70 75 74 20 66 69 6c 65 the output file
38a0: 2e 20 20 54 68 65 6e 20 66 69 6c 6c 20 69 6e 20 . Then fill in
38b0: 74 68 65 20 6e 45 78 74 72 61 20 76 61 6c 75 65 the nExtra value
38c0: 73 2e 0a 20 20 2a 2f 0a 61 64 64 5f 6e 65 78 74 s.. */.add_next
38d0: 72 61 3a 0a 20 20 4d 61 70 70 69 6e 67 53 6f 72 ra:. MappingSor
38e0: 74 54 6f 28 70 4d 61 70 29 3b 0a 20 20 61 4d 61 tTo(pMap);. aMa
38f0: 70 20 3d 20 70 4d 61 70 2d 3e 61 4d 61 70 3b 0a p = pMap->aMap;.
3900: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 4d 61 for(i=0; i<pMa
3910: 70 2d 3e 6e 55 73 65 64 2d 31 3b 20 69 2b 2b 29 p->nUsed-1; i++)
3920: 7b 0a 20 20 20 20 61 4d 61 70 5b 69 5d 2e 6e 45 {. aMap[i].nE
3930: 78 74 72 61 20 3d 20 61 4d 61 70 5b 69 2b 31 5d xtra = aMap[i+1]
3940: 2e 74 6f 46 69 72 73 74 20 2d 20 61 4d 61 70 5b .toFirst - aMap[
3950: 69 5d 2e 74 6f 4c 61 73 74 20 2d 20 31 3b 0a 20 i].toLast - 1;.
3960: 20 7d 0a 20 20 69 66 28 20 70 4d 61 70 2d 3e 6e }. if( pMap->n
3970: 55 73 65 64 3e 30 20 26 26 20 6f 72 69 67 4c 65 Used>0 && origLe
3980: 6e 4f 75 74 20 3e 20 61 4d 61 70 5b 69 5d 2e 74 nOut > aMap[i].t
3990: 6f 4c 61 73 74 2b 31 20 29 7b 0a 20 20 20 20 61 oLast+1 ){. a
39a0: 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 61 20 3d 20 Map[i].nExtra =
39b0: 6f 72 69 67 4c 65 6e 4f 75 74 20 2d 20 61 4d 61 origLenOut - aMa
39c0: 70 5b 69 5d 2e 74 6f 4c 61 73 74 20 2d 20 31 3b p[i].toLast - 1;
39d0: 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 72 . }.}../*.** Tr
39e0: 61 6e 73 6c 61 74 65 20 61 6e 20 69 6e 64 65 78 anslate an index
39f0: 20 69 6e 74 6f 20 61 20 66 69 6c 65 20 75 73 69 into a file usi
3a00: 6e 67 20 61 20 6d 61 70 70 69 6e 67 2e 0a 2a 2a ng a mapping..**
3a10: 0a 2a 2a 20 54 68 65 20 6d 61 70 70 69 6e 67 20 .** The mapping
3a20: 22 70 22 20 73 68 6f 77 73 20 68 6f 77 20 62 6c "p" shows how bl
3a30: 6f 63 6b 73 20 69 6e 20 74 68 65 20 69 6e 70 75 ocks in the inpu
3a40: 74 20 66 69 6c 65 20 6d 61 70 20 69 6e 74 6f 20 t file map into
3a50: 62 6c 6f 63 6b 73 0a 2a 2a 20 6f 66 20 74 68 65 blocks.** of the
3a60: 20 6f 75 74 70 75 74 20 66 69 6c 65 2e 20 20 54 output file. T
3a70: 68 65 20 69 6e 64 65 78 20 69 46 72 6f 6d 20 69 he index iFrom i
3a80: 73 20 61 6e 20 69 6e 64 65 78 20 69 6e 74 6f 20 s an index into
3a90: 74 68 65 20 69 6e 70 75 74 20 66 69 6c 65 2e 0a the input file..
3aa0: 2a 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 ** This routine
3ab0: 72 65 74 75 72 6e 73 20 74 68 65 20 69 6e 64 65 returns the inde
3ac0: 78 20 69 6e 74 6f 20 74 68 65 20 6f 75 74 70 75 x into the outpu
3ad0: 74 20 66 69 6c 65 20 6f 66 20 74 68 65 20 63 6f t file of the co
3ae0: 72 72 65 73 70 6f 6e 64 69 6e 67 0a 2a 2a 20 63 rresponding.** c
3af0: 68 61 72 61 63 74 65 72 2e 0a 2a 2a 0a 2a 2a 20 haracter..**.**
3b00: 49 66 20 70 49 6e 73 65 72 74 65 64 21 3d 30 20 If pInserted!=0
3b10: 61 6e 64 20 69 46 72 6f 6d 20 70 6f 69 6e 74 73 and iFrom points
3b20: 20 74 6f 20 74 68 65 20 6c 61 73 74 20 63 68 61 to the last cha
3b30: 72 61 63 74 65 72 20 62 65 66 6f 72 65 20 61 0a racter before a.
3b40: 2a 2a 20 69 6e 73 65 72 74 20 69 6e 20 74 68 65 ** insert in the
3b50: 20 6f 75 74 70 75 74 20 66 69 6c 65 2c 20 74 68 output file, th
3b60: 65 6e 20 74 68 65 20 72 65 74 75 72 6e 20 76 61 en the return va
3b70: 6c 75 65 20 69 73 20 61 64 6a 75 73 74 65 64 20 lue is adjusted
3b80: 66 6f 72 77 61 72 64 0a 2a 2a 20 73 6f 20 74 68 forward.** so th
3b90: 61 74 20 69 74 20 70 6f 69 6e 74 73 20 74 6f 20 at it points to
3ba0: 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 69 the end of the i
3bb0: 6e 73 65 72 74 69 6f 6e 20 61 6e 64 20 74 68 65 nsertion and the
3bc0: 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 62 79 number of.** by
3bd0: 74 65 73 20 69 6e 73 65 72 74 65 64 20 69 73 20 tes inserted is
3be0: 77 72 69 74 74 65 6e 20 69 6e 74 6f 20 2a 70 49 written into *pI
3bf0: 6e 73 65 72 74 65 64 2e 20 20 49 66 20 70 49 6e nserted. If pIn
3c00: 73 65 72 74 65 64 3d 3d 30 20 74 68 65 6e 0a 2a serted==0 then.*
3c10: 2a 20 69 46 72 6f 6d 20 61 6c 77 61 79 73 20 6d * iFrom always m
3c20: 61 70 73 20 64 69 72 65 63 74 6c 79 20 69 6e 20 aps directly in
3c30: 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e the correspondin
3c40: 67 20 6f 75 74 70 75 74 20 66 69 6c 65 0a 2a 2a g output file.**
3c50: 20 69 6e 64 65 78 20 72 65 67 61 72 64 6c 65 73 index regardles
3c60: 73 20 6f 66 20 77 68 65 74 68 65 72 20 6f 72 20 s of whether or
3c70: 6e 6f 74 20 69 74 20 70 6f 69 6e 74 73 20 74 6f not it points to
3c80: 20 74 68 65 20 6c 61 73 74 20 63 68 61 72 61 63 the last charac
3c90: 74 65 72 0a 2a 2a 20 62 65 66 6f 72 65 20 61 6e ter.** before an
3ca0: 20 69 6e 73 65 72 74 69 6f 6e 2e 0a 2a 2f 0a 73 insertion..*/.s
3cb0: 74 61 74 69 63 20 69 6e 74 20 4d 61 70 70 69 6e tatic int Mappin
3cc0: 67 54 72 61 6e 73 6c 61 74 65 28 4d 61 70 70 69 gTranslate(Mappi
3cd0: 6e 67 20 2a 70 2c 20 69 6e 74 20 69 46 72 6f 6d ng *p, int iFrom
3ce0: 2c 20 69 6e 74 20 2a 70 49 6e 73 65 72 74 65 64 , int *pInserted
3cf0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f ){. int i;. fo
3d00: 72 28 69 3d 30 3b 20 69 3c 70 2d 3e 6e 55 73 65 r(i=0; i<p->nUse
3d10: 64 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 d; i++){. if(
3d20: 20 69 46 72 6f 6d 3e 70 2d 3e 61 4d 61 70 5b 69 iFrom>p->aMap[i
3d30: 5d 2e 66 72 6f 6d 4c 61 73 74 20 29 20 63 6f 6e ].fromLast ) con
3d40: 74 69 6e 75 65 3b 0a 20 20 20 20 69 66 28 20 69 tinue;. if( i
3d50: 46 72 6f 6d 3c 3d 70 2d 3e 61 4d 61 70 5b 69 5d From<=p->aMap[i]
3d60: 2e 66 72 6f 6d 46 69 72 73 74 20 29 7b 0a 20 20 .fromFirst ){.
3d70: 20 20 20 20 72 65 74 75 72 6e 20 70 2d 3e 61 4d return p->aM
3d80: 61 70 5b 69 5d 2e 74 6f 46 69 72 73 74 3b 0a 20 ap[i].toFirst;.
3d90: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 70 49 6e }. if( pIn
3da0: 73 65 72 74 65 64 20 26 26 20 69 46 72 6f 6d 3d serted && iFrom=
3db0: 3d 70 2d 3e 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d =p->aMap[i].from
3dc0: 4c 61 73 74 20 29 7b 0a 20 20 20 20 20 20 69 6e Last ){. in
3dd0: 74 20 6e 20 3d 20 70 2d 3e 61 4d 61 70 5b 69 5d t n = p->aMap[i]
3de0: 2e 6e 45 78 74 72 61 3b 0a 20 20 20 20 20 20 2a .nExtra;. *
3df0: 70 49 6e 73 65 72 74 65 64 20 3d 20 6e 3b 0a 20 pInserted = n;.
3e00: 20 20 20 20 20 72 65 74 75 72 6e 20 70 2d 3e 61 return p->a
3e10: 4d 61 70 5b 69 5d 2e 74 6f 4c 61 73 74 20 2b 20 Map[i].toLast +
3e20: 6e 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 n;. }else{.
3e30: 20 20 20 20 72 65 74 75 72 6e 20 70 2d 3e 61 4d return p->aM
3e40: 61 70 5b 69 5d 2e 74 6f 46 69 72 73 74 20 2b 20 ap[i].toFirst +
3e50: 69 46 72 6f 6d 20 2d 20 70 2d 3e 61 4d 61 70 5b iFrom - p->aMap[
3e60: 69 5d 2e 66 72 6f 6d 46 69 72 73 74 3b 0a 20 20 i].fromFirst;.
3e70: 20 20 7d 0a 20 20 7d 0a 20 20 69 2d 2d 3b 0a 20 }. }. i--;.
3e80: 20 72 65 74 75 72 6e 20 70 2d 3e 61 4d 61 70 5b return p->aMap[
3e90: 69 5d 2e 74 6f 4c 61 73 74 20 2b 20 70 2d 3e 61 i].toLast + p->a
3ea0: 4d 61 70 5b 69 5d 2e 6e 45 78 74 72 61 3b 0a 7d Map[i].nExtra;.}
3eb0: 0a 0a 2f 2a 0a 2a 2a 20 44 6f 20 61 20 74 68 72 ../*.** Do a thr
3ec0: 65 65 2d 77 61 79 20 6d 65 72 67 65 2e 20 20 49 ee-way merge. I
3ed0: 6e 69 74 69 61 6c 69 7a 65 20 70 4f 75 74 20 74 nitialize pOut t
3ee0: 6f 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 72 65 o contain the re
3ef0: 73 75 6c 74 2e 0a 2a 2f 0a 76 6f 69 64 20 62 6c sult..*/.void bl
3f00: 6f 62 5f 6d 65 72 67 65 28 42 6c 6f 62 20 2a 70 ob_merge(Blob *p
3f10: 50 69 76 6f 74 2c 20 42 6c 6f 62 20 2a 70 56 31 Pivot, Blob *pV1
3f20: 2c 20 42 6c 6f 62 20 2a 70 56 32 2c 20 42 6c 6f , Blob *pV2, Blo
3f30: 62 20 2a 70 4f 75 74 29 7b 0a 20 20 4d 61 70 70 b *pOut){. Mapp
3f40: 69 6e 67 20 6d 61 70 31 2c 20 6d 61 70 32 3b 0a ing map1, map2;.
3f50: 20 20 69 6e 74 20 69 3b 0a 20 20 63 6f 6e 73 74 int i;. const
3f60: 20 63 68 61 72 20 2a 7a 56 31 2c 20 2a 7a 56 32 char *zV1, *zV2
3f70: 3b 0a 20 20 62 6c 6f 62 5f 7a 65 72 6f 28 70 4f ;. blob_zero(pO
3f80: 75 74 29 3b 0a 20 20 44 45 42 55 47 31 28 20 70 ut);. DEBUG1( p
3f90: 72 69 6e 74 66 28 22 6d 61 70 31 3a 5c 6e 22 29 rintf("map1:\n")
3fa0: 3b 20 29 0a 20 20 4d 61 70 70 69 6e 67 49 6e 69 ; ). MappingIni
3fb0: 74 28 0a 20 20 20 20 62 6c 6f 62 5f 62 75 66 66 t(. blob_buff
3fc0: 65 72 28 70 50 69 76 6f 74 29 2c 20 62 6c 6f 62 er(pPivot), blob
3fd0: 5f 73 69 7a 65 28 70 50 69 76 6f 74 29 2c 0a 20 _size(pPivot),.
3fe0: 20 20 20 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 blob_buffer(p
3ff0: 56 31 29 2c 20 62 6c 6f 62 5f 73 69 7a 65 28 70 V1), blob_size(p
4000: 56 31 29 2c 0a 20 20 20 20 26 6d 61 70 31 29 3b V1),. &map1);
4010: 0a 20 20 4d 61 70 70 69 6e 67 53 6f 72 74 46 72 . MappingSortFr
4020: 6f 6d 28 26 6d 61 70 31 29 3b 0a 20 20 44 45 42 om(&map1);. DEB
4030: 55 47 31 28 20 0a 20 20 20 20 70 72 69 6e 74 66 UG1( . printf
4040: 28 22 6d 61 70 31 2d 66 69 6e 61 6c 3a 5c 6e 22 ("map1-final:\n"
4050: 29 3b 0a 20 20 20 20 4d 61 70 70 69 6e 67 50 72 );. MappingPr
4060: 69 6e 74 28 26 6d 61 70 31 29 3b 0a 20 20 20 20 int(&map1);.
4070: 70 72 69 6e 74 66 28 22 6d 61 70 32 3a 5c 6e 22 printf("map2:\n"
4080: 29 3b 0a 20 20 29 0a 20 20 4d 61 70 70 69 6e 67 );. ). Mapping
4090: 49 6e 69 74 28 0a 20 20 20 20 62 6c 6f 62 5f 62 Init(. blob_b
40a0: 75 66 66 65 72 28 70 50 69 76 6f 74 29 2c 20 62 uffer(pPivot), b
40b0: 6c 6f 62 5f 73 69 7a 65 28 70 50 69 76 6f 74 29 lob_size(pPivot)
40c0: 2c 0a 20 20 20 20 62 6c 6f 62 5f 62 75 66 66 65 ,. blob_buffe
40d0: 72 28 70 56 32 29 2c 20 62 6c 6f 62 5f 73 69 7a r(pV2), blob_siz
40e0: 65 28 70 56 32 29 2c 0a 20 20 20 20 26 6d 61 70 e(pV2),. &map
40f0: 32 29 3b 0a 20 20 44 45 42 55 47 31 28 0a 20 20 2);. DEBUG1(.
4100: 20 20 70 72 69 6e 74 66 28 22 6d 61 70 32 2d 66 printf("map2-f
4110: 69 6e 61 6c 3a 5c 6e 22 29 3b 0a 20 20 20 20 4d inal:\n");. M
4120: 61 70 70 69 6e 67 50 72 69 6e 74 28 26 6d 61 70 appingPrint(&map
4130: 32 29 3b 0a 20 20 29 0a 20 20 7a 56 31 20 3d 20 2);. ). zV1 =
4140: 62 6c 6f 62 5f 62 75 66 66 65 72 28 70 56 31 29 blob_buffer(pV1)
4150: 3b 0a 20 20 7a 56 32 20 3d 20 62 6c 6f 62 5f 62 ;. zV2 = blob_b
4160: 75 66 66 65 72 28 70 56 32 29 3b 0a 20 20 69 66 uffer(pV2);. if
4170: 28 20 6d 61 70 32 2e 6e 55 73 65 64 3d 3d 30 20 ( map2.nUsed==0
4180: 29 20 72 65 74 75 72 6e 3b 0a 20 20 69 66 28 20 ) return;. if(
4190: 6d 61 70 31 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 map1.aMap[0].toF
41a0: 69 72 73 74 3e 30 20 29 7b 0a 20 20 20 20 62 6c irst>0 ){. bl
41b0: 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 74 2c 20 ob_append(pOut,
41c0: 7a 56 31 2c 20 6d 61 70 31 2e 61 4d 61 70 5b 30 zV1, map1.aMap[0
41d0: 5d 2e 74 6f 46 69 72 73 74 29 3b 0a 20 20 20 20 ].toFirst);.
41e0: 44 45 42 55 47 31 28 20 70 72 69 6e 74 66 28 22 DEBUG1( printf("
41f0: 49 4e 53 45 52 54 20 25 64 20 62 79 74 65 73 20 INSERT %d bytes
4200: 66 72 6f 6d 20 56 31 5b 30 2e 2e 25 64 5d 5c 6e from V1[0..%d]\n
4210: 22 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 6d ",. m
4220: 61 70 31 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 69 ap1.aMap[0].toFi
4230: 72 73 74 2c 20 6d 61 70 31 2e 61 4d 61 70 5b 30 rst, map1.aMap[0
4240: 5d 2e 74 6f 46 69 72 73 74 2d 31 29 3b 20 29 0a ].toFirst-1); ).
4250: 20 20 7d 0a 20 20 69 66 28 20 6d 61 70 32 2e 61 }. if( map2.a
4260: 4d 61 70 5b 30 5d 2e 74 6f 46 69 72 73 74 3e 30 Map[0].toFirst>0
4270: 20 29 7b 0a 20 20 20 20 62 6c 6f 62 5f 61 70 70 ){. blob_app
4280: 65 6e 64 28 70 4f 75 74 2c 20 7a 56 32 2c 20 6d end(pOut, zV2, m
4290: 61 70 32 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 69 ap2.aMap[0].toFi
42a0: 72 73 74 29 3b 0a 20 20 20 20 44 45 42 55 47 31 rst);. DEBUG1
42b0: 28 20 70 72 69 6e 74 66 28 22 49 4e 53 45 52 54 ( printf("INSERT
42c0: 20 25 64 20 62 79 74 65 73 20 66 72 6f 6d 20 56 %d bytes from V
42d0: 32 5b 30 2e 2e 25 64 5d 5c 6e 22 2c 0a 20 20 20 2[0..%d]\n",.
42e0: 20 20 20 20 20 20 20 20 20 6d 61 70 32 2e 61 4d map2.aM
42f0: 61 70 5b 30 5d 2e 74 6f 46 69 72 73 74 2c 20 6d ap[0].toFirst, m
4300: 61 70 32 2e 61 4d 61 70 5b 30 5d 2e 74 6f 46 69 ap2.aMap[0].toFi
4310: 72 73 74 2d 31 29 3b 20 29 0a 20 20 7d 0a 20 20 rst-1); ). }.
4320: 66 6f 72 28 69 3d 30 3b 20 69 3c 6d 61 70 32 2e for(i=0; i<map2.
4330: 6e 55 73 65 64 3b 20 69 2b 2b 29 7b 0a 20 20 20 nUsed; i++){.
4340: 20 69 6e 74 20 69 46 69 72 73 74 2c 20 69 4c 61 int iFirst, iLa
4350: 73 74 2c 20 6e 49 6e 73 65 72 74 3b 0a 20 20 20 st, nInsert;.
4360: 20 73 74 72 75 63 74 20 4d 61 70 70 69 6e 67 5f struct Mapping_
4370: 65 6e 74 72 79 20 2a 70 20 3d 20 26 6d 61 70 32 entry *p = &map2
4380: 2e 61 4d 61 70 5b 69 5d 3b 0a 20 20 20 20 69 46 .aMap[i];. iF
4390: 69 72 73 74 20 3d 20 4d 61 70 70 69 6e 67 54 72 irst = MappingTr
43a0: 61 6e 73 6c 61 74 65 28 26 6d 61 70 31 2c 20 70 anslate(&map1, p
43b0: 2d 3e 66 72 6f 6d 46 69 72 73 74 2c 20 30 29 3b ->fromFirst, 0);
43c0: 0a 20 20 20 20 69 4c 61 73 74 20 3d 20 4d 61 70 . iLast = Map
43d0: 70 69 6e 67 54 72 61 6e 73 6c 61 74 65 28 26 6d pingTranslate(&m
43e0: 61 70 31 2c 20 70 2d 3e 66 72 6f 6d 4c 61 73 74 ap1, p->fromLast
43f0: 2c 20 26 6e 49 6e 73 65 72 74 29 3b 0a 20 20 20 , &nInsert);.
4400: 20 62 6c 6f 62 5f 61 70 70 65 6e 64 28 70 4f 75 blob_append(pOu
4410: 74 2c 20 26 7a 56 31 5b 69 46 69 72 73 74 5d 2c t, &zV1[iFirst],
4420: 20 69 4c 61 73 74 20 2d 20 69 46 69 72 73 74 20 iLast - iFirst
4430: 2b 20 31 29 3b 0a 20 20 20 20 44 45 42 55 47 31 + 1);. DEBUG1
4440: 28 0a 20 20 20 20 20 20 70 72 69 6e 74 66 28 22 (. printf("
4450: 43 4f 50 59 20 25 64 20 62 79 74 65 73 20 66 72 COPY %d bytes fr
4460: 6f 6d 20 56 31 5b 25 64 2e 2e 25 64 5d 5c 6e 22 om V1[%d..%d]\n"
4470: 2c 20 69 4c 61 73 74 2d 69 46 69 72 73 74 2b 31 , iLast-iFirst+1
4480: 2c 20 69 46 69 72 73 74 2c 20 69 4c 61 73 74 29 , iFirst, iLast)
4490: 3b 0a 20 20 20 20 29 0a 20 20 20 20 69 66 28 20 ;. ). if(
44a0: 70 2d 3e 6e 45 78 74 72 61 3e 30 20 29 7b 0a 20 p->nExtra>0 ){.
44b0: 20 20 20 20 20 69 66 28 20 70 2d 3e 6e 45 78 74 if( p->nExt
44c0: 72 61 3d 3d 6e 49 6e 73 65 72 74 0a 20 20 20 20 ra==nInsert.
44d0: 20 20 20 20 20 20 26 26 20 6d 65 6d 63 6d 70 28 && memcmp(
44e0: 26 7a 56 32 5b 70 2d 3e 74 6f 4c 61 73 74 2b 31 &zV2[p->toLast+1
44f0: 5d 2c 20 26 7a 56 31 5b 69 4c 61 73 74 2d 6e 49 ], &zV1[iLast-nI
4500: 6e 73 65 72 74 2b 31 5d 2c 20 6e 49 6e 73 65 72 nsert+1], nInser
4510: 74 29 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 t)==0 ){.
4520: 20 2f 2a 20 4f 6d 69 74 20 61 20 64 75 70 6c 69 /* Omit a dupli
4530: 63 61 74 65 20 69 6e 73 65 72 74 20 2a 2f 0a 20 cate insert */.
4540: 20 20 20 20 20 20 20 44 45 42 55 47 31 28 20 70 DEBUG1( p
4550: 72 69 6e 74 66 28 22 4f 4d 49 54 20 64 75 70 6c rintf("OMIT dupl
4560: 69 63 61 74 65 20 69 6e 73 65 72 74 5c 6e 22 29 icate insert\n")
4570: 3b 20 29 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b ; ). }else{
4580: 0a 20 20 20 20 20 20 20 20 62 6c 6f 62 5f 61 70 . blob_ap
4590: 70 65 6e 64 28 70 4f 75 74 2c 20 26 7a 56 32 5b pend(pOut, &zV2[
45a0: 70 2d 3e 74 6f 4c 61 73 74 2b 31 5d 2c 20 70 2d p->toLast+1], p-
45b0: 3e 6e 45 78 74 72 61 29 3b 0a 20 20 20 20 20 20 >nExtra);.
45c0: 20 20 44 45 42 55 47 31 28 0a 20 20 20 20 20 20 DEBUG1(.
45d0: 20 20 20 20 70 72 69 6e 74 66 28 22 49 4e 53 45 printf("INSE
45e0: 52 54 20 25 64 20 62 79 74 65 73 20 66 72 6f 6d RT %d bytes from
45f0: 20 56 32 5b 25 64 2e 2e 25 64 5d 5c 6e 22 2c 0a V2[%d..%d]\n",.
4600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
4610: 20 20 70 2d 3e 6e 45 78 74 72 61 2c 20 70 2d 3e p->nExtra, p->
4620: 74 6f 4c 61 73 74 2b 31 2c 20 70 2d 3e 74 6f 4c toLast+1, p->toL
4630: 61 73 74 2b 70 2d 3e 6e 45 78 74 72 61 29 3b 0a ast+p->nExtra);.
4640: 20 20 20 20 20 20 20 20 29 0a 20 20 20 20 20 20 ).
4650: 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 4d 61 }. }. }. Ma
4660: 70 70 69 6e 67 43 6c 65 61 72 28 26 6d 61 70 31 ppingClear(&map1
4670: 29 3b 0a 20 20 4d 61 70 70 69 6e 67 43 6c 65 61 );. MappingClea
4680: 72 28 26 6d 61 70 32 29 3b 0a 7d 0a 0a 2f 2a 0a r(&map2);.}../*.
4690: 2a 2a 20 43 4f 4d 4d 41 4e 44 3a 20 20 74 65 73 ** COMMAND: tes
46a0: 74 2d 33 2d 77 61 79 2d 6d 65 72 67 65 0a 2a 2a t-3-way-merge.**
46b0: 0a 2a 2a 20 43 6f 6d 62 69 6e 65 20 63 68 61 6e .** Combine chan
46c0: 67 65 20 69 6e 20 67 6f 69 6e 67 20 66 72 6f 6d ge in going from
46d0: 20 50 49 56 4f 54 2d 3e 56 45 52 53 49 4f 4e 31 PIVOT->VERSION1
46e0: 20 77 69 74 68 20 74 68 65 20 63 68 61 6e 67 65 with the change
46f0: 20 67 6f 69 6e 67 0a 2a 2a 20 66 72 6f 6d 20 50 going.** from P
4700: 49 56 4f 54 2d 3e 56 45 52 53 49 4f 4e 32 20 61 IVOT->VERSION2 a
4710: 6e 64 20 77 72 69 74 65 20 74 68 65 20 63 6f 6d nd write the com
4720: 62 69 6e 65 64 20 63 68 61 6e 67 65 73 20 69 6e bined changes in
4730: 74 6f 20 4d 45 52 47 45 44 2e 0a 2a 2f 0a 76 6f to MERGED..*/.vo
4740: 69 64 20 64 65 6c 74 61 5f 33 77 61 79 6d 65 72 id delta_3waymer
4750: 67 65 5f 63 6d 64 28 76 6f 69 64 29 7b 0a 20 20 ge_cmd(void){.
4760: 42 6c 6f 62 20 70 69 76 6f 74 2c 20 76 31 2c 20 Blob pivot, v1,
4770: 76 32 2c 20 6d 65 72 67 65 64 3b 0a 20 20 69 66 v2, merged;. if
4780: 28 20 67 2e 61 72 67 63 21 3d 36 20 29 7b 0a 20 ( g.argc!=6 ){.
4790: 20 20 20 66 70 72 69 6e 74 66 28 73 74 64 65 72 fprintf(stder
47a0: 72 2c 22 55 73 61 67 65 3a 20 25 73 20 25 73 20 r,"Usage: %s %s
47b0: 50 49 56 4f 54 20 56 31 20 56 32 20 4d 45 52 47 PIVOT V1 V2 MERG
47c0: 45 44 5c 6e 22 2c 20 67 2e 61 72 67 76 5b 30 5d ED\n", g.argv[0]
47d0: 2c 20 67 2e 61 72 67 76 5b 31 5d 29 3b 0a 20 20 , g.argv[1]);.
47e0: 20 20 65 78 69 74 28 31 29 3b 0a 20 20 7d 0a 20 exit(1);. }.
47f0: 20 69 66 28 20 62 6c 6f 62 5f 72 65 61 64 5f 66 if( blob_read_f
4800: 72 6f 6d 5f 66 69 6c 65 28 26 70 69 76 6f 74 2c rom_file(&pivot,
4810: 20 67 2e 61 72 67 76 5b 32 5d 29 3c 30 20 29 7b g.argv[2])<0 ){
4820: 0a 20 20 20 20 66 70 72 69 6e 74 66 28 73 74 64 . fprintf(std
4830: 65 72 72 2c 22 63 61 6e 6e 6f 74 20 72 65 61 64 err,"cannot read
4840: 20 25 73 5c 6e 22 2c 20 67 2e 61 72 67 76 5b 32 %s\n", g.argv[2
4850: 5d 29 3b 0a 20 20 20 20 65 78 69 74 28 31 29 3b ]);. exit(1);
4860: 0a 20 20 7d 0a 20 20 69 66 28 20 62 6c 6f 62 5f . }. if( blob_
4870: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
4880: 76 31 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3c 30 v1, g.argv[3])<0
4890: 20 29 7b 0a 20 20 20 20 66 70 72 69 6e 74 66 28 ){. fprintf(
48a0: 73 74 64 65 72 72 2c 22 63 61 6e 6e 6f 74 20 72 stderr,"cannot r
48b0: 65 61 64 20 25 73 5c 6e 22 2c 20 67 2e 61 72 67 ead %s\n", g.arg
48c0: 76 5b 33 5d 29 3b 0a 20 20 20 20 65 78 69 74 28 v[3]);. exit(
48d0: 31 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20 62 6c 1);. }. if( bl
48e0: 6f 62 5f 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c ob_read_from_fil
48f0: 65 28 26 76 32 2c 20 67 2e 61 72 67 76 5b 34 5d e(&v2, g.argv[4]
4900: 29 3c 30 20 29 7b 0a 20 20 20 20 66 70 72 69 6e )<0 ){. fprin
4910: 74 66 28 73 74 64 65 72 72 2c 22 63 61 6e 6e 6f tf(stderr,"canno
4920: 74 20 72 65 61 64 20 25 73 5c 6e 22 2c 20 67 2e t read %s\n", g.
4930: 61 72 67 76 5b 34 5d 29 3b 0a 20 20 20 20 65 78 argv[4]);. ex
4940: 69 74 28 31 29 3b 0a 20 20 7d 0a 20 20 62 6c 6f it(1);. }. blo
4950: 62 5f 6d 65 72 67 65 28 26 70 69 76 6f 74 2c 20 b_merge(&pivot,
4960: 26 76 31 2c 20 26 76 32 2c 20 26 6d 65 72 67 65 &v1, &v2, &merge
4970: 64 29 3b 0a 20 20 69 66 28 20 62 6c 6f 62 5f 77 d);. if( blob_w
4980: 72 69 74 65 5f 74 6f 5f 66 69 6c 65 28 26 6d 65 rite_to_file(&me
4990: 72 67 65 64 2c 20 67 2e 61 72 67 76 5b 35 5d 29 rged, g.argv[5])
49a0: 3c 62 6c 6f 62 5f 73 69 7a 65 28 26 6d 65 72 67 <blob_size(&merg
49b0: 65 64 29 20 29 7b 0a 20 20 20 20 66 70 72 69 6e ed) ){. fprin
49c0: 74 66 28 73 74 64 65 72 72 2c 22 63 61 6e 6e 6f tf(stderr,"canno
49d0: 74 20 77 72 69 74 65 20 25 73 5c 6e 22 2c 20 67 t write %s\n", g
49e0: 2e 61 72 67 76 5b 34 5d 29 3b 0a 20 20 20 20 65 .argv[4]);. e
49f0: 78 69 74 28 31 29 3b 0a 20 20 7d 0a 20 20 62 6c xit(1);. }. bl
4a00: 6f 62 5f 72 65 73 65 74 28 26 70 69 76 6f 74 29 ob_reset(&pivot)
4a10: 3b 0a 20 20 62 6c 6f 62 5f 72 65 73 65 74 28 26 ;. blob_reset(&
4a20: 76 31 29 3b 0a 20 20 62 6c 6f 62 5f 72 65 73 65 v1);. blob_rese
4a30: 74 28 26 76 32 29 3b 0a 20 20 62 6c 6f 62 5f 72 t(&v2);. blob_r
4a40: 65 73 65 74 28 26 6d 65 72 67 65 64 29 3b 0a 7d eset(&merged);.}
4a50: 0a 0a 0a 2f 2a 0a 2a 2a 20 43 4f 4d 4d 41 4e 44 .../*.** COMMAND
4a60: 3a 20 20 74 65 73 74 2d 6d 61 70 70 69 6e 67 0a : test-mapping.
4a70: 2a 2f 0a 76 6f 69 64 20 6d 61 70 70 69 6e 67 5f */.void mapping_
4a80: 74 65 73 74 28 76 6f 69 64 29 7b 0a 20 20 69 6e test(void){. in
4a90: 74 20 69 3b 0a 20 20 63 6f 6e 73 74 20 63 68 61 t i;. const cha
4aa0: 72 20 2a 7a 3b 0a 20 20 42 6c 6f 62 20 61 2c 20 r *z;. Blob a,
4ab0: 62 3b 0a 20 20 4d 61 70 70 69 6e 67 20 6d 61 70 b;. Mapping map
4ac0: 3b 0a 20 20 69 66 28 20 67 2e 61 72 67 63 21 3d ;. if( g.argc!=
4ad0: 34 20 29 7b 0a 20 20 20 20 75 73 61 67 65 28 22 4 ){. usage("
4ae0: 46 49 4c 45 31 20 46 49 4c 45 32 22 29 3b 0a 20 FILE1 FILE2");.
4af0: 20 7d 0a 20 20 62 6c 6f 62 5f 72 65 61 64 5f 66 }. blob_read_f
4b00: 72 6f 6d 5f 66 69 6c 65 28 26 61 2c 20 67 2e 61 rom_file(&a, g.a
4b10: 72 67 76 5b 32 5d 29 3b 0a 20 20 62 6c 6f 62 5f rgv[2]);. blob_
4b20: 72 65 61 64 5f 66 72 6f 6d 5f 66 69 6c 65 28 26 read_from_file(&
4b30: 62 2c 20 67 2e 61 72 67 76 5b 33 5d 29 3b 0a 20 b, g.argv[3]);.
4b40: 20 6d 65 6d 73 65 74 28 26 6d 61 70 2c 20 30 2c memset(&map, 0,
4b50: 20 73 69 7a 65 6f 66 28 6d 61 70 29 29 3b 0a 20 sizeof(map));.
4b60: 20 4d 61 70 70 69 6e 67 49 6e 69 74 28 62 6c 6f MappingInit(blo
4b70: 62 5f 62 75 66 66 65 72 28 26 61 29 2c 20 62 6c b_buffer(&a), bl
4b80: 6f 62 5f 73 69 7a 65 28 26 61 29 2c 0a 20 20 20 ob_size(&a),.
4b90: 20 20 20 20 20 20 20 20 20 20 20 62 6c 6f 62 5f blob_
4ba0: 62 75 66 66 65 72 28 26 62 29 2c 20 62 6c 6f 62 buffer(&b), blob
4bb0: 5f 73 69 7a 65 28 26 62 29 2c 0a 20 20 20 20 20 _size(&b),.
4bc0: 20 20 20 20 20 20 20 20 20 26 6d 61 70 29 3b 0a &map);.
4bd0: 20 20 7a 20 3d 20 62 6c 6f 62 5f 62 75 66 66 65 z = blob_buffe
4be0: 72 28 26 61 29 3b 0a 20 20 66 6f 72 28 69 3d 30 r(&a);. for(i=0
4bf0: 3b 20 69 3c 6d 61 70 2e 6e 55 73 65 64 3b 20 69 ; i<map.nUsed; i
4c00: 2b 2b 29 7b 0a 20 20 20 20 70 72 69 6e 74 66 28 ++){. printf(
4c10: 22 3d 3d 3d 3d 3d 3d 3d 20 25 36 64 2e 2e 25 2d "======= %6d..%-
4c20: 36 64 20 25 36 64 2e 2e 25 2d 36 64 20 25 64 5c 6d %6d..%-6d %d\
4c30: 6e 22 2c 20 0a 20 20 20 20 20 20 20 20 20 6d 61 n", . ma
4c40: 70 2e 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 p.aMap[i].fromFi
4c50: 72 73 74 2c 20 6d 61 70 2e 61 4d 61 70 5b 69 5d rst, map.aMap[i]
4c60: 2e 66 72 6f 6d 4c 61 73 74 2c 0a 20 20 20 20 20 .fromLast,.
4c70: 20 20 20 20 6d 61 70 2e 61 4d 61 70 5b 69 5d 2e map.aMap[i].
4c80: 74 6f 46 69 72 73 74 2c 20 6d 61 70 2e 61 4d 61 toFirst, map.aMa
4c90: 70 5b 69 5d 2e 74 6f 4c 61 73 74 2c 0a 20 20 20 p[i].toLast,.
4ca0: 20 20 20 20 20 20 6d 61 70 2e 61 4d 61 70 5b 69 map.aMap[i
4cb0: 5d 2e 6e 45 78 74 72 61 29 3b 0a 20 20 20 20 70 ].nExtra);. p
4cc0: 72 69 6e 74 66 28 22 25 2e 2a 73 5c 6e 22 2c 20 rintf("%.*s\n",
4cd0: 6d 61 70 2e 61 4d 61 70 5b 69 5d 2e 66 72 6f 6d map.aMap[i].from
4ce0: 4c 61 73 74 20 2d 20 6d 61 70 2e 61 4d 61 70 5b Last - map.aMap[
4cf0: 69 5d 2e 66 72 6f 6d 46 69 72 73 74 20 2b 20 31 i].fromFirst + 1
4d00: 2c 20 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 , .
4d10: 20 20 20 20 20 20 20 20 26 7a 5b 6d 61 70 2e 61 &z[map.a
4d20: 4d 61 70 5b 69 5d 2e 66 72 6f 6d 46 69 72 73 74 Map[i].fromFirst
4d30: 5d 29 3b 0a 20 20 7d 0a 7d 0a ]);. }.}.