1 /* vi:set ts=8 sts=4 sw=4 noet:
2 *
3 * VIM - Vi IMproved by Bram Moolenaar
4 *
5 * Do ":help uganda" in Vim to read copying and usage conditions.
6 * Do ":help credits" in Vim to see a list of people who contributed.
7 * See README.txt for an overview of the Vim source code.
8 */
9
10 /*
11 * memfile_test.c: Unittests for memfile.c
12 * Mostly by Ivan Krasilnikov.
13 */
14
15 #undef NDEBUG
16 #include <assert.h>
17
18 // Must include main.c because it contains much more than just main()
19 #define NO_VIM_MAIN
20 #include "main.c"
21
22 // This file has to be included because the tested functions are static
23 #include "memfile.c"
24
25 #define index_to_key(i) ((i) ^ 15167)
26 #define TEST_COUNT 50000
27
28 /*
29 * Test mf_hash_*() functions.
30 */
31 static void
test_mf_hash(void)32 test_mf_hash(void)
33 {
34 mf_hashtab_T ht;
35 mf_hashitem_T *item;
36 blocknr_T key;
37 long_u i;
38 long_u num_buckets;
39
40 mf_hash_init(&ht);
41
42 // insert some items and check invariants
43 for (i = 0; i < TEST_COUNT; i++)
44 {
45 assert(ht.mht_count == i);
46
47 // check that number of buckets is a power of 2
48 num_buckets = ht.mht_mask + 1;
49 assert(num_buckets > 0 && (num_buckets & (num_buckets - 1)) == 0);
50
51 // check load factor
52 assert(ht.mht_count <= (num_buckets << MHT_LOG_LOAD_FACTOR));
53
54 if (i < (MHT_INIT_SIZE << MHT_LOG_LOAD_FACTOR))
55 {
56 // first expansion shouldn't have occurred yet
57 assert(num_buckets == MHT_INIT_SIZE);
58 assert(ht.mht_buckets == ht.mht_small_buckets);
59 }
60 else
61 {
62 assert(num_buckets > MHT_INIT_SIZE);
63 assert(ht.mht_buckets != ht.mht_small_buckets);
64 }
65
66 key = index_to_key(i);
67 assert(mf_hash_find(&ht, key) == NULL);
68
69 // allocate and add new item
70 item = LALLOC_CLEAR_ONE(mf_hashitem_T);
71 assert(item != NULL);
72 item->mhi_key = key;
73 mf_hash_add_item(&ht, item);
74
75 assert(mf_hash_find(&ht, key) == item);
76
77 if (ht.mht_mask + 1 != num_buckets)
78 {
79 // hash table was expanded
80 assert(ht.mht_mask + 1 == num_buckets * MHT_GROWTH_FACTOR);
81 assert(i + 1 == (num_buckets << MHT_LOG_LOAD_FACTOR));
82 }
83 }
84
85 // check presence of inserted items
86 for (i = 0; i < TEST_COUNT; i++)
87 {
88 key = index_to_key(i);
89 item = mf_hash_find(&ht, key);
90 assert(item != NULL);
91 assert(item->mhi_key == key);
92 }
93
94 // delete some items
95 for (i = 0; i < TEST_COUNT; i++)
96 {
97 if (i % 100 < 70)
98 {
99 key = index_to_key(i);
100 item = mf_hash_find(&ht, key);
101 assert(item != NULL);
102 assert(item->mhi_key == key);
103
104 mf_hash_rem_item(&ht, item);
105 assert(mf_hash_find(&ht, key) == NULL);
106
107 mf_hash_add_item(&ht, item);
108 assert(mf_hash_find(&ht, key) == item);
109
110 mf_hash_rem_item(&ht, item);
111 assert(mf_hash_find(&ht, key) == NULL);
112
113 vim_free(item);
114 }
115 }
116
117 // check again
118 for (i = 0; i < TEST_COUNT; i++)
119 {
120 key = index_to_key(i);
121 item = mf_hash_find(&ht, key);
122
123 if (i % 100 < 70)
124 {
125 assert(item == NULL);
126 }
127 else
128 {
129 assert(item != NULL);
130 assert(item->mhi_key == key);
131 }
132 }
133
134 // free hash table and all remaining items
135 mf_hash_free_all(&ht);
136 }
137
138 int
main(void)139 main(void)
140 {
141 test_mf_hash();
142 return 0;
143 }
144