0

I have implemented a doubly linked cyclic list and I do want to write tests.

So in this list, there is a deletion operator and I want to check if it is working properly. I hold an iterator to a node and then I deleted this node, now I want to verify that this iterator points to something that doesn't exist anymore. How can I write a test to verify this? While I was searching the net I found something about boost libraries and test libraries. Below there is a minimal example of what I am saying.

#include<iostream>
struct Node{
    Node* back;
    Node* front;
    int data;
}Node;

int main(int argc, char* argv[])
{
    Node* a = new Node;
    Node* b = a;
    delete a;

    //HOW TO CHECK IF THE NODE THAT I ALLOCATED, HAVE BEEN DELETED?
}
chaviaras michalis
  • 356
  • 2
  • 15
  • 4
    Sounds like you could continue a bit with the web search you mentioned :) See also [here](https://stackoverflow.com/q/242926/9593596) – lubgr Jul 03 '18 at 10:49
  • 1
    Please show the implementation, so it will be easy for us to create examples of tests that match your code. Otherwise it would be just general advice - not really helpful, and not fit for SO. – BartoszKP Jul 03 '18 at 11:14
  • @BartoszKP I agree with what you say about the implementation that isn't provided but I write a scientific code and I don't want to provide it. Furthermore, my question was very simple how to see if a node of a list had deleted. Thank you for your comment. – chaviaras michalis Jul 03 '18 at 16:04
  • 1
    @chaviarasmichalis You don't have to provide your actual code, and as a matter of fact, you shouldn't. You should provide [MCVE](https://stackoverflow.com/help/mcve). As it stands, the question is off-topic, no matter how obvious you think it is. – BartoszKP Jul 03 '18 at 18:44
  • 1
    @chaviarasmichalis Also, if you write "scientific code", whatever that is, use a standard implementation of a list that's already available in C++, and focus on the domain logic - you're wasting time reinventing the wheel. – BartoszKP Jul 03 '18 at 18:45
  • @BartoszKP As I know there is no STL doubly linked and cyclic list. https://stackoverflow.com/questions/21649295/doubly-linked-cyclic-list-in-standard-library – chaviaras michalis Jul 04 '18 at 06:53
  • 1
    @chaviarasmichalis Right, sorry I've missed that the list must be doubly linked. What about https://www.boost.org/doc/libs/1_67_0/doc/html/intrusive/list.html ? If I'm not mistaken it's header only. – BartoszKP Jul 04 '18 at 08:00
  • Also, in the code example you've posted you are essentially asking to test whether the compiler did the right thing. This doesn't make sense - you should test your code, not the compiler. If you call `delete x;`, you should safely assume that `x` will be properly deleted, and its destructor called. – BartoszKP Jul 04 '18 at 10:48
  • @BartoszKP The test will be in another file, also the node that will be deleted it is not something trivial. It is founded by an algorithm. I just wanted to show that what I am interested in is to check whether a specific piece of memory has been freed. – chaviaras michalis Jul 04 '18 at 14:06
  • 1
    @chaviarasmichalis So you want to test a piece of code that identifies the node to be deleted, not whether `delete` actually deletes the node and frees memory. If you really want to talk about unit-testing. – BartoszKP Jul 05 '18 at 08:50
  • @BartoszKP Yes. – chaviaras michalis Jul 05 '18 at 09:46
  • @chaviarasmichalis Try proceeding as follows, in a top-bottom manner, creating tests with only three lines each: first line: `auto given = aList(withNodes(node(1), node(-3)));` second line: `Node* result = whenIdentifyingNodeToDelete(given);`, third line: `assertEqual(result->data, -3);`. Then go and implement the details of each utility method. And of course start with a simplest case, i.e. `auto given = aNullNode();` then `auto given = aListWithNodes(Node(0));`, sequentially describing the desired behaviour of the algorithm - from trivial to complex cases. – BartoszKP Jul 05 '18 at 11:04
  • This way your tests are focused on describing logic, and the technical details of how to actually create a list, or what it means to identify the node to delete can be hidden in the utility methods. Of course fix the names to describe what they should do better - mine are just examples. – BartoszKP Jul 05 '18 at 11:06

3 Answers3

0

Unit tests are mostly compose of three parts; Arrange, Act and Assert.

  • In Arrange part you create your list.
  • In Act part you use your delete operator
  • In Assert part you compare the result with an expected value.

My favorite C++ Unit Test Framework is Google Test, you can find a very good tutorial here for the framework.

eneski
  • 1,575
  • 17
  • 40
0

Usually accessing an invalidated iterator would be undefined behaviour, or it would be when using standard-library containers at least.

Unless your container has some specific additionaly functionality to track whether an iterator is still valid or not, I would suggest using a different method to ensure the node has been deleted, for example by testing that the nodes originally before and after the deleted node now point to each other rather than to the deleted node.

If you want to actually test that the node has been freed, and the memory that contained it has not been leaked, then personally I would do this by running the entire test suite under Valgrind. This will track memory allocations and will produce warnings if you try to access memory out-of-bounds, if you leak memory, if you try to double-free, etc.

Valgrind can be configured to produce XML output, so you can have your test runner run the tests under Valgrind and automatically parse the output to ensure no leaks or other violations happened. Even if you find a way to test this specific case without Valgrind, it is always a good idea to make sure your test suite produces no errors when run under Valgrind, to catch any other mistakes you might have made.

Sean Burton
  • 907
  • 7
  • 15
  • If I test by the method you suggest by seeing before and after the deletion of a node, how can I see if the memory of the "deleted" node is leaked? – chaviaras michalis Jul 03 '18 at 14:59
  • Personally I would test that by running the test-suite under Valgrind, which will tell you if any memory-leaks have occurred. – Sean Burton Jul 03 '18 at 15:53
  • I do know about the valgrind but I want something more automated to add it in my unit test that I have implemented. – chaviaras michalis Jul 03 '18 at 16:02
  • You could do something involving overriding the `new` and `delete` functions to track allocations and test that no memory gets leaked, but that starts to get rather complicated and you're basically just reimplementing what Valgrind does anyway. You can always just have Valgrind produce XML output, and have your test runner automatically parse that to ensure no leaks happened. – Sean Burton Jul 03 '18 at 16:06
  • I am not so advanced to do what you say I think. Ok maybe I say a blander but is there a tool to check if a segmentation fault will happen and to stop it and print something to say that the test is passed? – chaviaras michalis Jul 03 '18 at 16:15
  • Again, I would use Valgrind. If you do something that might cause a segfault, such as accessing memory out of bounds, then because this is technically 'undefined behaviour' it is never guaranteed that the application will actually segfault. But Valgrind will catch many of these things and provide you with output showing exactly where they happened. – Sean Burton Jul 03 '18 at 16:26
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/174275/discussion-between-chaviaras-michalis-and-sean-burton). – chaviaras michalis Jul 03 '18 at 16:29
  • 2
    @chaviarasmichalis To avoid memory leaks just use automatic pointers (`unique_ptr` etc.) and stop focusing on low-level details. As suggested by Sean, use Valgrind to verify you don't have memory leaks and otherwise focus on the domain logic you need. – BartoszKP Jul 05 '18 at 11:20
  • 1
    Thank you very much @BartoszKP for all the information. You were very helpful I will read about the automatic pointers. – chaviaras michalis Jul 06 '18 at 07:45
0

You can deliberately trash or mark objects before you delete them so that their continued use would error quickly. This is not really a test tool, but is used to find bugs quickly rather than wait for corruption to eventually lead to a crash. You could zero an object, for example. In a doubly linked list the forward/backwards links in a deleted object that you have inappropriately retained a reference to should, therefore, be trashed. (If using pointers then it could be null. If using an index you may wish to fill the object with 0xFF) If you genuinely free the deleted item then it could have been reused. But I guess you could run this test before any further allocation has occurred. For debugging, it is your choice if the trashing is left in a release build. I would leave it in unless your dynamic list building is performance limited. It could, therefore, be used in a test too. Although I'm not sure I would always recommend this type of testing. To me the creation of a list of items and the deleting one and checking it is deleted would be enough. I would add leak tests too where I would repeat tasks such as delete numerous times and expect memory not to leak away.

William J Bagshaw
  • 558
  • 3
  • 15