string_merge.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649
  1. #include "string.h"
  2. #include "assert.h"
  3. #include "stddef.h"
  4. #include <limits.h>
  5. #include <stdbool.h>
  6. #include "minmax.h"
  7. #include "debug.h"
  8. #include "doc_elt_util.h"
  9. #include "doc_ref.h"
  10. #include "doc_stream.h"
  11. #include "print.h"
  12. #include "string_merge.h"
  13. #define OFFSET int
  14. void
  15. substr_print_merge (substr loc_text, substr rem_text, print_ctxt *ctxt, doc_stream *out)
  16. {
  17. line_diff (loc_text.string, loc_text.length, rem_text.string, rem_text.length,
  18. ctxt, out);
  19. return;
  20. }
  21. void
  22. line_diff (char *loc_s, size_t loc_len, char *rem_s, size_t rem_len,
  23. print_ctxt *print_ctxt, doc_stream *out)
  24. {
  25. /*
  26. * Scan the amount of lines in each string, create a state for each
  27. * line, camopareseq the lines, print the merged lines
  28. */
  29. size_t loc_line_count, rem_line_count;
  30. loc_line_count = count_lines (loc_s, loc_len);
  31. rem_line_count = count_lines (rem_s, rem_len);
  32. debug_msg (DOC, 5, "START: loc: len=%d, lines=%d\n"
  33. " rem: len=%d, lines=%d\n",
  34. loc_len, loc_line_count, rem_len, rem_line_count);
  35. /* create a index into the strings */
  36. size_t *loc_lines = malloc (sizeof (size_t) * (loc_line_count + 1));
  37. index_lines (loc_lines, loc_s, loc_len);
  38. size_t *rem_lines = malloc (sizeof (size_t) * (rem_line_count + 1));
  39. index_lines (rem_lines, rem_s, rem_len);
  40. /* store if a line has a match or not, initialized to false */
  41. bool *loc_state = calloc (loc_line_count, sizeof (bool));
  42. bool *rem_state = calloc (rem_line_count, sizeof (bool));
  43. /* calculate the mappings */
  44. string_index_compareseq (loc_s, loc_line_count, loc_lines, loc_state,
  45. rem_s, rem_line_count, rem_lines, rem_state);
  46. /* print the diff'd lines */
  47. size_t loc_index = 0;
  48. size_t rem_index = 0;
  49. while ( loc_index < loc_line_count ||
  50. rem_index < rem_line_count )
  51. {
  52. if ((loc_index < loc_line_count) &&
  53. (loc_state[loc_index] == unmapped))
  54. {
  55. debug_msg (DOC, 5, "note:\n");
  56. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  57. enter_content_conflict (print_ctxt, local_side, "Updated\n", out);
  58. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  59. loc_length, out);
  60. loc_index++;
  61. }
  62. else if ((rem_index < rem_line_count) &&
  63. (rem_state[rem_index] == unmapped))
  64. {
  65. debug_msg (DOC, 5, "note:\n");
  66. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  67. enter_content_conflict (print_ctxt, remote_side, "\n", out);
  68. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  69. rem_length, out);
  70. rem_index++;
  71. }
  72. else if (rem_state[rem_index] == mapped &&
  73. loc_state[loc_index] == mapped)
  74. {
  75. debug_msg (DOC, 5, "note:\n");
  76. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  77. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  78. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  79. loc_length, out);
  80. rem_index++;
  81. loc_index++;
  82. }
  83. }
  84. /* finish up any conflict markers if the loop left a conflicted state */
  85. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  86. free (loc_lines);
  87. free (rem_lines);
  88. free (loc_state);
  89. free (rem_state);
  90. return;
  91. }
  92. void
  93. line_diff_only_known_overlap3 (char *anc_s, size_t anc_len, char *loc_s, size_t loc_len,
  94. char *rem_s, size_t rem_len, print_ctxt *print_ctxt, doc_stream *out)
  95. {
  96. /*
  97. * Scan the amount of lines in each string, create a state for each
  98. * line, camopareseq the lines, print the merged lines
  99. */
  100. size_t anc_line_count, loc_line_count, rem_line_count;
  101. anc_line_count = count_lines (anc_s, anc_len);
  102. loc_line_count = count_lines (loc_s, loc_len);
  103. rem_line_count = count_lines (rem_s, rem_len);
  104. debug_msg (DOC, 5, "\nSTART: loc: len=%d, lines=%d\n"
  105. " rem: len=%d, lines=%d\n"
  106. " anc: len=%d, lines=%d\n",
  107. loc_len, loc_line_count, rem_len, rem_line_count, anc_len, anc_line_count);
  108. /* create a index into the strings */
  109. size_t *anc_lines = malloc (sizeof (size_t) * (anc_line_count + 1));
  110. index_lines (anc_lines, anc_s, anc_len);
  111. size_t *loc_lines = malloc (sizeof (size_t) * (loc_line_count + 1));
  112. index_lines (loc_lines, loc_s, loc_len);
  113. size_t *rem_lines = malloc (sizeof (size_t) * (rem_line_count + 1));
  114. index_lines (rem_lines, rem_s, rem_len);
  115. /* store if a line has a match or not, initialized to false */
  116. bool *loc_anc_state = calloc (anc_line_count, sizeof (bool));
  117. bool *loc_state = calloc (loc_line_count, sizeof (bool));
  118. bool *rem_anc_state = calloc (anc_line_count, sizeof (bool));
  119. bool *rem_state = calloc (rem_line_count, sizeof (bool));
  120. /* calculate the mappings for ancestor and local */
  121. string_index_compareseq (anc_s, anc_line_count, anc_lines, loc_anc_state,
  122. loc_s, loc_line_count, loc_lines, loc_state);
  123. /* calculate the mappings for ancestor and remote */
  124. string_index_compareseq (anc_s, anc_line_count, anc_lines, rem_anc_state,
  125. rem_s, rem_line_count, rem_lines, rem_state);
  126. /* print merge the objects */
  127. size_t loc_index = 0;
  128. size_t loc_anc_index = 0;
  129. size_t rem_index = 0;
  130. size_t rem_anc_index = 0;
  131. while ( loc_index < loc_line_count ||
  132. rem_index < rem_line_count )
  133. {
  134. if ((loc_index < loc_line_count) &&
  135. (loc_state[loc_index] == unmapped))
  136. {
  137. if ((rem_index < rem_line_count) &&
  138. (rem_state[rem_index] == unmapped))
  139. {
  140. /* overlapping inserts, print all local inserts,
  141. * followed by all remote inserts in conflict markers.
  142. * Stop printing when the next element is not an
  143. * insert */
  144. enter_content_conflict (print_ctxt, local_side, "Updated\n", out);
  145. while ((loc_index < loc_line_count) &&
  146. (loc_state[loc_index] == unmapped))
  147. {
  148. /* print all local unmapped */
  149. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  150. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  151. loc_length, out);
  152. loc_index ++;
  153. }
  154. enter_content_conflict (print_ctxt, remote_side, "\n", out);
  155. while ((rem_index < rem_line_count) &&
  156. (rem_state[rem_index] == unmapped))
  157. {
  158. /* print all remote unmapped */
  159. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  160. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  161. rem_length, out);
  162. rem_index ++;
  163. }
  164. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  165. }
  166. else
  167. {
  168. /* insert only in local */
  169. while ((loc_index < loc_line_count) &&
  170. (loc_state[loc_index] == unmapped))
  171. {
  172. /* print all local unmapped */
  173. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  174. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  175. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  176. loc_length, out);
  177. loc_index++;
  178. }
  179. }
  180. }
  181. else if ((rem_index < rem_line_count) &&
  182. (rem_state[rem_index] == unmapped))
  183. {
  184. /* insert in remote only */
  185. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  186. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  187. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  188. rem_length, out);
  189. rem_index++;
  190. }
  191. else if (rem_index < rem_line_count &&
  192. loc_index < loc_line_count &&
  193. rem_state[rem_index] == mapped &&
  194. loc_state[loc_index] == mapped)
  195. {
  196. /* two mapped lines, print one of them:
  197. * advance the ancestor pointers untill they are both 'mapped'
  198. * if the both the remote and local have the same ancestor, then print the line
  199. * if one of them points to a previos ancestor, it was deleted in the other file
  200. *
  201. * If an element was deleted in one file, advance the other file
  202. * If the element is in both files, advance all files forwards
  203. */
  204. /* advance the ancestors to the next mapped element */
  205. while (rem_anc_state[rem_anc_index] == unmapped &&
  206. rem_anc_index < anc_line_count)
  207. rem_anc_index ++;
  208. assert (rem_anc_state[rem_anc_index] == mapped);
  209. while (loc_anc_state[loc_anc_index] == unmapped &&
  210. loc_anc_index < anc_line_count)
  211. loc_anc_index ++;
  212. assert (loc_anc_state[loc_anc_index] == mapped);
  213. /* check to see if both elements point to the same ancestor */
  214. if (loc_anc_index == rem_anc_index)
  215. {
  216. /* same line in both files, print it */
  217. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  218. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  219. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  220. rem_length, out);
  221. rem_index++;
  222. loc_index++;
  223. loc_anc_index++;
  224. rem_anc_index++;
  225. }
  226. else if (loc_anc_index < rem_anc_index)
  227. {
  228. /* deleted line in remote */
  229. loc_index++;
  230. loc_anc_index++;
  231. }
  232. else /* loc_anc_index > rem_anc_index */
  233. {
  234. /* line deleted in local */
  235. rem_index++;
  236. rem_anc_index ++;
  237. }
  238. }
  239. }
  240. free (anc_lines);
  241. free (loc_lines);
  242. free (rem_lines);
  243. free (loc_anc_state);
  244. free (loc_state);
  245. free (rem_anc_state);
  246. free (rem_state);
  247. return;
  248. }
  249. void
  250. line_diff3 (char *anc_s, size_t anc_len, char *loc_s, size_t loc_len,
  251. char *rem_s, size_t rem_len, print_ctxt *print_ctxt, doc_stream *out)
  252. {
  253. /*
  254. * Scan the amount of lines in each string, create a state for each
  255. * line, camopareseq the lines, print the merged lines
  256. */
  257. size_t anc_line_count, loc_line_count, rem_line_count;
  258. anc_line_count = count_lines (anc_s, anc_len);
  259. loc_line_count = count_lines (loc_s, loc_len);
  260. rem_line_count = count_lines (rem_s, rem_len);
  261. debug_msg (DOC, 5, "\nSTART: loc: len=%d, lines=%d\n"
  262. " rem: len=%d, lines=%d\n"
  263. " anc: len=%d, lines=%d\n",
  264. loc_len, loc_line_count, rem_len, rem_line_count, anc_len, anc_line_count);
  265. /* create a index into the strings */
  266. size_t *anc_lines = malloc (sizeof (size_t) * (anc_line_count + 1));
  267. index_lines (anc_lines, anc_s, anc_len);
  268. size_t *loc_lines = malloc (sizeof (size_t) * (loc_line_count + 1));
  269. index_lines (loc_lines, loc_s, loc_len);
  270. size_t *rem_lines = malloc (sizeof (size_t) * (rem_line_count + 1));
  271. index_lines (rem_lines, rem_s, rem_len);
  272. /* store if a line has a match or not, initialized to false */
  273. bool *loc_anc_state = calloc (anc_line_count, sizeof (bool));
  274. bool *loc_state = calloc (loc_line_count, sizeof (bool));
  275. bool *rem_anc_state = calloc (anc_line_count, sizeof (bool));
  276. bool *rem_state = calloc (rem_line_count, sizeof (bool));
  277. /* calculate the mappings for ancestor and local */
  278. string_index_compareseq (anc_s, anc_line_count, anc_lines, loc_anc_state,
  279. loc_s, loc_line_count, loc_lines, loc_state);
  280. /* calculate the mappings for ancestor and remote */
  281. string_index_compareseq (anc_s, anc_line_count, anc_lines, rem_anc_state,
  282. rem_s, rem_line_count, rem_lines, rem_state);
  283. /* print merge the objects */
  284. size_t loc_index = 0;
  285. size_t loc_extent = 0;
  286. size_t anc_index = 0;
  287. size_t rem_index = 0;
  288. size_t rem_extent = 0;
  289. debug_msg (DOC, 5,"starting the merge\n");
  290. bool extent_found = false, loc_update = false, rem_update = false;
  291. int changes = 0;
  292. int rem_mapped_count = 0, loc_mapped_count = 0;
  293. while ( loc_index < loc_line_count ||
  294. rem_index < rem_line_count )
  295. {
  296. /* calculate the range of the extent */
  297. extent_found = false;
  298. loc_update = false;
  299. rem_update = false;
  300. changes = 0;
  301. rem_mapped_count = 1;
  302. loc_mapped_count = 1;
  303. /* find mapped ancestor */
  304. while ((anc_index < anc_line_count) &&
  305. ((rem_anc_state[anc_index] == unmapped) ||
  306. (loc_anc_state[anc_index] == unmapped)))
  307. {
  308. if (rem_anc_state[anc_index] == mapped)
  309. rem_mapped_count ++;
  310. if (loc_anc_state[anc_index] == mapped)
  311. loc_mapped_count ++;
  312. anc_index ++;
  313. }
  314. /* ancestor index now points to a mutualy mapped line.
  315. * mapped_count = mapped elements, including the element the extent points to
  316. */
  317. /* find the local extent */
  318. int mapped_count = 0;
  319. while (loc_extent < loc_line_count)
  320. {
  321. if (loc_state[loc_extent] == mapped)
  322. mapped_count ++;
  323. else
  324. loc_update = true;
  325. /* if the element is at the correct spot, break eaply to
  326. keep it from incrementing one last time */
  327. if (mapped_count >= loc_mapped_count)
  328. break;
  329. loc_extent ++;
  330. }
  331. /* find the remote extent */
  332. mapped_count = 0;
  333. while (rem_extent < rem_line_count)
  334. {
  335. if (rem_state[rem_extent] == mapped)
  336. mapped_count ++;
  337. else
  338. rem_update = true;
  339. if (mapped_count >= rem_mapped_count)
  340. break;
  341. rem_extent++;
  342. }
  343. /* the remote and local extents should be pointing at a ancestor
  344. element in both files */
  345. /* set the extent to one before the matched element */
  346. debug_msg (DOC, 5, "anc_index=%d\n", anc_index);
  347. debug_msg (DOC, 5, "loc_index=%d rem_index=%d\n", loc_index, rem_index);
  348. debug_msg (DOC, 5, "loc_update=%d rem_update=%d\n", loc_update, rem_update);
  349. debug_msg (DOC, 5, "mapped in rem, count=%d\n", rem_mapped_count);
  350. debug_msg (DOC, 5, "mapped in loc, count=%d\n", loc_mapped_count);
  351. debug_msg (DOC, 5, "extents are loc=%d, rem=%d\n", loc_extent, rem_extent);
  352. if (loc_update)
  353. {
  354. if (rem_update)
  355. {
  356. /* conflict both sides */
  357. /* overlapping inserts, print all local inserts,
  358. * followed by all remote inserts in conflict markers.
  359. * Stop printing when the next element is not an
  360. * insert */
  361. enter_content_conflict (print_ctxt, local_side, "Updated\n", out);
  362. while (loc_index < loc_extent)
  363. {
  364. /* print all local unmapped */
  365. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  366. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  367. loc_length, out);
  368. loc_index ++;
  369. }
  370. enter_content_conflict (print_ctxt, remote_side, "\n", out);
  371. while (rem_index < rem_extent)
  372. {
  373. /* print all remote unmapped */
  374. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  375. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  376. rem_length, out);
  377. rem_index ++;
  378. }
  379. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  380. }
  381. else /* !rem_update */
  382. {
  383. /* print local side */
  384. while (loc_index < loc_extent)
  385. {
  386. if (loc_state[loc_index] == unmapped)
  387. {
  388. /* print all local unmapped */
  389. size_t loc_length = loc_lines[loc_index+1] - loc_lines[loc_index];
  390. doc_stream_fwrite (loc_s + loc_lines[loc_index], sizeof (char),
  391. loc_length, out);
  392. }
  393. loc_index ++;
  394. }
  395. }
  396. }
  397. else if (rem_update)
  398. {
  399. /* print remote side */
  400. while ((rem_index < rem_extent) &&
  401. (rem_state[rem_index] == unmapped))
  402. {
  403. if (rem_state[rem_index] == unmapped)
  404. {
  405. /* print all remote unmapped */
  406. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  407. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  408. rem_length, out);
  409. }
  410. rem_index ++;
  411. }
  412. }
  413. /* print the element at the extent */
  414. if (rem_extent < rem_line_count)
  415. {
  416. /* same line in both files, print it */
  417. enter_content_conflict (print_ctxt, no_conflict, "Updated\n", out);
  418. size_t rem_length = rem_lines[rem_index+1] - rem_lines[rem_index];
  419. doc_stream_fwrite (rem_s + rem_lines[rem_index], sizeof (char),
  420. rem_length, out);
  421. loc_index = loc_extent+1;
  422. rem_index = rem_extent+1;
  423. loc_extent++;
  424. rem_extent++;
  425. anc_index++;
  426. }
  427. else
  428. break;
  429. }
  430. free (anc_lines);
  431. free (loc_lines);
  432. free (rem_lines);
  433. free (loc_anc_state);
  434. free (loc_state);
  435. free (rem_anc_state);
  436. free (rem_state);
  437. return;
  438. }
  439. size_t
  440. count_lines (char *string, size_t length)
  441. {
  442. /* if there are X '\n's, there are (X+1) lines */
  443. size_t count = 1;
  444. size_t pos;
  445. for (pos = 0; pos < length; pos++)
  446. {
  447. if (string[pos] == '\n')
  448. count++;
  449. }
  450. return count;
  451. }
  452. void
  453. index_lines (size_t array[], char* string, size_t length)
  454. {
  455. /* The array will be indexed, such that the start and the end of the
  456. * string are the first and last elements, and the newlines are
  457. * marked in between.
  458. */
  459. size_t count = 1;
  460. size_t pos;
  461. /* the start of the string */
  462. array[0] = 0;
  463. /* the newlines */
  464. debug_msg (DOC, 5, "length: %d\n", length);
  465. for (pos = 0; pos < length; pos++)
  466. {
  467. if (string[pos] == '\n')
  468. {
  469. debug_msg (DOC, 5, "count: %d, pos=%d\n", count, pos);
  470. array[count] = pos+1;
  471. count++;
  472. }
  473. }
  474. /* the end of the sring */
  475. array[count] = length;
  476. return;
  477. }
  478. struct context;
  479. #undef USE_HEURISTIC
  480. #undef ELEMENT
  481. #undef EQUAL
  482. /* compareseq functions */
  483. static void note_delete (struct context *ctxt, OFFSET xoff);
  484. static void note_insert (struct context *ctxt, OFFSET yoff);
  485. static int compare (struct context *ctxt, OFFSET xoff, OFFSET yoff);
  486. /* extra fields for the compareseq context */
  487. #define EXTRA_CONTEXT_FIELDS \
  488. bool *loc_state; \
  489. bool *rem_state; \
  490. size_t *loc_indices; \
  491. size_t *rem_indices; \
  492. char *loc_string; \
  493. char *rem_string;
  494. /* ised to note adds and deletes in subsequences */
  495. #define NOTE_DELETE(ctxt, xoff) note_delete (ctxt, xoff)
  496. #define NOTE_INSERT(ctxt, yoff) note_insert (ctxt, yoff)
  497. #define XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff) compare (ctxt, xoff, yoff)
  498. #include "diffseq.h"
  499. #define OFFSET int
  500. void
  501. string_index_compareseq (char *loc_string, size_t loc_count,
  502. size_t *loc_indices, bool *loc_state,
  503. char *rem_string, size_t rem_count,
  504. size_t *rem_indices, bool *rem_state)
  505. {
  506. /* prepare the compareseq context */
  507. struct context ctxt;
  508. /* Add the caller data */
  509. ctxt.loc_state = loc_state;
  510. ctxt.loc_indices = loc_indices;
  511. ctxt.loc_string = loc_string;
  512. ctxt.rem_state = rem_state;
  513. ctxt.rem_indices = rem_indices;
  514. ctxt.rem_string = rem_string;
  515. /* Allocate data for the algorithm to use*/
  516. size_t diags = loc_count + rem_count + 3;
  517. void *mem = malloc (diags * (2 * sizeof (OFFSET)));
  518. ctxt.fdiag = mem;
  519. ctxt.bdiag = ctxt.fdiag + diags;
  520. ctxt.fdiag += rem_count + 1;
  521. ctxt.bdiag = ctxt.fdiag + diags;
  522. /* run a diffseq on the elements */
  523. compareseq (0, /* children index lower bound */
  524. loc_count, /* children index upper bound */
  525. 0, /* children index lower bound */
  526. rem_count, /* children index upper bound */
  527. 1, /* find optimal solution */
  528. &ctxt); /* difseq context created above */
  529. free (mem);
  530. }
  531. static void
  532. note_delete (struct context *ctxt, OFFSET xoff)
  533. {
  534. debug_msg (DOC, 5, "delete: %d\n", xoff);
  535. ctxt->loc_state[xoff] = unmapped;
  536. return;
  537. }
  538. static void
  539. note_insert (struct context *ctxt, OFFSET yoff)
  540. {
  541. debug_msg (DOC, 5, "insert: %d\n", yoff);
  542. ctxt->rem_state[yoff] = unmapped;
  543. return;
  544. }
  545. static int
  546. compare (struct context *ctxt, OFFSET xoff, OFFSET yoff)
  547. {
  548. int result = 0;
  549. size_t loc_length = (ctxt->loc_indices[xoff + 1] - ctxt->loc_indices[xoff]);
  550. size_t rem_length = (ctxt->rem_indices[yoff + 1] - ctxt->rem_indices[yoff]);
  551. if (loc_length == rem_length)
  552. {
  553. debug_msg (DOC, 5, "length: %d & %d\n", loc_length, rem_length);
  554. if (strncmp(ctxt->loc_string + ctxt->loc_indices[xoff],
  555. ctxt->rem_string + ctxt->rem_indices[yoff], loc_length) == 0)
  556. result = 1;
  557. }
  558. debug_msg (DOC, 5, "compare: %d & %d = %d\n", xoff, yoff, result);
  559. return result;
  560. }