1 /*
2 Copyright (c) 1991-1999 Thomas T. Wetmore IV
3
4 Permission is hereby granted, free of charge, to any person
5 obtaining a copy of this software and associated documentation
6 files (the "Software"), to deal in the Software without
7 restriction, including without limitation the rights to use, copy,
8 modify, merge, publish, distribute, sublicense, and/or sell copies
9 of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be
13 included in all copies or substantial portions of the Software.
14
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24 /* modified 05 Jan 2000 by Paul B. McBride (pmcbride@tiac.net) */
25 /*=============================================================
26 * nodeutls.c -- Various node utility functions
27 * Copyright(c) 1995-96 by T.T. Wetmore IV; all rights reserved
28 * 3.0.3 - 15 Feb 96
29 *===========================================================*/
30
31 #include "llstdlib.h"
32 #include "btree.h"
33 #include "table.h"
34 #include "translat.h"
35 #include "gedcom.h"
36
37
38 /*********************************************
39 * local function prototypes
40 *********************************************/
41
42 /* alphabetical */
43 static BOOLEAN nvaldiff(NODE node1, NODE node2);
44
45 /*======================================================================
46 * unique_nodes -- Remove duplicates from list of nodes -- original list
47 * is modified
48 *====================================================================*/
49 NODE
unique_nodes(NODE node,BOOLEAN kids)50 unique_nodes (NODE node,
51 BOOLEAN kids) /* children matter */
52 {
53 NODE node0 = node, prev, this, next;
54
55 if (!node) return NULL;
56 while (node) {
57 prev = node;
58 this = nsibling(node);
59 while (this) {
60 if (iso_nodes(node, this, kids, FALSE)) {
61 nsibling(prev) = next = nsibling(this);
62 nsibling(this) = NULL;
63 free_nodes(this);
64 this = next;
65 } else {
66 prev = this;
67 this = nsibling(this);
68 }
69 }
70 node = nsibling(node);
71 }
72 return node0;
73 }
74 /*==============================================
75 * union_nodes -- Return union of two node trees
76 *============================================*/
77 NODE
union_nodes(NODE node1,NODE node2,BOOLEAN kids,BOOLEAN copy)78 union_nodes (NODE node1,
79 NODE node2,
80 BOOLEAN kids, /* children matter */
81 BOOLEAN copy) /* copy operands first */
82 {
83 NODE curs1, next1, prev1, curs2, prev2;
84
85 if (copy) node1 = copy_nodes(node1, TRUE, TRUE);
86 if (copy) node2 = copy_nodes(node2, TRUE, TRUE);
87 prev2 = NULL;
88 curs2 = node2;
89 while (curs2) {
90 prev1 = NULL;
91 curs1 = node1;
92 while (curs1 && !iso_nodes(curs1, curs2, kids, FALSE)) {
93 prev1 = curs1;
94 curs1 = nsibling(curs1);
95 }
96 if (curs1) {
97 next1 = nsibling(curs1);
98 nsibling(curs1) = NULL;
99 free_nodes(curs1);
100 if (prev1)
101 nsibling(prev1) = next1;
102 else
103 node1 = next1;
104 }
105 prev2 = curs2;
106 curs2 = nsibling(curs2);
107 }
108 if (prev2) {
109 nsibling(prev2) = node1;
110 return node2;
111 }
112 return node1;
113 }
114
115 #ifdef UNUSED_CODE
116 /*=========================================================
117 * intersect_nodes -- Return intersection of two node trees
118 * UNUSED CODE
119 *=======================================================*/
120 NODE
intersect_nodes(NODE node1,NODE node2,BOOLEAN kids)121 intersect_nodes (NODE node1,
122 NODE node2,
123 BOOLEAN kids) /* children matter */
124 {
125 NODE prev1, curs1, next1, prev2, curs2, next2;
126 NODE node3, curs3;
127
128 if (!node1 || !node2) return NULL;
129 node1 = copy_nodes(node1, TRUE, TRUE);
130 node2 = copy_nodes(node2, TRUE, TRUE);
131 node3 = curs3 = NULL;
132
133 prev1 = NULL;
134 curs1 = node1;
135 while (curs1) {
136 prev2 = NULL;
137 curs2 = node2;
138 while (curs2 && !iso_nodes(curs1, curs2, kids, FALSE)) {
139 prev2 = curs2;
140 curs2 = nsibling(curs2);
141 }
142 if (curs2) {
143 next2 = nsibling(curs2);
144 nsibling(curs2) = NULL;
145
146 if (node3)
147 curs3 = nsibling(curs3) = curs2;
148 else
149 node3 = curs3 = curs2;
150 if (prev2)
151 nsibling(prev2) = next2;
152 else
153 node2 = next2;
154
155 next1 = nsibling(curs1);
156 nsibling(curs1) = NULL;
157 free_nodes(curs1);
158 if (prev1)
159 nsibling(prev1) = next1;
160 else
161 node1 = next1;
162 curs1 = next1;
163
164 } else {
165 prev1 = curs1;
166 curs1 = nsibling(curs1);
167 }
168 }
169 free_nodes(node1);
170 free_nodes(node2);
171 return node3;
172 }
173 #endif /* UNUSED_CODE */
174 /*========================================================================
175 * classify_nodes -- Convert two value lists to three lists - first
176 * returned list holds all values that were only in original first
177 * list - second returned list holds all values that were just in
178 * original second list - third returned list holds all values that were
179 * in both original lists
180 * pnode1 & pnode2 are the input lists to compare
181 * pnode1, pnode2, & pnode3 are the output lists.
182 *======================================================================*/
183 void
classify_nodes(NODE * pnode1,NODE * pnode2,NODE * pnode3)184 classify_nodes (NODE *pnode1, NODE *pnode2, NODE *pnode3)
185 {
186 NODE node1, node2, node3, curs1, curs2, curs3;
187 NODE prev1, prev2, next2;
188
189 curs1 = node1 = unique_nodes(*pnode1, FALSE);
190 curs2 = node2 = unique_nodes(*pnode2, FALSE);
191 curs3 = node3 = prev1 = prev2 = NULL;
192
193 while (curs1 && curs2) {
194 if (!nvaldiff(curs1, curs2)) {
195 if (node3)
196 curs3 = nsibling(curs3) = curs1;
197 else
198 node3 = curs3 = curs1;
199
200 curs1 = nsibling(curs1);
201 nsibling(curs3) = NULL;
202
203 if (prev1)
204 nsibling(prev1) = curs1;
205 else
206 node1 = curs1;
207
208 next2 = nsibling(curs2);
209 if (prev2)
210 nsibling(prev2) = next2;
211 else
212 node2 = next2;
213 nsibling(curs2) = NULL;
214 free_nodes(curs2);
215 curs2 = next2;
216 continue;
217 }
218 prev2 = curs2;
219 if ((curs2 = nsibling(curs2))) continue;
220 prev1 = curs1;
221 curs1 = nsibling(curs1);
222 prev2 = NULL;
223 curs2 = node2;
224 }
225 *pnode1 = node1;
226 *pnode2 = node2;
227 *pnode3 = node3;
228 }
229 /*===============================================
230 * nvaldiff -- Do nodes have different values ?
231 * handles NULLs in either
232 * Created: 2001/04/08, Perry Rapp
233 *=============================================*/
234 static BOOLEAN
nvaldiff(NODE node1,NODE node2)235 nvaldiff (NODE node1, NODE node2)
236 {
237 if (!nval(node1) && !nval(node2)) return FALSE;
238 if (!nval(node1) || !nval(node2)) return TRUE;
239 return strcmp(nval(node1), nval(node2));
240 }
241 #ifdef UNUSED_CODE
242 /*========================================================================
243 * difference_nodes -- Return difference of two node lists -- all in node1
244 * that are not in node2
245 * UNUSED CODE
246 *======================================================================*/
247 NODE
difference_nodes(NODE node1,NODE node2,BOOLEAN kids)248 difference_nodes (NODE node1,
249 NODE node2,
250 BOOLEAN kids) /* children matter */
251 {
252 NODE prev1, next1, curs1, curs2;
253 node1 = copy_nodes(node1, TRUE, TRUE);
254 prev1 = NULL;
255 curs1 = node1;
256 while (curs1) {
257 curs2 = node2;
258 while (curs2 && !iso_nodes(curs1, curs2, kids, FALSE))
259 curs2 = nsibling(curs2);
260 if (curs2) {
261 next1 = nsibling(curs1);
262 nsibling(curs1) = NULL;
263 free_nodes(curs1);
264 if (!prev1)
265 node1 = next1;
266 else
267 nsibling(prev1) = next1;
268 curs1 = next1;
269 } else {
270 prev1 = curs1;
271 curs1 = nsibling(curs1);
272 }
273 }
274 return node1;
275 }
276 #endif /* UNUSED_CODE */
277 #ifdef UNUSED_CODE
278 /*================================================================
279 * value_in_nodes -- See if a list of nodes contains a given value
280 * UNUSED CODE
281 *==============================================================*/
282 BOOLEAN
value_in_nodes(NODE node,STRING value)283 value_in_nodes (NODE node,
284 STRING value)
285 {
286 while (node) {
287 if (eqstr(value, nval(node))) return TRUE;
288 node = nsibling(node);
289 }
290 return FALSE;
291 }
292 #endif /* UNUSED_CODE */
293