vim-patch:8.1.0644: finding next sign ID is inefficient

Problem:    Finding next sign ID is inefficient.
Solution:   Add next_sign_id. (Yegappan Lakshmanan, closes vim/vim#3717)
https://github.com/vim/vim/commit/6436cd83f90a0efc326798792e49e8ff96a43dce

7 files changed, 74 insertions, 29 deletions

diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 3ddd2a7163..06207c93f2 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -5257,6 +5257,16 @@ bool find_win_for_buf(buf_T *buf, win_T **wp, tabpage_T **tp)
 }
 
 static hashtab_T	sg_table;	// sign group (signgroup_T) hashtable
+static int		next_sign_id = 1; // next sign id in the global group
+
+/*
+ * Initialize data needed for managing signs
+ */
+    void
+init_signs(void)
+{
+    hash_init(&sg_table);		// sign group hash table
+}
 
 /*
  * A new sign in group 'groupname' is added. If the group is not present,
@@ -5264,16 +5274,10 @@ static hashtab_T	sg_table;	// sign group (signgroup_T) hashtable
  */
 static signgroup_T * sign_group_ref(char_u *groupname)
 {
-  static int		initialized = FALSE;
   hash_T		hash;
   hashitem_T		*hi;
   signgroup_T		*group;
 
-  if (!initialized) {
-    initialized = TRUE;
-    hash_init(&sg_table);
-  }
-
   hash = hash_hash(groupname);
   hi = hash_lookup(&sg_table, S_LEN(groupname), hash);
   if (HASHITEM_EMPTY(hi))
@@ -5285,6 +5289,7 @@ static signgroup_T * sign_group_ref(char_u *groupname)
       return NULL;
     STRCPY(group->sg_name, groupname);
     group->refcount = 1;
+	group->next_sign_id = 1;
     hash_add_item(&sg_table, hi, group->sg_name, hash);
   }
   else
@@ -5321,6 +5326,49 @@ static void sign_group_unref(char_u *groupname)
 }
 
 /*
+ * Get the next free sign identifier in the specified group
+ */
+    int
+sign_group_get_next_signid(buf_T *buf, char_u *groupname)
+{
+    int			id = 1;
+    signgroup_T		*group = NULL;
+    signlist_T		*sign;
+    hashitem_T		*hi;
+    int			found = FALSE;
+
+    if (groupname != NULL)
+    {
+	hi = hash_find(&sg_table, groupname);
+	if (HASHITEM_EMPTY(hi))
+	    return id;
+	group = HI2SG(hi);
+    }
+
+    // Search for the next usuable sign identifier
+    while (!found)
+    {
+	if (group == NULL)
+	    id = next_sign_id++;		// global group
+	else
+	    id = group->next_sign_id++;
+
+	// Check whether this sign is already placed in the buffer
+	found = TRUE;
+	FOR_ALL_SIGNS_IN_BUF(buf, sign)
+	{
+	    if (id == sign->id && sign_in_group(sign, groupname))
+	    {
+		found = FALSE;		// sign identifier is in use
+		break;
+	    }
+	}
+    }
+
+    return id;
+}
+
+/*
  * Insert a new sign into the signlist for buffer 'buf' between the 'prev' and
  * 'next' signs.
  */
@@ -5542,7 +5590,7 @@ void buf_addsign(
     signlist_T *prev;    // the previous sign
 
     prev = NULL;
-    FOR_ALL_SIGNS_IN_BUF(buf) {
+    FOR_ALL_SIGNS_IN_BUF(buf, sign) {
         if (lnum == sign->lnum && id == sign->id &&
             sign_in_group(sign, groupname)) {
           // Update an existing sign
@@ -5583,7 +5631,7 @@ linenr_T buf_change_sign_type(
 {
     signlist_T *sign;  // a sign in the signlist
 
-    FOR_ALL_SIGNS_IN_BUF(buf) {
+    FOR_ALL_SIGNS_IN_BUF(buf, sign) {
         if (sign->id == markId && sign_in_group(sign, group)) {
             sign->typenr = typenr;
             return sign->lnum;
@@ -5611,7 +5659,7 @@ int buf_getsigntype(buf_T *buf, linenr_T lnum, SignType type,
     signlist_T *matches[9];
     int nr_matches = 0;
 
-    FOR_ALL_SIGNS_IN_BUF(buf) {
+    FOR_ALL_SIGNS_IN_BUF(buf, sign) {
         if (sign->lnum == lnum
                 && (type == SIGN_ANY
                     || (type == SIGN_TEXT
@@ -5711,7 +5759,7 @@ int buf_findsign(
 {
     signlist_T *sign;  // a sign in the signlist
 
-    FOR_ALL_SIGNS_IN_BUF(buf) {
+    FOR_ALL_SIGNS_IN_BUF(buf, sign) {
         if (sign->id == id && sign_in_group(sign, group)){
             return (int)sign->lnum;
         }
@@ -5731,7 +5779,7 @@ static signlist_T * buf_getsign_at_line(
 {
   signlist_T	*sign;		// a sign in the signlist
 
-  FOR_ALL_SIGNS_IN_BUF(buf) {
+  FOR_ALL_SIGNS_IN_BUF(buf, sign) {
     if (sign->lnum == lnum) {
       return sign;
     }
@@ -5751,7 +5799,7 @@ signlist_T *buf_getsign_with_id(
 {
   signlist_T	*sign;		// a sign in the signlist
 
-  FOR_ALL_SIGNS_IN_BUF(buf) {
+  FOR_ALL_SIGNS_IN_BUF(buf, sign) {
     if (sign->id == id && sign_in_group(sign, group)) {
       return sign;
     }
@@ -5849,7 +5897,7 @@ void sign_list_placed(buf_T *rbuf, char_u *sign_group)
             MSG_PUTS_ATTR(lbuf, HL_ATTR(HLF_D));
             msg_putchar('\n');
         }
-        FOR_ALL_SIGNS_IN_BUF(buf) {
+        FOR_ALL_SIGNS_IN_BUF(buf, sign) {
           if (got_int) {
             break;
           }
@@ -5887,7 +5935,7 @@ void sign_mark_adjust(linenr_T line1, linenr_T line2, long amount, long amount_a
     curbuf->b_signcols_max = -1;
     lastp = &curbuf->b_signlist;
 
-    FOR_ALL_SIGNS_IN_BUF(curbuf) {
+    FOR_ALL_SIGNS_IN_BUF(curbuf, sign) {
         next = sign->next;
         if (sign->lnum >= line1 && sign->lnum <= line2) {
             if (amount == MAXLNUM) {
diff --git a/src/nvim/eval.c b/src/nvim/eval.c
index b276b570b2..de2c9168c2 100644
--- a/src/nvim/eval.c
+++ b/src/nvim/eval.c
@@ -9294,7 +9294,7 @@ static list_T *get_buffer_signs(buf_T *buf)
   dict_T	*d;
   list_T *const l = tv_list_alloc(kListLenMayKnow);
 
-  FOR_ALL_SIGNS_IN_BUF(buf) {
+  FOR_ALL_SIGNS_IN_BUF(buf, sign) {
     if ((d = sign_get_info(sign)) != NULL) {
       tv_list_append_dict(l, d);
     }
@@ -15558,6 +15558,8 @@ f_sign_getplaced(typval_T *argvars, typval_T *rettv)
 		group = tv_get_string_chk(&di->di_tv);
 		if (group == NULL)
 		    return;
+		if (*group == '\0')	// empty string means global group
+		    group = NULL;
 	    }
 	}
     }
diff --git a/src/nvim/ex_cmds.c b/src/nvim/ex_cmds.c
index 82b16a721e..abfa9ad2e5 100644
--- a/src/nvim/ex_cmds.c
+++ b/src/nvim/ex_cmds.c
@@ -5803,15 +5803,7 @@ int sign_place(
   }
   if (*sign_id == 0)
   {
-    // Allocate a new sign id
-    int		id = 1;
-    signlist_T	*sign;
-
-    while ((sign = buf_getsign_with_id(buf, id, sign_group)) != NULL) {
-      id++;
-    }
-
-    *sign_id = id;
+    *sign_id = sign_group_get_next_signid(buf, sign_group);
   }
 
   if (lnum > 0) {
@@ -6083,7 +6075,7 @@ void ex_sign(exarg_T *eap)
       }
     } else if (idx == SIGNCMD_JUMP) {
       // ":sign jump {id} file={fname}"
-      if (lnum >= 0 || sign_name != NULL) {
+      if (lnum >= 0 || sign_name != NULL || buf == NULL){
         EMSG(_(e_invarg));
       } else if ((lnum = buf_findsign(buf, id, group)) > 0) {
         // goto a sign ...
@@ -6244,7 +6236,7 @@ static void sign_get_placed_in_buf(
   }
   tv_dict_add_list(d, S_LEN("signs"), l);
 
-  FOR_ALL_SIGNS_IN_BUF(buf) {
+  FOR_ALL_SIGNS_IN_BUF(buf, sign) {
     if (!sign_in_group(sign, sign_group)) {
       continue;
     }
diff --git a/src/nvim/globals.h b/src/nvim/globals.h
index 9890cba637..8a6f0accda 100644
--- a/src/nvim/globals.h
+++ b/src/nvim/globals.h
@@ -483,7 +483,7 @@ EXTERN buf_T    *curbuf INIT(= NULL);    // currently active buffer
   for (buf_T *buf = lastbuf; buf != NULL; buf = buf->b_prev)
 
 // Iterate through all the signs placed in a buffer
-#define FOR_ALL_SIGNS_IN_BUF(buf) \
+#define FOR_ALL_SIGNS_IN_BUF(buf, sign) \
 	for (sign = buf->b_signlist; sign != NULL; sign = sign->next)
 
 
diff --git a/src/nvim/main.c b/src/nvim/main.c
index 4e1c7dff57..93b31d684e 100644
--- a/src/nvim/main.c
+++ b/src/nvim/main.c
@@ -1337,6 +1337,8 @@ static void init_path(const char *exename)
   // shipped with Windows package. This also mimics SearchPath().
   os_setenv_append_path(exepath);
 #endif
+
+    init_signs();
 }
 
 /// Get filename from command line, if any.
diff --git a/src/nvim/sign_defs.h b/src/nvim/sign_defs.h
index e3028a80ba..e9c2312ae9 100644
--- a/src/nvim/sign_defs.h
+++ b/src/nvim/sign_defs.h
@@ -9,6 +9,7 @@
 typedef struct signgroup_S
 {
     uint16_t	refcount;		// number of signs in this group
+    int next_sign_id;     // next sign id for this group
     char_u	sg_name[1];		// sign group name
 } signgroup_T;
 
diff --git a/src/nvim/testdir/test_signs.vim b/src/nvim/testdir/test_signs.vim
index a0acc54b5b..b745ee04bd 100644
--- a/src/nvim/testdir/test_signs.vim
+++ b/src/nvim/testdir/test_signs.vim
@@ -301,7 +301,7 @@ func Test_sign_delete_buffer()
   sign undefine Sign
 endfunc
 
-" Test for VimL functions for managing signs
+" Test for Vim script functions for managing signs
 func Test_sign_funcs()
   " Remove all the signs
   call sign_unplace('*')
@@ -733,7 +733,7 @@ func Test_sign_id_autogen()
   call assert_equal(3, sign_place(0, '', 'sign1', 'Xsign',
 	      \ {'lnum' : 14}))
   call sign_unplace('', {'buffer' : 'Xsign', 'id' : 2})
-  call assert_equal(2, sign_place(0, '', 'sign1', 'Xsign',
+  call assert_equal(4, sign_place(0, '', 'sign1', 'Xsign',
 	      \ {'lnum' : 12}))
 
   call assert_equal(1, sign_place(0, 'g1', 'sign1', 'Xsign',