Merge pull request #31539 from bfredl/wininfo

refactor(wininfo): change wininfo from a linked list to an array

8 files changed, 67 insertions, 86 deletions

diff --git a/src/klib/kvec.h b/src/klib/kvec.h
index 1b9e6fd9f8..ea8cbe48cf 100644
--- a/src/klib/kvec.h
+++ b/src/klib/kvec.h
@@ -135,6 +135,10 @@
          : 0UL)), \
      &(v).items[(i)]))
 
+#define kv_shift(v, i, n) ((v).size -= (n), (i) < (v).size \
+                           && memmove(&kv_A(v, (i)), &kv_A(v, (i)+(n)), \
+                                      ((v).size-(i))*sizeof(kv_A(v, i))))
+
 #define kv_printf(v, ...) kv_do_printf(&(v), __VA_ARGS__)
 
 /// Type of a vector with a few first members allocated on stack
diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 56ddadeb5c..5dcf7d8f49 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -875,6 +875,7 @@ static void free_buffer(buf_T *buf)
   aubuflocal_remove(buf);
   xfree(buf->additional_data);
   xfree(buf->b_prompt_text);
+  kv_destroy(buf->b_wininfo);
   callback_free(&buf->b_prompt_callback);
   callback_free(&buf->b_prompt_interrupt);
   clear_fmark(&buf->b_last_cursor, 0);
@@ -901,13 +902,10 @@ static void free_buffer(buf_T *buf)
 /// Free the b_wininfo list for buffer "buf".
 static void clear_wininfo(buf_T *buf)
 {
-  wininfo_T *wip;
-
-  while (buf->b_wininfo != NULL) {
-    wip = buf->b_wininfo;
-    buf->b_wininfo = wip->wi_next;
-    free_wininfo(wip, buf);
+  for (size_t i = 0; i < kv_size(buf->b_wininfo); i++) {
+    free_wininfo(kv_A(buf->b_wininfo, i), buf);
   }
+  kv_size(buf->b_wininfo) = 0;
 }
 
 /// Free stuff in the buffer for ":bdel" and when wiping out the buffer.
@@ -1926,7 +1924,8 @@ buf_T *buflist_new(char *ffname_arg, char *sfname_arg, linenr_T lnum, int flags)
   }
 
   clear_wininfo(buf);
-  buf->b_wininfo = xcalloc(1, sizeof(wininfo_T));
+  WinInfo *curwin_info = xcalloc(1, sizeof(WinInfo));
+  kv_push(buf->b_wininfo, curwin_info);
 
   if (buf == curbuf) {
     free_buffer_stuff(buf, kBffInitChangedtick);  // delete local vars et al.
@@ -1964,9 +1963,9 @@ buf_T *buflist_new(char *ffname_arg, char *sfname_arg, linenr_T lnum, int flags)
     buf_copy_options(buf, BCO_ALWAYS);
   }
 
-  buf->b_wininfo->wi_mark = (fmark_T)INIT_FMARK;
-  buf->b_wininfo->wi_mark.mark.lnum = lnum;
-  buf->b_wininfo->wi_win = curwin;
+  curwin_info->wi_mark = (fmark_T)INIT_FMARK;
+  curwin_info->wi_mark.mark.lnum = lnum;
+  curwin_info->wi_win = curwin;
 
   hash_init(&buf->b_s.b_keywtab);
   hash_init(&buf->b_s.b_keywtab_ic);
@@ -2631,30 +2630,26 @@ void buflist_setfpos(buf_T *const buf, win_T *const win, linenr_T lnum, colnr_T
                      bool copy_options)
   FUNC_ATTR_NONNULL_ARG(1)
 {
-  wininfo_T *wip;
+  WinInfo *wip;
 
-  for (wip = buf->b_wininfo; wip != NULL; wip = wip->wi_next) {
+  size_t i;
+  for (i = 0; i < kv_size(buf->b_wininfo); i++) {
+    wip = kv_A(buf->b_wininfo, i);
     if (wip->wi_win == win) {
       break;
     }
   }
-  if (wip == NULL) {
+
+  if (i == kv_size(buf->b_wininfo)) {
     // allocate a new entry
-    wip = xcalloc(1, sizeof(wininfo_T));
+    wip = xcalloc(1, sizeof(WinInfo));
     wip->wi_win = win;
     if (lnum == 0) {            // set lnum even when it's 0
       lnum = 1;
     }
   } else {
     // remove the entry from the list
-    if (wip->wi_prev) {
-      wip->wi_prev->wi_next = wip->wi_next;
-    } else {
-      buf->b_wininfo = wip->wi_next;
-    }
-    if (wip->wi_next) {
-      wip->wi_next->wi_prev = wip->wi_prev;
-    }
+    kv_shift(buf->b_wininfo, i, 1);
     if (copy_options && wip->wi_optset) {
       clear_winopt(&wip->wi_opt);
       deleteFoldRecurse(buf, &wip->wi_folds);
@@ -2679,17 +2674,15 @@ void buflist_setfpos(buf_T *const buf, win_T *const win, linenr_T lnum, colnr_T
   }
 
   // insert the entry in front of the list
-  wip->wi_next = buf->b_wininfo;
-  buf->b_wininfo = wip;
-  wip->wi_prev = NULL;
-  if (wip->wi_next) {
-    wip->wi_next->wi_prev = wip;
-  }
+  kv_pushp(buf->b_wininfo);
+  memmove(&kv_A(buf->b_wininfo, 1), &kv_A(buf->b_wininfo, 0),
+          (kv_size(buf->b_wininfo) - 1) * sizeof(kv_A(buf->b_wininfo, 0)));
+  kv_A(buf->b_wininfo, 0) = wip;
 }
 
 /// Check that "wip" has 'diff' set and the diff is only for another tab page.
 /// That's because a diff is local to a tab page.
-static bool wininfo_other_tab_diff(wininfo_T *wip)
+static bool wininfo_other_tab_diff(WinInfo *wip)
   FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL
 {
   if (!wip->wi_opt.wo_diff) {
@@ -2713,42 +2706,38 @@ static bool wininfo_other_tab_diff(wininfo_T *wip)
 /// @param skip_diff_buffer  when true, avoid windows with 'diff' set that is in another tab page.
 ///
 /// @return  NULL when there isn't any info.
-static wininfo_T *find_wininfo(buf_T *buf, bool need_options, bool skip_diff_buffer)
+static WinInfo *find_wininfo(buf_T *buf, bool need_options, bool skip_diff_buffer)
   FUNC_ATTR_NONNULL_ALL FUNC_ATTR_PURE
 {
-  wininfo_T *wip;
-
-  for (wip = buf->b_wininfo; wip != NULL; wip = wip->wi_next) {
+  for (size_t i = 0; i < kv_size(buf->b_wininfo); i++) {
+    WinInfo *wip = kv_A(buf->b_wininfo, i);
     if (wip->wi_win == curwin
         && (!skip_diff_buffer || !wininfo_other_tab_diff(wip))
         && (!need_options || wip->wi_optset)) {
-      break;
+      return wip;
     }
   }
 
-  if (wip != NULL) {
-    return wip;
-  }
-
   // If no wininfo for curwin, use the first in the list (that doesn't have
   // 'diff' set and is in another tab page).
   // If "need_options" is true skip entries that don't have options set,
   // unless the window is editing "buf", so we can copy from the window
   // itself.
   if (skip_diff_buffer) {
-    for (wip = buf->b_wininfo; wip != NULL; wip = wip->wi_next) {
+    for (size_t i = 0; i < kv_size(buf->b_wininfo); i++) {
+      WinInfo *wip = kv_A(buf->b_wininfo, i);
       if (!wininfo_other_tab_diff(wip)
           && (!need_options
               || wip->wi_optset
               || (wip->wi_win != NULL
                   && wip->wi_win->w_buffer == buf))) {
-        break;
+        return wip;
       }
     }
-  } else {
-    wip = buf->b_wininfo;
+  } else if (kv_size(buf->b_wininfo)) {
+    return kv_A(buf->b_wininfo, 0);
   }
-  return wip;
+  return NULL;
 }
 
 /// Reset the local window options to the values last used in this window.
@@ -2760,7 +2749,7 @@ void get_winopts(buf_T *buf)
   clear_winopt(&curwin->w_onebuf_opt);
   clearFolding(curwin);
 
-  wininfo_T *const wip = find_wininfo(buf, true, true);
+  WinInfo *const wip = find_wininfo(buf, true, true);
   if (wip != NULL && wip->wi_win != curwin && wip->wi_win != NULL
       && wip->wi_win->w_buffer == buf) {
     win_T *wp = wip->wi_win;
@@ -2800,7 +2789,7 @@ fmark_T *buflist_findfmark(buf_T *buf)
 {
   static fmark_T no_position = { { 1, 0, 0 }, 0, 0, { 0 }, NULL };
 
-  wininfo_T *const wip = find_wininfo(buf, false, false);
+  WinInfo *const wip = find_wininfo(buf, false, false);
   return (wip == NULL) ? &no_position : &(wip->wi_mark);
 }
 
diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index bb6eef3c29..3fe44beab9 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -70,7 +70,7 @@ typedef struct {
 // Mask to check for flags that prevent normal writing
 #define BF_WRITE_MASK   (BF_NOTEDITED + BF_NEW + BF_READERR)
 
-typedef struct wininfo_S wininfo_T;
+typedef struct wininfo_S WinInfo;
 typedef struct frame_S frame_T;
 typedef uint64_t disptick_T;  // display tick type
 
@@ -85,7 +85,7 @@ typedef struct {
 
 // Structure that contains all options that are local to a window.
 // Used twice in a window: for the current buffer and for all buffers.
-// Also used in wininfo_T.
+// Also used in WinInfo.
 typedef struct {
   int wo_arab;
 #define w_p_arab w_onebuf_opt.wo_arab  // 'arabic'
@@ -219,8 +219,6 @@ typedef struct {
 // The window-info is kept in a list at b_wininfo.  It is kept in
 // most-recently-used order.
 struct wininfo_S {
-  wininfo_T *wi_next;         // next entry or NULL for last entry
-  wininfo_T *wi_prev;         // previous entry or NULL for first entry
   win_T *wi_win;          // pointer to window that did set wi_mark
   fmark_T wi_mark;                // last cursor mark in the file
   bool wi_optset;               // true when wi_opt has useful values
@@ -411,7 +409,7 @@ struct file_buffer {
                                 // change
   linenr_T b_mod_xlines;        // number of extra buffer lines inserted;
                                 // negative when lines were deleted
-  wininfo_T *b_wininfo;         // list of last used info for each window
+  kvec_t(WinInfo *) b_wininfo;  // list of last used info for each window
   disptick_T b_mod_tick_syn;    // last display tick syntax was updated
   disptick_T b_mod_tick_decor;  // last display tick decoration providers
                                 // where invoked
diff --git a/src/nvim/eval/buffer.c b/src/nvim/eval/buffer.c
index 73bfd6db2a..b4181eb186 100644
--- a/src/nvim/eval/buffer.c
+++ b/src/nvim/eval/buffer.c
@@ -66,12 +66,11 @@ buf_T *find_buffer(typval_T *avar)
 /// If there is a window for "curbuf", make it the current window.
 static void find_win_for_curbuf(void)
 {
-  wininfo_T *wip;
-
   // The b_wininfo list should have the windows that recently contained the
   // buffer, going over this is faster than going over all the windows.
   // Do check the buffer is still there.
-  FOR_ALL_BUF_WININFO(curbuf, wip) {
+  for (size_t i = 0; i < kv_size(curbuf->b_wininfo); i++) {
+    WinInfo *wip = kv_A(curbuf->b_wininfo, i);
     if (wip->wi_win != NULL && wip->wi_win->w_buffer == curbuf) {
       curwin = wip->wi_win;
       break;
diff --git a/src/nvim/eval/funcs.c b/src/nvim/eval/funcs.c
index f700e732a9..768d7664f7 100644
--- a/src/nvim/eval/funcs.c
+++ b/src/nvim/eval/funcs.c
@@ -2402,14 +2402,15 @@ static void f_getchangelist(typval_T *argvars, typval_T *rettv, EvalFuncData fpt
   if (buf == curwin->w_buffer) {
     changelistindex = curwin->w_changelistidx;
   } else {
-    wininfo_T *wip;
+    changelistindex = buf->b_changelistlen;
 
-    FOR_ALL_BUF_WININFO(buf, wip) {
+    for (size_t i = 0; i < kv_size(buf->b_wininfo); i++) {
+      WinInfo *wip = kv_A(buf->b_wininfo, i);
       if (wip->wi_win == curwin) {
+        changelistindex = wip->wi_changelistidx;
         break;
       }
     }
-    changelistindex = wip != NULL ? wip->wi_changelistidx : buf->b_changelistlen;
   }
   tv_list_append_number(rettv->vval.v_list, (varnumber_T)changelistindex);
 
diff --git a/src/nvim/ex_session.c b/src/nvim/ex_session.c
index e7837467e4..ddc2705a02 100644
--- a/src/nvim/ex_session.c
+++ b/src/nvim/ex_session.c
@@ -659,9 +659,8 @@ static int makeopens(FILE *fd, char *dirnow)
         && buf->b_fname != NULL
         && buf->b_p_bl) {
       if (fprintf(fd, "badd +%" PRId64 " ",
-                  buf->b_wininfo == NULL
-                  ? 1
-                  : (int64_t)buf->b_wininfo->wi_mark.mark.lnum) < 0
+                  kv_size(buf->b_wininfo) == 0
+                  ? 1 : (int64_t)kv_A(buf->b_wininfo, 0)->wi_mark.mark.lnum) < 0
           || ses_fname(fd, buf, &ssop_flags, true) == FAIL) {
         return FAIL;
       }
diff --git a/src/nvim/globals.h b/src/nvim/globals.h
index 472b77ccbe..a473180349 100644
--- a/src/nvim/globals.h
+++ b/src/nvim/globals.h
@@ -405,9 +405,6 @@ EXTERN buf_T *curbuf INIT( = NULL);    // currently active buffer
 #define FOR_ALL_BUFFERS_BACKWARDS(buf) \
   for (buf_T *buf = lastbuf; buf != NULL; buf = buf->b_prev)
 
-#define FOR_ALL_BUF_WININFO(buf, wip) \
-  for ((wip) = (buf)->b_wininfo; (wip) != NULL; (wip) = (wip)->wi_next)
-
 // List of files being edited (global argument list).  curwin->w_alist points
 // to this when the window is using the global argument list.
 EXTERN alist_T global_alist;    // global argument list
diff --git a/src/nvim/window.c b/src/nvim/window.c
index 1430b2efb2..3eb505d0ce 100644
--- a/src/nvim/window.c
+++ b/src/nvim/window.c
@@ -5163,8 +5163,8 @@ win_T *win_alloc(win_T *after, bool hidden)
   return new_wp;
 }
 
-// Free one wininfo_T.
-void free_wininfo(wininfo_T *wip, buf_T *bp)
+// Free one WinInfo.
+void free_wininfo(WinInfo *wip, buf_T *bp)
 {
   if (wip->wi_optset) {
     clear_winopt(&wip->wi_opt);
@@ -5229,30 +5229,24 @@ void win_free(win_T *wp, tabpage_T *tp)
   // Remove the window from the b_wininfo lists, it may happen that the
   // freed memory is re-used for another window.
   FOR_ALL_BUFFERS(buf) {
-    for (wininfo_T *wip = buf->b_wininfo; wip != NULL; wip = wip->wi_next) {
+    WinInfo *wip_wp = NULL;
+    size_t pos_null = kv_size(buf->b_wininfo);
+    for (size_t i = 0; i < kv_size(buf->b_wininfo); i++) {
+      WinInfo *wip = kv_A(buf->b_wininfo, i);
       if (wip->wi_win == wp) {
-        wininfo_T *wip2;
-
-        // If there already is an entry with "wi_win" set to NULL it
-        // must be removed, it would never be used.
-        // Skip "wip" itself, otherwise Coverity complains.
-        for (wip2 = buf->b_wininfo; wip2 != NULL; wip2 = wip2->wi_next) {
-          // `wip2 != wip` to satisfy Coverity. #14884
-          if (wip2 != wip && wip2->wi_win == NULL) {
-            if (wip2->wi_next != NULL) {
-              wip2->wi_next->wi_prev = wip2->wi_prev;
-            }
-            if (wip2->wi_prev == NULL) {
-              buf->b_wininfo = wip2->wi_next;
-            } else {
-              wip2->wi_prev->wi_next = wip2->wi_next;
-            }
-            free_wininfo(wip2, buf);
-            break;
-          }
-        }
+        wip_wp = wip;
+      } else if (wip->wi_win == NULL) {
+        pos_null = i;
+      }
+    }
 
-        wip->wi_win = NULL;
+    if (wip_wp) {
+      wip_wp->wi_win = NULL;
+      // If there already is an entry with "wi_win" set to NULL it
+      // must be removed, it would never be used.
+      if (pos_null < kv_size(buf->b_wininfo)) {
+        free_wininfo(kv_A(buf->b_wininfo, pos_null), buf);
+        kv_shift(buf->b_wininfo, pos_null, 1);
       }
     }
   }