1 /* vi:set ts=8 sts=4 sw=4: 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 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 = (mf_hashitem_T *)lalloc_clear(sizeof(mf_hashtab_T), FALSE); 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 139 main(void) 140 { 141 test_mf_hash(); 142 return 0; 143 } 144