refactor(extmarks): use a more efficient representation

marktree.c was originally constructed as a "generic" datatype,
to make the prototyping of its internal logic as simple as possible
and also as the usecases for various kinds of extmarks/decorations was not yet decided.
As a consequence of this, various extra indirections and allocations was
needed to use marktree to implement extmarks (ns/id pairs) and
decorations of different kinds (some which is just a single highlight
id, other an allocated list of virtual text/lines)

This change removes a lot of indirection, by making Marktree specialized
for the usecase. In particular, the namespace id and mark id is stored
directly, instead of the 64-bit global id particular to the Marktree
struct. This removes the two maps needed to convert between global and
per-ns ids.

Also, "small" decorations are stored inline, i.e. those who
doesn't refer to external heap memory anyway. That is highlights (with
priority+flags) are stored inline, while virtual text, which anyway
occurs a lot of heap allocations, do not. (previously a hack was used
to elide heap allocations for highlights with standard prio+flags)

TODO(bfredl): the functionaltest-lua CI version of gcc is having
severe issues with uint16_t bitfields, so splitting up compound
assignments and redundant casts are needed. Clean this up once we switch
to a working compiler version.

15 files changed, 462 insertions, 460 deletions

diff --git a/src/nvim/api/deprecated.c b/src/nvim/api/deprecated.c
index 76b699800e..18243fec2b 100644
--- a/src/nvim/api/deprecated.c
+++ b/src/nvim/api/deprecated.c
@@ -130,7 +130,7 @@ Integer nvim_buf_set_virtual_text(Buffer buffer, Integer src_id, Integer line, A
     return 0;
   }
 
-  uint64_t ns_id = src2ns(&src_id);
+  uint32_t ns_id = src2ns(&src_id);
   int width;
 
   VirtText virt_text = parse_virt_text(chunks, err, &width);
@@ -148,11 +148,12 @@ Integer nvim_buf_set_virtual_text(Buffer buffer, Integer src_id, Integer line, A
     return src_id;
   }
 
-  Decoration *decor = xcalloc(1, sizeof(*decor));
-  decor->virt_text = virt_text;
-  decor->virt_text_width = width;
+  Decoration decor = DECORATION_INIT;
+  decor.virt_text = virt_text;
+  decor.virt_text_width = width;
+  decor.priority = 0;
 
-  extmark_set(buf, ns_id, NULL, (int)line, 0, -1, -1, decor, true,
+  extmark_set(buf, ns_id, NULL, (int)line, 0, -1, -1, &decor, true,
               false, kExtmarkNoUndo);
   return src_id;
 }
diff --git a/src/nvim/api/extmark.c b/src/nvim/api/extmark.c
index 742b953c2a..a37bbae668 100644
--- a/src/nvim/api/extmark.c
+++ b/src/nvim/api/extmark.c
@@ -85,12 +85,12 @@ const char *describe_ns(NS ns_id)
 }
 
 // Is the Namespace in use?
-static bool ns_initialized(uint64_t ns)
+static bool ns_initialized(uint32_t ns)
 {
   if (ns < 1) {
     return false;
   }
-  return ns < (uint64_t)next_namespace_id;
+  return ns < (uint32_t)next_namespace_id;
 }
 
 
@@ -111,27 +111,27 @@ static Array extmark_to_array(ExtmarkInfo extmark, bool id, bool add_dict)
       PUT(dict, "end_col", INTEGER_OBJ(extmark.end_col));
     }
 
-    if (extmark.decor) {
-      Decoration *decor = extmark.decor;
-      if (decor->hl_id) {
-        String name = cstr_to_string((const char *)syn_id2name(decor->hl_id));
-        PUT(dict, "hl_group", STRING_OBJ(name));
-      }
-      if (kv_size(decor->virt_text)) {
-        Array chunks = ARRAY_DICT_INIT;
-        for (size_t i = 0; i < decor->virt_text.size; i++) {
-          Array chunk = ARRAY_DICT_INIT;
-          VirtTextChunk *vtc = &decor->virt_text.items[i];
-          ADD(chunk, STRING_OBJ(cstr_to_string(vtc->text)));
-          if (vtc->hl_id > 0) {
-            ADD(chunk,
-                STRING_OBJ(cstr_to_string((const char *)syn_id2name(vtc->hl_id))));
-          }
-          ADD(chunks, ARRAY_OBJ(chunk));
+    Decoration *decor = &extmark.decor;
+    if (decor->hl_id) {
+      String name = cstr_to_string((const char *)syn_id2name(decor->hl_id));
+      PUT(dict, "hl_group", STRING_OBJ(name));
+    }
+    if (kv_size(decor->virt_text)) {
+      Array chunks = ARRAY_DICT_INIT;
+      for (size_t i = 0; i < decor->virt_text.size; i++) {
+        Array chunk = ARRAY_DICT_INIT;
+        VirtTextChunk *vtc = &decor->virt_text.items[i];
+        ADD(chunk, STRING_OBJ(cstr_to_string(vtc->text)));
+        if (vtc->hl_id > 0) {
+          ADD(chunk,
+              STRING_OBJ(cstr_to_string((const char *)syn_id2name(vtc->hl_id))));
         }
-        PUT(dict, "virt_text", ARRAY_OBJ(chunks));
+        ADD(chunks, ARRAY_OBJ(chunk));
       }
+      PUT(dict, "virt_text", ARRAY_OBJ(chunks));
+    }
 
+    if (decor->hl_id || kv_size(decor->virt_text)) {
       PUT(dict, "priority", INTEGER_OBJ(decor->priority));
     }
 
@@ -166,7 +166,7 @@ ArrayOf(Integer) nvim_buf_get_extmark_by_id(Buffer buffer, Integer ns_id,
     return rv;
   }
 
-  if (!ns_initialized((uint64_t)ns_id)) {
+  if (!ns_initialized((uint32_t)ns_id)) {
     api_set_error(err, kErrorTypeValidation, "Invalid ns_id");
     return rv;
   }
@@ -191,7 +191,7 @@ ArrayOf(Integer) nvim_buf_get_extmark_by_id(Buffer buffer, Integer ns_id,
   }
 
 
-  ExtmarkInfo extmark = extmark_from_id(buf, (uint64_t)ns_id, (uint64_t)id);
+  ExtmarkInfo extmark = extmark_from_id(buf, (uint32_t)ns_id, (uint32_t)id);
   if (extmark.row < 0) {
     return rv;
   }
@@ -252,7 +252,7 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object e
     return rv;
   }
 
-  if (!ns_initialized((uint64_t)ns_id)) {
+  if (!ns_initialized((uint32_t)ns_id)) {
     api_set_error(err, kErrorTypeValidation, "Invalid ns_id");
     return rv;
   }
@@ -310,7 +310,7 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object e
   }
 
 
-  ExtmarkInfoArray marks = extmark_get(buf, (uint64_t)ns_id, l_row, l_col,
+  ExtmarkInfoArray marks = extmark_get(buf, (uint32_t)ns_id, l_row, l_col,
                                        u_row, u_col, (int64_t)limit, reverse);
 
   for (size_t i = 0; i < kv_size(marks); i++) {
@@ -417,14 +417,14 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
     goto error;
   }
 
-  if (!ns_initialized((uint64_t)ns_id)) {
+  if (!ns_initialized((uint32_t)ns_id)) {
     api_set_error(err, kErrorTypeValidation, "Invalid ns_id");
     goto error;
   }
 
-  uint64_t id = 0;
+  uint32_t id = 0;
   if (opts->id.type == kObjectTypeInteger && opts->id.data.integer > 0) {
-    id = (uint64_t)opts->id.data.integer;
+    id = (uint32_t)opts->id.data.integer;
   } else if (HAS_KEY(opts->id)) {
     api_set_error(err, kErrorTypeValidation, "id is not a positive integer");
     goto error;
@@ -628,20 +628,6 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
     col2 = 0;
   }
 
-  Decoration *d = NULL;
-
-  if (ephemeral) {
-    d = &decor;
-  } else if (kv_size(decor.virt_text) || kv_size(decor.virt_lines)
-             || decor.priority != DECOR_PRIORITY_BASE
-             || decor.hl_eol) {
-    // TODO(bfredl): this is a bit sketchy. eventually we should
-    // have predefined decorations for both marks/ephemerals
-    d = xcalloc(1, sizeof(*d));
-    *d = decor;
-  } else if (decor.hl_id) {
-    d = decor_hl(decor.hl_id);
-  }
 
   // TODO(bfredl): synergize these two branches even more
   if (ephemeral && decor_state.buf == buf) {
@@ -652,12 +638,8 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
       goto error;
     }
 
-    extmark_set(buf, (uint64_t)ns_id, &id, (int)line, (colnr_T)col, line2, col2,
-                d, right_gravity, end_right_gravity, kExtmarkNoUndo);
-
-    if (kv_size(decor.virt_lines)) {
-      redraw_buf_line_later(buf, MIN(buf->b_ml.ml_line_count, line+1+(decor.virt_lines_above?0:1)));
-    }
+    extmark_set(buf, (uint32_t)ns_id, &id, (int)line, (colnr_T)col, line2, col2,
+                &decor, right_gravity, end_right_gravity, kExtmarkNoUndo);
   }
 
   return (Integer)id;
@@ -682,23 +664,23 @@ Boolean nvim_buf_del_extmark(Buffer buffer, Integer ns_id, Integer id, Error *er
   if (!buf) {
     return false;
   }
-  if (!ns_initialized((uint64_t)ns_id)) {
+  if (!ns_initialized((uint32_t)ns_id)) {
     api_set_error(err, kErrorTypeValidation, "Invalid ns_id");
     return false;
   }
 
-  return extmark_del(buf, (uint64_t)ns_id, (uint64_t)id);
+  return extmark_del(buf, (uint32_t)ns_id, (uint32_t)id);
 }
 
-uint64_t src2ns(Integer *src_id)
+uint32_t src2ns(Integer *src_id)
 {
   if (*src_id == 0) {
     *src_id = nvim_create_namespace((String)STRING_INIT);
   }
   if (*src_id < 0) {
-    return UINT64_MAX;
+    return (((uint32_t)1) << 31) - 1;
   } else {
-    return (uint64_t)(*src_id);
+    return (uint32_t)(*src_id);
   }
 }
 
@@ -753,7 +735,7 @@ Integer nvim_buf_add_highlight(Buffer buffer, Integer ns_id, String hl_group, In
     col_end = MAXCOL;
   }
 
-  uint64_t ns = src2ns(&ns_id);
+  uint32_t ns = src2ns(&ns_id);
 
   if (!(line < buf->b_ml.ml_line_count)) {
     // safety check, we can't add marks outside the range
@@ -773,10 +755,13 @@ Integer nvim_buf_add_highlight(Buffer buffer, Integer ns_id, String hl_group, In
     end_line++;
   }
 
+  Decoration decor = DECORATION_INIT;
+  decor.hl_id = hl_id;
+
   extmark_set(buf, ns, NULL,
               (int)line, (colnr_T)col_start,
               end_line, (colnr_T)col_end,
-              decor_hl(hl_id), true, false, kExtmarkNoUndo);
+              &decor, true, false, kExtmarkNoUndo);
   return ns_id;
 }
 
@@ -808,7 +793,7 @@ void nvim_buf_clear_namespace(Buffer buffer, Integer ns_id, Integer line_start,
   if (line_end < 0 || line_end > MAXLNUM) {
     line_end = MAXLNUM;
   }
-  extmark_clear(buf, (ns_id < 0 ? 0 : (uint64_t)ns_id),
+  extmark_clear(buf, (ns_id < 0 ? 0 : (uint32_t)ns_id),
                 (int)line_start, 0,
                 (int)line_end-1, MAXCOL);
 }
diff --git a/src/nvim/api/private/helpers.c b/src/nvim/api/private/helpers.c
index f9603acbda..f777fa1d27 100644
--- a/src/nvim/api/private/helpers.c
+++ b/src/nvim/api/private/helpers.c
@@ -1141,7 +1141,7 @@ bool extmark_get_index_from_obj(buf_T *buf, Integer ns_id, Object obj, int
       return false;
     }
 
-    ExtmarkInfo extmark = extmark_from_id(buf, (uint64_t)ns_id, (uint64_t)id);
+    ExtmarkInfo extmark = extmark_from_id(buf, (uint32_t)ns_id, (uint32_t)id);
     if (extmark.row >= 0) {
       *row = extmark.row;
       *col = extmark.col;
diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index 63a550c017..bba53b415a 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -866,8 +866,7 @@ struct file_buffer {
   int b_mapped_ctrl_c;          // modes where CTRL-C is mapped
 
   MarkTree b_marktree[1];
-  Map(uint64_t, ExtmarkItem) b_extmark_index[1];
-  Map(uint64_t, ExtmarkNs) b_extmark_ns[1];         // extmark namespaces
+  Map(uint32_t, uint32_t) b_extmark_ns[1];         // extmark namespaces
   size_t b_virt_line_blocks;    // number of virt_line blocks
 
   // array of channel_id:s which have asked to receive updates for this
diff --git a/src/nvim/decoration.c b/src/nvim/decoration.c
index c0f3c32f93..935b233752 100644
--- a/src/nvim/decoration.c
+++ b/src/nvim/decoration.c
@@ -13,8 +13,6 @@
 # include "decoration.c.generated.h"
 #endif
 
-static PMap(uint64_t) hl_decors;
-
 /// Add highlighting to a buffer, bounded by two cursor positions,
 /// with an offset.
 ///
@@ -33,9 +31,9 @@ void bufhl_add_hl_pos_offset(buf_T *buf, int src_id, int hl_id, lpos_T pos_start
 {
   colnr_T hl_start = 0;
   colnr_T hl_end = 0;
-  Decoration *decor = decor_hl(hl_id);
+  Decoration decor = DECORATION_INIT;
+  decor.hl_id = hl_id;
 
-  decor->priority = DECOR_PRIORITY_BASE;
   // TODO(bfredl): if decoration had blocky mode, we could avoid this loop
   for (linenr_T lnum = pos_start.lnum; lnum <= pos_end.lnum; lnum++) {
     int end_off = 0;
@@ -59,40 +57,23 @@ void bufhl_add_hl_pos_offset(buf_T *buf, int src_id, int hl_id, lpos_T pos_start
       hl_start = pos_start.col + offset;
       hl_end = pos_end.col + offset;
     }
-    (void)extmark_set(buf, (uint64_t)src_id, NULL,
-                      (int)lnum-1, hl_start, (int)lnum-1+end_off, hl_end,
-                      decor, true, false, kExtmarkNoUndo);
-  }
-}
-
-Decoration *decor_hl(int hl_id)
-{
-  assert(hl_id > 0);
-  Decoration **dp = (Decoration **)pmap_ref(uint64_t)(&hl_decors,
-                                                      (uint64_t)hl_id, true);
-  if (*dp) {
-    return *dp;
+    extmark_set(buf, (uint32_t)src_id, NULL,
+                (int)lnum-1, hl_start, (int)lnum-1+end_off, hl_end,
+                &decor, true, false, kExtmarkNoUndo);
   }
-
-  Decoration *decor = xcalloc(1, sizeof(*decor));
-  decor->hl_id = hl_id;
-  decor->shared = true;
-  decor->priority = DECOR_PRIORITY_BASE;
-  *dp = decor;
-  return decor;
 }
 
 void decor_redraw(buf_T *buf, int row1, int row2, Decoration *decor)
 {
-  if (decor->hl_id && row2 >= row1) {
+  if ((!decor || decor->hl_id) && row2 >= row1) {
     redraw_buf_range_later(buf, row1+1, row2+1);
   }
 
-  if (kv_size(decor->virt_text)) {
+  if (decor && kv_size(decor->virt_text)) {
     redraw_buf_line_later(buf, row1+1);
   }
 
-  if (kv_size(decor->virt_lines)) {
+  if (decor && kv_size(decor->virt_lines)) {
     redraw_buf_line_later(buf, MIN(buf->b_ml.ml_line_count,
                                    row1+1+(decor->virt_lines_above?0:1)));
   }
@@ -100,17 +81,17 @@ void decor_redraw(buf_T *buf, int row1, int row2, Decoration *decor)
 
 void decor_remove(buf_T *buf, int row, int row2, Decoration *decor)
 {
-  if (kv_size(decor->virt_lines)) {
+  decor_redraw(buf, row, row2, decor);
+  if (decor && kv_size(decor->virt_lines)) {
     assert(buf->b_virt_line_blocks > 0);
     buf->b_virt_line_blocks--;
   }
-  decor_redraw(buf, row, row2, decor);
   decor_free(decor);
 }
 
 void decor_free(Decoration *decor)
 {
-  if (decor && !decor->shared) {
+  if (decor) {
     clear_virttext(&decor->virt_text);
     for (size_t i = 0; i < kv_size(decor->virt_lines); i++) {
       clear_virttext(&kv_A(decor->virt_lines, i).line);
@@ -134,17 +115,16 @@ Decoration *decor_find_virttext(buf_T *buf, int row, uint64_t ns_id)
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, row, 0,  itr);
   while (true) {
-    mtmark_t mark = marktree_itr_current(itr);
-    if (mark.row < 0 || mark.row > row) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0 || mark.pos.row > row) {
       break;
-    } else if (marktree_decor_level(mark.id) < kDecorLevelVisible) {
+    } else if (marktree_decor_level(mark) < kDecorLevelVisible) {
       goto next_mark;
     }
-    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                       mark.id, false);
-    if (item && (ns_id == 0 || ns_id == item->ns_id)
-        && item->decor && kv_size(item->decor->virt_text)) {
-      return item->decor;
+    Decoration *decor = mark.decor_full;
+    if ((ns_id == 0 || ns_id == mark.ns)
+        && decor && kv_size(decor->virt_text)) {
+      return decor;
     }
 next_mark:
     marktree_itr_next(buf->b_marktree, itr);
@@ -163,7 +143,20 @@ bool decor_redraw_reset(buf_T *buf, DecorState *state)
     }
   }
   kv_size(state->active) = 0;
-  return map_size(buf->b_extmark_index);
+  return buf->b_marktree->n_keys;
+}
+
+Decoration get_decor(mtkey_t mark)
+{
+  if (mark.decor_full) {
+    return *mark.decor_full;
+  } else {
+    Decoration fake = DECORATION_INIT;
+    fake.hl_id = mark.hl_id;
+    fake.priority = mark.priority;
+    fake.hl_eol = (mark.flags & MT_FLAG_HL_EOL);
+    return fake;
+  }
 }
 
 
@@ -176,42 +169,35 @@ bool decor_redraw_start(buf_T *buf, int top_row, DecorState *state)
   }
   marktree_itr_rewind(buf->b_marktree, state->itr);
   while (true) {
-    mtmark_t mark = marktree_itr_current(state->itr);
-    if (mark.row < 0) {  // || mark.row > end_row
+    mtkey_t mark = marktree_itr_current(state->itr);
+    if (mark.pos.row < 0) {  // || mark.row > end_row
       break;
     }
-    if ((mark.row < top_row && mark.id&MARKTREE_END_FLAG)
-        || marktree_decor_level(mark.id) < kDecorLevelVisible) {
+    if ((mark.pos.row < top_row && mt_end(mark))
+        || marktree_decor_level(mark) < kDecorLevelVisible) {
       goto next_mark;
     }
 
-    uint64_t start_id = mark.id & ~MARKTREE_END_FLAG;
-    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                       start_id, false);
-    if (!item || !item->decor) {
-      goto next_mark;
-    }
-    Decoration *decor = item->decor;
+    Decoration decor = get_decor(mark);
 
-    mtpos_t altpos = marktree_lookup(buf->b_marktree,
-                                     mark.id^MARKTREE_END_FLAG, NULL);
+    mtpos_t altpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
 
-    if ((!(mark.id&MARKTREE_END_FLAG) && altpos.row < top_row
-         && !kv_size(decor->virt_text))
-        || ((mark.id&MARKTREE_END_FLAG) && altpos.row >= top_row)) {
+    if ((!mt_end(mark) && altpos.row < top_row
+         && !kv_size(decor.virt_text))
+        || (mt_end(mark) && altpos.row >= top_row)) {
       goto next_mark;
     }
 
-    if (mark.id&MARKTREE_END_FLAG) {
-      decor_add(state, altpos.row, altpos.col, mark.row, mark.col,
-                decor, false);
+    if (mt_end(mark)) {
+      decor_add(state, altpos.row, altpos.col, mark.pos.row, mark.pos.col,
+                &decor, false);
     } else {
       if (altpos.row == -1) {
-        altpos.row = mark.row;
-        altpos.col = mark.col;
+        altpos.row = mark.pos.row;
+        altpos.col = mark.pos.col;
       }
-      decor_add(state, mark.row, mark.col, altpos.row, altpos.col,
-                decor, false);
+      decor_add(state, mark.pos.row, mark.pos.col, altpos.row, altpos.col,
+                &decor, false);
     }
 
 next_mark:
@@ -266,43 +252,36 @@ int decor_redraw_col(buf_T *buf, int col, int win_col, bool hidden, DecorState *
   while (true) {
     // TODO(bfredl): check duplicate entry in "intersection"
     // branch
-    mtmark_t mark = marktree_itr_current(state->itr);
-    if (mark.row < 0 || mark.row > state->row) {
+    mtkey_t mark = marktree_itr_current(state->itr);
+    if (mark.pos.row < 0 || mark.pos.row > state->row) {
       break;
-    } else if (mark.row == state->row && mark.col > col) {
-      state->col_until = mark.col-1;
+    } else if (mark.pos.row == state->row && mark.pos.col > col) {
+      state->col_until = mark.pos.col-1;
       break;
     }
 
-    if ((mark.id&MARKTREE_END_FLAG)
-        || marktree_decor_level(mark.id) < kDecorLevelVisible) {
+    if (mt_end(mark)
+        || marktree_decor_level(mark) < kDecorLevelVisible) {
       goto next_mark;
     }
 
-    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                       mark.id, false);
-    if (!item || !item->decor) {
-      goto next_mark;
-    }
-    Decoration *decor = item->decor;
+    Decoration decor = get_decor(mark);
 
-    mtpos_t endpos = marktree_lookup(buf->b_marktree,
-                                     mark.id|MARKTREE_END_FLAG, NULL);
+    mtpos_t endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
 
     if (endpos.row == -1) {
-      endpos.row = mark.row;
-      endpos.col = mark.col;
+      endpos = mark.pos;
     }
 
-    if (endpos.row < mark.row
-        || (endpos.row == mark.row && endpos.col <= mark.col)) {
-      if (!kv_size(decor->virt_text)) {
+    if (endpos.row < mark.pos.row
+        || (endpos.row == mark.pos.row && endpos.col <= mark.pos.col)) {
+      if (!kv_size(decor.virt_text)) {
         goto next_mark;
       }
     }
 
-    decor_add(state, mark.row, mark.col, endpos.row, endpos.col,
-              decor, false);
+    decor_add(state, mark.pos.row, mark.pos.col, endpos.row, endpos.col,
+              &decor, false);
 
 next_mark:
     marktree_itr_next(buf->b_marktree, state->itr);
@@ -452,18 +431,18 @@ int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines)
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, row, 0,  itr);
   while (true) {
-    mtmark_t mark = marktree_itr_current(itr);
-    if (mark.row < 0 || mark.row >= end_row) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0 || mark.pos.row >= end_row) {
       break;
-    } else if (marktree_decor_level(mark.id) < kDecorLevelVirtLine) {
+    } else if (marktree_decor_level(mark) < kDecorLevelVirtLine) {
       goto next_mark;
     }
-    bool above = mark.row > (int)(lnum - 2);
-    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark.id, false);
-    if (item && item->decor && item->decor->virt_lines_above == above) {
-      virt_lines += (int)kv_size(item->decor->virt_lines);
+    bool above = mark.pos.row > (int)(lnum - 2);
+    Decoration *decor = mark.decor_full;
+    if (decor && decor->virt_lines_above == above) {
+      virt_lines += (int)kv_size(decor->virt_lines);
       if (lines) {
-        kv_splice(*lines, item->decor->virt_lines);
+        kv_splice(*lines, decor->virt_lines);
       }
     }
 next_mark:
diff --git a/src/nvim/decoration.h b/src/nvim/decoration.h
index 611b4223da..209e2176f2 100644
--- a/src/nvim/decoration.h
+++ b/src/nvim/decoration.h
@@ -42,7 +42,6 @@ struct Decoration {
   // TODO(bfredl): at some point turn this into FLAGS
   bool virt_text_hide;
   bool hl_eol;
-  bool shared;  // shared decoration, don't free
   bool virt_lines_above;
   // TODO(bfredl): style, signs, etc
   DecorPriority priority;
@@ -50,7 +49,7 @@ struct Decoration {
   int virt_text_width;  // width of virt_text
 };
 #define DECORATION_INIT { KV_INITIAL_VALUE, KV_INITIAL_VALUE, 0, kVTEndOfLine, kHlModeUnknown, \
-                          false, false, false, false, DECOR_PRIORITY_BASE, 0, 0 }
+                          false, false, false, DECOR_PRIORITY_BASE, 0, 0 }
 
 typedef struct {
   int start_row;
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index c4d8f75a21..cee657c8c9 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -48,28 +48,29 @@
 # include "extmark.c.generated.h"
 #endif
 
-static ExtmarkNs *buf_ns_ref(buf_T *buf, uint64_t ns_id, bool put)
+static uint32_t *buf_ns_ref(buf_T *buf, uint32_t ns_id, bool put)
 {
-  return map_ref(uint64_t, ExtmarkNs)(buf->b_extmark_ns, ns_id, put);
+  return map_ref(uint32_t, uint32_t)(buf->b_extmark_ns, ns_id, put);
 }
 
 
 /// Create or update an extmark
 ///
 /// must not be used during iteration!
-/// @returns the internal mark id
-uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t *idp, int row, colnr_T col, int end_row,
-                     colnr_T end_col, Decoration *decor, bool right_gravity, bool end_right_gravity,
-                     ExtmarkOp op)
+void extmark_set(buf_T *buf, uint32_t ns_id, uint32_t *idp, int row, colnr_T col, int end_row,
+                 colnr_T end_col, Decoration *decor, bool right_gravity, bool end_right_gravity,
+                 ExtmarkOp op)
 {
-  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, true);
-  assert(ns != NULL);
-  mtpos_t old_pos;
-  uint64_t mark = 0;
-  uint64_t id = idp ? *idp : 0;
+  uint32_t *ns = buf_ns_ref(buf, ns_id, true);
+  uint32_t id = idp ? *idp : 0;
+  bool decor_full = false;
 
   uint8_t decor_level = kDecorLevelNone;  // no decor
   if (decor) {
+    if (kv_size(decor->virt_text) || kv_size(decor->virt_lines)) {
+      decor_full = true;
+      decor = xmemdup(decor, sizeof *decor);
+    }
     decor_level = kDecorLevelVisible;  // decor affects redraw
     if (kv_size(decor->virt_lines)) {
       decor_level = kDecorLevelVirtLine;  // decor affects horizontal size
@@ -77,50 +78,64 @@ uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t *idp, int row, colnr_T
   }
 
   if (id == 0) {
-    id = ns->free_id++;
+    id = ++*ns;
   } else {
-    uint64_t old_mark = map_get(uint64_t, uint64_t)(ns->map, id);
-    if (old_mark) {
-      if (old_mark & MARKTREE_PAIRED_FLAG || end_row > -1) {
+    MarkTreeIter itr[1] = { 0 };
+    mtkey_t old_mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
+    if (old_mark.id) {
+      if (mt_paired(old_mark) || end_row > -1) {
         extmark_del(buf, ns_id, id);
       } else {
-        MarkTreeIter itr[1] = { 0 };
-        old_pos = marktree_lookup(buf->b_marktree, old_mark, itr);
+        // TODO(bfredl): we need to do more if "revising" a decoration mark.
         assert(itr->node);
-        if (old_pos.row == row && old_pos.col == col) {
-          ExtmarkItem it = map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                          old_mark);
-          if (it.decor) {
-            decor_remove(buf, row, row, it.decor);
+        if (old_mark.pos.row == row && old_mark.pos.col == col) {
+          if (marktree_decor_level(old_mark) > kDecorLevelNone) {
+            decor_remove(buf, row, row, old_mark.decor_full);
+            old_mark.decor_full = NULL;
+          }
+          old_mark.flags = 0;
+          if (decor_full) {
+            old_mark.decor_full = decor;
+          } else if (decor) {
+            old_mark.hl_id = decor->hl_id;
+            // Workaround: the gcc compiler of functionaltest-lua build
+            // apparently incapable of handling basic integer constants.
+            // This can be underanged as soon as we bump minimal gcc version.
+            old_mark.flags = (uint16_t)(old_mark.flags
+                                        | (decor->hl_eol ? (uint16_t)MT_FLAG_HL_EOL : (uint16_t)0));
+            old_mark.priority = decor->priority;
           }
-          mark = marktree_revise(buf->b_marktree, itr, decor_level);
+          marktree_revise(buf->b_marktree, itr, decor_level, old_mark);
           goto revised;
         }
         marktree_del_itr(buf->b_marktree, itr, false);
       }
     } else {
-      ns->free_id = MAX(ns->free_id, id+1);
+      *ns = MAX(*ns, id);
     }
   }
 
-  if (end_row > -1) {
-    mark = marktree_put_pair(buf->b_marktree,
-                             row, col, right_gravity,
-                             end_row, end_col, end_right_gravity, decor_level);
-  } else {
-    mark = marktree_put(buf->b_marktree, row, col, right_gravity, decor_level);
+  mtkey_t mark = { { row, col }, ns_id, id, 0,
+                    mt_flags(right_gravity, decor_level), 0, NULL };
+  if (decor_full) {
+    mark.decor_full = decor;
+  } else if (decor) {
+    mark.hl_id = decor->hl_id;
+    // workaround: see above
+    mark.flags = (uint16_t)(mark.flags | (decor->hl_eol ? (uint16_t)MT_FLAG_HL_EOL : (uint16_t)0));
+    mark.priority = decor->priority;
   }
 
-revised:
-  map_put(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark,
-                                 (ExtmarkItem){ ns_id, id, decor });
-  map_put(uint64_t, uint64_t)(ns->map, id, mark);
+  marktree_put(buf->b_marktree, mark, end_row, end_col, end_right_gravity);
 
+revised:
   if (op != kExtmarkNoUndo) {
     // TODO(bfredl): this doesn't cover all the cases and probably shouldn't
     // be done "prematurely". Any movement in undo history might necessitate
-    // adding new marks to old undo headers.
-    u_extmark_set(buf, mark, row, col);
+    // adding new marks to old undo headers. add a test case for this (doesn't
+    // fail extmark_spec.lua, and it should)
+    uint64_t mark_id = mt_lookup_id(ns_id, id, false);
+    u_extmark_set(buf, mark_id, row, col);
   }
 
   if (decor) {
@@ -133,18 +148,17 @@ revised:
   if (idp) {
     *idp = id;
   }
-  return mark;
 }
 
 static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
 {
   MarkTreeIter itr[1] = { 0 };
-  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, itr);
-  if (pos.row == -1) {
+  mtkey_t key = marktree_lookup(buf->b_marktree, mark, itr);
+  if (key.pos.row == -1) {
     return false;
   }
 
-  if (pos.row == row && pos.col == col) {
+  if (key.pos.row == row && key.pos.col == col) {
     return true;
   }
 
@@ -154,45 +168,35 @@ static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
 
 // Remove an extmark
 // Returns 0 on missing id
-bool extmark_del(buf_T *buf, uint64_t ns_id, uint64_t id)
+bool extmark_del(buf_T *buf, uint32_t ns_id, uint32_t id)
 {
-  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, false);
-  if (!ns) {
-    return false;
-  }
-
-  uint64_t mark = map_get(uint64_t, uint64_t)(ns->map, id);
-  if (!mark) {
+  MarkTreeIter itr[1] = { 0 };
+  mtkey_t key = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
+  if (!key.id) {
     return false;
   }
-
-  MarkTreeIter itr[1] = { 0 };
-  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, itr);
-  assert(pos.row >= 0);
+  assert(key.pos.row >= 0);
   marktree_del_itr(buf->b_marktree, itr, false);
-  ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark);
-  mtpos_t pos2 = pos;
 
-  if (mark & MARKTREE_PAIRED_FLAG) {
-    pos2 = marktree_lookup(buf->b_marktree, mark|MARKTREE_END_FLAG, itr);
-    assert(pos2.row >= 0);
+  mtkey_t key2 = key;
+
+  if (mt_paired(key)) {
+    key2 = marktree_lookup_ns(buf->b_marktree, ns_id, id, true, itr);
+    assert(key2.pos.row >= 0);
     marktree_del_itr(buf->b_marktree, itr, false);
   }
 
-  if (item.decor) {
-    decor_remove(buf, pos.row, pos2.row, item.decor);
+  if (marktree_decor_level(key) > kDecorLevelNone) {
+    decor_remove(buf, key.pos.row, key2.pos.row, key.decor_full);
   }
 
-  map_del(uint64_t, uint64_t)(ns->map, id);
-  map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark);
-
   // TODO(bfredl): delete it from current undo header, opportunistically?
   return true;
 }
 
 // Free extmarks in a ns between lines
 // if ns = 0, it means clear all namespaces
-bool extmark_clear(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_col, int u_row, colnr_T u_col)
+bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_row, colnr_T u_col)
 {
   if (!map_size(buf->b_extmark_ns)) {
     return false;
@@ -201,68 +205,58 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_col, int u_r
   bool marks_cleared = false;
 
   bool all_ns = (ns_id == 0);
-  ExtmarkNs *ns = NULL;
+  uint32_t *ns = NULL;
   if (!all_ns) {
     ns = buf_ns_ref(buf, ns_id, false);
     if (!ns) {
       // nothing to do
       return false;
     }
-
-    // TODO(bfredl): if map_size(ns->map) << buf->b_marktree.n_nodes
-    // it could be faster to iterate over the map instead
   }
 
   // the value is either zero or the lnum (row+1) if highlight was present.
   static Map(uint64_t, ssize_t) delete_set = MAP_INIT;
-  typedef struct { Decoration *decor; int row1; } DecorItem;
+  typedef struct { int row1; } DecorItem;
   static kvec_t(DecorItem) decors;
 
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, l_row, l_col, itr);
   while (true) {
-    mtmark_t mark = marktree_itr_current(itr);
-    if (mark.row < 0
-        || mark.row > u_row
-        || (mark.row == u_row && mark.col > u_col)) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0
+        || mark.pos.row > u_row
+        || (mark.pos.row == u_row && mark.pos.col > u_col)) {
       break;
     }
-    ssize_t *del_status = map_ref(uint64_t, ssize_t)(&delete_set, mark.id,
+    ssize_t *del_status = map_ref(uint64_t, ssize_t)(&delete_set, mt_lookup_key(mark),
                                                      false);
     if (del_status) {
       marktree_del_itr(buf->b_marktree, itr, false);
       if (*del_status >= 0) {  // we had a decor_id
         DecorItem it = kv_A(decors, *del_status);
-        decor_remove(buf, it.row1, mark.row, it.decor);
+        decor_remove(buf, it.row1, mark.pos.row, mark.decor_full);
       }
-      map_del(uint64_t, ssize_t)(&delete_set, mark.id);
+      map_del(uint64_t, ssize_t)(&delete_set, mt_lookup_key(mark));
       continue;
     }
 
-    uint64_t start_id = mark.id & ~MARKTREE_END_FLAG;
-    ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                      start_id);
-
-    assert(item.ns_id > 0 && item.mark_id > 0);
-    if (item.mark_id > 0 && (item.ns_id == ns_id || all_ns)) {
+    assert(mark.ns > 0 && mark.id > 0);
+    if (mark.ns == ns_id || all_ns) {
       marks_cleared = true;
-      if (mark.id & MARKTREE_PAIRED_FLAG) {
-        uint64_t other = mark.id ^ MARKTREE_END_FLAG;
+      if (mt_paired(mark)) {
+        uint64_t other = mt_lookup_id(mark.ns, mark.id, !mt_end(mark));
         ssize_t decor_id = -1;
-        if (item.decor) {
+        if (marktree_decor_level(mark) > kDecorLevelNone) {
           // Save the decoration and the first pos. Clear the decoration
           // later when we know the full range.
           decor_id = (ssize_t)kv_size(decors);
           kv_push(decors,
-                  ((DecorItem) { .decor = item.decor, .row1 = mark.row }));
+                  ((DecorItem) { .row1 = mark.pos.row }));
         }
         map_put(uint64_t, ssize_t)(&delete_set, other, decor_id);
-      } else if (item.decor) {
-        decor_remove(buf, mark.row, mark.row, item.decor);
+      } else if (mark.decor_full) {
+        decor_remove(buf, mark.pos.row, mark.pos.row, mark.decor_full);
       }
-      ExtmarkNs *my_ns = all_ns ? buf_ns_ref(buf, item.ns_id, false) : ns;
-      map_del(uint64_t, uint64_t)(my_ns->map, item.mark_id);
-      map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index, start_id);
       marktree_del_itr(buf->b_marktree, itr, false);
     } else {
       marktree_itr_next(buf->b_marktree, itr);
@@ -271,12 +265,12 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_col, int u_r
   uint64_t id;
   ssize_t decor_id;
   map_foreach(&delete_set, id, decor_id, {
-    mtpos_t pos = marktree_lookup(buf->b_marktree, id, itr);
+    mtkey_t mark = marktree_lookup(buf->b_marktree, id, itr);
     assert(itr->node);
     marktree_del_itr(buf->b_marktree, itr, false);
     if (decor_id >= 0) {
       DecorItem it = kv_A(decors, decor_id);
-      decor_remove(buf, it.row1, pos.row, it.decor);
+      decor_remove(buf, it.row1, mark.pos.row, mark.decor_full);
     }
   });
   map_clear(uint64_t, ssize_t)(&delete_set);
@@ -290,7 +284,7 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_col, int u_r
 // will be searched to the start, or end
 // dir can be set to control the order of the array
 // amount = amount of marks to find or -1 for all
-ExtmarkInfoArray extmark_get(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_col, int u_row,
+ExtmarkInfoArray extmark_get(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_row,
                              colnr_T u_col, int64_t amount, bool reverse)
 {
   ExtmarkInfoArray array = KV_INITIAL_VALUE;
@@ -300,30 +294,24 @@ ExtmarkInfoArray extmark_get(buf_T *buf, uint64_t ns_id, int l_row, colnr_T l_co
                        itr, reverse, false, NULL);
   int order = reverse ? -1 : 1;
   while ((int64_t)kv_size(array) < amount) {
-    mtmark_t mark = marktree_itr_current(itr);
-    mtpos_t endpos = { -1, -1 };
-    if (mark.row < 0
-        || (mark.row - u_row) * order > 0
-        || (mark.row == u_row && (mark.col - u_col) * order > 0)) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0
+        || (mark.pos.row - u_row) * order > 0
+        || (mark.pos.row == u_row && (mark.pos.col - u_col) * order > 0)) {
       break;
     }
-    if (mark.id & MARKTREE_END_FLAG) {
+    if (mt_end(mark)) {
       goto next_mark;
-    } else if (mark.id & MARKTREE_PAIRED_FLAG) {
-      endpos = marktree_lookup(buf->b_marktree, mark.id | MARKTREE_END_FLAG,
-                               NULL);
     }
 
-
-    ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                      mark.id);
-    if (item.ns_id == ns_id) {
-      kv_push(array, ((ExtmarkInfo) { .ns_id = item.ns_id,
-                                      .mark_id = item.mark_id,
-                                      .row = mark.row, .col = mark.col,
+    if (mark.ns == ns_id) {
+      mtpos_t endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
+      kv_push(array, ((ExtmarkInfo) { .ns_id = mark.ns,
+                                      .mark_id = mark.id,
+                                      .row = mark.pos.row, .col = mark.pos.col,
                                       .end_row = endpos.row,
                                       .end_col = endpos.col,
-                                      .decor = item.decor }));
+                                      .decor = get_decor(mark) }));
     }
 next_mark:
     if (reverse) {
@@ -336,36 +324,23 @@ next_mark:
 }
 
 // Lookup an extmark by id
-ExtmarkInfo extmark_from_id(buf_T *buf, uint64_t ns_id, uint64_t id)
+ExtmarkInfo extmark_from_id(buf_T *buf, uint32_t ns_id, uint32_t id)
 {
-  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, false);
-  ExtmarkInfo ret = { 0, 0, -1, -1, -1, -1, NULL };
-  if (!ns) {
+  ExtmarkInfo ret = { 0, 0, -1, -1, -1, -1, DECORATION_INIT };
+  mtkey_t mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, NULL);
+  if (!mark.id) {
     return ret;
   }
-
-  uint64_t mark = map_get(uint64_t, uint64_t)(ns->map, id);
-  if (!mark) {
-    return ret;
-  }
-
-  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, NULL);
-  mtpos_t endpos = { -1, -1 };
-  if (mark & MARKTREE_PAIRED_FLAG) {
-    endpos = marktree_lookup(buf->b_marktree, mark | MARKTREE_END_FLAG, NULL);
-  }
-  assert(pos.row >= 0);
-
-  ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index,
-                                                    mark);
+  assert(mark.pos.row >= 0);
+  mtpos_t endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
 
   ret.ns_id = ns_id;
   ret.mark_id = id;
-  ret.row = pos.row;
-  ret.col = pos.col;
+  ret.row = mark.pos.row;
+  ret.col = mark.pos.col;
   ret.end_row = endpos.row;
   ret.end_col = endpos.col;
-  ret.decor = item.decor;
+  ret.decor = get_decor(mark);
 
   return ret;
 }
@@ -378,25 +353,26 @@ void extmark_free_all(buf_T *buf)
     return;
   }
 
-  uint64_t id;
-  ExtmarkNs ns;
-  ExtmarkItem item;
+  MarkTreeIter itr[1] = { 0 };
+  marktree_itr_get(buf->b_marktree, 0, 0, itr);
+  while (true) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0) {
+      break;
+    }
 
-  marktree_clear(buf->b_marktree);
+    // don't free mark.decor_full twice for a paired mark.
+    if (!(mt_paired(mark) && mt_end(mark))) {
+      decor_free(mark.decor_full);
+    }
 
-  map_foreach(buf->b_extmark_ns, id, ns, {
-    (void)id;
-    map_destroy(uint64_t, uint64_t)(ns.map);
-  });
-  map_destroy(uint64_t, ExtmarkNs)(buf->b_extmark_ns);
-  map_init(uint64_t, ExtmarkNs, buf->b_extmark_ns);
+    marktree_itr_next(buf->b_marktree, itr);
+  }
 
-  map_foreach(buf->b_extmark_index, id, item, {
-    (void)id;
-    decor_free(item.decor);
-  });
-  map_destroy(uint64_t, ExtmarkItem)(buf->b_extmark_index);
-  map_init(uint64_t, ExtmarkItem, buf->b_extmark_index);
+  marktree_clear(buf->b_marktree);
+
+  map_destroy(uint32_t, uint32_t)(buf->b_extmark_ns);
+  map_init(uint32_t, uint32_t, buf->b_extmark_ns);
 }
 
 
@@ -437,16 +413,16 @@ void u_extmark_copy(buf_T *buf, int l_row, colnr_T l_col, int u_row, colnr_T u_c
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, l_row, l_col, itr);
   while (true) {
-    mtmark_t mark = marktree_itr_current(itr);
-    if (mark.row < 0
-        || mark.row > u_row
-        || (mark.row == u_row && mark.col > u_col)) {
+    mtkey_t mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0
+        || mark.pos.row > u_row
+        || (mark.pos.row == u_row && mark.pos.col > u_col)) {
       break;
     }
     ExtmarkSavePos pos;
-    pos.mark = mark.id;
-    pos.old_row = mark.row;
-    pos.old_col = mark.col;
+    pos.mark = mt_lookup_key(mark);
+    pos.old_row = mark.pos.row;
+    pos.old_col = mark.pos.col;
     pos.row = -1;
     pos.col = -1;
 
diff --git a/src/nvim/extmark.h b/src/nvim/extmark.h
index c70db9f7aa..c6ec1d0aa8 100644
--- a/src/nvim/extmark.h
+++ b/src/nvim/extmark.h
@@ -3,6 +3,7 @@
 
 #include "nvim/buffer_defs.h"
 #include "nvim/extmark_defs.h"
+#include "nvim/decoration.h"
 #include "nvim/marktree.h"
 #include "nvim/pos.h"
 
@@ -15,7 +16,7 @@ typedef struct {
   colnr_T col;
   int end_row;
   colnr_T end_col;
-  Decoration *decor;
+  Decoration decor;  // TODO(bfredl): CHONKY
 } ExtmarkInfo;
 
 typedef kvec_t(ExtmarkInfo) ExtmarkInfoArray;
diff --git a/src/nvim/extmark_defs.h b/src/nvim/extmark_defs.h
index bbe8504ebf..5570b5c71e 100644
--- a/src/nvim/extmark_defs.h
+++ b/src/nvim/extmark_defs.h
@@ -4,23 +4,11 @@
 #include "nvim/lib/kvec.h"
 #include "nvim/types.h"
 
-typedef struct Decoration Decoration;
-
 typedef struct {
   char *text;
   int hl_id;
 } VirtTextChunk;
 
-
-typedef struct {
-  uint64_t ns_id;
-  uint64_t mark_id;
-  // TODO(bfredl): a lot of small allocations. Should probably use
-  // kvec_t(Decoration) as an arena. Alternatively, store ns_id/mark_id
-  // _inline_ in MarkTree and use the map only for decorations.
-  Decoration *decor;
-} ExtmarkItem;
-
 typedef struct undo_object ExtmarkUndoObject;
 typedef kvec_t(ExtmarkUndoObject) extmark_undo_vec_t;
 
diff --git a/src/nvim/map.c b/src/nvim/map.c
index c77433df71..77ebc2a387 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -171,10 +171,7 @@ MAP_IMPL(ptr_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(uint64_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(uint64_t, ssize_t, SSIZE_INITIALIZER)
 MAP_IMPL(uint64_t, uint64_t, DEFAULT_INITIALIZER)
-#define EXTMARK_NS_INITIALIZER { { MAP_INIT }, 1 }
-MAP_IMPL(uint64_t, ExtmarkNs, EXTMARK_NS_INITIALIZER)
-#define EXTMARK_ITEM_INITIALIZER { 0, 0, NULL }
-MAP_IMPL(uint64_t, ExtmarkItem, EXTMARK_ITEM_INITIALIZER)
+MAP_IMPL(uint32_t, uint32_t, DEFAULT_INITIALIZER)
 MAP_IMPL(handle_T, ptr_t, DEFAULT_INITIALIZER)
 #define MSGPACK_HANDLER_INITIALIZER { .fn = NULL, .fast = false }
 MAP_IMPL(String, MsgpackRpcRequestHandler, MSGPACK_HANDLER_INITIALIZER)
diff --git a/src/nvim/map.h b/src/nvim/map.h
index dbd85a4e1f..5e56f4dd65 100644
--- a/src/nvim/map.h
+++ b/src/nvim/map.h
@@ -40,16 +40,8 @@ MAP_DECLS(ptr_t, ptr_t)
 MAP_DECLS(uint64_t, ptr_t)
 MAP_DECLS(uint64_t, ssize_t)
 MAP_DECLS(uint64_t, uint64_t)
+MAP_DECLS(uint32_t, uint32_t)
 
-// NB: this is the only way to define a struct both containing and contained
-// in a map...
-typedef struct ExtmarkNs {  // For namespacing extmarks
-  Map(uint64_t, uint64_t) map[1];  // For fast lookup
-  uint64_t free_id;         // For automatically assigning id's
-} ExtmarkNs;
-
-MAP_DECLS(uint64_t, ExtmarkNs)
-MAP_DECLS(uint64_t, ExtmarkItem)
 MAP_DECLS(handle_T, ptr_t)
 MAP_DECLS(String, MsgpackRpcRequestHandler)
 MAP_DECLS(HlEntry, int)
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index 38014ab375..8ae138b2eb 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -56,12 +56,6 @@
 #define T MT_BRANCH_FACTOR
 #define ILEN (sizeof(mtnode_t)+(2 * T) * sizeof(void *))
 
-#define RIGHT_GRAVITY (((uint64_t)1) << 63)
-#define ANTIGRAVITY(id) ((id)&(RIGHT_GRAVITY-1))
-#define IS_RIGHT(id) ((id)&RIGHT_GRAVITY)
-
-#define PAIRED MARKTREE_PAIRED_FLAG
-#define END_FLAG MARKTREE_END_FLAG
 #define ID_INCR (((uint64_t)1) << 2)
 
 #define rawkey(itr) (itr->node->key[itr->i])
@@ -119,7 +113,7 @@ static int key_cmp(mtkey_t a, mtkey_t b)
   }
   // NB: keeping the events at the same pos sorted by id is actually not
   // necessary only make sure that START is before END etc.
-  return mt_generic_cmp(a.id, b.id);
+  return mt_generic_cmp(a.flags, b.flags);
 }
 
 static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
@@ -148,7 +142,7 @@ static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
 
 static inline void refkey(MarkTree *b, mtnode_t *x, int i)
 {
-  pmap_put(uint64_t)(b->id2node, ANTIGRAVITY(x->key[i].id), x);
+  pmap_put(uint64_t)(b->id2node, mt_lookup_key(x->key[i]), x);
 }
 
 // put functions
@@ -221,38 +215,28 @@ static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k)
   }
 }
 
-uint64_t marktree_put(MarkTree *b, int row, int col, bool right_gravity, uint8_t decor_level)
+void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_right)
 {
-  uint64_t id = (b->next_id+=ID_INCR);
-  assert(decor_level < DECOR_LEVELS);
-  id = id | ((uint64_t)decor_level << DECOR_OFFSET);
-  uint64_t keyid = id;
-  if (right_gravity) {
-    // order all right gravity keys after the left ones, for effortless
-    // insertion (but not deletion!)
-    keyid |= RIGHT_GRAVITY;
-  }
-  marktree_put_key(b, row, col, keyid);
-  return id;
-}
+  assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK));
+  if (end_row >= 0) {
+    key.flags |= MT_FLAG_PAIRED;
+  }
 
-uint64_t marktree_put_pair(MarkTree *b, int start_row, int start_col, bool start_right, int end_row,
-                           int end_col, bool end_right, uint8_t decor_level)
-{
-  uint64_t id = (b->next_id+=ID_INCR)|PAIRED;
-  assert(decor_level < DECOR_LEVELS);
-  id = id | ((uint64_t)decor_level << DECOR_OFFSET);
-  uint64_t start_id = id|(start_right?RIGHT_GRAVITY:0);
-  uint64_t end_id = id|END_FLAG|(end_right?RIGHT_GRAVITY:0);
-  marktree_put_key(b, start_row, start_col, start_id);
-  marktree_put_key(b, end_row, end_col, end_id);
-  return id;
+  marktree_put_key(b, key);
+
+  if (end_row >= 0) {
+    mtkey_t end_key = key;
+    end_key.flags = (uint16_t)((uint16_t)(key.flags & ~MT_FLAG_RIGHT_GRAVITY)
+                               |(uint16_t)MT_FLAG_END
+                               |(uint16_t)(end_right ? MT_FLAG_RIGHT_GRAVITY : 0));
+    end_key.pos = (mtpos_t){ end_row, end_col };
+    marktree_put_key(b, end_key);
+  }
 }
 
-void marktree_put_key(MarkTree *b, int row, int col, uint64_t id)
+void marktree_put_key(MarkTree *b, mtkey_t k)
 {
-  mtkey_t k = { .pos = { .row = row, .col = col }, .id = id };
-
+  k.flags |= MT_FLAG_REAL;  // let's be real.
   if (!b->root) {
     b->root = (mtnode_t *)xcalloc(1, ILEN);
     b->n_nodes++;
@@ -302,7 +286,7 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
 
   mtnode_t *cur = itr->node;
   int curi = itr->i;
-  uint64_t id = cur->key[curi].id;
+  uint64_t id = mt_lookup_key(cur->key[curi]);
   // fprintf(stderr, "\nDELET %lu\n", id);
 
   if (itr->node->level) {
@@ -364,7 +348,7 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
   }
 
   b->n_keys--;
-  pmap_del(uint64_t)(b->id2node, ANTIGRAVITY(id));
+  pmap_del(uint64_t)(b->id2node, id);
 
   // 5.
   bool itr_dirty = false;
@@ -570,23 +554,29 @@ void marktree_free_node(mtnode_t *x)
 }
 
 /// NB: caller must check not pair!
-uint64_t marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level)
+void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_t key)
 {
-  uint64_t old_id = rawkey(itr).id;
-  pmap_del(uint64_t)(b->id2node, ANTIGRAVITY(old_id));
-  uint64_t new_id = (b->next_id += ID_INCR) + ((uint64_t)decor_level << DECOR_OFFSET);
-  rawkey(itr).id = new_id + (RIGHT_GRAVITY&old_id);
-  refkey(b, itr->node, itr->i);
-  return new_id;
+  // TODO(bfredl): clean up this mess and re-instantiate &= and |= forms
+  // once we upgrade to a non-broken version of gcc in functionaltest-lua CI
+  rawkey(itr).flags = (uint16_t)((uint16_t)rawkey(itr).flags & (uint16_t)~MT_FLAG_DECOR_MASK);
+  rawkey(itr).flags = (uint16_t)((uint16_t)rawkey(itr).flags
+                                 | (uint16_t)(decor_level << MT_FLAG_DECOR_OFFSET)
+                                 | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK));
+  rawkey(itr).decor_full = key.decor_full;
+  rawkey(itr).hl_id = key.hl_id;
+  rawkey(itr).priority = key.priority;
 }
 
 void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col)
 {
-  uint64_t old_id = rawkey(itr).id;
+  mtkey_t key = rawkey(itr);
   // TODO(bfredl): optimize when moving a mark within a leaf without moving it
   // across neighbours!
   marktree_del_itr(b, itr, false);
-  marktree_put_key(b, row, col, old_id);
+  key.pos = (mtpos_t){ row, col };
+
+
+  marktree_put_key(b, key);
   itr->node = NULL;  // itr might become invalid by put
 }
 
@@ -602,14 +592,15 @@ bool marktree_itr_get(MarkTree *b, int row, int col, MarkTreeIter *itr)
 bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool gravity,
                           mtpos_t *oldbase)
 {
-  mtkey_t k = { .pos = p, .id = gravity ? RIGHT_GRAVITY : 0 };
-  if (last && !gravity) {
-    k.id = UINT64_MAX;
-  }
   if (b->n_keys == 0) {
     itr->node = NULL;
     return false;
   }
+
+  mtkey_t k = { .pos = p, .flags = gravity ? MT_FLAG_RIGHT_GRAVITY : 0 };
+  if (last && !gravity) {
+    k.flags = MT_FLAG_LAST;
+  }
   itr->pos = (mtpos_t){ 0, 0 };
   itr->node = b->root;
   itr->lvl = 0;
@@ -816,25 +807,29 @@ mtpos_t marktree_itr_pos(MarkTreeIter *itr)
   return pos;
 }
 
-mtmark_t marktree_itr_current(MarkTreeIter *itr)
+mtkey_t marktree_itr_current(MarkTreeIter *itr)
 {
   if (itr->node) {
-    uint64_t keyid = rawkey(itr).id;
-    mtpos_t pos = marktree_itr_pos(itr);
-    mtmark_t mark = { .row = pos.row,
-                      .col = pos.col,
-                      .id = ANTIGRAVITY(keyid),
-                      .right_gravity = keyid & RIGHT_GRAVITY };
-    return mark;
-  }
-  return (mtmark_t){ -1, -1, 0, false };
+    mtkey_t key = rawkey(itr);
+    key.pos = marktree_itr_pos(itr);
+    return key;
+  }
+  return MT_INVALID_KEY;
 }
 
-static void swap_id(uint64_t *id1, uint64_t *id2)
+static bool itr_eq(MarkTreeIter *itr1, MarkTreeIter *itr2)
 {
-  uint64_t temp = *id1;
-  *id1 = *id2;
-  *id2 = temp;
+  return (&rawkey(itr1) == &rawkey(itr2));
+}
+
+static void itr_swap(MarkTreeIter *itr1, MarkTreeIter *itr2)
+{
+  mtkey_t key1 = rawkey(itr1);
+  mtkey_t key2 = rawkey(itr2);
+  rawkey(itr1) = key2;
+  rawkey(itr1).pos = key1.pos;
+  rawkey(itr2) = key1;
+  rawkey(itr2).pos = key2.pos;
 }
 
 bool marktree_splice(MarkTree *b, int start_line, int start_col, int old_extent_line,
@@ -865,7 +860,7 @@ bool marktree_splice(MarkTree *b, int start_line, int start_col, int old_extent_
     mtpos_t ipos = marktree_itr_pos(itr);
     if (!pos_leq(old_extent, ipos)
         || (old_extent.row == ipos.row && old_extent.col == ipos.col
-            && !IS_RIGHT(rawkey(itr).id))) {
+            && !mt_right(rawkey(itr)))) {
       marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL);
       assert(enditr->node);
       // "assert" (itr <= enditr)
@@ -895,13 +890,13 @@ continue_same_node:
         break;
       }
 
-      if (IS_RIGHT(rawkey(itr).id)) {
-        while (rawkey(itr).id != rawkey(enditr).id
-               && IS_RIGHT(rawkey(enditr).id)) {
+      if (mt_right(rawkey(itr))) {
+        while (!itr_eq(itr, enditr)
+               && mt_right(rawkey(enditr))) {
           marktree_itr_prev(b, enditr);
         }
-        if (!IS_RIGHT(rawkey(enditr).id)) {
-          swap_id(&rawkey(itr).id, &rawkey(enditr).id);
+        if (!mt_right(rawkey(enditr))) {
+          itr_swap(itr, enditr);
           refkey(b, itr->node, itr->i);
           refkey(b, enditr->node, enditr->i);
         } else {
@@ -911,7 +906,7 @@ continue_same_node:
         }
       }
 
-      if (rawkey(itr).id == rawkey(enditr).id) {
+      if (itr_eq(itr, enditr)) {
         // actually, will be past_right after this key
         past_right = true;
       }
@@ -1006,13 +1001,13 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
   marktree_itr_get_ext(b, start, itr, false, true, NULL);
   kvec_t(mtkey_t) saved = KV_INITIAL_VALUE;
   while (itr->node) {
-    mtpos_t pos = marktree_itr_pos(itr);
-    if (!pos_leq(pos, end) || (pos.row == end.row && pos.col == end.col
-                               && rawkey(itr).id & RIGHT_GRAVITY)) {
+    mtkey_t k = marktree_itr_current(itr);
+    if (!pos_leq(k.pos, end) || (k.pos.row == end.row && k.pos.col == end.col
+                                 && mt_right(k))) {
       break;
     }
-    relative(start, &pos);
-    kv_push(saved, ((mtkey_t){ .pos = pos, .id = rawkey(itr).id }));
+    relative(start, &k.pos);
+    kv_push(saved, k);
     marktree_del_itr(b, itr, false);
   }
 
@@ -1024,30 +1019,36 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
   for (size_t i = 0; i < kv_size(saved); i++) {
     mtkey_t item = kv_A(saved, i);
     unrelative(new, &item.pos);
-    marktree_put_key(b, item.pos.row, item.pos.col, item.id);
+    marktree_put_key(b, item);
   }
   kv_destroy(saved);
 }
 
 /// @param itr OPTIONAL. set itr to pos.
-mtpos_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
+mtkey_t marktree_lookup_ns(MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr)
+{
+  return marktree_lookup(b, mt_lookup_id(ns, id, end), itr);
+}
+
+/// @param itr OPTIONAL. set itr to pos.
+mtkey_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
 {
   mtnode_t *n = pmap_get(uint64_t)(b->id2node, id);
   if (n == NULL) {
     if (itr) {
       itr->node = NULL;
     }
-    return (mtpos_t){ -1, -1 };
+    return MT_INVALID_KEY;
   }
   int i = 0;
   for (i = 0; i < n->n; i++) {
-    if (ANTIGRAVITY(n->key[i].id) == id) {
+    if (mt_lookup_key(n->key[i]) == id) {
       goto found;
     }
   }
   abort();
 found: {}
-  mtpos_t pos = n->key[i].pos;
+  mtkey_t key = n->key[i];
   if (itr) {
     itr->i = i;
     itr->node = n;
@@ -1066,14 +1067,23 @@ found_node:
       itr->s[b->root->level-p->level].i = i;
     }
     if (i > 0) {
-      unrelative(p->key[i-1].pos, &pos);
+      unrelative(p->key[i-1].pos, &key.pos);
     }
     n = p;
   }
   if (itr) {
     marktree_itr_fix_pos(b, itr);
   }
-  return pos;
+  return key;
+}
+
+mtpos_t marktree_get_altpos(MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
+{
+  mtkey_t end = MT_INVALID_KEY;
+  if (mt_paired(mark)) {
+    end = marktree_lookup_ns(b, mark.ns, mark.id, !mt_end(mark), itr);
+  }
+  return end.pos;
 }
 
 static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
@@ -1092,6 +1102,20 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
   assert(x == itr->node);
 }
 
+// for unit test
+void marktree_put_test(MarkTree *b, uint32_t id, int row, int col, bool right_gravity)
+{
+  mtkey_t key = { { row, col }, UINT32_MAX, id, 0,
+                    mt_flags(right_gravity, 0), 0, NULL };
+  marktree_put(b, key, -1, -1, false);
+}
+
+// for unit test
+bool mt_right_test(mtkey_t key)
+{
+  return mt_right(key);
+}
+
 void marktree_check(MarkTree *b)
 {
 #ifndef NDEBUG
@@ -1134,11 +1158,11 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig
     }
     assert(pos_leq(*last, x->key[i].pos));
     if (last->row == x->key[i].pos.row && last->col == x->key[i].pos.col) {
-      assert(!*last_right || IS_RIGHT(x->key[i].id));
+      assert(!*last_right || mt_right(x->key[i]));
     }
-    *last_right = IS_RIGHT(x->key[i].id);
+    *last_right = mt_right(x->key[i]);
     assert(x->key[i].pos.col >= 0);
-    assert(pmap_get(uint64_t)(b->id2node, ANTIGRAVITY(x->key[i].id)) == x);
+    assert(pmap_get(uint64_t)(b->id2node, mt_lookup_key(x->key[i])) == x);
   }
 
   if (x->level) {
diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index a1dcdf5164..95d63dd14a 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -3,8 +3,10 @@
 
 #include <stdint.h>
 
+#include "nvim/assert.h"
 #include "nvim/garray.h"
 #include "nvim/map.h"
+#include "nvim/types.h"
 #include "nvim/pos.h"
 
 #define MT_MAX_DEPTH 20
@@ -15,13 +17,6 @@ typedef struct {
   int32_t col;
 } mtpos_t;
 
-typedef struct {
-  int32_t row;
-  int32_t col;
-  uint64_t id;
-  bool right_gravity;
-} mtmark_t;
-
 typedef struct mtnode_s mtnode_t;
 typedef struct {
   int oldcol;
@@ -39,12 +34,75 @@ typedef struct {
 
 // Internal storage
 //
-// NB: actual marks have id > 0, so we can use (row,col,0) pseudo-key for
+// NB: actual marks have flags > 0, so we can use (row,col,0) pseudo-key for
 // "space before (row,col)"
 typedef struct {
   mtpos_t pos;
-  uint64_t id;
+  uint32_t ns;
+  uint32_t id;
+  int32_t hl_id;
+  uint16_t flags;
+  uint16_t priority;
+  Decoration *decor_full;
 } mtkey_t;
+#define MT_INVALID_KEY (mtkey_t) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
+
+#define MT_FLAG_REAL (((uint16_t)1) << 0)
+#define MT_FLAG_END (((uint16_t)1) << 1)
+#define MT_FLAG_PAIRED (((uint16_t)1) << 2)
+#define MT_FLAG_HL_EOL (((uint16_t)1) << 3)
+
+#define DECOR_LEVELS 4
+#define MT_FLAG_DECOR_OFFSET 4
+#define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS-1)) << MT_FLAG_DECOR_OFFSET)
+
+// next flag is (((uint16_t)1) << 6)
+
+// These _must_ be last to preserve ordering of marks
+#define MT_FLAG_RIGHT_GRAVITY (((uint16_t)1) << 14)
+#define MT_FLAG_LAST (((uint16_t)1) << 15)
+
+#define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_RIGHT_GRAVITY | MT_FLAG_HL_EOL)
+
+#define MARKTREE_END_FLAG (((uint64_t)1) << 63)
+static inline uint64_t mt_lookup_id(uint32_t ns, uint32_t id, bool enda)
+{
+  return (uint64_t)ns << 32 | id | (enda?MARKTREE_END_FLAG:0);
+}
+#undef MARKTREE_END_FLAG
+
+static inline uint64_t mt_lookup_key(mtkey_t key)
+{
+  return mt_lookup_id(key.ns, key.id, key.flags & MT_FLAG_END);
+}
+
+static inline bool mt_paired(mtkey_t key)
+{
+  return key.flags & MT_FLAG_PAIRED;
+}
+
+static inline bool mt_end(mtkey_t key)
+{
+  return key.flags & MT_FLAG_END;
+}
+
+static inline bool mt_right(mtkey_t key)
+{
+  return key.flags & MT_FLAG_RIGHT_GRAVITY;
+}
+
+static inline uint8_t marktree_decor_level(mtkey_t key)
+{
+  return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
+}
+
+static inline uint16_t mt_flags(bool right_gravity, uint8_t decor_level)
+{
+  assert(decor_level < DECOR_LEVELS);
+  return (uint16_t)((right_gravity ? MT_FLAG_RIGHT_GRAVITY : 0)
+                    | (decor_level << MT_FLAG_DECOR_OFFSET));
+}
+
 
 struct mtnode_s {
   int32_t n;
@@ -61,7 +119,6 @@ struct mtnode_s {
 typedef struct {
   mtnode_t *root;
   size_t n_keys, n_nodes;
-  uint64_t next_id;
   // TODO(bfredl): the pointer to node could be part of the larger
   // Map(uint64_t, ExtmarkItem) essentially;
   PMap(uint64_t) id2node[1];
@@ -72,16 +129,4 @@ typedef struct {
 # include "marktree.h.generated.h"
 #endif
 
-#define MARKTREE_PAIRED_FLAG (((uint64_t)1) << 1)
-#define MARKTREE_END_FLAG (((uint64_t)1) << 0)
-
-#define DECOR_LEVELS 4
-#define DECOR_OFFSET 61
-#define DECOR_MASK (((uint64_t)(DECOR_LEVELS-1)) << DECOR_OFFSET)
-
-static inline uint8_t marktree_decor_level(uint64_t id)
-{
-  return (uint8_t)((id&DECOR_MASK) >> DECOR_OFFSET);
-}
-
 #endif  // NVIM_MARKTREE_H
diff --git a/src/nvim/types.h b/src/nvim/types.h
index 604155c33e..73cd2204d6 100644
--- a/src/nvim/types.h
+++ b/src/nvim/types.h
@@ -32,4 +32,6 @@ typedef enum {
   kTrue  = 1,
 } TriState;
 
+typedef struct Decoration Decoration;
+
 #endif  // NVIM_TYPES_H
diff --git a/test/unit/marktree_spec.lua b/test/unit/marktree_spec.lua
index 10d02d2eb4..3c96bc5f58 100644
--- a/test/unit/marktree_spec.lua
+++ b/test/unit/marktree_spec.lua
@@ -32,11 +32,11 @@ local function shadoworder(tree, shadow, iter, giveorder)
     local mark = lib.marktree_itr_current(iter)
     local id = tonumber(mark.id)
     local spos = shadow[id]
-    if (mark.row ~= spos[1] or mark.col ~= spos[2]) then
-      error("invalid pos for "..id..":("..mark.row..", "..mark.col..") instead of ("..spos[1]..", "..spos[2]..")")
+    if (mark.pos.row ~= spos[1] or mark.pos.col ~= spos[2]) then
+      error("invalid pos for "..id..":("..mark.pos.row..", "..mark.pos.col..") instead of ("..spos[1]..", "..spos[2]..")")
     end
-    if mark.right_gravity ~= spos[3] then
-        error("invalid gravity for "..id..":("..mark.row..", "..mark.col..")")
+    if lib.mt_right_test(mark) ~= spos[3] then
+        error("invalid gravity for "..id..":("..mark.pos.row..", "..mark.pos.col..")")
     end
     if count > 0 then
       if not pos_leq(last, spos) then
@@ -87,7 +87,21 @@ local function dosplice(tree, shadow, start, old_extent, new_extent)
   shadowsplice(shadow, start, old_extent, new_extent)
 end
 
+local last_id = nil
+
+local function put(tree, row, col, gravitate)
+  last_id = last_id + 1
+  local my_id = last_id
+
+  lib.marktree_put_test(tree, my_id, row, col, gravitate);
+  return my_id
+end
+
 describe('marktree', function()
+  before_each(function()
+    last_id = 0
+  end)
+
  itp('works', function()
     local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit
     local shadow = {}
@@ -97,7 +111,7 @@ describe('marktree', function()
     for i = 1,100 do
       for j = 1,100 do
         local gravitate = (i%2) > 0
-        local id = tonumber(lib.marktree_put(tree, j, i, gravitate, 0))
+        local id = put(tree, j, i, gravitate)
         ok(id > 0)
         eq(nil, shadow[id])
         shadow[id] = {j,i,gravitate}
@@ -115,12 +129,12 @@ describe('marktree', function()
     eq({}, id2pos)
 
     for i,ipos in pairs(shadow) do
-      local pos = lib.marktree_lookup(tree, i, iter)
-      eq(ipos[1], pos.row)
-      eq(ipos[2], pos.col)
+      local p = lib.marktree_lookup_ns(tree, -1, i, false, iter)
+      eq(ipos[1], p.pos.row)
+      eq(ipos[2], p.pos.col)
       local k = lib.marktree_itr_current(iter)
-      eq(ipos[1], k.row)
-      eq(ipos[2], k.col, ipos[1])
+      eq(ipos[1], k.pos.row)
+      eq(ipos[2], k.pos.col, ipos[1])
       lib.marktree_itr_next(tree, iter)
       -- TODO(bfredl): use id2pos to check neighbour?
       -- local k2 = lib.marktree_itr_current(iter)
@@ -130,8 +144,8 @@ describe('marktree', function()
       lib.marktree_itr_get(tree, ipos[1], ipos[2], iter)
       local k = lib.marktree_itr_current(iter)
       eq(i, tonumber(k.id))
-      eq(ipos[1], k.row)
-      eq(ipos[2], k.col)
+      eq(ipos[1], k.pos.row)
+      eq(ipos[2], k.pos.col)
     end
 
     ok(lib.marktree_itr_first(tree, iter))
@@ -146,8 +160,8 @@ describe('marktree', function()
         lib.marktree_itr_get(tree, i, 50+ci, iter)
         local k = lib.marktree_itr_current(iter)
         local id = tonumber(k.id)
-        eq(shadow[id][1], k.row)
-        eq(shadow[id][2], k.col)
+        eq(shadow[id][1], k.pos.row)
+        eq(shadow[id][2], k.pos.col)
         lib.marktree_del_itr(tree, iter, false)
         shadow[id] = nil
       end
@@ -191,7 +205,7 @@ describe('marktree', function()
     -- https://github.com/neovim/neovim/pull/14719
     lib.marktree_clear(tree)
     for i = 1,20 do
-      lib.marktree_put(tree, i, i, false, 0)
+      put(tree, i, i, false)
     end
 
     lib.marktree_itr_get(tree, 10, 10, iter)