Fix O(n^2) in emacs-27/inotify support. This speedups LSP on big repositories.

inotify.patch

diff --git a/src/inotify.c b/src/inotify.c
index 549a82b401..50ba2fab9f 100644
--- a/src/inotify.c
+++ b/src/inotify.c
@@ -202,18 +202,25 @@ add_watch (int wd, Lisp_Object filename,
 	   uint32_t imask, Lisp_Object callback)
 {
   Lisp_Object descriptor = INT_TO_INTEGER (wd);
-  Lisp_Object tail = assoc_no_quit (descriptor, watch_list);
+  Lisp_Object tail;
   Lisp_Object watch, watch_id;
   Lisp_Object mask = INT_TO_INTEGER (imask);
 
+  struct Lisp_Hash_Table *h = XHASH_TABLE (watch_list);
+  Lisp_Object hash;
+  ptrdiff_t j = hash_lookup (h, descriptor, &hash);
+
   EMACS_INT id = 0;
-  if (NILP (tail))
+  if (j < 0)
     {
       tail = list1 (descriptor);
-      watch_list = Fcons (tail, watch_list);
+      hash_put (h, descriptor, tail, hash);
     }
   else
     {
+      tail = HASH_VALUE (h, j);
+      if (!EQ (XCAR (tail), descriptor))
+        emacs_abort();
       /* Assign a watch ID that is not already in use, by looking
 	 for a gap in the existing sorted list.  */
       for (; ! NILP (XCDR (tail)); tail = XCDR (tail), id++)
@@ -233,58 +240,35 @@ add_watch (int wd, Lisp_Object filename,
   return Fcons (descriptor, watch_id);
 }
 
-/* Find the watch list element (if any) matching DESCRIPTOR.  Return
-   nil if not found.  If found, return t if the first element matches
-   DESCRIPTOR; otherwise, return the cons whose cdr matches
-   DESCRIPTOR.  This lets the caller easily remove the element
-   matching DESCRIPTOR without having to search for it again, and
-   without calling Fdelete (which might quit).  */
-
-static Lisp_Object
-find_descriptor (Lisp_Object descriptor)
-{
-  Lisp_Object tail, prevtail = Qt;
-  for (tail = watch_list; !NILP (tail); prevtail = tail, tail = XCDR (tail))
-    if (equal_no_quit (XCAR (XCAR (tail)), descriptor))
-      return prevtail;
-  return Qnil;
-}
-
-/*  Remove all watches associated with the watch list element after
-    PREVTAIL, or after the first element if PREVTAIL is t.  If INVALID_P
-    is true, the descriptor is already invalid, i.e., it received a
+/*  Remove all watches associated with the descriptor. If INVALID_P is
+    true, the descriptor is already invalid, i.e., it received a
     IN_IGNORED event.  In this case skip calling inotify_rm_watch.  */
 static void
-remove_descriptor (Lisp_Object prevtail, bool invalid_p)
+remove_descriptor (Lisp_Object descriptor, bool invalid_p)
 {
-  Lisp_Object tail = CONSP (prevtail) ? XCDR (prevtail) : watch_list;
-
   int inotify_errno = 0;
   if (! invalid_p)
     {
       int wd;
-      CONS_TO_INTEGER (XCAR (XCAR (tail)), int, wd);
+      CONS_TO_INTEGER (descriptor, int, wd);
       if (inotify_rm_watch (inotifyfd, wd) != 0)
 	inotify_errno = errno;
     }
 
-  if (CONSP (prevtail))
-    XSETCDR (prevtail, XCDR (tail));
-  else
+  struct Lisp_Hash_Table *h = XHASH_TABLE (watch_list);
+
+  hash_remove_from_table(h, descriptor);
+  if (HASH_TABLE_SIZE (h) == 0)
     {
-      watch_list = XCDR (tail);
-      if (NILP (watch_list))
-	{
-	  delete_read_fd (inotifyfd);
-	  emacs_close (inotifyfd);
-	  inotifyfd = -1;
-	}
+      delete_read_fd (inotifyfd);
+      emacs_close (inotifyfd);
+      inotifyfd = -1;
     }
 
   if (inotify_errno != 0)
     {
       errno = inotify_errno;
-      report_file_notify_error ("Could not rm watch", XCAR (tail));
+      report_file_notify_error ("Could not rm watch", descriptor);
     }
 }
 
@@ -292,17 +276,19 @@ remove_descriptor (Lisp_Object prevtail, bool invalid_p)
 static void
 remove_watch (Lisp_Object descriptor, Lisp_Object id)
 {
-  Lisp_Object prevtail = find_descriptor (descriptor);
-  if (NILP (prevtail))
+  struct Lisp_Hash_Table *h = XHASH_TABLE (watch_list);
+  ptrdiff_t j = hash_lookup (h, descriptor, NULL);
+  if (j < 0)
     return;
 
-  Lisp_Object elt = XCAR (CONSP (prevtail) ? XCDR (prevtail) : watch_list);
+  Lisp_Object elt = HASH_VALUE (h, j);
+
   for (Lisp_Object prev = elt; !NILP (XCDR (prev)); prev = XCDR (prev))
     if (EQ (id, XCAR (XCAR (XCDR (prev)))))
       {
 	XSETCDR (prev, XCDR (XCDR (prev)));
 	if (NILP (XCDR (elt)))
-	  remove_descriptor (prevtail, false);
+	  remove_descriptor (descriptor, false);
 	break;
       }
 }
@@ -330,12 +316,13 @@ inotify_callback (int fd, void *_)
     {
       struct inotify_event *ev = (struct inotify_event *) &buffer[i];
       Lisp_Object descriptor = INT_TO_INTEGER (ev->wd);
-      Lisp_Object prevtail = find_descriptor (descriptor);
+      struct Lisp_Hash_Table *h = XHASH_TABLE (watch_list);
+      ptrdiff_t j = hash_lookup (h, descriptor, NULL);
 
-      if (! NILP (prevtail))
+      if (j >= 0)
         {
-	  Lisp_Object tail = CONSP (prevtail) ? XCDR (prevtail) : watch_list;
-	  for (Lisp_Object watches = XCDR (XCAR (tail)); ! NILP (watches);
+          Lisp_Object elt = HASH_VALUE (h, j);
+	  for (Lisp_Object watches = XCDR (elt); ! NILP (watches);
 	       watches = XCDR (watches))
             {
               event.arg = inotifyevent_to_event (XCAR (watches), ev);
@@ -344,7 +331,7 @@ inotify_callback (int fd, void *_)
             }
           /* If event was removed automatically: Drop it from watch list.  */
           if (ev->mask & IN_IGNORED)
-	    remove_descriptor (prevtail, true);
+	    remove_descriptor (descriptor, true);
         }
       i += sizeof (*ev) + ev->len;
     }
@@ -431,6 +418,9 @@ renames (moved-from and moved-to).
       add_read_fd (inotifyfd, &inotify_callback, NULL);
     }
 
+  watch_list = make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE,
+                                DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
+                                Qnil, false);
   encoded_file_name = ENCODE_FILE (filename);
   wd = inotify_add_watch (inotifyfd, SSDATA (encoded_file_name), mask);
   if (wd < 0)
@@ -442,7 +432,8 @@ renames (moved-from and moved-to).
 static bool
 valid_watch_descriptor (Lisp_Object wd)
 {
-  return (CONSP (wd)
+  return (!NILP (watch_list)
+          && CONSP (wd)
 	  && (RANGED_FIXNUMP (0, XCAR (wd), INT_MAX)
 	      || (CONSP (XCAR (wd))
 		  && RANGED_FIXNUMP ((MOST_POSITIVE_FIXNUM >> 16) + 1,
@@ -485,10 +476,11 @@ DEFUN ("inotify-valid-p", Finotify_valid_p, Sinotify_valid_p, 1, 1, 0,
 {
   if (! valid_watch_descriptor (watch_descriptor))
     return Qnil;
-  Lisp_Object tail = assoc_no_quit (XCAR (watch_descriptor), watch_list);
-  if (NILP (tail))
+  struct Lisp_Hash_Table *h = XHASH_TABLE (watch_list);
+  ptrdiff_t j = hash_lookup (h, XCAR (watch_descriptor), NULL);
+  if (j < 0)
     return Qnil;
-  Lisp_Object watch = assq_no_quit (XCDR (watch_descriptor), XCDR (tail));
+  Lisp_Object watch = assq_no_quit (XCDR (watch_descriptor), HASH_VALUE (h, j));
   return ! NILP (watch) ? Qt : Qnil;
 }