author | Pierre-Yves David <pierre-yves.david@octobus.net> |
Mon, 09 Oct 2023 15:12:16 +0200 | |
changeset 51300 | 83c6dceeb10d |
parent 36830 | 882657a9f768 |
permissions | -rw-r--r-- |
36700 | 1 |
/* |
2 |
* LibXDiff by Davide Libenzi ( File Differential Library ) |
|
3 |
* Copyright (C) 2003 Davide Libenzi |
|
4 |
* |
|
5 |
* This library is free software; you can redistribute it and/or |
|
6 |
* modify it under the terms of the GNU Lesser General Public |
|
7 |
* License as published by the Free Software Foundation; either |
|
8 |
* version 2.1 of the License, or (at your option) any later version. |
|
9 |
* |
|
10 |
* This library is distributed in the hope that it will be useful, |
|
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
13 |
* Lesser General Public License for more details. |
|
14 |
* |
|
15 |
* You should have received a copy of the GNU Lesser General Public |
|
16 |
* License along with this library; if not, see |
|
17 |
* <http://www.gnu.org/licenses/>. |
|
18 |
* |
|
19 |
* Davide Libenzi <davidel@xmailserver.org> |
|
20 |
* |
|
21 |
*/ |
|
22 |
||
23 |
#if !defined(XTYPES_H) |
|
24 |
#define XTYPES_H |
|
25 |
||
26 |
||
27 |
||
28 |
typedef struct s_chanode { |
|
29 |
struct s_chanode *next; |
|
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
30 |
int64_t icurr; |
36700 | 31 |
} chanode_t; |
32 |
||
33 |
typedef struct s_chastore { |
|
34 |
chanode_t *head, *tail; |
|
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
35 |
int64_t isize, nsize; |
36700 | 36 |
chanode_t *ancur; |
37 |
chanode_t *sncur; |
|
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
38 |
int64_t scurr; |
36700 | 39 |
} chastore_t; |
40 |
||
41 |
typedef struct s_xrecord { |
|
42 |
struct s_xrecord *next; |
|
43 |
char const *ptr; |
|
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
44 |
int64_t size; |
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
45 |
uint64_t ha; |
36700 | 46 |
} xrecord_t; |
47 |
||
48 |
typedef struct s_xdfile { |
|
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
49 |
/* manual memory management */ |
36700 | 50 |
chastore_t rcha; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
51 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
52 |
/* number of records (lines) */ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
53 |
int64_t nrec; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
54 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
55 |
/* hash table size |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
56 |
* the maximum hash value in the table is (1 << hbits) */ |
36700 | 57 |
unsigned int hbits; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
58 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
59 |
/* hash table, hash value => xrecord_t |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
60 |
* note: xrecord_t is a linked list. */ |
36700 | 61 |
xrecord_t **rhash; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
62 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
63 |
/* range excluding common prefix and suffix |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
64 |
* [recs[i] for i in range(0, dstart)] are common prefix. |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
65 |
* [recs[i] for i in range(dstart, dend + 1 - dstart)] are interesting |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
66 |
* lines */ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
67 |
int64_t dstart, dend; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
68 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
69 |
/* pointer to records (lines) */ |
36700 | 70 |
xrecord_t **recs; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
71 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
72 |
/* record changed, use original "recs" index |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
73 |
* rchag[i] can be either 0 or 1. 1 means recs[i] (line i) is marked |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
74 |
* "changed". */ |
36700 | 75 |
char *rchg; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
76 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
77 |
/* cleaned-up record index => original "recs" index |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
78 |
* clean-up means: |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
79 |
* rule 1. remove common prefix and suffix |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
80 |
* rule 2. remove records that are only on one side, since they can |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
81 |
* not match the other side |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
82 |
* rindex[0] is likely dstart, if not removed up by rule 2. |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
83 |
* rindex[nreff - 1] is likely dend, if not removed by rule 2. |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
84 |
*/ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
85 |
int64_t *rindex; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
86 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
87 |
/* rindex size */ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
88 |
int64_t nreff; |
36829
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
89 |
|
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
90 |
/* cleaned-up record index => hash value |
0c7350656f93
xdiff: add comments for fields in xdfile_t
Jun Wu <quark@fb.com>
parents:
36828
diff
changeset
|
91 |
* ha[i] = recs[rindex[i]]->ha */ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
92 |
uint64_t *ha; |
36700 | 93 |
} xdfile_t; |
94 |
||
95 |
typedef struct s_xdfenv { |
|
96 |
xdfile_t xdf1, xdf2; |
|
36828
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36700
diff
changeset
|
97 |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36700
diff
changeset
|
98 |
/* number of lines for common prefix and suffix that are removed |
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36700
diff
changeset
|
99 |
* from xdf1 and xdf2 as a preprocessing step */ |
36830
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36829
diff
changeset
|
100 |
int64_t nprefix, nsuffix; |
36700 | 101 |
} xdfenv_t; |
102 |
||
103 |
||
104 |
||
105 |
#endif /* #if !defined(XTYPES_H) */ |