Merge pull request #24875 from bfredl/memfilemap

refactor(memfile): change mf_trans and mf_hash from ad-hoc hashtable to Map

9 files changed, 73 insertions, 321 deletions

diff --git a/src/nvim/bufwrite.c b/src/nvim/bufwrite.c
index 2796ed1f0b..445e946543 100644
--- a/src/nvim/bufwrite.c
+++ b/src/nvim/bufwrite.c
@@ -1402,7 +1402,7 @@ int buf_write(buf_T *buf, char *fname, char *sfname, linenr_T start, linenr_T en
       while ((fd = os_open(wfname, fflags, mode)) < 0) {
         // A forced write will try to create a new file if the old one
         // is still readonly. This may also happen when the directory
-        // is read-only. In that case the mch_remove() will fail.
+        // is read-only. In that case the os_remove() will fail.
         if (err.msg == NULL) {
 #ifdef UNIX
           FileInfo file_info;
diff --git a/src/nvim/macros.h b/src/nvim/macros.h
index 57cb298572..5eaf97ff87 100644
--- a/src/nvim/macros.h
+++ b/src/nvim/macros.h
@@ -82,15 +82,6 @@
 #define READBIN    "rb"
 #define APPENDBIN  "ab"
 
-// mch_open_rw(): invoke os_open() with third argument for user R/W.
-#if defined(UNIX)  // open in rw------- mode
-# define MCH_OPEN_RW(n, f)      os_open((n), (f), (mode_t)0600)
-#elif defined(MSWIN)
-# define MCH_OPEN_RW(n, f)      os_open((n), (f), S_IREAD | S_IWRITE)
-#else
-# define MCH_OPEN_RW(n, f)      os_open((n), (f), 0)
-#endif
-
 #define REPLACE_NORMAL(s) (((s)& REPLACE_FLAG) && !((s)& VREPLACE_FLAG))
 
 // MB_PTR_ADV(): advance a pointer to the next character, taking care of
diff --git a/src/nvim/map.c b/src/nvim/map.c
index e2c6443245..33a7759a1b 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -25,6 +25,8 @@
 #define equal_uint32_t equal_simple
 #define hash_int(x) hash_uint32_t((uint32_t)(x))
 #define equal_int equal_simple
+#define hash_int64_t(key) hash_uint64_t((uint64_t)key)
+#define equal_int64_t equal_simple
 
 #if defined(ARCH_64)
 # define hash_ptr_t(key) hash_uint64_t((uint64_t)(key))
@@ -182,6 +184,16 @@ void mh_clear(MapHash *h)
 #undef VAL_NAME
 #undef KEY_NAME
 
+#define KEY_NAME(x) x##int64_t
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, int64_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
 #define KEY_NAME(x) x##HlEntry
 #include "nvim/map_key_impl.c.h"
 #define VAL_NAME(x) quasiquote(x, int)
diff --git a/src/nvim/map.h b/src/nvim/map.h
index a84d533262..bfba014736 100644
--- a/src/nvim/map.h
+++ b/src/nvim/map.h
@@ -27,6 +27,7 @@ static const ptr_t value_init_ptr_t = NULL;
 static const ssize_t value_init_ssize_t = -1;
 static const uint32_t value_init_uint32_t = 0;
 static const uint64_t value_init_uint64_t = 0;
+static const int64_t value_init_int64_t = 0;
 static const String value_init_String = STRING_INIT;
 static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER;
 
@@ -123,6 +124,7 @@ KEY_DECLS(int)
 KEY_DECLS(cstr_t)
 KEY_DECLS(ptr_t)
 KEY_DECLS(uint64_t)
+KEY_DECLS(int64_t)
 KEY_DECLS(uint32_t)
 KEY_DECLS(String)
 KEY_DECLS(HlEntry)
@@ -137,6 +139,8 @@ MAP_DECLS(uint32_t, ptr_t)
 MAP_DECLS(uint64_t, ptr_t)
 MAP_DECLS(uint64_t, ssize_t)
 MAP_DECLS(uint64_t, uint64_t)
+MAP_DECLS(int64_t, int64_t)
+MAP_DECLS(int64_t, ptr_t)
 MAP_DECLS(uint32_t, uint32_t)
 MAP_DECLS(HlEntry, int)
 MAP_DECLS(String, int)
diff --git a/src/nvim/memfile.c b/src/nvim/memfile.c
index 333ff75f7b..6722d6bd8a 100644
--- a/src/nvim/memfile.c
+++ b/src/nvim/memfile.c
@@ -101,11 +101,9 @@ memfile_T *mf_open(char *fname, int flags)
   }
 
   mfp->mf_free_first = NULL;         // free list is empty
-  mfp->mf_used_first = NULL;         // used list is empty
-  mfp->mf_used_last = NULL;
   mfp->mf_dirty = MF_DIRTY_NO;
-  mf_hash_init(&mfp->mf_hash);
-  mf_hash_init(&mfp->mf_trans);
+  mfp->mf_hash = (PMap(int64_t)) MAP_INIT;
+  mfp->mf_trans = (Map(int64_t, int64_t)) MAP_INIT;
   mfp->mf_page_size = MEMFILE_PAGE_SIZE;
 
   // Try to set the page size equal to device's block size. Speeds up I/O a lot.
@@ -182,15 +180,15 @@ void mf_close(memfile_T *mfp, bool del_file)
   }
 
   // free entries in used list
-  for (bhdr_T *hp = mfp->mf_used_first, *nextp; hp != NULL; hp = nextp) {
-    nextp = hp->bh_next;
+  bhdr_T *hp;
+  map_foreach_value(&mfp->mf_hash, hp, {
     mf_free_bhdr(hp);
-  }
+  })
   while (mfp->mf_free_first != NULL) {  // free entries in free list
     xfree(mf_rem_free(mfp));
   }
-  mf_hash_free(&mfp->mf_hash);
-  mf_hash_free_all(&mfp->mf_trans);     // free hashtable and its items
+  map_destroy(int64_t, &mfp->mf_hash);
+  map_destroy(int64_t, &mfp->mf_trans);  // free hashtable and its items
   mf_free_fnames(mfp);
   xfree(mfp);
 }
@@ -271,8 +269,7 @@ bhdr_T *mf_new(memfile_T *mfp, bool negative, unsigned page_count)
   hp->bh_flags = BH_LOCKED | BH_DIRTY;    // new block is always dirty
   mfp->mf_dirty = MF_DIRTY_YES;
   hp->bh_page_count = page_count;
-  mf_ins_used(mfp, hp);
-  mf_ins_hash(mfp, hp);
+  pmap_put(int64_t)(&mfp->mf_hash, hp->bh_bnum, hp);
 
   // Init the data to all zero, to avoid reading uninitialized data.
   // This also avoids that the passwd file ends up in the swap file!
@@ -294,7 +291,7 @@ bhdr_T *mf_get(memfile_T *mfp, blocknr_T nr, unsigned page_count)
   }
 
   // see if it is in the cache
-  bhdr_T *hp = mf_find_hash(mfp, nr);
+  bhdr_T *hp = pmap_get(int64_t)(&mfp->mf_hash, nr);
   if (hp == NULL) {                             // not in the hash list
     if (nr < 0 || nr >= mfp->mf_infile_count) {  // can't be in the file
       return NULL;
@@ -317,13 +314,11 @@ bhdr_T *mf_get(memfile_T *mfp, blocknr_T nr, unsigned page_count)
       return NULL;
     }
   } else {
-    mf_rem_used(mfp, hp);       // remove from list, insert in front below
-    mf_rem_hash(mfp, hp);
+    pmap_del(int64_t)(&mfp->mf_hash, hp->bh_bnum, NULL);
   }
 
   hp->bh_flags |= BH_LOCKED;
-  mf_ins_used(mfp, hp);         // put in front of used list
-  mf_ins_hash(mfp, hp);         // put in front of hash list
+  pmap_put(int64_t)(&mfp->mf_hash, hp->bh_bnum, hp);  // put in front of hash table
 
   return hp;
 }
@@ -356,8 +351,7 @@ void mf_put(memfile_T *mfp, bhdr_T *hp, bool dirty, bool infile)
 void mf_free(memfile_T *mfp, bhdr_T *hp)
 {
   xfree(hp->bh_data);           // free data
-  mf_rem_hash(mfp, hp);         // get *hp out of the hash list
-  mf_rem_used(mfp, hp);         // get *hp out of the used list
+  pmap_del(int64_t)(&mfp->mf_hash, hp->bh_bnum, NULL);  // get *hp out of the hash table
   if (hp->bh_bnum < 0) {
     xfree(hp);                  // don't want negative numbers in free list
     mfp->mf_neg_count--;
@@ -399,7 +393,8 @@ int mf_sync(memfile_T *mfp, int flags)
   // fails then we give up.
   int status = OK;
   bhdr_T *hp;
-  for (hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) {
+  // note, "last" block is typically earlier in the hash list
+  map_foreach_value(&mfp->mf_hash, hp, {
     if (((flags & MFS_ALL) || hp->bh_bnum >= 0)
         && (hp->bh_flags & BH_DIRTY)
         && (status == OK || (hp->bh_bnum >= 0
@@ -424,7 +419,7 @@ int mf_sync(memfile_T *mfp, int flags)
         break;
       }
     }
-  }
+  })
 
   // If the whole list is flushed, the memfile is not dirty anymore.
   // In case of an error, dirty flag is also set, to avoid trying all the time.
@@ -447,61 +442,15 @@ int mf_sync(memfile_T *mfp, int flags)
 /// These are blocks that need to be written to a newly created swapfile.
 void mf_set_dirty(memfile_T *mfp)
 {
-  for (bhdr_T *hp = mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) {
+  bhdr_T *hp;
+  map_foreach_value(&mfp->mf_hash, hp, {
     if (hp->bh_bnum > 0) {
       hp->bh_flags |= BH_DIRTY;
     }
-  }
+  })
   mfp->mf_dirty = MF_DIRTY_YES;
 }
 
-/// Insert block in front of memfile's hash list.
-static void mf_ins_hash(memfile_T *mfp, bhdr_T *hp)
-{
-  mf_hash_add_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
-}
-
-/// Remove block from memfile's hash list.
-static void mf_rem_hash(memfile_T *mfp, bhdr_T *hp)
-{
-  mf_hash_rem_item(&mfp->mf_hash, (mf_hashitem_T *)hp);
-}
-
-/// Lookup block with number "nr" in memfile's hash list.
-static bhdr_T *mf_find_hash(memfile_T *mfp, blocknr_T nr)
-{
-  return (bhdr_T *)mf_hash_find(&mfp->mf_hash, nr);
-}
-
-/// Insert block at the front of memfile's used list.
-static void mf_ins_used(memfile_T *mfp, bhdr_T *hp)
-{
-  hp->bh_next = mfp->mf_used_first;
-  mfp->mf_used_first = hp;
-  hp->bh_prev = NULL;
-  if (hp->bh_next == NULL) {    // list was empty, adjust last pointer
-    mfp->mf_used_last = hp;
-  } else {
-    hp->bh_next->bh_prev = hp;
-  }
-}
-
-/// Remove block from memfile's used list.
-static void mf_rem_used(memfile_T *mfp, bhdr_T *hp)
-{
-  if (hp->bh_next == NULL) {               // last block in used list
-    mfp->mf_used_last = hp->bh_prev;
-  } else {
-    hp->bh_next->bh_prev = hp->bh_prev;
-  }
-
-  if (hp->bh_prev == NULL) {               // first block in used list
-    mfp->mf_used_first = hp->bh_next;
-  } else {
-    hp->bh_prev->bh_next = hp->bh_next;
-  }
-}
-
 /// Release as many blocks as possible.
 ///
 /// Used in case of out of memory
@@ -520,17 +469,18 @@ bool mf_release_all(void)
 
       // Flush as many blocks as possible, only if there is a swapfile.
       if (mfp->mf_fd >= 0) {
-        for (bhdr_T *hp = mfp->mf_used_last; hp != NULL;) {
+        for (int i = 0; i < (int)map_size(&mfp->mf_hash);) {
+          bhdr_T *hp = mfp->mf_hash.values[i];
           if (!(hp->bh_flags & BH_LOCKED)
               && (!(hp->bh_flags & BH_DIRTY)
                   || mf_write(mfp, hp) != FAIL)) {
-            mf_rem_used(mfp, hp);
-            mf_rem_hash(mfp, hp);
+            pmap_del(int64_t)(&mfp->mf_hash, hp->bh_bnum, NULL);
             mf_free_bhdr(hp);
-            hp = mfp->mf_used_last;    // restart, list was changed
             retval = true;
+            // Rerun with the same value of i. another item will have taken
+            // its place (or it was the last)
           } else {
-            hp = hp->bh_prev;
+            i++;
           }
         }
       }
@@ -558,7 +508,7 @@ static void mf_free_bhdr(bhdr_T *hp)
 /// Insert a block in the free list.
 static void mf_ins_free(memfile_T *mfp, bhdr_T *hp)
 {
-  hp->bh_next = mfp->mf_free_first;
+  hp->bh_data = mfp->mf_free_first;
   mfp->mf_free_first = hp;
 }
 
@@ -568,7 +518,7 @@ static void mf_ins_free(memfile_T *mfp, bhdr_T *hp)
 static bhdr_T *mf_rem_free(memfile_T *mfp)
 {
   bhdr_T *hp = mfp->mf_free_first;
-  mfp->mf_free_first = hp->bh_next;
+  mfp->mf_free_first = hp->bh_data;
   return hp;
 }
 
@@ -637,7 +587,7 @@ static int mf_write(memfile_T *mfp, bhdr_T *hp)
     blocknr_T nr = hp->bh_bnum;  // block nr which is being written
     if (nr > mfp->mf_infile_count) {            // beyond end of file
       nr = mfp->mf_infile_count;
-      hp2 = mf_find_hash(mfp, nr);              // NULL caught below
+      hp2 = pmap_get(int64_t)(&mfp->mf_hash, nr);  // NULL caught below
     } else {
       hp2 = hp;
     }
@@ -690,8 +640,6 @@ static int mf_trans_add(memfile_T *mfp, bhdr_T *hp)
     return OK;
   }
 
-  mf_blocknr_trans_item_T *np = xmalloc(sizeof(mf_blocknr_trans_item_T));
-
   // Get a new number for the block.
   // If the first item in the free list has sufficient pages, use its number.
   // Otherwise use mf_blocknr_max.
@@ -714,15 +662,13 @@ static int mf_trans_add(memfile_T *mfp, bhdr_T *hp)
     mfp->mf_blocknr_max += page_count;
   }
 
-  np->nt_old_bnum = hp->bh_bnum;            // adjust number
-  np->nt_new_bnum = new_bnum;
-
-  mf_rem_hash(mfp, hp);                     // remove from old hash list
+  blocknr_T old_bnum = hp->bh_bnum;            // adjust number
+  pmap_del(int64_t)(&mfp->mf_hash, hp->bh_bnum, NULL);
   hp->bh_bnum = new_bnum;
-  mf_ins_hash(mfp, hp);                     // insert in new hash list
+  pmap_put(int64_t)(&mfp->mf_hash, new_bnum, hp);
 
   // Insert "np" into "mf_trans" hashtable with key "np->nt_old_bnum".
-  mf_hash_add_item(&mfp->mf_trans, (mf_hashitem_T *)np);
+  map_put(int64_t, int64_t)(&mfp->mf_trans, old_bnum, new_bnum);
 
   return OK;
 }
@@ -733,20 +679,16 @@ static int mf_trans_add(memfile_T *mfp, bhdr_T *hp)
 ///          The old number           When not found.
 blocknr_T mf_trans_del(memfile_T *mfp, blocknr_T old_nr)
 {
-  mf_blocknr_trans_item_T *np =
-    (mf_blocknr_trans_item_T *)mf_hash_find(&mfp->mf_trans, old_nr);
-
-  if (np == NULL) {  // not found
+  blocknr_T *num = map_ref(int64_t, int64_t)(&mfp->mf_trans, old_nr, false);
+  if (num == NULL) {  // not found
     return old_nr;
   }
 
   mfp->mf_neg_count--;
-  blocknr_T new_bnum = np->nt_new_bnum;
+  blocknr_T new_bnum = *num;
 
   // remove entry from the trans list
-  mf_hash_rem_item(&mfp->mf_trans, (mf_hashitem_T *)np);
-
-  xfree(np);
+  map_del(int64_t, int64_t)(&mfp->mf_trans, old_nr, NULL);
 
   return new_bnum;
 }
@@ -810,7 +752,7 @@ static bool mf_do_open(memfile_T *mfp, char *fname, int flags)
     emsg(_("E300: Swap file already exists (symlink attack?)"));
   } else {
     // try to open the file
-    mfp->mf_fd = MCH_OPEN_RW(mfp->mf_fname, flags | O_NOFOLLOW);
+    mfp->mf_fd = os_open(mfp->mf_fname, flags | O_NOFOLLOW, S_IREAD | S_IWRITE);
   }
 
   // If the file cannot be opened, use memory only
@@ -823,152 +765,3 @@ static bool mf_do_open(memfile_T *mfp, char *fname, int flags)
 
   return true;
 }
-
-//
-// Implementation of mf_hashtab_T.
-//
-
-/// The number of buckets in the hashtable is increased by a factor of
-/// MHT_GROWTH_FACTOR when the average number of items per bucket
-/// exceeds 2 ^ MHT_LOG_LOAD_FACTOR.
-enum {
-  MHT_LOG_LOAD_FACTOR = 6,
-  MHT_GROWTH_FACTOR = 2,  // must be a power of two
-};
-
-/// Initialize an empty hash table.
-static void mf_hash_init(mf_hashtab_T *mht)
-{
-  CLEAR_POINTER(mht);
-  mht->mht_buckets = mht->mht_small_buckets;
-  mht->mht_mask = MHT_INIT_SIZE - 1;
-}
-
-/// Free the array of a hash table. Does not free the items it contains!
-/// The hash table must not be used again without another mf_hash_init() call.
-static void mf_hash_free(mf_hashtab_T *mht)
-{
-  if (mht->mht_buckets != mht->mht_small_buckets) {
-    xfree(mht->mht_buckets);
-  }
-}
-
-/// Free the array of a hash table and all the items it contains.
-static void mf_hash_free_all(mf_hashtab_T *mht)
-{
-  for (size_t idx = 0; idx <= mht->mht_mask; idx++) {
-    mf_hashitem_T *next;
-    for (mf_hashitem_T *mhi = mht->mht_buckets[idx]; mhi != NULL; mhi = next) {
-      next = mhi->mhi_next;
-      xfree(mhi);
-    }
-  }
-
-  mf_hash_free(mht);
-}
-
-/// Find by key.
-///
-/// @return  A pointer to a mf_hashitem_T or NULL if the item was not found.
-static mf_hashitem_T *mf_hash_find(mf_hashtab_T *mht, blocknr_T key)
-{
-  mf_hashitem_T *mhi = mht->mht_buckets[(size_t)key & mht->mht_mask];
-  while (mhi != NULL && mhi->mhi_key != key) {
-    mhi = mhi->mhi_next;
-  }
-  return mhi;
-}
-
-/// Add item to hashtable. Item must not be NULL.
-static void mf_hash_add_item(mf_hashtab_T *mht, mf_hashitem_T *mhi)
-{
-  size_t idx = (size_t)mhi->mhi_key & mht->mht_mask;
-  mhi->mhi_next = mht->mht_buckets[idx];
-  mhi->mhi_prev = NULL;
-  if (mhi->mhi_next != NULL) {
-    mhi->mhi_next->mhi_prev = mhi;
-  }
-  mht->mht_buckets[idx] = mhi;
-
-  mht->mht_count++;
-
-  /// Grow hashtable when we have more thank 2^MHT_LOG_LOAD_FACTOR
-  /// items per bucket on average.
-  if ((mht->mht_count >> MHT_LOG_LOAD_FACTOR) > mht->mht_mask) {
-    mf_hash_grow(mht);
-  }
-}
-
-/// Remove item from hashtable. Item must be non NULL and within hashtable.
-static void mf_hash_rem_item(mf_hashtab_T *mht, mf_hashitem_T *mhi)
-{
-  if (mhi->mhi_prev == NULL) {
-    mht->mht_buckets[(size_t)mhi->mhi_key & mht->mht_mask] =
-      mhi->mhi_next;
-  } else {
-    mhi->mhi_prev->mhi_next = mhi->mhi_next;
-  }
-
-  if (mhi->mhi_next != NULL) {
-    mhi->mhi_next->mhi_prev = mhi->mhi_prev;
-  }
-
-  mht->mht_count--;
-
-  // We could shrink the table here, but it typically takes little memory,
-  // so why bother?
-}
-
-/// Increase number of buckets in the hashtable by MHT_GROWTH_FACTOR and
-/// rehash items.
-static void mf_hash_grow(mf_hashtab_T *mht)
-{
-  size_t size = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR * sizeof(void *);
-  mf_hashitem_T **buckets = xcalloc(1, size);
-
-  int shift = 0;
-  while ((mht->mht_mask >> shift) != 0) {
-    shift++;
-  }
-
-  for (size_t i = 0; i <= mht->mht_mask; i++) {
-    /// Traverse the items in the i-th original bucket and move them into
-    /// MHT_GROWTH_FACTOR new buckets, preserving their relative order
-    /// within each new bucket. Preserving the order is important because
-    /// mf_get() tries to keep most recently used items at the front of
-    /// each bucket.
-    ///
-    /// Here we strongly rely on the fact that hashes are computed modulo
-    /// a power of two.
-
-    mf_hashitem_T *tails[MHT_GROWTH_FACTOR];
-    CLEAR_FIELD(tails);
-
-    for (mf_hashitem_T *mhi = mht->mht_buckets[i];
-         mhi != NULL; mhi = mhi->mhi_next) {
-      size_t j = (mhi->mhi_key >> shift) & (MHT_GROWTH_FACTOR - 1);
-      if (tails[j] == NULL) {
-        buckets[i + (j << shift)] = mhi;
-        tails[j] = mhi;
-        mhi->mhi_prev = NULL;
-      } else {
-        tails[j]->mhi_next = mhi;
-        mhi->mhi_prev = tails[j];
-        tails[j] = mhi;
-      }
-    }
-
-    for (size_t j = 0; j < MHT_GROWTH_FACTOR; j++) {
-      if (tails[j] != NULL) {
-        tails[j]->mhi_next = NULL;
-      }
-    }
-  }
-
-  if (mht->mht_buckets != mht->mht_small_buckets) {
-    xfree(mht->mht_buckets);
-  }
-
-  mht->mht_buckets = buckets;
-  mht->mht_mask = (mht->mht_mask + 1) * MHT_GROWTH_FACTOR - 1;
-}
diff --git a/src/nvim/memfile_defs.h b/src/nvim/memfile_defs.h
index 917dd6a905..bf9bb208a4 100644
--- a/src/nvim/memfile_defs.h
+++ b/src/nvim/memfile_defs.h
@@ -5,6 +5,7 @@
 #include <stdint.h>
 #include <stdlib.h>
 
+#include "nvim/map.h"
 #include "nvim/pos.h"
 #include "nvim/types.h"
 
@@ -15,57 +16,20 @@
 /// with negative numbers are currently in memory only.
 typedef int64_t blocknr_T;
 
-/// A hash item.
-///
-/// Items' keys are block numbers.
-/// Items in the same bucket are organized into a doubly-linked list.
-///
-/// Therefore, items can be arbitrary data structures beginning with pointers
-/// for the list and and a block number key.
-typedef struct mf_hashitem {
-  struct mf_hashitem *mhi_next;
-  struct mf_hashitem *mhi_prev;
-  blocknr_T mhi_key;
-} mf_hashitem_T;
-
-/// Initial size for a hashtable.
-#define MHT_INIT_SIZE 64
-
-/// A chained hashtable with block numbers as keys and arbitrary data structures
-/// as items.
-///
-/// This is an intrusive data structure: we require that items begin with
-/// mf_hashitem_T which contains the key and linked list pointers. List of items
-/// in each bucket is doubly-linked.
-typedef struct mf_hashtab {
-  size_t mht_mask;              ///< mask used to mod hash value to array index
-                                ///< (nr of items in array is 'mht_mask + 1')
-  size_t mht_count;             ///< number of items inserted
-  mf_hashitem_T **mht_buckets;  ///< points to the array of buckets (can be
-                                ///< mht_small_buckets or a newly allocated array
-                                ///< when mht_small_buckets becomes too small)
-  mf_hashitem_T *mht_small_buckets[MHT_INIT_SIZE];  ///< initial buckets
-} mf_hashtab_T;
-
 /// A block header.
 ///
 /// There is a block header for each previously used block in the memfile.
 ///
 /// The block may be linked in the used list OR in the free list.
-/// The used blocks are also kept in hash lists.
 ///
 /// The used list is a doubly linked list, most recently used block first.
 /// The blocks in the used list have a block of memory allocated.
-/// The hash lists are used to quickly find a block in the used list.
 /// The free list is a single linked list, not sorted.
 /// The blocks in the free list have no block of memory allocated and
 /// the contents of the block in the file (if any) is irrelevant.
 typedef struct bhdr {
-  mf_hashitem_T bh_hashitem;         ///< header for hash table and key
-#define bh_bnum bh_hashitem.mhi_key  ///< block number, part of bh_hashitem
+  blocknr_T bh_bnum;                 ///< key used in hash table
 
-  struct bhdr *bh_next;              ///< next block header in free or used list
-  struct bhdr *bh_prev;              ///< previous block header in used list
   void *bh_data;                     ///< pointer to memory (for used block)
   unsigned bh_page_count;            ///< number of pages in this block
 
@@ -74,18 +38,6 @@ typedef struct bhdr {
   unsigned bh_flags;                 ///< BH_DIRTY or BH_LOCKED
 } bhdr_T;
 
-/// A block number translation list item.
-///
-/// When a block with a negative number is flushed to the file, it gets
-/// a positive number. Because the reference to the block is still the negative
-/// number, we remember the translation to the new positive number in the
-/// double linked trans lists. The structure is the same as the hash lists.
-typedef struct mf_blocknr_trans_item {
-  mf_hashitem_T nt_hashitem;             ///< header for hash table and key
-#define nt_old_bnum nt_hashitem.mhi_key  ///< old, negative, number
-  blocknr_T nt_new_bnum;                 ///< new, positive, number
-} mf_blocknr_trans_item_T;
-
 typedef enum {
   MF_DIRTY_NO = 0,      ///< no dirty blocks
   MF_DIRTY_YES,         ///< there are dirty blocks
@@ -98,10 +50,16 @@ typedef struct memfile {
   char *mf_ffname;                   ///< idem, full path
   int mf_fd;                         ///< file descriptor
   bhdr_T *mf_free_first;             ///< first block header in free list
-  bhdr_T *mf_used_first;             ///< mru block header in used list
-  bhdr_T *mf_used_last;              ///< lru block header in used list
-  mf_hashtab_T mf_hash;              ///< hash lists
-  mf_hashtab_T mf_trans;             ///< trans lists
+
+  /// The used blocks are kept in mf_hash.
+  /// mf_hash are used to quickly find a block in the used list.
+  PMap(int64_t) mf_hash;
+
+  /// When a block with a negative number is flushed to the file, it gets
+  /// a positive number. Because the reference to the block is still the negative
+  /// number, we remember the translation to the new positive number.
+  Map(int64_t, int64_t) mf_trans;
+
   blocknr_T mf_blocknr_max;          ///< highest positive block number + 1
   blocknr_T mf_blocknr_min;          ///< lowest negative block number - 1
   blocknr_T mf_neg_count;            ///< number of negative blocks numbers
diff --git a/src/nvim/memline.c b/src/nvim/memline.c
index ff5f621611..ecc52a4da8 100644
--- a/src/nvim/memline.c
+++ b/src/nvim/memline.c
@@ -3684,22 +3684,19 @@ static long char_to_long(const char *s_in)
 /// - 'fileencoding'
 void ml_setflags(buf_T *buf)
 {
-  bhdr_T *hp;
   ZERO_BL *b0p;
 
   if (!buf->b_ml.ml_mfp) {
     return;
   }
-  for (hp = buf->b_ml.ml_mfp->mf_used_last; hp != NULL; hp = hp->bh_prev) {
-    if (hp->bh_bnum == 0) {
-      b0p = hp->bh_data;
-      b0p->b0_dirty = buf->b_changed ? B0_DIRTY : 0;
-      b0p->b0_flags = (char)((b0p->b0_flags & ~B0_FF_MASK) | (uint8_t)(get_fileformat(buf) + 1));
-      add_b0_fenc(b0p, buf);
-      hp->bh_flags |= BH_DIRTY;
-      mf_sync(buf->b_ml.ml_mfp, MFS_ZERO);
-      break;
-    }
+  bhdr_T *hp = pmap_get(int64_t)(&buf->b_ml.ml_mfp->mf_hash, 0);
+  if (hp) {
+    b0p = hp->bh_data;
+    b0p->b0_dirty = buf->b_changed ? B0_DIRTY : 0;
+    b0p->b0_flags = (char)((b0p->b0_flags & ~B0_FF_MASK) | (uint8_t)(get_fileformat(buf) + 1));
+    add_b0_fenc(b0p, buf);
+    hp->bh_flags |= BH_DIRTY;
+    mf_sync(buf->b_ml.ml_mfp, MFS_ZERO);
   }
 }
 
diff --git a/src/nvim/menu.c b/src/nvim/menu.c
index 1d35c97b39..3b2e45e2a4 100644
--- a/src/nvim/menu.c
+++ b/src/nvim/menu.c
@@ -618,8 +618,6 @@ static void free_menu(vimmenu_T **menup)
 {
   vimmenu_T *menu = *menup;
 
-  // Don't change *menup until after calling gui_mch_destroy_menu(). The
-  // MacOS code needs the original structure to properly delete the menu.
   *menup = menu->next;
   xfree(menu->name);
   xfree(menu->dname);
diff --git a/src/nvim/window.c b/src/nvim/window.c
index 9d804ecae7..a615bd6797 100644
--- a/src/nvim/window.c
+++ b/src/nvim/window.c
@@ -5171,7 +5171,6 @@ static void win_free(win_T *wp, tabpage_T *tp)
   alist_unlink(wp->w_alist);
 
   // Don't execute autocommands while the window is halfway being deleted.
-  // gui_mch_destroy_scrollbar() may trigger a FocusGained event.
   block_autocmds();
 
   clear_winopt(&wp->w_onebuf_opt);