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. |
16 | typedef 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. |
25 | typedef 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. |
40 | typedef 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. |
63 | typedef 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. |
83 | typedef 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. |
90 | typedef 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 | |