Advertisement
osowatzke

Untitled

Apr 1st, 2020
143
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.03 KB | None | 0 0
  1. // Inform the compiler that this included module is written in C instead of C++.
  2. extern "C" {
  3. #include "hash_table.h"
  4. }
  5. #include "gtest/gtest.h"
  6.  
  7.  
  8. // Use the TEST macro to define your tests.
  9. //
  10. // TEST has two parameters: the test case name and the test name.
  11. // After using the macro, you should define your test logic between a
  12. // pair of braces. You can use a bunch of macros to indicate the
  13. // success or failure of a test. EXPECT_TRUE and EXPECT_EQ are
  14. // examples of such macros. For a complete list, see gtest.h.
  15. //
  16. // <TechnicalDetails>
  17. //
  18. // In Google Test, tests are grouped into test cases. This is how we
  19. // keep test code organized. You should put logically related tests
  20. // into the same test case.
  21. //
  22. // The test case name and the test name should both be valid C++
  23. // identifiers. And you should not use underscore (_) in the names.
  24. //
  25. // Google Test guarantees that each test you define is run exactly
  26. // once, but it makes no guarantee on the order the tests are
  27. // executed. Therefore, you should write your tests in such a way
  28. // that their results don't depend on their order.
  29. //
  30. // </TechnicalDetails>
  31.  
  32. // The #define directive defines a constant value that can be accessed throughout
  33. // your code. Here it defines the default number of buckets in the hash table.
  34. // You can change this number, but make sure to update the hash function with
  35. // the right algorithm to compute the indices for buckets.
  36. // For example, if the BUCKET_NUM is set to 5, the hash function should map a
  37. // positive number to an integer between 0 and 4.
  38. #define BUCKET_NUM 3
  39.  
  40. // Dummy value to store in hash table entry
  41. // Please beware that any type of data (e.g. int, double, struct and etc.) can
  42. // be stored in hash table for testing your hash table. Only the pointer to
  43. // the data will be stored in the HashTableEntry.
  44. struct HTItem {};
  45.  
  46. // Helper function for creating a lot of dummy values.
  47. void make_items(HTItem* result[], unsigned n)
  48. {
  49. // Populate the array with pointers to the dummy values.
  50. while(n--)
  51. {
  52. result[n] = (HTItem*) malloc(sizeof(HTItem));
  53. }
  54. }
  55.  
  56. // A simple hash function that maps a positive number to an integer between 0~(BUCKET_NUM-1).
  57. unsigned int hash(unsigned int key) {
  58. return key%BUCKET_NUM;
  59. }
  60.  
  61.  
  62. ////////////////////////
  63. // Initialization tests
  64. ////////////////////////
  65. TEST(InitTest, CreateDestroyHashTable)
  66. {
  67. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  68. destroyHashTable(ht);
  69. }
  70.  
  71.  
  72. ////////////////
  73. // Access tests
  74. ////////////////
  75. TEST(AccessTest, GetKey_TableEmpty)
  76. {
  77. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  78.  
  79. // Test when table is empty.
  80. EXPECT_EQ(NULL, getItem(ht, 0));
  81. EXPECT_EQ(NULL, getItem(ht, 1));
  82. EXPECT_EQ(NULL, getItem(ht, 2));
  83.  
  84. // Test with index greater than the number of buckets.
  85. EXPECT_EQ(NULL, getItem(ht, 10));
  86.  
  87. destroyHashTable(ht);
  88. }
  89.  
  90. TEST(AccessTest, GetSingleKey)
  91. {
  92. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  93.  
  94. // Create list of items
  95. size_t num_items = 1;
  96. HTItem* m[num_items];
  97. make_items(m, num_items);
  98.  
  99. insertItem(ht, 0, m[0]);
  100. EXPECT_EQ(m[0], getItem(ht, 0));
  101.  
  102. destroyHashTable(ht); // dummy item is also freed here
  103. }
  104.  
  105. TEST(AccessTest, GetKey_KeyNotPresent)
  106. {
  107. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  108.  
  109. // Create a list of items to add to hash table.
  110. size_t num_items = 1;
  111. HTItem* m[num_items];
  112. make_items(m, num_items);
  113.  
  114. // Insert one item into the hash table.
  115. insertItem(ht, 0, m[0]);
  116.  
  117. // Test if the hash table returns NULL when the key is not found.
  118. EXPECT_EQ(NULL, getItem(ht, 1));
  119.  
  120. // Destroy the hash table togeter with the inserted values
  121. destroyHashTable(ht);
  122. }
  123.  
  124. TEST(AccessTest, GetTwoKeys_DifferentBuckets)
  125. {
  126. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  127.  
  128. // Create a list of items to add to the hash table
  129. size_t num_items = 2;
  130. HTItem* m[num_items];
  131. make_items(m, num_items);
  132.  
  133. // Insert both items sequentially into the hash table
  134. insertItem(ht,0,m[0]);
  135. insertItem(ht,1,m[1]);
  136.  
  137. // Read items from bucket in the same way they were added
  138. EXPECT_EQ(m[0], getItem(ht,0));
  139. EXPECT_EQ(m[1], getItem(ht,1));
  140.  
  141. // Destroy the hash table together with the inserted values
  142. destroyHashTable(ht);
  143. }
  144.  
  145. TEST(AccessTest, GetTwoKeys_SameBucket)
  146. {
  147. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  148.  
  149. // Create a list of items to add to the hash table
  150. size_t num_items = 2;
  151. HTItem* m[num_items];
  152. make_items(m, num_items);
  153.  
  154. // Insert both items into the same bucket
  155. insertItem(ht,0,m[0]);
  156. insertItem(ht,BUCKET_NUM,m[1]);
  157.  
  158. // Read items from the bucket in the same way they were added
  159. EXPECT_EQ(m[0], getItem(ht,0));
  160. EXPECT_EQ(m[1], getItem(ht,BUCKET_NUM));
  161.  
  162. // Destroy the hash table together with the inserted values
  163. destroyHashTable(ht);
  164. }
  165.  
  166. TEST(AccessTest, GetMultipleKeys_SameBucket)
  167. {
  168. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  169.  
  170. // Create a list of items to add to the hash table
  171. size_t num_items = 10;
  172. HTItem* m[num_items];
  173. make_items(m, num_items);
  174.  
  175. // Use a for loop to insert the items into the same bucket
  176. unsigned int i;
  177. for (i=0; i<num_items; ++i){
  178. insertItem(ht,i*BUCKET_NUM,m[i]);
  179. }
  180.  
  181. // Read items from the bucket in the opposite way they were added
  182. for(i=num_items; i<=0; --i){
  183. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  184. }
  185.  
  186. // Destroy the hash table together with the inserted values
  187. destroyHashTable(ht);
  188. }
  189.  
  190. ////////////////////////////
  191. // Removal and delete tests
  192. ////////////////////////////
  193. TEST(RemoveTest, SingleValidRemove)
  194. {
  195. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  196.  
  197. // Create a list of items to add to hash table.
  198. size_t num_items = 1;
  199. HTItem* m[num_items];
  200. make_items(m, num_items);
  201.  
  202. // Insert one item into the hash table.
  203. insertItem(ht, 0, m[0]);
  204.  
  205. // After removing an item with a specific key, the data stored in the
  206. // corresponding entry should be returned. If the key is not present in the
  207. // hash table, then NULL should be returned.
  208. void* data = removeItem(ht, 0);
  209.  
  210. // Since the key we want to remove is present in the hash table, the correct
  211. // data should be returned.
  212. EXPECT_EQ(m[0], data);
  213.  
  214. // Free the data
  215. free(data);
  216.  
  217. destroyHashTable(ht);
  218. }
  219.  
  220. TEST(RemoveTest, SingleInvalidRemove)
  221. {
  222. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  223.  
  224. // When the hash table is empty, the remove funtion should still work.
  225. EXPECT_EQ(NULL, removeItem(ht, 1));
  226.  
  227. destroyHashTable(ht);
  228. }
  229.  
  230. TEST(RemoveTest, RemovefromHead)
  231. {
  232. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  233.  
  234. // Create a list of items to add to the hash table
  235. size_t num_items = 3;
  236. HTItem* m[num_items];
  237. make_items(m, num_items);
  238.  
  239. // Use a for loop to insert the items into the same bucket
  240. unsigned int i;
  241. for (i=0; i<num_items; ++i){
  242. insertItem(ht,i*BUCKET_NUM,m[i]);
  243. }
  244.  
  245. // After removing an item with a specific key, the data stored in the
  246. // corresponding entry should be returned. If the key is not present in the
  247. // hash table, then NULL should be returned.
  248. void* data = removeItem(ht, 0);
  249. EXPECT_EQ(m[0], data);
  250.  
  251. // When trying to get Item with the same key, the item is no longer there
  252. EXPECT_EQ(NULL, getItem(ht, 0));
  253.  
  254.  
  255. // Use a for loop to ensure that the remaining items are untouched and accessible
  256. for(i=1; i<num_items; ++i){
  257. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  258. }
  259.  
  260. // free the data
  261. free(data);
  262.  
  263. destroyHashTable(ht);
  264. }
  265.  
  266. TEST(RemoveTest, RemovefromMiddle)
  267. {
  268. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  269.  
  270. // Create a list of items to add to the hash table
  271. size_t num_items = 3;
  272. HTItem* m[num_items];
  273. make_items(m, num_items);
  274.  
  275. // Use a for loop to insert the items into the same bucket
  276. unsigned int i;
  277. for (i=0; i<num_items; ++i){
  278. insertItem(ht,i*BUCKET_NUM,m[i]);
  279. }
  280.  
  281. // After removing an item with a specific key, the data stored in the
  282. // corresponding entry should be returned. If the key is not present in the
  283. // hash table, then NULL should be returned.
  284. void* data = removeItem(ht, BUCKET_NUM);
  285. EXPECT_EQ(m[1], data);
  286.  
  287. // When trying to get Item with the same key, the item is no longer there
  288. EXPECT_EQ(NULL, getItem(ht,BUCKET_NUM));
  289.  
  290. // Use a for loop to ensure that the remaining items are untouched and accessible
  291. for(i=0; i<num_items; ++i){
  292. if (i==1){
  293. continue;
  294. }
  295. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  296. }
  297.  
  298. // free the data
  299. free(data);
  300.  
  301. destroyHashTable(ht);
  302. }
  303.  
  304. TEST(RemoveTest, RemovefromEnd)
  305. {
  306. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  307.  
  308. // Create a list of items to add to the hash table
  309. size_t num_items = 3;
  310. HTItem* m[num_items];
  311. make_items(m, num_items);
  312.  
  313. // Use a for loop to insert the items into the same bucket
  314. unsigned int i;
  315. for (i=0; i<num_items; ++i){
  316. insertItem(ht,i*BUCKET_NUM,m[i]);
  317. }
  318.  
  319. // After removing an item with a specific key, the data stored in the
  320. // corresponding entry should be returned. If the key is not present in the
  321. // hash table, then NULL should be returned.
  322. void* data = removeItem(ht, 2*BUCKET_NUM);
  323. EXPECT_EQ(m[2], data);
  324.  
  325. // When trying to get Item with the same key, the item is no longer there
  326. EXPECT_EQ(NULL, getItem(ht,2*BUCKET_NUM));
  327.  
  328. // Use a for loop to ensure that the remaining items are untouched and accessible
  329. for(i=0; i<(num_items-1); ++i){
  330. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  331. }
  332.  
  333. // free the data
  334. free(data);
  335.  
  336. destroyHashTable(ht);
  337. }
  338.  
  339. TEST(DeleteTest, DeletefromHead)
  340. {
  341. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  342.  
  343. // Create a list of items to add to the hash table
  344. size_t num_items = 3;
  345. HTItem* m[num_items];
  346. make_items(m, num_items);
  347.  
  348. // Use a for loop to insert the items into the same bucket
  349. unsigned int i;
  350. for (i=0; i<num_items; ++i){
  351. insertItem(ht,i*BUCKET_NUM,m[i]);
  352. }
  353.  
  354. // delete the item and ensure that it is no longer in the hash table
  355. deleteItem(ht,0);
  356. EXPECT_EQ(NULL, getItem(ht,0));
  357.  
  358. // Use a for loop to ensure that the remaining items are untouched and accessible
  359. for(i=1; i<num_items; ++i){
  360. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  361. }
  362.  
  363. // Destroy the hashtable and the inserted values
  364. destroyHashTable(ht);
  365. }
  366.  
  367. TEST(DeleteTest, DeletefromMiddle)
  368. {
  369. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  370.  
  371. // Create a list of items to add to the hash table
  372. size_t num_items = 3;
  373. HTItem* m[num_items];
  374. make_items(m, num_items);
  375.  
  376. // Use a for loop to insert the items into the same bucket
  377. unsigned int i;
  378. for (i=0; i<num_items; ++i){
  379. insertItem(ht,i*BUCKET_NUM,m[i]);
  380. }
  381.  
  382. // delete the item and ensure that it is no longer in the hash table
  383. deleteItem(ht,BUCKET_NUM);
  384. EXPECT_EQ(NULL, getItem(ht,BUCKET_NUM));
  385.  
  386. // Use a for loop to ensure that the remaining items are untouched and accessible
  387. for(i=0; i<num_items; ++i){
  388. if (i==1){
  389. continue;
  390. }
  391. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  392. }
  393.  
  394. // Destroy the hashtable and the inserted values
  395. destroyHashTable(ht);
  396. }
  397.  
  398. TEST(DeleteTest, DeletefromEnd)
  399. {
  400. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  401.  
  402. // Create a list of items to add to the hash table
  403. size_t num_items = 3;
  404. HTItem* m[num_items];
  405. make_items(m, num_items);
  406.  
  407. // Use a for loop to insert the items into the same bucket
  408. unsigned int i;
  409. for (i=0; i<num_items; ++i){
  410. insertItem(ht,i*BUCKET_NUM,m[i]);
  411. }
  412.  
  413. // delete the item and ensure that it is no longer in the hash table
  414. deleteItem(ht,2*BUCKET_NUM);
  415. EXPECT_EQ(NULL, getItem(ht,2*BUCKET_NUM));
  416.  
  417. // Use a for loop to ensure that the remaining items are untouched and accessible
  418. for(i=0; i<(num_items-1); ++i){
  419. EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
  420. }
  421.  
  422. // Destroy the hashtable and the inserted values
  423. destroyHashTable(ht);
  424. }
  425.  
  426. ///////////////////
  427. // Insersion tests
  428. ///////////////////
  429. TEST(InsertTest, SingleNoOverwrite){
  430. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  431.  
  432. // Create a list of items to add to the hash table
  433. size_t num_items = 1;
  434. HTItem* m[num_items];
  435. make_items(m, num_items);
  436.  
  437. // When an item is not replaced, the insertItem function should return null
  438. EXPECT_EQ(NULL, insertItem(ht, 0, m[0]));
  439.  
  440. // Ensure that we can access the added value
  441. EXPECT_EQ(m[0], getItem(ht,0));
  442.  
  443. // Destroy the hashtable and the inserted value
  444. destroyHashTable(ht);
  445. }
  446.  
  447. TEST(InsertTest, InsertAsOverwrite)
  448. {
  449. HashTable* ht = createHashTable(hash, BUCKET_NUM);
  450.  
  451. // Create list of items to be added to the hash table.
  452. size_t num_items = 2;
  453. HTItem* m[num_items];
  454. make_items(m, num_items);
  455.  
  456. // Only insert one item with key=0 into the hash table.
  457. insertItem(ht, 0, m[0]);
  458.  
  459. // When we are inserting a different value with the same key=0, the hash table
  460. // entry should hold the new value instead. In the test case, the hash table entry
  461. // corresponding to key=0 will hold m[1] and return m[0] as the return value.
  462. EXPECT_EQ(m[0], insertItem(ht, 0, m[1]));
  463.  
  464. // Now check if the new value m[1] has indeed been stored in hash table with
  465. // key=0.
  466. EXPECT_EQ(m[1], getItem(ht,0));
  467.  
  468. destroyHashTable(ht);
  469. free(m[0]); // don't forget to free item 0
  470. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement