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

Memfile used a private implementation of an open hash table with intrusive collision chains, but there is
no reason to assume the standard khash_t based Map won't work just fine.

Yes, we are taking full ownership and maintenance over memline and memfile.
No one is going to maintain it for us.

Trust the plan.

1 files changed, 12 insertions, 54 deletions

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