I've been making a doubly linked list and the while statements are going a bit wonky. I'm sure there's a simple explanation, but I'm not seeing it. Can anyone help?
This is working (Embarcadero RAD studio 11.1 - C Builder - Classic compiler (not Clang))
TDoubleLinkedNode* __fastcall TDoubleLinkedList::CreateNode ( int ID
, UnicodeString Name
)
{
// use "malloc" (or "new") to create the node in the heap
// it won't be deleted automatically when the function goes out of scope
// return the pointer to the structure
// let the calling function set PriorNode & NextNode
struct TDoubleLinkedNode* ReturnNode = (struct TDoubleLinkedNode*)malloc(sizeof(struct TDoubleLinkedNode));
ReturnNode->ID = ID;
ReturnNode->Name = Name;
ReturnNode->ptr_PriorNode = NULL;
ReturnNode->ptr_NextNode = NULL;
return ReturnNode;
}
void __fastcall TDoubleLinkedList::Add_ToEnd ( int ID
, UnicodeString Name
)
{
struct TDoubleLinkedNode* newNode = CreateNode(ID,Name);
if(this->IsEmpty)
{
// Head Pointer has not been initialised. Set as newNode
this->FHeadNode = newNode;
// This is the first Record.
newNode->ptr_PriorNode = NULL;
newNode->ptr_NextNode = NULL;
return;
}
else
{
struct TDoubleLinkedNode* oldHeadNode = this->FHeadNode;
struct TDoubleLinkedNode* tempNode = this->FHeadNode;
do // keep iterating until a break statement is triggered
{
if (tempNode->ptr_NextNode == NULL) // terminate the do while statement
{
break;
}
tempNode = tempNode->ptr_NextNode; // Move to the "Next" record
}
while (true); // always repeat...
tempNode->ptr_NextNode = newNode;
newNode->ptr_PriorNode = tempNode;
newNode->ptr_NextNode = NULL;
}
}
However, if I replace
do
{
if (tempNode->ptr_NextNode == NULL)break;
}
while (true);
with
while (tempNode->ptr_NextNode != NULL)
{
tempNode = tempNode->ptr_NextNode ;
}
the while statement does not break when tempNode->ptr_NextNode == NULL
resulting in tempNode being set to NULL making the tempNode->ptr_NextNode = newNode
that follows fail (Since you can't assign data to a non existent object).
I have been stepping through and the while is definitely running when tempNode->ptr_NextNode == NULL , when my understanding is it shouldn't??
I'm sure this isn't the only area that's messed up (there's quite a few while statements). I'm adding 6 test records and only able to retrieve 5! so it's obvious something is up. If you can shed some light on what I'm not understanding I'd be grateful
thanks, J
CodePudding user response:
I haven't used CBuilder for some 20 years, but if what you say is exactly what happens, if replacing that 'do while' loop to that 'while' changes the behavior, and you can clearly see that crazy thing occurring when you are stepping through it, it also seems illogical to me.
I don't know how it is now, but there in the beginning of the century, since C Builder has a lot of complicated links with Object Pascal libraries, it was not so uncommon to reach very strange situations, with crazy things happening in debug. What used to help was to do a "rebuild all", possibly removing all temporary files I could find in the project.
Maybe it helps.
And I also support our colleagues' comments regarding updating your code to use more appropriate C alternatives, much simpler and efficient ones, if possible (I know sometimes you can be working on legacy software which may not be easy to update).
And it is actually also very likely you are seen undefined behavior due to corrupted content, as people also said in comments. That only you can determine.
Update: I've just seen the other answer here just posted by Remy Lebeau, and I would like to add he is right regarding the bad use of malloc. Searching google I see that UnicodeString seems to be an object from Object Pascal, is it? Really seems a non-POD and you will run into trouble anyway, don't use malloc for C objects.
CodePudding user response:
Your while
loop code is fine (though coded oddly, and inefficiently).
Chances are, you are invoking undefined/illegal behavior elsewhere in the code, and that is likely affecting the while
loop as a side effect.
For instance, DO NOT use malloc()
/free()
in C , use new
/delete
instead. Your TDoubleLinkedList
struct contains a Name
member that is clearly a non-POD class type, as it is being assigned a UnicodeString
value. That member's constructor will NOT be run when using malloc()
to allocate the TDoubleLinkedList
instance, thus invoking undefined behavior when the Name
parameter is assigned to the ReturnNode->Name
member.
That being said, you should get rid of CreateNode()
entirely, and instead add a proper constructor to TDoubleLinkedNode
itself, eg:
struct TDoubleLinkedNode
{
int ID;
UnicodeString Name;
TDoubleLinkedNode *ptr_PriorNode;
TDoubleLinkedNode *ptr_NextNode;
TDoubleLinkedNode(int id, UnicodeString name, TDoubleLinkedNode *priorNode = NULL, TDoubleLinkedNode *nextNode = NULL) :
ID(id),
Name(name),
ptr_PriorNode(priorNode),
ptr_NextNode(nextNode)
{
}
};
And then Add_ToEnd()
can be simplified:
void __fastcall TDoubleLinkedList::Add_ToEnd ( int ID,
UnicodeString Name
)
{
TDoubleLinkedNode* newNode = new TDoubleLinkedNode(ID, Name);
if (!FHeadNode)
{
// Head Pointer has not been initialised. Set as newNode
FHeadNode = newNode;
return;
}
TDoubleLinkedNode* tempNode = FHeadNode;
while (tempNode->ptr_NextNode) {
tempNode = tempNode->ptr_NextNode; // Move to the "Next" record
}
tempNode->ptr_NextNode = newNode;
newNode->ptr_PriorNode = tempNode;
}
Which can actually be simplified much further:
void __fastcall TDoubleLinkedList::Add_ToEnd ( int ID,
UnicodeString Name
)
{
TDoubleLinkedNode** tempNode = &FHeadNode;
while (*tempNode) {
tempNode = &((*tempNode)->ptr_NextNode);
}
*tempNode = new TDoubleLinkedNode(ID, Name, *tempNode);
}
And more so if you add a FTailNode
member to your class:
void __fastcall TDoubleLinkedList::Add_ToEnd ( int ID,
UnicodeString Name
)
{
TDoubleLinkedNode **tempNode = (FTailNode) ? &(FTailNode->ptr_NextNode) : &FHeadNode;
FTailNode = new TDoubleLinkedNode(ID, Name, FTailNode);
*tempNode = FTailNode;
}
That being said, a better solution is to not create a linked list manually at all. Use the standard std::list
container in the <list>
header, eg:
#include <list>
struct TNodeData
{
int ID;
UnicodeString Name;
};
class TDoubleLinkedList
{
private:
std::list<TNodeData> FData;
public:
...
void __fastcall Add_ToEnd(int ID, UnicodeString Name);
...
};
void __fastcall TDoubleLinkedList::Add_ToEnd ( int ID,
UnicodeString Name
)
{
FData.push_back(TNodeData{ID, Name});
}