[Home] [Downloads] [Search] [Help/forum]

Gammon Forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  Programming
. -> [Folder]  General
. . -> [Subject]  Complex problem, long time pain
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?

Complex problem, long time pain

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Posted by Trom   (82 posts)  [Biography] bio
Date Thu 11 May 2006 07:17 PM (UTC)

Amended on Thu 11 May 2006 07:24 PM (UTC) by Trom

Message
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.
[Go to top] top

Posted by Nick Gammon   Australia  (21,321 posts)  [Biography] bio   Forum Administrator
Date Reply #1 on Thu 11 May 2006 08:26 PM (UTC)

Amended on Sun 14 May 2006 02:24 AM (UTC) by Nick Gammon

Message
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
  }



- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Trom   (82 posts)  [Biography] bio
Date Reply #2 on Sat 13 May 2006 09:55 PM (UTC)
Message
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).
[Go to top] top

Posted by Nick Gammon   Australia  (21,321 posts)  [Biography] bio   Forum Administrator
Date Reply #3 on Sat 13 May 2006 10:53 PM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Trom   (82 posts)  [Biography] bio
Date Reply #4 on Sun 14 May 2006 01:25 AM (UTC)

Amended on Sun 14 May 2006 01:28 AM (UTC) by Trom

Message
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.
[Go to top] top

Posted by Nick Gammon   Australia  (21,321 posts)  [Biography] bio   Forum Administrator
Date Reply #5 on Sun 14 May 2006 02:25 AM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Trom   (82 posts)  [Biography] bio
Date Reply #6 on Tue 06 Jun 2006 01:22 PM (UTC)
Message
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.
[Go to top] top

Posted by Nick Cash   USA  (626 posts)  [Biography] bio
Date Reply #7 on Tue 06 Jun 2006 04:44 PM (UTC)
Message
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 );
}

~Nick Cash
http://www.nick-cash.com
[Go to top] top

Posted by Trom   (82 posts)  [Biography] bio
Date Reply #8 on Tue 06 Jun 2006 06:07 PM (UTC)

Amended on Tue 06 Jun 2006 06:12 PM (UTC) by Trom

Message
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?
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #9 on Tue 06 Jun 2006 09:04 PM (UTC)
Message
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.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (21,321 posts)  [Biography] bio   Forum Administrator
Date Reply #10 on Tue 06 Jun 2006 10:02 PM (UTC)
Message
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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Trom   (82 posts)  [Biography] bio
Date Reply #11 on Tue 06 Jun 2006 10:02 PM (UTC)
Message
would you be able to give an example of what you meant?
[Go to top] top

Posted by Nick Gammon   Australia  (21,321 posts)  [Biography] bio   Forum Administrator
Date Reply #12 on Tue 06 Jun 2006 10:06 PM (UTC)
Message
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 Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by Nick Cash   USA  (626 posts)  [Biography] bio
Date Reply #13 on Wed 07 Jun 2006 10:20 PM (UTC)
Message
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.

~Nick Cash
http://www.nick-cash.com
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


8,332 views.

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at FutureQuest]