doc_ref.c 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292
  1. /**
  2. * @file doc_ref.c
  3. */
  4. #include <stdlib.h>
  5. #include "debug.h"
  6. #include "config.h"
  7. #include "gl_list.h"
  8. /* for difseq */
  9. #include <limits.h>
  10. #include <stdbool.h>
  11. #include "minmax.h"
  12. #include "doc_elt.h"
  13. #include "doc_ref.h"
  14. bool
  15. doc_reflist_isupdated (gl_list_t reflist)
  16. {
  17. gl_list_iterator_t i;
  18. i = gl_list_iterator (reflist);
  19. doc_ref *ref = NULL;
  20. bool updated = false;
  21. while (!updated
  22. && gl_list_iterator_next (&i, (const void **) &ref, NULL))
  23. {
  24. /*
  25. if (!doc_ref_contains (ref, ANC_SRC))
  26. {
  27. updated = true;
  28. break;
  29. }
  30. */
  31. updated = doc_elt_isupdated (ref);
  32. }
  33. debug_msg (DOC, 4, "reflist updated = %d\n", updated);
  34. gl_list_iterator_free (&i);
  35. return updated;
  36. }
  37. void
  38. doc_reflist_print (gl_list_t reflist, void *context, doc_stream *out)
  39. {
  40. /**
  41. * @todo make the print ctxt pass around correctly
  42. */
  43. debug_msg (DOC, 5, "Printing element list\n");
  44. gl_list_iterator_t i;
  45. i = gl_list_iterator (reflist);
  46. doc_ref *ref;
  47. doc_elt *elt;
  48. while (gl_list_iterator_next (&i, (const void **) &ref, NULL))
  49. {
  50. debug_msg (DOC, 4, "Printing element\n");
  51. elt = doc_ref_get_elt (ref);
  52. doc_elt_print (ref, context, out);
  53. }
  54. debug_msg (DOC, 5, "Finished printing element\n");
  55. gl_list_iterator_free (&i);
  56. return;
  57. }
  58. struct context;
  59. typedef enum mapped_state
  60. {
  61. state_mapped = 0,
  62. state_unmapped = 1
  63. } mapped_state;
  64. #define OFFSET int
  65. #undef USE_HEURISTIC
  66. #undef ELEMENT
  67. #undef EQUAL
  68. static void note_delete (struct context *ctxt, OFFSET xoff);
  69. static void note_insert (struct context *ctxt, OFFSET yoff);
  70. static int is_related (struct context *ctxt, OFFSET xoff, OFFSET yoff);
  71. #define EXTRA_CONTEXT_FIELDS \
  72. mapped_state *a_state; \
  73. mapped_state *d_state; \
  74. gl_list_t ancestor; \
  75. gl_list_t descendant; \
  76. merge_ctxt *merge_ctxt;
  77. #define NOTE_DELETE(ctxt, xoff) note_delete (ctxt, xoff)
  78. #define NOTE_INSERT(ctxt, yoff) note_insert (ctxt, yoff)
  79. #define XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff) is_related (ctxt, xoff, yoff)
  80. #include "diffseq.h"
  81. #define OFFSET int
  82. static void
  83. note_delete (struct context *ctxt, OFFSET xoff)
  84. {
  85. debug_msg (MERGE, 3, "deleting %d\n", xoff);
  86. ctxt->a_state[xoff] = state_unmapped;
  87. return;
  88. }
  89. static void
  90. note_insert (struct context *ctxt, OFFSET yoff)
  91. {
  92. debug_msg (MERGE, 3, "inserting %d\n", yoff);
  93. ctxt->d_state[yoff] = state_unmapped;
  94. return;
  95. }
  96. static int
  97. is_related (struct context *ctxt, OFFSET xoff, OFFSET yoff)
  98. {
  99. doc_ref *a_ref = (doc_ref * )gl_list_get_at (ctxt->ancestor, xoff);
  100. doc_ref *d_ref = (doc_ref *)gl_list_get_at (ctxt->descendant, yoff);
  101. int result = doc_elt_isrelated (a_ref, d_ref, ctxt->merge_ctxt);
  102. debug_msg (MERGE, 4, "comparing (%d, %d)=%d\n", xoff, yoff, result);
  103. return result;
  104. }
  105. void
  106. doc_reflist_merge (doc_ref *parent, gl_list_t ancestor, gl_list_t descendant, merge_ctxt *merge_ctxt)
  107. {
  108. /* First, create a mapped_state for every element that will be mapped.
  109. * Compare the two strigs marking mapped and unmapped nodes. Then,
  110. * merge the two lists, combining mapped elements ino a sigle element.
  111. */
  112. size_t a_size = gl_list_size (ancestor);
  113. size_t d_size = gl_list_size (descendant);
  114. /* Create a mapped state for every element. Must initialize to 0. */
  115. mapped_state *a_state = calloc (a_size, sizeof (mapped_state));
  116. mapped_state *d_state = calloc (d_size, sizeof (mapped_state));
  117. debug_msg (MERGE, 3, "Start merge, sizes %d and %d\n", a_size, d_size);
  118. /* Send the elements through compareseq. compareseq will leave
  119. * add/remove notes in the mapped_states.
  120. */
  121. /* prepare the compareseq context */
  122. struct context ctxt;
  123. /* Add the caller data */
  124. ctxt.d_state = d_state;
  125. ctxt.a_state = a_state;
  126. ctxt.ancestor = ancestor;
  127. ctxt.descendant = descendant;
  128. ctxt.merge_ctxt = merge_ctxt;
  129. /* Allocate data for the algorithm to use*/
  130. size_t diags = a_size + d_size + 3;
  131. void *mem = malloc (diags * (2 * sizeof (OFFSET)));
  132. ctxt.fdiag = mem;
  133. ctxt.bdiag = ctxt.fdiag + diags;
  134. ctxt.fdiag += d_size + 1;
  135. ctxt.bdiag = ctxt.fdiag + diags;
  136. /* run a diffseq on the elements */
  137. compareseq (0, /* children index lower bound */
  138. a_size, /* children index upper bound */
  139. 0, /* children index lower bound */
  140. d_size, /* children index upper bound */
  141. 1, /* find optimal solution */
  142. &ctxt); /* difseq context created above */
  143. debug_msg (MERGE, 3, "Finish compareseq\n");
  144. free (mem);
  145. /*
  146. * Create the mappings and update the merge_tree.
  147. *
  148. * go through the list in the end and
  149. * - when there is a 'matched' nodes
  150. * - delete the matched elements delta, mark a 'change' in the mapping,
  151. * - point the mapping to the element
  152. * - when there is an insert:
  153. * - add the dnode at that point
  154. * - when there is a delete:
  155. * - mark it in the mapping
  156. */
  157. int a_index = 0; /* # of checked elt's in *tree list */
  158. int d_index = 0;
  159. int inserted = 0; /* number of nodes inserted into the ancestor
  160. tree. Used to make sure the index stays
  161. correct */
  162. int next = 0; /* between two inserted nodes, which one is next */
  163. while ((a_index != a_size)
  164. || (d_index != d_size))
  165. {
  166. #if 0
  167. /* If they are unmapped, pick the order to put them in the list */
  168. if ((d_index != d_size) &&
  169. (d_state[d_index] == state_unmapped) &&
  170. (a_index != a_size) &&
  171. (a_state[a_index-inserted] == state_unmapped))
  172. {
  173. /**
  174. * @todo replace this with a function that lets the parent decide the order
  175. */
  176. if (0)
  177. {
  178. next = 1;
  179. }
  180. else
  181. {
  182. next = 2;
  183. }
  184. }
  185. else
  186. #endif
  187. if ((d_index != d_size)
  188. && (d_state[d_index] == state_unmapped))
  189. {
  190. next = 1;
  191. }
  192. else if ((a_index != a_size)
  193. && (a_state[a_index-inserted] == state_unmapped))
  194. {
  195. next = 2;
  196. }
  197. else
  198. {
  199. /* both are mapped */
  200. next = 0;
  201. }
  202. if (next == 1)
  203. {
  204. /* Insert an unmatched node */
  205. debug_msg (MERGE, 3, "Inserting node d_index=%d\n", d_index);
  206. doc_ref * d_ref = (doc_ref *) gl_list_get_at (descendant, d_index);
  207. gl_list_nx_add_at (ancestor, a_index, (void *) d_ref);
  208. /* check for a circular conflict */
  209. //doc_ref_set_parent (d_ref, parent);
  210. /* this next line should not be necessary */
  211. //doc_ref_check_for_circular_conflict (d_ref);
  212. //mark_insert_children ();
  213. doc_elt_note_insert (d_ref, merge_ctxt);
  214. a_index++;
  215. a_size++;
  216. inserted++;
  217. d_index++;
  218. }
  219. else if (next == 2)
  220. {
  221. /* Delete an unmatched node */
  222. debug_msg (MERGE, 3, "Removing node a_index=%d\n", a_index);
  223. doc_ref * a_ref = (doc_ref *) gl_list_get_at (ancestor, a_index);
  224. // mark_remove_children (m_child, src);
  225. doc_elt_note_delete (a_ref, merge_ctxt);
  226. a_index++;
  227. }
  228. else if ((a_index != a_size) && (d_index != d_size))
  229. {
  230. /* Match and merge matched nodes */
  231. debug_msg (MERGE, 3, "Matching node\n");
  232. doc_ref * a_ref = (doc_ref *) gl_list_get_at (ancestor, a_index);
  233. doc_ref * d_ref = (doc_ref *) gl_list_get_at (descendant, d_index);
  234. assert ((a_state[a_index-inserted] == state_mapped) &&
  235. (d_state[d_index] == state_mapped));
  236. /* set the document source of the doc_ref to the combined sources */
  237. doc_ref_add_src (a_ref, doc_ref_get_src (d_ref));
  238. /* get the element to merge the content and children */
  239. doc_elt_merge (a_ref, d_ref, merge_ctxt);
  240. /* make the doc_refs point to the same element */
  241. //doc_ref_set_elt (d_ref, doc_ref_get_elt (a_ref) );
  242. //doc_ref_set_parent (d_ref, doc_ref_get_parent (a_ref));
  243. //printf ("merging docrefs, par=%d, ref=%d\n", doc_ref_get_elt (a_ref), doc_ref_get_elt (d_ref));
  244. a_index++;
  245. d_index++;
  246. }
  247. }
  248. free (a_state);
  249. free (d_state);
  250. return;
  251. }