# HG changeset patch
# User Bram Moolenaar <Bram@vim.org>
# Date 1545867006 -3600
# Node ID a6319aca721b551e62dda2f617c320a4f903c82c
# Parent  18c956b49ee56660833534d027abafdbae6d0a8e
patch 8.1.0644: finding next sign ID is inefficient

commit https://github.com/vim/vim/commit/6436cd83f90a0efc326798792e49e8ff96a43dce
Author: Bram Moolenaar <Bram@vim.org>
Date:   Thu Dec 27 00:28:33 2018 +0100

    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 https://github.com/vim/vim/issues/3717)

diff --git a/runtime/doc/eval.txt b/runtime/doc/eval.txt
--- a/runtime/doc/eval.txt
+++ b/runtime/doc/eval.txt
@@ -7936,10 +7936,10 @@ sign_getplaced([{expr} [, {dict}]])			*s
 			lnum	select signs placed in this line. For the use
 				of {lnum}, see |line()|.
 		If {group} is '*', then signs in all the groups including the
-		global group are returned. If {group} is not supplied, then
-		only signs in the global group are returned.  If no arguments
-		are supplied, then signs in the global group placed in all the
-		buffers are returned.
+		global group are returned. If {group} is not supplied or is an
+		empty string, then only signs in the global group are
+		returned.  If no arguments are supplied, then signs in the
+		global group placed in all the buffers are returned.
 
 		Each list item in the returned value is a dictionary with the
 		following entries:
diff --git a/src/buffer.c b/src/buffer.c
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -5866,6 +5866,16 @@ win_found:
 
 #if defined(FEAT_SIGNS) || defined(PROTO)
 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,
@@ -5874,17 +5884,10 @@ static hashtab_T	sg_table;	// sign group
     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, groupname, hash);
     if (HASHITEM_EMPTY(hi))
@@ -5896,6 +5899,7 @@ 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
@@ -5933,6 +5937,49 @@ 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.
  */
@@ -6072,7 +6119,7 @@ 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))
@@ -6107,7 +6154,7 @@ 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))
 	{
@@ -6132,7 +6179,7 @@ buf_getsigntype(
 {
     signlist_T	*sign;		/* a sign in a b_signlist */
 
-    FOR_ALL_SIGNS_IN_BUF(buf)
+    FOR_ALL_SIGNS_IN_BUF(buf, sign)
 	if (sign->lnum == lnum
 		&& (type == SIGN_ANY
 # ifdef FEAT_SIGN_ICONS
@@ -6216,7 +6263,7 @@ 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 sign->lnum;
 
@@ -6234,7 +6281,7 @@ 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;
 
@@ -6252,7 +6299,7 @@ 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;
 
@@ -6288,7 +6335,7 @@ buf_findsigntype_id(
 {
     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 && sign->typenr == typenr)
 	    return sign->id;
 
@@ -6306,7 +6353,7 @@ buf_signcount(buf_T *buf, linenr_T lnum)
     signlist_T	*sign;		// a sign in the signlist
     int		count = 0;
 
-    FOR_ALL_SIGNS_IN_BUF(buf)
+    FOR_ALL_SIGNS_IN_BUF(buf, sign)
 	if (sign->lnum == lnum)
 	    if (sign_get_image(sign->typenr) != NULL)
 		count++;
@@ -6391,7 +6438,7 @@ sign_list_placed(buf_T *rbuf, char_u *si
 	    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;
@@ -6427,7 +6474,7 @@ sign_mark_adjust(
 {
     signlist_T	*sign;		/* a sign in a b_signlist */
 
-    FOR_ALL_SIGNS_IN_BUF(curbuf)
+    FOR_ALL_SIGNS_IN_BUF(curbuf, sign)
     {
 	if (sign->lnum >= line1 && sign->lnum <= line2)
 	{
diff --git a/src/evalfunc.c b/src/evalfunc.c
--- a/src/evalfunc.c
+++ b/src/evalfunc.c
@@ -4434,7 +4434,7 @@ get_buffer_signs(buf_T *buf, list_T *l)
     signlist_T	*sign;
     dict_T	*d;
 
-    FOR_ALL_SIGNS_IN_BUF(buf)
+    FOR_ALL_SIGNS_IN_BUF(buf, sign)
     {
 	if ((d = sign_get_info(sign)) != NULL)
 	    list_append_dict(l, d);
@@ -11415,6 +11415,8 @@ f_sign_getplaced(typval_T *argvars, typv
 		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/ex_cmds.c b/src/ex_cmds.c
--- a/src/ex_cmds.c
+++ b/src/ex_cmds.c
@@ -7871,16 +7871,7 @@ sign_place(
 	return FAIL;
     }
     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)
 	// ":sign place {id} line={lnum} name={name} file={fname}":
@@ -8193,7 +8184,7 @@ 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 ... */
@@ -8350,7 +8341,7 @@ sign_get_placed_in_buf(
 	return;
     dict_add_list(d, "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/globals.h b/src/globals.h
--- a/src/globals.h
+++ b/src/globals.h
@@ -609,7 +609,7 @@ EXTERN buf_T	*curbuf INIT(= NULL);	/* cu
 #define FOR_ALL_BUFFERS(buf) for (buf = firstbuf; buf != NULL; buf = buf->b_next)
 
 // 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)
 
 /* Flag that is set when switching off 'swapfile'.  It means that all blocks
diff --git a/src/main.c b/src/main.c
--- a/src/main.c
+++ b/src/main.c
@@ -1032,6 +1032,10 @@ common_init(mparm_T *paramp)
 #ifdef FEAT_EVAL
     set_lang_var();		/* set v:lang and v:ctype */
 #endif
+
+#ifdef FEAT_SIGNS
+    init_signs();
+#endif
 }
 
 /*
diff --git a/src/proto/buffer.pro b/src/proto/buffer.pro
--- a/src/proto/buffer.pro
+++ b/src/proto/buffer.pro
@@ -75,6 +75,8 @@ int buf_getsigntype(buf_T *buf, linenr_T
 linenr_T buf_delsign(buf_T *buf, int id, char_u *group);
 int buf_findsign(buf_T *buf, int id, char_u *group);
 #ifdef FEAT_SIGNS
+void init_signs(void);
+int sign_group_get_next_signid(buf_T *buf, char_u *groupname);
 int sign_in_group(signlist_T *sign, char_u *group);
 dict_T *sign_get_info(signlist_T *sign);
 signlist_T *buf_getsign_with_id(buf_T *buf, int id, char_u *group);
diff --git a/src/structs.h b/src/structs.h
--- a/src/structs.h
+++ b/src/structs.h
@@ -737,6 +737,7 @@ typedef struct proptype_S
 typedef struct signgroup_S
 {
     short_u	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/testdir/test_signs.vim b/src/testdir/test_signs.vim
--- a/src/testdir/test_signs.vim
+++ b/src/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',
diff --git a/src/version.c b/src/version.c
--- a/src/version.c
+++ b/src/version.c
@@ -800,6 +800,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    644,
+/**/
     643,
 /**/
     642,