From 480778b805bd8bdc5d657560230e9c50feda1d0f Mon Sep 17 00:00:00 2001
From: Bram Moolenaar <Bram@vim.org>
Date: Thu, 14 Jul 2016 22:09:39 +0200
Subject: patch 7.4.2036 Problem:    Looking up a buffer by number is slow if
 there are many. Solution:   Use a hashtab.

---
 src/buffer.c  | 48 ++++++++++++++++++++++++++++++++++++++++--------
 src/structs.h |  3 +++
 src/version.c |  2 ++
 3 files changed, 45 insertions(+), 8 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 9511d6159..65ab22fc8 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -349,6 +349,28 @@ buf_valid(buf_T *buf)
     return FALSE;
 }
 
+/*
+ * A hash table used to quickly lookup a buffer by its number.
+ */
+static hashtab_T buf_hashtab;
+
+    static void
+buf_hashtab_add(buf_T *buf)
+{
+    sprintf((char *)buf->b_key, "%x", buf->b_fnum);
+    if (hash_add(&buf_hashtab, buf->b_key) == FAIL)
+	EMSG(_("E931: Buffer cannot be registered"));
+}
+
+    static void
+buf_hashtab_remove(buf_T *buf)
+{
+    hashitem_T *hi = hash_find(&buf_hashtab, buf->b_key);
+
+    if (!HASHITEM_EMPTY(hi))
+	hash_remove(&buf_hashtab, hi);
+}
+
 /*
  * Close the link to a buffer.
  * "action" is used when there is no longer a window for the buffer.
@@ -723,6 +745,9 @@ free_buffer(buf_T *buf)
 #endif
 #ifdef FEAT_AUTOCMD
     aubuflocal_remove(buf);
+
+    buf_hashtab_remove(buf);
+
     if (autocmd_busy)
     {
 	/* Do not free the buffer structure while autocommands are executing,
@@ -1703,6 +1728,8 @@ do_autochdir(void)
  * functions for dealing with the buffer list
  */
 
+static int  top_file_num = 1;		/* highest file number */
+
 /*
  * Add a file name to the buffer list.  Return a pointer to the buffer.
  * If the same file name already exists return a pointer to that buffer.
@@ -1715,8 +1742,6 @@ do_autochdir(void)
  *				    if the buffer already exists.
  * This is the ONLY way to create a new buffer.
  */
-static int  top_file_num = 1;		/* highest file number */
-
     buf_T *
 buflist_new(
     char_u	*ffname,	/* full path of fname or relative */
@@ -1729,6 +1754,9 @@ buflist_new(
     stat_T	st;
 #endif
 
+    if (top_file_num == 1)
+	hash_init(&buf_hashtab);
+
     fname_expand(curbuf, &ffname, &sfname);	/* will allocate ffname */
 
     /*
@@ -1907,6 +1935,7 @@ buflist_new(
 	    }
 	    top_file_num = 1;
 	}
+	buf_hashtab_add(buf);
 
 	/*
 	 * Always copy the options from the current buffer.
@@ -2579,19 +2608,22 @@ fname_match(
 #endif
 
 /*
- * find file in buffer list by number
+ * Find a file in the buffer list by buffer number.
  */
     buf_T *
 buflist_findnr(int nr)
 {
-    buf_T	*buf;
+    char_u	key[VIM_SIZEOF_INT * 2 + 1];
+    hashitem_T	*hi;
 
     if (nr == 0)
 	nr = curwin->w_alt_fnum;
-    /* Assume newer buffers are used more often, start from the end. */
-    for (buf = lastbuf; buf != NULL; buf = buf->b_prev)
-	if (buf->b_fnum == nr)
-	    return buf;
+    sprintf((char *)key, "%x", nr);
+    hi = hash_find(&buf_hashtab, key);
+
+    if (!HASHITEM_EMPTY(hi))
+	return (buf_T *)(hi->hi_key
+			     - ((unsigned)(curbuf->b_key - (char_u *)curbuf)));
     return NULL;
 }
 
diff --git a/src/structs.h b/src/structs.h
index 0cf280061..97e4e97cb 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -1753,6 +1753,9 @@ struct file_buffer
     unsigned int b_fab_mrs;	/* Max record size  */
 #endif
     int		b_fnum;		/* buffer number for this file. */
+    char_u	b_key[VIM_SIZEOF_INT * 2 + 1];
+				/* key used for buf_hashtab, holds b_fnum as
+				   hex string */
 
     int		b_changed;	/* 'modified': Set to TRUE if something in the
 				   file has been changed and not written out. */
diff --git a/src/version.c b/src/version.c
index 0dfb7593b..23a5993ad 100644
--- a/src/version.c
+++ b/src/version.c
@@ -758,6 +758,8 @@ static char *(features[]) =
 
 static int included_patches[] =
 {   /* Add new patch number below this line */
+/**/
+    2036,
 /**/
     2035,
 /**/
-- 
cgit v1.2.1