Add user-registers for arbitrary registers.

This allows users to define behaviors for arbitrary registers. These
registers can be any character including multibyte characters. This
means that any character may be used as a register and if that register
is not a builtin register, it will defer to a user-defined vimscript
function for behavior.

This is done throw an option called 'userregfun'

The function that 'userregfun' defines is a function that takes 3
arguments:

   action - Either set to "put" or "yank"
   register - The character representing the register.
   content - If the action is "yank" this string contains the content
             yanked.

Multibyte registers are still broken for expressions. So while

  let @&=xyz

Works as expected,

  let @λ=xyz

will still throw a parse error.

11 files changed, 304 insertions, 52 deletions

diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index f42293b137..1e04341f97 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -700,6 +700,7 @@ struct file_buffer {
   char_u *b_p_cfu;              ///< 'completefunc'
   char_u *b_p_ofu;              ///< 'omnifunc'
   char_u *b_p_tfu;              ///< 'tagfunc'
+  char_u *b_p_urf;              ///< 'userregfunc'
   int b_p_eol;                  ///< 'endofline'
   int b_p_fixeol;               ///< 'fixendofline'
   int b_p_et;                   ///< 'expandtab'
diff --git a/src/nvim/eval.c b/src/nvim/eval.c
index ae64732eb9..7e6e73abc3 100644
--- a/src/nvim/eval.c
+++ b/src/nvim/eval.c
@@ -5284,7 +5284,7 @@ bool garbage_collect(bool testing)
 
   // registers (ShaDa additional data)
   {
-    const void *reg_iter = NULL;
+    iter_register_T reg_iter = ITER_REGISTER_NULL;
     do {
       yankreg_T reg;
       char name = NUL;
@@ -5293,7 +5293,7 @@ bool garbage_collect(bool testing)
       if (name != NUL) {
         ABORTING(set_ref_dict)(reg.additional_data, copyID);
       }
-    } while (reg_iter != NULL);
+    } while (reg_iter != ITER_REGISTER_NULL);
   }
 
   // global marks (ShaDa additional data)
diff --git a/src/nvim/eval/funcs.c b/src/nvim/eval/funcs.c
index fa5a3eb67b..ef1b436661 100644
--- a/src/nvim/eval/funcs.c
+++ b/src/nvim/eval/funcs.c
@@ -4459,6 +4459,7 @@ static void f_has(typval_T *argvars, typval_T *rettv, FunPtr fptr)
     "nvim",
     "colorcolchar",
     "omnihighlight",
+    "userreg",
   };
 
   bool n = false;
diff --git a/src/nvim/ops.c b/src/nvim/ops.c
index 12fb8439f1..4a9fd6425b 100644
--- a/src/nvim/ops.c
+++ b/src/nvim/ops.c
@@ -55,7 +55,24 @@
 #include "nvim/vim.h"
 #include "nvim/window.h"
 
-static yankreg_T y_regs[NUM_REGISTERS];
+#include "nvim/yanktrie.h"
+
+struct yank_registers {
+  yanktrie_T inner;
+};
+
+yank_registers_T y_regs;
+
+static yankreg_T *get_reg(yank_registers_T *regs, int idx) 
+{
+  return yanktrie_get(&regs->inner, (size_t) idx);
+
+}
+
+static yankreg_T *get_global_reg(int idx)
+{
+  return get_reg(&y_regs, idx);
+}
 
 static yankreg_T *y_previous = NULL;  // ptr to last written yankreg
 
@@ -783,6 +800,23 @@ char_u *get_expr_line_src(void)
   return vim_strsave(expr_line);
 }
 
+int get_userreg(int regname)
+{
+  if ((regname >= 'a' && regname <= 'z')
+      || (regname >= 'A' && regname <= 'Z')
+      || (regname >= '0' && regname <= '9')
+      || (regname <= 127 && strchr("\"-:.%#=*+_/", regname))
+      || regname == Ctrl_F
+      || regname == Ctrl_P
+      || regname == Ctrl_W
+      || regname == Ctrl_A
+      || (regname + USER_REGISTERS_START) < regname) {
+    return -1;
+  }
+
+  return regname + USER_REGISTERS_START;
+}
+
 /// Returns whether `regname` is a valid name of a yank register.
 /// Note: There is no check for 0 (default register), caller should do this.
 /// The black hole register '_' is regarded as valid.
@@ -798,7 +832,8 @@ bool valid_yank_reg(int regname, bool writing)
       || regname == '-'
       || regname == '_'
       || regname == '*'
-      || regname == '+') {
+      || regname == '+'
+      || get_userreg(regname) != -1) {
     return true;
   }
   return false;
@@ -847,7 +882,7 @@ yankreg_T *get_yank_register(int regname, int mode)
   if (i == -1) {
     i = 0;
   }
-  reg = &y_regs[i];
+  reg = get_global_reg(i);
 
   if (mode == YREG_YANK) {
     // remember the written register for unnamed paste
@@ -1272,7 +1307,96 @@ static void stuffescaped(const char *arg, bool literally)
 /// @param errmsg     give error message when failing
 ///
 /// @return  true if "regname" is a special register,
-bool get_spec_reg(int regname, char_u **argp, bool *allocated, bool errmsg)
+bool get_spec_reg(int regname, char_u **argp, bool *allocated, bool errmsg);
+
+/*
+ * Executes a call to the put() function on a user-defined register to get the
+ * contents of a user defined register.
+ */
+static int eval_urf_put(char_u *ufn, int regname, char_u **argp)
+{
+  char_u regname_str[5];
+  int len;
+
+  len = (*mb_char2len)(regname);
+  regname_str[len] = 0;
+  utf_char2bytes(regname, regname_str);
+
+  typval_T args[3];
+  args[0].v_type = VAR_STRING;
+  args[1].v_type = VAR_STRING;
+  args[2].v_type = VAR_UNKNOWN;
+
+  args[0].vval.v_string = (char_u *)"put";
+  args[1].vval.v_string = regname_str;
+
+  *argp = (char_u *)call_func_retstr((char *)ufn, 3, args);
+  return *argp == NULL;
+}
+
+/*
+ * Executes the yank() function on a user-defined register to set the contents
+ * of that register.
+ */
+static int eval_yank_userreg(const char_u *ufn, int regname, yankreg_T *reg)
+{
+  if (!reg)
+    return -1;
+
+  char_u *totalbuf;
+  size_t totallen = 0;
+  size_t i, j, k;
+  int ret, len;
+  char_u regname_str[5];
+
+  {
+    // Concat the contents of the register to pass into the yank()
+    // user-defined function.
+    for (i = 0; i < reg->y_size; ++i) {
+      totallen += strlen((char *)reg->y_array[i]) + 1;
+    }
+    totalbuf = xmalloc(sizeof(char_u) * totallen);
+    j = 0;
+    for (i = 0; i < reg->y_size; ++i) {
+      for (k = 0; reg->y_array[i][k] != 0; ++k, ++j) {
+        totalbuf[j] = reg->y_array[i][k];
+      }
+      if (i < reg->y_size - 1) {
+        totalbuf[j++] = '\n';
+      }
+    }
+    totalbuf[j++] = 0;
+  }
+
+  len = (*mb_char2len)(regname);
+  regname_str[len] = 0;
+  utf_char2bytes(regname, regname_str);
+
+  typval_T args[4];
+  args[0].v_type = VAR_STRING;
+  args[1].v_type = VAR_STRING;
+  args[2].v_type = VAR_STRING;
+  args[3].v_type = VAR_UNKNOWN;
+
+  args[0].vval.v_string = (char_u *)"yank";
+  args[1].vval.v_string = regname_str;
+  args[2].vval.v_string = totalbuf;
+
+  char_u *dup_ufn = (char_u *)xstrdup((char *)ufn);
+  ret = (int)call_func_retnr(dup_ufn, 3, args);
+  xfree(dup_ufn);
+  xfree(totalbuf);
+  return ret;
+}
+
+// If "regname" is a special register, return true and store a pointer to its
+// value in "argp".
+bool get_spec_reg(
+    int regname,
+    char_u **argp,
+    bool *allocated,        // return: true when value was allocated
+    bool errmsg             // give error message when failing
+)
 {
   size_t cnt;
 
@@ -1350,6 +1474,15 @@ bool get_spec_reg(int regname, char_u **argp, bool *allocated, bool errmsg)
   case '_':                     // black hole: always empty
     *argp = (char_u *)"";
     return true;
+
+  default:                     /* User-defined registers. */
+    if (get_userreg(regname) != -1) {
+      if (!curbuf->b_p_urf || strlen((char *) curbuf->b_p_urf) == 0)
+        return false;
+      eval_urf_put(curbuf->b_p_urf, regname, argp);
+      *allocated = true;
+      return true;
+    }
   }
 
   return false;
@@ -1396,14 +1529,14 @@ bool cmdline_paste_reg(int regname, bool literally_arg, bool remcr)
 // Shift the delete registers: "9 is cleared, "8 becomes "9, etc.
 static void shift_delete_registers(bool y_append)
 {
-  free_register(&y_regs[9]);  // free register "9
+  free_register(get_global_reg(9));  // free register "9
   for (int n = 9; n > 1; n--) {
-    y_regs[n] = y_regs[n - 1];
+    *get_global_reg(n) = *get_global_reg(n - 1);
   }
   if (!y_append) {
-    y_previous = &y_regs[1];
+    y_previous = get_global_reg(1);
   }
-  y_regs[1].y_array = NULL;  // set register "1 to empty
+  get_global_reg(1)->y_array = NULL;  // set register "1 to empty
 }
 
 /*
@@ -1501,7 +1634,7 @@ int op_delete(oparg_T *oap)
     if (oap->regname != 0 || oap->motion_type == kMTLineWise
         || oap->line_count > 1 || oap->use_reg_one) {
       shift_delete_registers(is_append_register(oap->regname));
-      reg = &y_regs[1];
+      reg = get_global_reg(1);
       op_yank_reg(oap, false, reg, false);
       did_yank = true;
     }
@@ -2496,7 +2629,7 @@ int op_change(oparg_T *oap)
  */
 void init_yank(void)
 {
-  memset(&(y_regs[0]), 0, sizeof(y_regs));
+  init_yanktrie(&y_regs.inner);
 }
 
 #if defined(EXITFREE)
@@ -2505,7 +2638,7 @@ void clear_registers(void)
   int i;
 
   for (i = 0; i < NUM_REGISTERS; i++) {
-    free_register(&y_regs[i]);
+    free_register(get_global_reg(i));
   }
 }
 
@@ -2549,6 +2682,11 @@ bool op_yank(oparg_T *oap, bool message, int deleting)
 
   yankreg_T *reg = get_yank_register(oap->regname, YREG_YANK);
   op_yank_reg(oap, message, reg, is_append_register(oap->regname));
+
+  if (get_userreg(oap->regname) != -1) {
+    return eval_yank_userreg(curbuf->b_p_urf, oap->regname, reg) != -1;
+  }
+
   // op_delete will set_clipboard and do_autocmd
   if (!deleting) {
     set_clipboard(oap->regname, reg);
@@ -3005,7 +3143,7 @@ void do_put(int regname, yankreg_T *reg, int dir, long count, int flags)
 
   if (insert_string != NULL) {
     y_type = kMTCharWise;
-    if (regname == '=') {
+    if (regname == '=' || get_userreg(regname) != -1) {
       /* For the = register we need to split the string at NL
        * characters.
        * Loop twice: count the number of lines and save them. */
@@ -3689,10 +3827,10 @@ void ex_display(exarg_T *eap)
       if (y_previous != NULL) {
         yb = y_previous;
       } else {
-        yb = &(y_regs[0]);
+        yb = get_global_reg(0);
       }
     } else {
-      yb = &(y_regs[i]);
+      yb = get_global_reg(i);
     }
 
     get_clipboard(name, &yb, true);
@@ -5383,6 +5521,10 @@ static void finish_write_reg(int name, yankreg_T *reg, yankreg_T *old_y_previous
   // Send text of clipboard register to the clipboard.
   set_clipboard(name, reg);
 
+  if (get_userreg(name) != -1) {
+    eval_yank_userreg(curbuf->b_p_urf, name, reg);
+  }
+
   // ':let @" = "val"' should change the meaning of the "" register
   if (name != '"') {
     y_previous = old_y_previous;
@@ -5971,7 +6113,7 @@ static yankreg_T *adjust_clipboard_name(int *name, bool quiet, bool writing)
   }
 
   if (explicit_cb_reg) {
-    target = &y_regs[*name == '*' ? STAR_REGISTER : PLUS_REGISTER];
+    target = get_global_reg(*name == '*' ? STAR_REGISTER : PLUS_REGISTER);
     if (writing && (cb_flags & (*name == '*' ? CB_UNNAMED : CB_UNNAMEDPLUS))) {
       clipboard_needs_update = false;
     }
@@ -5988,10 +6130,10 @@ static yankreg_T *adjust_clipboard_name(int *name, bool quiet, bool writing)
 
     if (cb_flags & CB_UNNAMEDPLUS) {
       *name = (cb_flags & CB_UNNAMED && writing) ? '"': '+';
-      target = &y_regs[PLUS_REGISTER];
+      target = get_global_reg(PLUS_REGISTER);
     } else {
       *name = '*';
-      target = &y_regs[STAR_REGISTER];
+      target = get_global_reg(STAR_REGISTER);
     }
     goto end;
   }
@@ -6308,11 +6450,11 @@ static inline bool reg_empty(const yankreg_T *const reg)
 /// Iterate over global registers.
 ///
 /// @see op_register_iter
-const void *op_global_reg_iter(const void *const iter, char *const name, yankreg_T *const reg,
-                               bool *is_unnamed)
+iter_register_T op_global_reg_iter(iter_register_T iter, char *const name,
+                               yankreg_T *const reg, bool *is_unnamed)
   FUNC_ATTR_NONNULL_ARG(2, 3, 4) FUNC_ATTR_WARN_UNUSED_RESULT
 {
-  return op_reg_iter(iter, y_regs, name, reg, is_unnamed);
+  return op_reg_iter(iter, &y_regs, name, reg, is_unnamed);
 }
 
 /// Iterate over registers `regs`.
@@ -6324,30 +6466,31 @@ const void *op_global_reg_iter(const void *const iter, char *const name, yankreg
 ///
 /// @return Pointer that must be passed to next `op_register_iter` call or
 ///         NULL if iteration is over.
-const void *op_reg_iter(const void *const iter, const yankreg_T *const regs, char *const name,
-                        yankreg_T *const reg, bool *is_unnamed)
+iter_register_T op_reg_iter(iter_register_T iter, yank_registers_T *regs,
+                        char *const name, yankreg_T *const reg,
+                        bool *is_unnamed)
   FUNC_ATTR_NONNULL_ARG(3, 4, 5) FUNC_ATTR_WARN_UNUSED_RESULT
 {
   *name = NUL;
-  const yankreg_T *iter_reg = (iter == NULL
-                               ? &(regs[0])
-                               : (const yankreg_T *const)iter);
-  while (iter_reg - &(regs[0]) < NUM_SAVED_REGISTERS && reg_empty(iter_reg)) {
-    iter_reg++;
-  }
-  if (iter_reg - &(regs[0]) == NUM_SAVED_REGISTERS || reg_empty(iter_reg)) {
-    return NULL;
-  }
-  int iter_off = (int)(iter_reg - &(regs[0]));
-  *name = (char)get_register_name(iter_off);
-  *reg = *iter_reg;
-  *is_unnamed = (iter_reg == y_previous);
-  while (++iter_reg - &(regs[0]) < NUM_SAVED_REGISTERS) {
-    if (!reg_empty(iter_reg)) {
-      return (void *)iter_reg;
+  int iter_idx = (int)(iter == ITER_REGISTER_NULL ? 0 : iter - 1);
+
+  while (iter_idx < NUM_SAVED_REGISTERS && reg_empty(get_reg(regs, iter_idx)))
+    ++iter_idx;
+
+  if (iter_idx >= NUM_SAVED_REGISTERS || reg_empty(get_reg(regs, iter_idx)))
+    return ITER_REGISTER_NULL;
+
+  *reg = *get_reg(regs, iter_idx);
+  *name = (char)get_register_name((int)iter_idx);
+  *is_unnamed = (get_reg(regs, iter_idx) == y_previous);
+
+  while (++iter_idx < NUM_SAVED_REGISTERS) {
+    if (!reg_empty(get_reg(regs, iter_idx))) {
+      return (iter_register_T)(iter_idx + 1);
     }
   }
-  return NULL;
+
+  return ITER_REGISTER_NULL;
 }
 
 /// Get a number of non-empty registers
@@ -6355,8 +6498,8 @@ size_t op_reg_amount(void)
   FUNC_ATTR_WARN_UNUSED_RESULT
 {
   size_t ret = 0;
-  for (size_t i = 0; i < NUM_SAVED_REGISTERS; i++) {
-    if (!reg_empty(y_regs + i)) {
+  for (int i = 0; i < NUM_SAVED_REGISTERS; i++) {
+    if (!reg_empty(get_global_reg(i))) {
       ret++;
     }
   }
@@ -6376,11 +6519,11 @@ bool op_reg_set(const char name, const yankreg_T reg, bool is_unnamed)
   if (i == -1) {
     return false;
   }
-  free_register(&y_regs[i]);
-  y_regs[i] = reg;
+  free_register(get_global_reg(i));
+  *get_global_reg(i) = reg;
 
   if (is_unnamed) {
-    y_previous = &y_regs[i];
+    y_previous = get_global_reg(i);
   }
   return true;
 }
@@ -6396,7 +6539,7 @@ const yankreg_T *op_reg_get(const char name)
   if (i == -1) {
     return NULL;
   }
-  return &y_regs[i];
+  return get_global_reg(i);
 }
 
 /// Set the previous yank register
@@ -6412,7 +6555,7 @@ bool op_reg_set_previous(const char name)
     return false;
   }
 
-  y_previous = &y_regs[i];
+  y_previous = get_global_reg(i);
   return true;
 }
 
diff --git a/src/nvim/ops.h b/src/nvim/ops.h
index 112ffbeaba..4ab6c54782 100644
--- a/src/nvim/ops.h
+++ b/src/nvim/ops.h
@@ -22,6 +22,7 @@ typedef int (*Indenter)(void);
 #define PUT_LINE_SPLIT   16     // split line for linewise register
 #define PUT_LINE_FORWARD 32     // put linewise register below Visual sel.
 #define PUT_BLOCK_INNER  64     // in block mode, do not add trailing spaces
+#define ITER_REGISTER_NULL 0
 
 /*
  * Registers:
@@ -37,7 +38,8 @@ typedef int (*Indenter)(void);
 // The following registers should not be saved in ShaDa file:
 #define STAR_REGISTER 37
 #define PLUS_REGISTER 38
-#define NUM_REGISTERS 39
+#define USER_REGISTERS_START 39
+#define NUM_REGISTERS USER_REGISTERS_START
 
 // Operator IDs; The order must correspond to opchars[] in ops.c!
 #define OP_NOP          0       // no pending operation
@@ -90,6 +92,9 @@ typedef struct yankreg {
   dict_T *additional_data;  ///< Additional data from ShaDa file.
 } yankreg_T;
 
+/// Returns a reference to a user-defined register.
+int get_userreg(const int regname);
+
 /// Convert register name into register index
 ///
 /// @param[in]  regname  Register name.
@@ -111,10 +116,15 @@ static inline int op_reg_index(const int regname)
   } else if (regname == '+') {
     return PLUS_REGISTER;
   } else {
-    return -1;
+    return get_userreg(regname);
   }
 }
 
+struct yank_registers;
+typedef struct yank_registers yank_registers_T;
+
+typedef size_t iter_register_T;
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "ops.h.generated.h"
 #endif
diff --git a/src/nvim/option.c b/src/nvim/option.c
index d88467b57f..b7d27f2709 100644
--- a/src/nvim/option.c
+++ b/src/nvim/option.c
@@ -5758,6 +5758,7 @@ static char_u *get_varp(vimoption_T *p)
 # endif
   case PV_CFU:    return (char_u *)&(curbuf->b_p_cfu);
   case PV_OFU:    return (char_u *)&(curbuf->b_p_ofu);
+  case PV_URF:    return (char_u *)&(curbuf->b_p_urf);
   case PV_EOL:    return (char_u *)&(curbuf->b_p_eol);
   case PV_FIXEOL: return (char_u *)&(curbuf->b_p_fixeol);
   case PV_ET:     return (char_u *)&(curbuf->b_p_et);
@@ -6058,6 +6059,7 @@ void buf_copy_options(buf_T *buf, int flags)
 # endif
       buf->b_p_cfu = vim_strsave(p_cfu);
       buf->b_p_ofu = vim_strsave(p_ofu);
+      buf->b_p_urf = vim_strsave(p_urf);
       buf->b_p_tfu = vim_strsave(p_tfu);
       buf->b_p_sts = p_sts;
       buf->b_p_sts_nopaste = p_sts_nopaste;
diff --git a/src/nvim/option_defs.h b/src/nvim/option_defs.h
index e588d3f373..67eb405465 100644
--- a/src/nvim/option_defs.h
+++ b/src/nvim/option_defs.h
@@ -740,6 +740,7 @@ EXTERN int p_write;             // 'write'
 EXTERN int p_wa;                // 'writeany'
 EXTERN int p_wb;                // 'writebackup'
 EXTERN long p_wd;               // 'writedelay'
+EXTERN char_u *p_urf;           // 'userregister'
 
 EXTERN int p_force_on;          ///< options that cannot be turned off.
 EXTERN int p_force_off;         ///< options that cannot be turned on.
@@ -834,6 +835,7 @@ enum {
   , BV_WM
   , BV_VSTS
   , BV_VTS
+  , BV_URF
   , BV_COUNT        // must be the last one
 };
 
diff --git a/src/nvim/options.lua b/src/nvim/options.lua
index 8b9cdefd57..728dc55a2d 100644
--- a/src/nvim/options.lua
+++ b/src/nvim/options.lua
@@ -2657,6 +2657,15 @@ return {
       defaults={if_true=4000}
     },
     {
+      full_name='userregfun', abbreviation='urf',
+      type='string', scope={'buffer'},
+      secure=true,
+      vi_def=true,
+      alloced=true,
+      varname='p_urf',
+      defaults={if_true=""}
+    },
+    {
       full_name='varsofttabstop', abbreviation='vsts',
       short_desc=N_("list of numbers of spaces that <Tab> uses while editing"),
       type='string', list='comma', scope={'buffer'},
diff --git a/src/nvim/shada.c b/src/nvim/shada.c
index 7d277fe5c8..96937b24d7 100644
--- a/src/nvim/shada.c
+++ b/src/nvim/shada.c
@@ -2492,7 +2492,7 @@ static inline void shada_initialize_registers(WriteMergerState *const wms,
                                               int max_reg_lines)
   FUNC_ATTR_NONNULL_ALL FUNC_ATTR_ALWAYS_INLINE
 {
-  const void *reg_iter = NULL;
+  iter_register_T reg_iter = ITER_REGISTER_NULL;
   const bool limit_reg_lines = max_reg_lines >= 0;
   do {
     yankreg_T reg;
@@ -2523,7 +2523,7 @@ static inline void shada_initialize_registers(WriteMergerState *const wms,
         }
       }
     };
-  } while (reg_iter != NULL);
+  } while (reg_iter != ITER_REGISTER_NULL);
 }
 
 /// Replace numbered mark in WriteMergerState
diff --git a/src/nvim/yanktrie.c b/src/nvim/yanktrie.c
new file mode 100644
index 0000000000..de20966cb2
--- /dev/null
+++ b/src/nvim/yanktrie.c
@@ -0,0 +1,57 @@
+#include "nvim/yanktrie.h"
+
+#include "nvim/memory.h"
+
+void init_yanktrie(yanktrie_T* yanktrie)
+{
+  memset(yanktrie, 0, sizeof(yanktrie_T));
+}
+
+yankreg_T* loose_get(yanktrie_T* trie, size_t index, int rec)
+{
+  int minor_index = index & 0x0F;
+
+  if (rec == 4) {
+    return &trie->u.value;
+  }
+
+  if (trie->u.children[minor_index] == NULL) {
+    trie->u.children[minor_index] = (yanktrie_T*)xmalloc(sizeof(yanktrie_T));
+    init_yanktrie(trie->u.children[minor_index]);
+  }
+
+  return loose_get(trie->u.children[minor_index], index >> 4, rec + 1);
+}
+
+yankreg_T* yanktrie_get(yanktrie_T* trie, size_t index)
+{
+  return loose_get(trie, index, 0);
+}
+
+static void yanktrie_loose_foreach(yanktrie_T* trie,
+                                   void (*fn)(void*, size_t, yankreg_T*),
+                                   int depth,
+                                   size_t index,
+                                   void* closure)
+{
+  size_t i;
+  if (!trie)
+    return;
+
+  if (depth == 4) {
+    fn(closure, index, &trie->u.value);
+    return;
+  } else {
+    for (i = 0; i < 16; ++i) {
+      yanktrie_loose_foreach(trie->u.children[i], fn, depth + 1, index << 4 | i,
+                             closure);
+    }
+  }
+}
+
+void yanktrie_foreach(yanktrie_T* trie,
+                      void (*fn)(void*, size_t, yankreg_T*),
+                      void* closure)
+{
+  yanktrie_loose_foreach(trie, fn, 0, 0, closure);
+}
diff --git a/src/nvim/yanktrie.h b/src/nvim/yanktrie.h
new file mode 100644
index 0000000000..3e5508ac1b
--- /dev/null
+++ b/src/nvim/yanktrie.h
@@ -0,0 +1,27 @@
+#ifndef YANK_TRIE_H_
+#define YANK_TRIE_H_
+
+#include <stdbool.h>
+#include "nvim/ops.h"
+
+/*
+ * yanktrie.h: implementation of a datastructure to hold an arbitrary number of
+ * yank registers.
+ */
+
+typedef struct YANKTRIE {
+  union {
+    struct YANKTRIE* children[16]; /* nybble-wise trie. */
+    yankreg_T value;
+  } u;
+} yanktrie_T;
+
+
+void init_yanktrie(yanktrie_T* yanktrie);
+
+yankreg_T* yanktrie_get(yanktrie_T* yanktrie, size_t index);
+
+void yanktrie_foreach(
+    yanktrie_T* trie, void (*fn)(void*, size_t, yankreg_T*), void* closure);
+
+#endif