This forum is a read-only archive of the Gammon Software forum (2000–2026). No new posts can be made. Search the archive.

Complex problem, long time pain

Posted by Trom on Thu 11 May 2006 07:17 PM — 14 posts, 45,456 views.

Trom #0
This problem has been nagging me for a long while now. This will also be somewhat hard to explain, but was probably done before many times (my guess).

This is using rom/rot's codebase, so the structures for pointers and so on apply the same way.


/* something along these lines */

typedef the_data THE_DATA;
struct the_data {
  // variables
};
struct char_data {
  THE_DATA *linklist;
};




THE_DATA *temp;
temp = ch->linklist
while ( temp != NULL )
  temp = temp->next;
temp = memoryallocation;
temp->value = 20;
/* this would put the value 20 into the last object in the 'linklist' found in 'ch'. */


The above is pseudocode obviously. The goal is to add a new object to a linklist thats within a linklist. The next part of this is doing all this through another variable (as shown with 'temp'). The above code doesn't work because temp is just a copy. I've never actually learned c language through books or schooling so i maybe missing something thats easy for the rest.

Help would be appreciated.
Amended on Thu 11 May 2006 07:24 PM by Trom
Nick Gammon Australia Forum Administrator #1
You have found the end of the linked list but then thrown it away by doing a memory allocation into temp. You need another variable:


THE_DATA * temp = ch->linklist;  // start (first element) of existing list
THE_DATA * new_item = malloc (sizeof THE_DATA);  // new element for list

new_item->value = 20;  // put data into new element
new_item->next = NULL;  // end of the list now

// now insert into list


if (temp == NULL)   // empty list is special case
  ch->linklist = new_item;
else
  {
  while ( temp->next != NULL )
    temp = temp->next;
  temp->next = new_item;  // put new_item at end of existing list
  }

Amended on Sun 14 May 2006 02:24 AM by Nick Gammon
Trom #2
I used the above but at the very end in the final else statement i assigned it not to ->next but to the variable itself. The mud compiles and runs but doesn't save values. I added a function to just display all the values in the list when the character types a command, it says the 2 values for the linklist are both 0 (which is default).
Nick Gammon Australia Forum Administrator #3
Quote:

I used the above but at the very end in the final else statement i assigned it not to ->next but to the variable itself.


Why did you do that? That won't work.
Trom #4
When i did that, it crashed the mud with segmentation fault error. After the removal of ->next it didn't crash, rom or c language itself seems to be very picky about playing with null structures.
Amended on Sun 14 May 2006 01:28 AM by Trom
Nick Gammon Australia Forum Administrator #5
Ah I see the problem. My loop went one too far. I have changed the post above (part in bold) to stop when temp->next isn't null. That should fix it.
Trom #6
Okay i've returned to this same thing again. The code suggestions helped to avoid crashing but i'm still getting a problem with it sticking. The structures are null (not remaining on the linklist).



/* struct char_data {
**   LL_DATA *linklist;  
*/ }

do_something ( CHAR_DATA *ch ) {
  LL_DATA *new_obj = malloc ( sizeof(LL_DATA) );
  LL_DATA *all_objs = ch->linklist;

  new_obj->value = 10;
  new_obj->next = NULL;

  if ( all_objs != NULL ) {
    while (all_objs->next != NULL) {
      all_objs = all_objs->next;
    }
    all_objs->next = new_obj;
  }
  else {
    all_objs = new_obj;
  }  

  return;
}


The above code is a summarization of what i have going on in generalistic variable names. After doing this ch->linklist remains completely null.
Nick Cash USA #7
I think the problem in your code is here:

  else {
    all_objs = new_obj;
  }

all_objs is a local pointer variable that will be thrown away when the function exits. What you need to do is:

else
{
  ch->linklist = new_obj; /* make sure to set the pointer in the struct instead of the local one */
}

That should get the list started, and the other code looks like it should work.


On the other hand, why not just add the object to the front of the list? Then you can avoid the while loop and a special case for the first obj.

To do that, you might have:

void do_something ( CHAR_DATA *ch, char* arg )
{
  LL_DATA *new_obj = malloc ( sizeof(LL_DATA) );

  new_obj->value = 10;

  /* add to list */
  new_obj->next = ch->linklist;
  ch->linklist = new_obj;

  return;
}


Far simpler for the same effect.

Similarly, you could take a bit of the work out of it (with special cases and what not) and use the default SMAUG set up for doubly linked lists. A small example would be (using a bit from your example):

 /* in the char_data struct */
 LL_DATA* first_link;
 LL_DATA* last_link;

 /* in the LL_DATA struct */
 LL_DATA* next;
 LL_DATA* prev;

void do_something( CHAR_DATA *ch, char* arg )
{
  LL_DATA* data = malloc( sizeof(LL_DATA) );

  data->value = 10;

  LINK( data, ch->first_link, ch->last_link, next, prev );
}
Trom #8
The way you corrected it using the add to the end method would only replace the object each time a new one is added (meaning it holds only one object). My plan is to allow it to add numerous objects in a link list without a defined end (which is why i'm putting emphasis on linklists).

As for the smaug way, i'm using rom. I could probably change it around like that but i also don't like how it uses global variables. Also i've been working on this for a while, if i can get this to work its mostly done as is (smaug way would require redoing a lot of things).

Anyways i thought it was possible to do it this way, or is it not possible to add an object to the end of a linklist, thats inside a structure (ch->linklist).

According to whiteknights suggestion:

LL_DATA *linklist = ch->linklist;


the above probably makes a copy of it and the copy goes away when the function is done. If that is true then, how is it possible to make a direct link to 'ch->linklist' using a pointer variable?
Amended on Tue 06 Jun 2006 06:12 PM by Trom
David Haley USA #9
Actually, Whiteknight's code does pretty much what you want it to do. It does add the object to the beginning, and not the end; it does that for efficiency reasons. But it doesn't replace anything or any of that bad stuff.

Quote:
According to whiteknights suggestion:
LL_DATA *linklist = ch->linklist;

the above probably makes a copy of it and the copy goes away when the function is done. If that is true then, how is it possible to make a direct link to 'ch->linklist' using a pointer variable?


This only copies the pointer; it doesn't copy the whole linked list at all. If you make modifications to this pointer, you will be changing the original list. The only thing you can't do this way is change the address of the original pointer by changing the address of the copied pointer.
Nick Gammon Australia Forum Administrator #10
Quote:

The code suggestions helped to avoid crashing but i'm still getting a problem with it sticking. The structures are null (not remaining on the linklist).


Well, you are not doing what I suggested so I am not surprised it doesn't work. My code had these lines:


if (temp == NULL)   // empty list is special case
  ch->linklist = new_item;
else


The middle line, in bold, changes the ch->linklist, thus the new structure appears in the list.

Your code:


else {
    all_objs = new_obj;
  }


This modifies a *copy* of ch->linklist, not ch->linklist itself. Won't work.

Let me give you an example:



a = 5

b = a

b = b + 1


Now you ask why isn't "a" equal to 6? Because you have made a copy of "a" and changed the copy.

Quote:

The way you corrected it using the add to the end method would only replace the object each time a new one is added (meaning it holds only one object). My plan is to allow it to add numerous objects in a link list without a defined end (which is why i'm putting emphasis on linklists).


No, try using my method and see what happens. I understand linked lists very well, and my method will add a new item to the end of the list, which can be indefinitely long.
Trom #11
would you be able to give an example of what you meant?
Nick Gammon Australia Forum Administrator #12
Whiteknight's suggestion is indeed faster (for long lists) and has the characteristic that new items will appear at the head of the list. My method will put them at the end. Both will work, depends if you want to add to the head or the tail.
Nick Cash USA #13
Quote:

I could probably change it around like that but i also don't like how it uses global variables.


It doesnt. I was just giving an example. The comments were there to tell you what struct those particular variables would have been in.