PPP2 Chapter 17 Exercise 11

[DragonOsman]

Odin and Zeus were successfully erased from the gods list. I tried to erase them, but also tried to only put them into the dest list if there isn't already a God with the same name in there.

The erase() function properly removes the nodes. Should I use it together with delete, then? Erase and then delete the node?

What do you think this is telling you?

That I'm access something I shouldn't.

I'll look at the variables' values in a bit.

[jlb]

I'll look at the variables' values in a bit.

Okay then I'll answer your questions in a "bit" as well.

[DragonOsman]

Okay. "head" and the current node's previous pointer are both pointing at Amaterasu and "tail" is 0xDDDDDDDD. It's what's causing the read access violation. Current node is Bishamonten and next pointer is pointing at Izanagi. Susanoo was deleted. I have to adjust the next and previous pointers as necessary and then delete the node. I forgot.

Edit: Is this about the right idea?

Link *gods_trav = gods->find("Susanoo");
gods_trav = gods_trav->previous();
delete gods->find("Susanoo");
gods_trav->next() = nullptr;

Either way, though, I get a compiler error saying that the expression must be a modifiable lvalue, on the gods_trav->next() = nullptr; line. How do I change the pointer, then?

[jlb]

I'll answer your questions in a "bit", after you answer all of the questions I asked earlier today.

[DragonOsman]

I need to answer these questions, right?

An even better question is why does your gods Link contain the same gods as your jap gods Link? I would expect the gods Link, after glancing at your latest code dump, to have Odin, Zeus, and Amaterasu. And how many news do you have, and how many deletes doe your have? Oh and why are you trying to delete gods, norse_gods, greek_gods, and jap_gods?

For this:

An even better question is why does your gods Link contain the same gods as your jap gods Link? I would expect the gods Link, after glancing at your latest code dump, to have Odin, Zeus, and Amaterasu.

As I had said before, what I'd tried to do was to first just erase the node from the gods list and then compare its name string with one already in the list to check if I'm inserting a duplicate node.

And how many news do you have, and how many deletes doe your have?

15 news and 16 deletes. I don't get it, though. Why is there one extra delete?

Oh and why are you trying to delete gods, norse_gods, greek_gods, and jap_gods?

I thought I needed to delete the main list as well. But if I need to have the same number deletes as the number of news, then never mind.

How about this (pseudocode):

Initialize temporary Link* object
find node with desired name in list
if Link* object is not NULL
delete node from list
erase() node form list

I'm thinking of making that a separate function and calling it with a name string for each "God" I want to delete. There reason I think it'd be good to delete it first is that it won't be in the list anymore if I erase() it first. If I understand the code correctly.

[DragonOsman]

I tried to do it like this:

gods->find("Susanoo")->erase();
delete gods->find("Susanoo");
gods->find("Izanagi")->erase();
delete gods->find("Izanagi");
gods->find("Bishamonten")->erase();
delete gods->find("Bishamonten");
gods->find("Amaterasu")->erase();
delete gods->find("Amaterasu");
norse_gods->find("Thor")->erase();
delete norse_gods->find("Thor");
norse_gods->find("Odin")->erase();
delete norse_gods->find("Odin");
norse_gods->find("Frejya")->erase();
delete norse_gods->find("Frejya");
norse_gods->find("Baldr")->erase();
delete norse_gods->find("Baldr");
greek_gods->find("Zeus")->erase();
delete greek_gods->find("Zeus");
greek_gods->find("Hera")->erase();
delete greek_gods->find("Hera");
greek_gods->find("Athena")->erase();
delete greek_gods->find("Athena");
greek_gods->find("Ares")->erase();
delete greek_gods->find("Ares");
jap_gods->find("Susanoo")->erase();
delete jap_gods->find("Susanoo");
jap_gods->find("Izanagi")->erase();
delete jap_gods->find("Izanagi");
jap_gods->find("Bishamonten")->erase();
delete jap_gods->find("Bishamonten");
jap_gods->find("Amaterasu")->erase();
delete jap_gods->find("Amaterasu");

But now I got a read access violation when trying to find() Amaterasu in the gods list. While trying to test if m_prev is NULL here:

Link *head = this;
while (head->m_prev)
{
	head = head->m_prev;
}

, head was 0xDDDDDDDD.

[DragonOsman]

And also please help me out with using std::unique_ptr with this. I'd rather just use RAII to clean everything up if I'm allowed to. I'll try to get the manual new and delete working here first, though.

[jlb]

As I had said before, what I'd tried to do was to first just erase the node from the gods list and then compare its name string with one already in the list to check if I'm inserting a duplicate node.

I've asked the following question several times but you have always failed to answer the question so please answer the following question:

Why do you have any duplications in the first place?

15 news and 16 deletes. I don't get it, though. Why is there one extra delete?

You wrote the code, so why the mismatch? I count 12 gods in your various links, so why so many deletes?

I thought I needed to delete the main list as well.

Why would you think this?

[DragonOsman]

Duplications are to be expected when I have to use Links to initialize norse_gods, greek_gods and jap_gods, right? And besides, if I initialize them to nullptr, calling move_nodes() on them crashes the program, and I don't know how to fix it.

There are 12 gods, but 15 news. There are extra three news for the initialization of norse_gods, greek_gods and jap_gods, each, respectively. And I have one extra delete because I tried to delete the Japanese gods that remained in the gods list. I think.

Why would you think this?

As for why I'd think that, I'm not sure. Maybe I had a brain fart.

[jlb]

Duplications are to be expected when I have to use Links to initialize norse_gods, greek_gods and jap_gods, right?

No, why do you think you need to initialize your Link with a value? Wouldn't initializing the Link with a nullptr be a better option?

And besides, if I initialize them to nullptr, calling move_nodes() on them crashes the program, and I don't know how to fix it.

Then I suppose you should strive to fix this issue before you try to worry about deleting the memory. Because if you don't you're probably never going to be able to figure out how to properly delete the memory.

And I have one extra delete because I tried to delete the Japanese gods that remained in the gods list.

Why do you think you would need to delete those gods in the gods Link? If your move is working properly there should be no gods left in that Link.

As for why I'd think that, I'm not sure. Maybe I had a brain fart.

To ascribe the problem to a "brain fart" you would first need to understand what you're doing. IMO you're so lost that maybe you should just move on and consider this part of this exercise a failure.

[helios]

I would have to agree with that last statement.

[DragonOsman]

@jlb: I tried to add different behavior in move_nodes for when the Link I'm trying to add a node to is NULL, but it kept going to the "else" for the condition that the Link is NULL even when there already should've been a node there. I'll try it again and show you the code.

[DragonOsman]

This is what I tried to do:

Link *norse_gods = nullptr;
Link *greek_gods = nullptr;
Link *jap_gods = nullptr;

while (gods->find_if_myth("Norse"))
{
	move_nodes(norse_gods, gods, "Norse");
}
while (gods->find_if_myth("Greek"))
{
	move_nodes(greek_gods, gods, "Greek");
}
while (gods->find_if_myth("Japanese"))
{
	move_nodes(jap_gods, gods, "Japanese");
}

void move_nodes(Link *dest_list, Link *source_list, const std::string &myth)
{
	Link *trav = source_list->find_if_myth(myth);
	if (trav)
	{
		trav->erase();
		dest_list = dest_list->add_ordered(trav);
	}
}

For some reason, even after this returned, jap_gods, norse_gods and greek_gods are still NULL even though I can see that the node I tried to insert is already in the dest_list Link. Is it because I'm not returning anything from this function? Or is there some other reason?

[jlb]

How is that last snippet significantly different from the code you had in your last code dump? The only thing I see different is it is missing an inconsequential if() statement in the previous dump.

are still NULL even though I can see that the node I tried to insert is already in the dest_list Link.

How can you tell?

What exactly are you looking at and when?

[DragonOsman]

I look at my dest_list Link on "Watch" in my debugger and I see that it has Odin and Thor in it when the myth string is "Norse", but that it still keeps moving Odin into it over and over again. The norse_gods Link also has Odin and Thor in it after the second call to move_nodes (within the loop, I mean), but it still keeps inserting Odin into the norse_list Link.

I took out the "inconsequential" if-condition because I noticed that it wasn't needed. But I'm not sure what else to do.

This what I have now:

Link *move_nodes(Link *dest_list, Link *source_list, const std::string &myth)
{
	Link *trav = source_list->find_if_myth(myth);
	if (trav)
	{
		if (trav->god().m_myth == myth)
		{
			trav->erase();
			if (trav->god().m_myth == myth)
			{
				dest_list = dest_list->add_ordered(trav);
			}
		}
	}
	return dest_list;
}

[jlb]

This what I have now:

That's nice, not even going to comment on that throw at this time.

I look at my dest_list Link on "Watch" in my debugger and I see that it has Odin and Thor in it when the myth string is "Norse"

As I guessed, you're not looking at the correct part of the data, remember that the name and myth are really not that important, it's the rest of the data.

This part of the program is all about pointers, what those pointers are actually pointing to are secondary.

[DragonOsman]

I just looked at source_list, source_list->m_succ, source_list->m_succ->m_succ, trav->m_succ, source_list->m_prev, dest_list, dest_list->m_succ, dest_list->m_prev, and trav. There's something really weird going on there. When Thor is inserted into dest_list while myth == "Norse", dest_list->m_succ is already Zeus. But trav->m_succ is also Zeus. dest_list just got Zeus inserted into it, dest_list's current node is Bishamonten and next node is Frejya. Previous node is Baldr. In source_list, the next node after Frejya is Hera. And now it's stuck in an infinite loop because each time around the loop in main(), trav in move_nodes() is always Odin (after Thor is inserted).

I wonder if trav->erase() is a problem and I should really do [trav = trav->erase()[/code]. And there's also the return type of move_nodes(). But changing them also creates problems.

Edit: And before I forget: dest_list->m_prev is Susanoo.

[jlb]

I just looked at source_list, source_list->m_succ, source_list->m_succ->m_succ, trav->m_succ, source_list->m_prev, dest_list, dest_list->m_succ, dest_list->m_prev, and trav.

Where are you looking at those pointers?

And now it's stuck in an infinite loop because each time around the loop in main(), trav in move_nodes() is always Odin (after Thor is inserted).

Sounds like maybe something is not really being inserted.

By the way what is your find() function returning in main() if the "find" fails?

I wonder if trav->erase() is a problem and I should really do [trav = trav->erase()[/quotejavascript:editbox1.editTag('output')]
Why are you wondering? Did you step into that function and watch the pointers as you step through the function?

[quote]And there's also the return type of move_nodes(). But changing them also creates problems.

[sarcasm] Yea, this is a really really good problem description.[/sarcasm]

Edit: And before I forget: dest_list->m_prev is Susanoo.

Okay, so what? Without any content as to where and when just posting some value is worthless. And as I have said this is all about pointers, names are really not relevant.

You need to follow the pointers starting in main() right after you populate the gods Links.

Do you understand that this is a problem that is probably being caused by a subtle pointer problem? Remember this is not a Linked List, it is just a collection of Links and because of this fact this program is very difficult to correctly troubleshoot. IMO, just using the debugger is not enough. Along with the debugger you should be printing the values out in multiple places, possibly to a "log" file so you can flip back and forth between locations to see what is really happening.

[DragonOsman]

I'm looking at the pointers in just the move_nodes() function. I return nullptr if any of my Link finding functions fail. Because I'm checking for NULL when I call them.

As for when I'm saying dest_list->m_prev is that, I'm talking about when I try to insert Odin into dest_list. I mean there's one Link before and one Link after in there already when I try to do that.

[jlb]

I'm looking at the pointers in just the move_nodes() function.

What good does this do you? What if the actual problem occurs before this function?

By the way I see you've moved on as I suggested several posts ago so this will be my last post in this topic.