[PATCH 3/5] riched20: Move the marked paragraph list to a rbtree.

[Huw Davies]

Signed-off-by: Huw Davies <huw(a)codeweavers.com>
---
 dlls/riched20/editor.c  |  1 -
 dlls/riched20/editstr.h |  5 +--
 dlls/riched20/para.c    | 73 ++++++-----------------------------------
 dlls/riched20/wrap.c    | 39 +++++++++-------------
 4 files changed, 28 insertions(+), 90 deletions(-)

diff --git a/dlls/riched20/editor.c b/dlls/riched20/editor.c
index 2fb7e3650d4..e7e33c27585 100644
--- a/dlls/riched20/editor.c
+++ b/dlls/riched20/editor.c
@@ -3062,7 +3062,6 @@ ME_TextEditor *ME_MakeEditor(ITextHost *texthost, BOOL bEmulateVersion10)
   ed->bEmulateVersion10 = bEmulateVersion10;
   ed->styleFlags = 0;
   ed->exStyleFlags = 0;
-  ed->first_marked_para = NULL;
   ed->total_rows = 0;
   ITextHost_TxGetPropertyBits(texthost,
                               (TXTBIT_RICHTEXT|TXTBIT_MULTILINE|
diff --git a/dlls/riched20/editstr.h b/dlls/riched20/editstr.h
index 2c5737f3e93..fd5c9bc3df8 100644
--- a/dlls/riched20/editstr.h
+++ b/dlls/riched20/editstr.h
@@ -47,6 +47,7 @@
 #include "wine/debug.h"
 #include "wine/heap.h"
 #include "wine/list.h"
+#include "wine/rbtree.h"
 
 #ifdef __ASM_USE_THISCALL_WRAPPER
 extern const struct ITextHostVtbl itextHostStdcallVtbl DECLSPEC_HIDDEN;
@@ -216,7 +217,7 @@ typedef struct tagME_Paragraph
   struct para_num para_num;
   ME_Run *eop_run; /* ptr to the end-of-para run */
   struct tagME_DisplayItem *prev_para, *next_para;
-  struct tagME_DisplayItem *prev_marked, *next_marked;
+  struct wine_rb_entry marked_entry;
 } ME_Paragraph;
 
 typedef struct tagME_Cell /* v4.1 */
@@ -431,7 +432,6 @@ typedef struct tagME_TextEditor
   int imeStartIndex;
   DWORD selofs; /* The size of the selection bar on the left side of control */
   ME_SelectionType nSelectionType;
-  ME_DisplayItem *first_marked_para;
 
   /* Track previous notified selection */
   CHARRANGE notified_cr;
@@ -445,6 +445,7 @@ typedef struct tagME_TextEditor
   int wheel_remain;
   struct list style_list;
   struct list reobj_list;
+  struct wine_rb_tree marked_paras;
 } ME_TextEditor;
 
 typedef struct tagME_Context
diff --git a/dlls/riched20/para.c b/dlls/riched20/para.c
index 9d8693ed411..58dcfc8e712 100644
--- a/dlls/riched20/para.c
+++ b/dlls/riched20/para.c
@@ -35,7 +35,6 @@ static ME_DisplayItem *make_para(ME_TextEditor *editor)
 
     ME_SetDefaultParaFormat(editor, &item->member.para.fmt);
     item->member.para.nFlags = MEPF_REWRAP;
-    item->member.para.next_marked = item->member.para.prev_marked = NULL;
 
     return item;
 }
@@ -74,74 +73,21 @@ int get_total_width(ME_TextEditor *editor)
     return total_width;
 }
 
-void para_mark_remove( ME_TextEditor *editor, ME_Paragraph *para )
+static int para_mark_compare( const void *key, const struct wine_rb_entry *entry )
 {
-    ME_DisplayItem *di = para_get_di( para );
-    ME_DisplayItem *head = editor->first_marked_para;
+    ME_Paragraph *para = WINE_RB_ENTRY_VALUE( entry, ME_Paragraph, marked_entry );
 
-    if (!di->member.para.next_marked && !di->member.para.prev_marked)
-    {
-        if (di == head)
-            editor->first_marked_para = NULL;
-    }
-    else if (di->member.para.next_marked && di->member.para.prev_marked)
-    {
-        di->member.para.prev_marked->member.para.next_marked = di->member.para.next_marked;
-        di->member.para.next_marked->member.para.prev_marked = di->member.para.prev_marked;
-        di->member.para.prev_marked = di->member.para.next_marked = NULL;
-    }
-    else if (di->member.para.next_marked)
-    {
-        assert(di == editor->first_marked_para);
-        editor->first_marked_para = di->member.para.next_marked;
-        di->member.para.next_marked->member.para.prev_marked = NULL;
-        di->member.para.next_marked = NULL;
-    }
-    else
-    {
-        di->member.para.prev_marked->member.para.next_marked = NULL;
-        di->member.para.prev_marked = NULL;
-    }
+    return *(int *)key - para->nCharOfs;
 }
 
-void para_mark_add( ME_TextEditor *editor, ME_Paragraph *para )
+void para_mark_remove( ME_TextEditor *editor, ME_Paragraph *para )
 {
-    ME_DisplayItem *di = para_get_di( para );
-    ME_DisplayItem *iter = editor->first_marked_para;
+    wine_rb_remove_key( &editor->marked_paras, ¶->nCharOfs );
+}
 
-    if (!iter)
-    {
-        editor->first_marked_para = di;
-        return;
-    }
-    while (iter)
-    {
-        if (iter == di)
-            return;
-        else if (di->member.para.nCharOfs < iter->member.para.nCharOfs)
-        {
-            if (iter == editor->first_marked_para)
-                editor->first_marked_para = di;
-            di->member.para.next_marked = iter;
-            iter->member.para.prev_marked = di;
-            break;
-        }
-        else if (di->member.para.nCharOfs >= iter->member.para.nCharOfs)
-        {
-            if (!iter->member.para.next_marked || di->member.para.nCharOfs < iter->member.para.next_marked->member.para.nCharOfs)
-            {
-                if (iter->member.para.next_marked)
-                {
-                    di->member.para.next_marked = iter->member.para.next_marked;
-                    iter->member.para.next_marked->member.para.prev_marked = di;
-                }
-                di->member.para.prev_marked = iter;
-                iter->member.para.next_marked = di;
-                break;
-            }
-        }
-        iter = iter->member.para.next_marked;
-    }
+void para_mark_add( ME_TextEditor *editor, ME_Paragraph *para )
+{
+    wine_rb_put( &editor->marked_paras, ¶->nCharOfs, ¶->marked_entry );
 }
 
 ME_Run *para_first_run( ME_Paragraph *para )
@@ -229,6 +175,7 @@ void ME_MakeFirstParagraph(ME_TextEditor *editor)
 
   text->pLast->member.para.nCharOfs = editor->bEmulateVersion10 ? 2 : 1;
 
+  wine_rb_init( &editor->marked_paras, para_mark_compare );
   para_mark_add( editor, ¶->member.para );
   ME_DestroyContext(&c);
 }
diff --git a/dlls/riched20/wrap.c b/dlls/riched20/wrap.c
index cb17f2963b0..819915d4c09 100644
--- a/dlls/riched20/wrap.c
+++ b/dlls/riched20/wrap.c
@@ -1029,19 +1029,22 @@ static void adjust_para_y(ME_Paragraph *para, ME_Context *c, ME_DisplayItem *rep
 BOOL ME_WrapMarkedParagraphs(ME_TextEditor *editor)
 {
   ME_Paragraph *para, *next;
+  struct wine_rb_entry *entry, *next_entry;
   ME_Context c;
-  int totalWidth = editor->nTotalWidth, diff = 0, prev_width;
+  int totalWidth = editor->nTotalWidth, prev_width;
   ME_DisplayItem *repaint_start = NULL, *repaint_end = NULL;
 
-  if (!editor->first_marked_para)
-    return FALSE;
+  if (!editor->marked_paras.root) return FALSE;
 
   ME_InitContext(&c, editor, ITextHost_TxGetDC(editor->texthost));
 
-  para = &editor->first_marked_para->member.para;
-  c.pt = para->pt;
-  while (para_get_di( para ) != editor->pBuffer->pLast)
+  entry = wine_rb_head( editor->marked_paras.root );
+  while (entry)
   {
+    para = WINE_RB_ENTRY_VALUE( entry, ME_Paragraph, marked_entry );
+    next_entry = wine_rb_next( entry );
+
+    c.pt = para->pt;
     prev_width = para->nWidth;
     ME_WrapTextParagraph( editor, &c, para );
     if (prev_width == totalWidth && para->nWidth < totalWidth)
@@ -1056,11 +1059,10 @@ BOOL ME_WrapMarkedParagraphs(ME_TextEditor *editor)
 
     if (para->next_para)
     {
-      diff = c.pt.y - para->next_para->member.para.pt.y;
-      if (diff)
+      if (c.pt.y != para->next_para->member.para.pt.y)
       {
         next = para;
-        while (next->next_para && next != ¶->next_marked->member.para &&
+        while (next->next_para && &next->marked_entry != next_entry &&
                next != &editor->pBuffer->pLast->member.para)
         {
           ME_MarkRepaintEnd(next->next_para, &repaint_start, &repaint_end);
@@ -1070,26 +1072,15 @@ BOOL ME_WrapMarkedParagraphs(ME_TextEditor *editor)
         }
       }
     }
-    if (para->next_marked)
-    {
-      ME_Paragraph *tmp = para;
-      para = ¶->next_marked->member.para;
-      para_mark_remove( editor, tmp );
-    }
-    else
-    {
-      para_mark_remove( editor, para );
-      para = &editor->pBuffer->pLast->member.para;
-    }
-    c.pt.y = para->pt.y;
+    entry = next_entry;
   }
+  wine_rb_clear( &editor->marked_paras, NULL, NULL );
+
   editor->sizeWindow.cx = c.rcView.right-c.rcView.left;
   editor->sizeWindow.cy = c.rcView.bottom-c.rcView.top;
 
-  editor->nTotalLength = c.pt.y;
+  editor->nTotalLength = editor->pBuffer->pLast->member.para.pt.y;
   editor->nTotalWidth = totalWidth;
-  editor->pBuffer->pLast->member.para.pt.x = 0;
-  editor->pBuffer->pLast->member.para.pt.y = c.pt.y;
 
   ME_DestroyContext(&c);
 
-- 
2.23.0