1#ifndef NVIM_MEMFILE_DEFS_H
2#define NVIM_MEMFILE_DEFS_H
3
4#include <stdint.h>
5#include <stdbool.h>
6#include <stdlib.h>
7
8#include "nvim/types.h"
9#include "nvim/pos.h"
10
11/// A block number.
12///
13/// Blocks numbered from 0 upwards have been assigned a place in the actual
14/// file. The block number is equal to the page number in the file. The blocks
15/// with negative numbers are currently in memory only.
16typedef int64_t blocknr_T;
17
18/// A hash item.
19///
20/// Items' keys are block numbers.
21/// Items in the same bucket are organized into a doubly-linked list.
22///
23/// Therefore, items can be arbitrary data structures beginning with pointers
24/// for the list and and a block number key.
25typedef struct mf_hashitem {
26 struct mf_hashitem *mhi_next;
27 struct mf_hashitem *mhi_prev;
28 blocknr_T mhi_key;
29} mf_hashitem_T;
30
31/// Initial size for a hashtable.
32#define MHT_INIT_SIZE 64
33
34/// A chained hashtable with block numbers as keys and arbitrary data structures
35/// as items.
36///
37/// This is an intrusive data structure: we require that items begin with
38/// mf_hashitem_T which contains the key and linked list pointers. List of items
39/// in each bucket is doubly-linked.
40typedef struct mf_hashtab {
41 size_t mht_mask; /// mask used to mod hash value to array index
42 /// (nr of items in array is 'mht_mask + 1')
43 size_t mht_count; /// number of items inserted
44 mf_hashitem_T **mht_buckets; /// points to the array of buckets (can be
45 /// mht_small_buckets or a newly allocated array
46 /// when mht_small_buckets becomes too small)
47 mf_hashitem_T *mht_small_buckets[MHT_INIT_SIZE]; /// initial buckets
48} mf_hashtab_T;
49
50/// A block header.
51///
52/// There is a block header for each previously used block in the memfile.
53///
54/// The block may be linked in the used list OR in the free list.
55/// The used blocks are also kept in hash lists.
56///
57/// The used list is a doubly linked list, most recently used block first.
58/// The blocks in the used list have a block of memory allocated.
59/// The hash lists are used to quickly find a block in the used list.
60/// The free list is a single linked list, not sorted.
61/// The blocks in the free list have no block of memory allocated and
62/// the contents of the block in the file (if any) is irrelevant.
63typedef struct bhdr {
64 mf_hashitem_T bh_hashitem; /// header for hash table and key
65#define bh_bnum bh_hashitem.mhi_key /// block number, part of bh_hashitem
66
67 struct bhdr *bh_next; /// next block header in free or used list
68 struct bhdr *bh_prev; /// previous block header in used list
69 void *bh_data; /// pointer to memory (for used block)
70 unsigned bh_page_count; /// number of pages in this block
71
72#define BH_DIRTY 1U
73#define BH_LOCKED 2U
74 unsigned bh_flags; // BH_DIRTY or BH_LOCKED
75} bhdr_T;
76
77/// A block number translation list item.
78///
79/// When a block with a negative number is flushed to the file, it gets
80/// a positive number. Because the reference to the block is still the negative
81/// number, we remember the translation to the new positive number in the
82/// double linked trans lists. The structure is the same as the hash lists.
83typedef struct mf_blocknr_trans_item {
84 mf_hashitem_T nt_hashitem; /// header for hash table and key
85#define nt_old_bnum nt_hashitem.mhi_key /// old, negative, number
86 blocknr_T nt_new_bnum; /// new, positive, number
87} mf_blocknr_trans_item_T;
88
89/// A memory file.
90typedef struct memfile {
91 char_u *mf_fname; /// name of the file
92 char_u *mf_ffname; /// idem, full path
93 int mf_fd; /// file descriptor
94 bhdr_T *mf_free_first; /// first block header in free list
95 bhdr_T *mf_used_first; /// mru block header in used list
96 bhdr_T *mf_used_last; /// lru block header in used list
97 mf_hashtab_T mf_hash; /// hash lists
98 mf_hashtab_T mf_trans; /// trans lists
99 blocknr_T mf_blocknr_max; /// highest positive block number + 1
100 blocknr_T mf_blocknr_min; /// lowest negative block number - 1
101 blocknr_T mf_neg_count; /// number of negative blocks numbers
102 blocknr_T mf_infile_count; /// number of pages in the file
103 unsigned mf_page_size; /// number of bytes in a page
104 bool mf_dirty; /// TRUE if there are dirty blocks
105} memfile_T;
106
107#endif // NVIM_MEMFILE_DEFS_H
108