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 static void test_mf_hash __ARGS((void)); 29 30 /* 31 * Test mf_hash_*() functions. 32 */ 33 static void 34 test_mf_hash() 35 { 36 mf_hashtab_T ht; 37 mf_hashitem_T *item; 38 blocknr_T key; 39 long_u i; 40 long_u num_buckets; 41 42 mf_hash_init(&ht); 43 44 /* insert some items and check invariants */ 45 for (i = 0; i < TEST_COUNT; i++) 46 { 47 assert(ht.mht_count == i); 48 49 /* check that number of buckets is a power of 2 */ 50 num_buckets = ht.mht_mask + 1; 51 assert(num_buckets > 0 && (num_buckets & (num_buckets - 1)) == 0); 52 53 /* check load factor */ 54 assert(ht.mht_count <= (num_buckets << MHT_LOG_LOAD_FACTOR)); 55 56 if (i < (MHT_INIT_SIZE << MHT_LOG_LOAD_FACTOR)) 57 { 58 /* first expansion shouldn't have occurred yet */ 59 assert(num_buckets == MHT_INIT_SIZE); 60 assert(ht.mht_buckets == ht.mht_small_buckets); 61 } 62 else 63 { 64 assert(num_buckets > MHT_INIT_SIZE); 65 assert(ht.mht_buckets != ht.mht_small_buckets); 66 } 67 68 key = index_to_key(i); 69 assert(mf_hash_find(&ht, key) == NULL); 70 71 /* allocate and add new item */ 72 item = (mf_hashitem_T *)lalloc_clear(sizeof(mf_hashtab_T), FALSE); 73 assert(item != NULL); 74 item->mhi_key = key; 75 mf_hash_add_item(&ht, item); 76 77 assert(mf_hash_find(&ht, key) == item); 78 79 if (ht.mht_mask + 1 != num_buckets) 80 { 81 /* hash table was expanded */ 82 assert(ht.mht_mask + 1 == num_buckets * MHT_GROWTH_FACTOR); 83 assert(i + 1 == (num_buckets << MHT_LOG_LOAD_FACTOR)); 84 } 85 } 86 87 /* check presence of inserted items */ 88 for (i = 0; i < TEST_COUNT; i++) 89 { 90 key = index_to_key(i); 91 item = mf_hash_find(&ht, key); 92 assert(item != NULL); 93 assert(item->mhi_key == key); 94 } 95 96 /* delete some items */ 97 for (i = 0; i < TEST_COUNT; i++) 98 { 99 if (i % 100 < 70) 100 { 101 key = index_to_key(i); 102 item = mf_hash_find(&ht, key); 103 assert(item != NULL); 104 assert(item->mhi_key == key); 105 106 mf_hash_rem_item(&ht, item); 107 assert(mf_hash_find(&ht, key) == NULL); 108 109 mf_hash_add_item(&ht, item); 110 assert(mf_hash_find(&ht, key) == item); 111 112 mf_hash_rem_item(&ht, item); 113 assert(mf_hash_find(&ht, key) == NULL); 114 115 vim_free(item); 116 } 117 } 118 119 /* check again */ 120 for (i = 0; i < TEST_COUNT; i++) 121 { 122 key = index_to_key(i); 123 item = mf_hash_find(&ht, key); 124 125 if (i % 100 < 70) 126 { 127 assert(item == NULL); 128 } 129 else 130 { 131 assert(item != NULL); 132 assert(item->mhi_key == key); 133 } 134 } 135 136 /* free hash table and all remaining items */ 137 mf_hash_free_all(&ht); 138 } 139 140 int 141 main() 142 { 143 test_mf_hash(); 144 return 0; 145 } 146