Problems with pointers for "Linked Lists"

Hello everyone,

I have spent a good afternoon trying to work this one out!

Basically, I’m trying to create an XML data structure using a Link-list with a “parent” property for each element.

The problem that I am having is that the structures “Node_1”, “Node_2” and “Node_3” are not being changed in the “AddNode” function.

The one thing that keeps letting me down is that the “parent” property is not remembering which element it is assigned.

desired output:

Program Finished Running
</PrintList node=“First” Next=“second” Parent="">
</PrintList node=“second” Next=“third” Parent=“First”>
</PrintList node=“third” Next="" Parent=“First”>

However, the “Parent” properties are not returning any data.

#include <stdio.h>

// Library to support string opperation
#include <string.h>

struct XML_Node{
  char *name;
  char *data;
  struct XML_Node *previous;
  struct XML_Node *next;
  struct XML_Node *parent;
};

struct XML_Node *RootNode;
struct XML_Node *LastNode;

 struct XML_Node Node_1; 
 struct XML_Node Node_2;
 struct XML_Node Node_3;
  
  
/************************************************/

void setup(){

  Serial.begin(9600);

  RootNode = LastNode = NULL; //Initialise start and finish pointers

}
void loop(){

  /*****************************************************************/

  char str_Name[] = "First";
  char str_Name2[] = "second";
  char str_Name3[] = "third";
  char str_Data[] = "Test Data";

  AddNode(&Node_1, NULL, str_Name, str_Data, &RootNode, &LastNode);

  AddNode(&Node_2, &Node_1, str_Name2, str_Data, &RootNode, &LastNode);
  
  AddNode(&Node_3, &Node_1, str_Name3, str_Data, &RootNode, &LastNode);
  
 
  /*****************************************************************/
  StopProgram(0);
}
/*Create a new XML node*/
void AddNode(struct XML_Node *i,   //New element >>
struct XML_Node *ParentNode,       //points to parent node
char *NodeName, char *NodeData,    //pointers to the name and data
struct XML_Node **RootNode,        //first element on list
struct XML_Node **LastNode) {      //Last element on list

  struct XML_Node *old, *p;
    if(!RootNode) Serial.print("<!--ERROR: RootNode-->\n");
    if(!LastNode) Serial.print("<!--ERROR: LastNode-->\n");
    if(!NodeName || !NodeData) Serial.print("<!--ERROR: Input Strings-->\n");
    
  i = (struct XML_Node *)malloc(sizeof(struct XML_Node));
  if(!i) {
    return;  //if memory allocation didn't work, return error
  }

  i->name = NodeName;  //Store data and name locations
  i->data = NodeData;

  if(!*LastNode) { //if empty list, root element 
    Serial.print("<!--Creating Root Element-->\n");
    i->next = NULL;
    i->previous = NULL;
    i->parent = NULL;

    *LastNode = i;
    *RootNode = i;

    return;
  }
  Serial.print("<!--Creating non-root Element-->\n");  
  if(!ParentNode) Serial.print("<!--ERROR: ParentNode-->\n");
  
  //Start at top of list
  p = *RootNode;
  old = NULL;

  while(p){ //find last element
    old = p;
    p = p->next; 
  }

  old->next = i; //put on end
  i->next = NULL;
  i->previous = old;
  i->parent = ParentNode;
  
  *LastNode = i;
  
}

/*Prints out to screen the list tree, starting at "StartNode"*/
void PrintTree(struct XML_Node *StartNode) {

  if(!StartNode) return;

  struct XML_Node *info;

  info = StartNode;

  while(info) {

    Serial.print("</PrintList node=\"");  
    Serial.print(info->name); 
    Serial.print("\" Next="); 
    Serial.print("\""); 
    Serial.print(info->next->name); 
    Serial.print("\"");
    Serial.print(" Parent="); 
    Serial.print("\""); 
    Serial.print(info->parent->name); 
    Serial.print("\"");
    Serial.println(">");

    info = info->next;
  }

}

inline void StopProgram(char Position){
  if(Position) Serial.println(Position, HEX);
  Serial.println("\nProgram Finished Running");
  PrintTree(RootNode);
  for(;;); 
}

Any help would be very appreciated.

:slight_smile:

Hey again,

I've worked out that the program works when "Node_1", "Node_2" and "Node_3" have their names and data pointers set outside the function AddNode().

ie.

AddNode(&Node_1, NULL, str_Name, str_Data, &RootNode, &LastNode);

  Node_1.name = str_Name; Node_1.data = str_Data;

This means that the problem is in the connection between the structures "Node_x" and the structure pointed to in AddNode()...

Question: - If the function can change the value of the pointers for next and previous, why can't it change the pointers for name and data?...

Any ideas?

Hey all,

I worked the problem out!!!

The problem was in the malloc().

The malloc() was there before the subroutine, when Node_x was a pointer, not literal XML_Node. The Nodes where changed, but (for some unknown reason) I have kept the memory request in and overlooked it for hours at a time.

What was happening (for all those playing at home) was that the malloc() was over riding *i as a new entry.

:)

InvalidApple,

Glad you figured out your problem. There is another potential problem in your program, though.

In loop(), you declare the arrays str_Name, str_Name2, and then initialize them with strings. You then pass those arrays as pointers to AddNode(). Your AddNode function allocates space for a structure and puts those pointers in the structure. So far, so good. However, if loop() ever exits (it doesn't in the example you gave) those pointers are no longer valid. When you declare variables inside a function, they are by default "automatic" variables, which means they are on the stack, and only exist until the function exits.

One solution would be to add the modifier "static" to the declarations:static char str_Name[] = "First";etc.

A better solution would be for AddNode() to allocate space for the string, copy the string passed to it into the allocated space, and put the pointer to the allocated space into the structure.

Regards,

-Mike

Thanks Mike,

“Great minds think alike”, as I had added that property before finishing up last night.

It’s good to see that people are playing at home!

Here is what I ended up with:

/*******************************************************************
 * Program Name: Create XML Node
 * Author: LDU (2010)
 *
 * Language: Arduino C/C++
 * 
 * Copywrite: Beerware
 * (If you like the program feel free to use it-
 * And if you meet me in a pub some time, you can
 * buy me a beer.)
 *
 * Description:
 * Creates a list that can be used to create, insert, delete and
 * modify an XML file.
 * 
 * -A list element is inserted at the end by using AddNode();
 * -The list created is printed by PrintTree();
 * -The program is stopped with StopProgram().
 * 
 ********************************************************************/
/********************************************************************
 * Included headers
 ********************************************************************/
#include <stdio.h>
#include <string.h>
/********************************************************************/

/********************************************************************
 * Global structures
 ********************************************************************/
struct XML_Node{
  char *name;
  char *data;
  struct XML_Node *previous;
  struct XML_Node *next;
  struct XML_Node *parent;
};
/********************************************************************/

/********************************************************************
 * Global Variables
 ********************************************************************/
struct XML_Node *RootNode; //List 1 start & finish
struct XML_Node *LastNode;

/************************************************/

/************************************************/

void setup(){

  Serial.begin(9600);

  RootNode = LastNode = NULL; //Initialise start and finish list pointers

}
void loop(){

  /*****************************************************************/
  struct XML_Node Node_1; 
  struct XML_Node Node_2;
  struct XML_Node Node_3;

  static char str_Name[] = "First";
  static char str_Name2[] = "second";
  static char str_Name3[] = "third";
  static char str_Data[] = "Test Data";

  AddNode(&Node_1, NULL, str_Name, str_Data, &RootNode, &LastNode);

  AddNode(&Node_2, &Node_1, str_Name2, str_Data, &RootNode, &LastNode);

  AddNode(&Node_3, &Node_2, str_Name3, str_Data, &RootNode, &LastNode);

  StopProgram(0);

  /*****************************************************************/
}

/*******************************************************************
 * Create a new XML node
 ********************************************************************
 * Format:
 * AddNode(Element As *XML_Node, Parent Node As *XML_Node,
 * Name As *char, Data As *char, List Root Element As **XML_NODE,
 * Lists Last Node As **XML_Node) Handles creating a new XML element
 ********************************************************************/
void AddNode(struct XML_Node *i,   //New element >> (i)nput
struct XML_Node *ParentNode,       //points to parent node
char *NodeName, char *NodeData,    //pointers to the name and data
struct XML_Node **RootNode,        //first element on list
struct XML_Node **LastNode) {      //Last element on list

  struct XML_Node *old, *p;

  //If there is an input error, exit function
  if(!RootNode || !LastNode|| !NodeName || !NodeData) return;

  i->name = NodeName;  //Store data and name locations
  i->data = NodeData;

  if(!*LastNode) { //if empty list, this is the root element 

    i->next = NULL;        //Setup information for element
    i->previous = NULL;
    i->parent = NULL;

    *LastNode = i;        //Setup infomation for list
    *RootNode = i;

    return;
  }

  //At this point, if there is no Parent, do not
  //make node- exit function
  if(!ParentNode) return;

  //Start search at top of list
  p = *RootNode;
  old = NULL;

  while(p){ //find last element
    old = p;
    p = p->next; 
  }

  old->next = i;         //put on end
  i->next = NULL;        //Setup informaiton for element
  i->previous = old;
  i->parent = ParentNode;

  *LastNode = i;         //Setup information for list

}

/*****************************************************************
 * Prints out to screen the list tree, starting at "StartNode"
 *****************************************************************/
void PrintTree(struct XML_Node *StartNode) {

  //if no input, exit right away
  if(!StartNode) return;

  struct XML_Node *info;  //point to start of printing
  info = StartNode;    

  while(info) {           //Go through list in order and print

    Serial.print("</PrintList node=\"");  
    Serial.print(info->name); 
    Serial.print("\" Next="); 
    Serial.print("\""); 
    Serial.print(info->next->name); 
    Serial.print("\"");
    Serial.print(" Parent="); 
    Serial.print("\""); 
    Serial.print(info->parent->name); 
    Serial.print("\"");
    Serial.println(">");

    info = info->next;
  }

}
/*****************************************************************/

/*****************************************************************
 * Stop program is used for stopping the program and displaying 
 * final values
 *****************************************************************/
inline void StopProgram(char Position){

  //if a location specifier given, print it
  if(Position) Serial.println(Position, HEX);  

  //prompt user 
  Serial.println("\nProgram Finished Running");

  //print results
  PrintTree(RootNode);

  //hold program here
  for(;;); 
}
/*****************************************************************/

All the best.

IA,

Yup, glad I bought the "Home Edition" so I could play along with you in the studio.

I forgot to mention that Node_1, Node_2, and Node_3 should also be static for the same reason.

Regards,

-Mike

Mike,

When the loop goes around for a second time, I think that a reallocation of memory for the structures would be an interesting problem.

I suppose that I am still getting used to the loop() function in place of main().