Archived

This topic is now archived and is closed to further replies.

psyjax

Saving linked lists in standard ANSI C

Recommended Posts

In my game I keep alot of the data in linked lists since they are easy to handle. For example, the various NPC's have a linked list used for storing the abilities they posses. Since abilities are generated in game, etc. Now, it's easy to save regular structures using fwrite(), but how do you save a linked list and preserve the links? The following is a sample of my structures:
//Stats type deffinitions


typedef struct StatsStructure StatsStructure, *StatsPtr;
typedef struct AbilityStructure AbilityStructure, *AbilityPtr;

//Ability structure


struct AbilityStructure
{
    //insert ability data here

    AbilityPtr  prevAbil;
    AbilityPtr  nextAbil;
};

//Stats structure


struct StatsStructure
{
    //insert various stats here. HP, Str, etc.

    AbilityPtr  firstAbil;
    AbilityPtr  lastAbil;
};
Basicaly, as the abilities are created they are stored within the sprite in a list. How would you store these linkages? Thanks [edited by - psyjax on January 16, 2004 9:54:07 PM]

Share this post


Link to post
Share on other sites
Interesting, I was thinking about this exact same problem last night. You can't just malloc a big chunk, load them all in and then fix up the pointers, because that would comprimise your ability to free single elements of the list.

I think the best way to do this is to count how many items, you have, then write that number to the start of the file. Next, loop through the list from beginning to end and write each item. This will put them in the same order in the file as they were in the list. Then, when you load them, you can read the count number, and re-create the list by loading it in order.

eg.


void save(const char* name)
{
int count = 0;
FILE* f = fopen(name, "wb");

AbilityPtr ptr = AbilityList;

while(ptr)
{
count++;
ptr = ptr->nextAbil;
}

fwrite(&count, 4, 1, f);

while(ptr)
{
fwrite(ptr, sizeof(AbilityStructure), 1, f);
ptr = ptr->nextAbil;
}

fclose(f);
}

void load(const char* name)
{
FILE* f = fopen(name, "rb");
int count;
fread(&count, sizeof(int), 1, f);

AbilityPtr ptr = malloc(sizeof(AbilityStructure));

while(count)
{
fread(ptr, sizeof(AbilityStructure, 1, f);
ptr->next = malloc(sizeof(AbilityStructure));
ptr->next->prev = ptr;
ptr = ptr->next;
count--;
}

fclose(f);
}


Of course, all of that is just off the top of my head, has not been compiled or tested and may have logic errors. But you should be able to get the basic idea.

I hope that helps!

Melekor

EDIT: [ code ] formating and [ i ] problems

[edited by - Melekor on January 16, 2004 10:52:41 PM]

Share this post


Link to post
Share on other sites
Two ways come to mind straight away.

1. Count items in list. Write count value. Write id and data for each ability.
2. Write id and data for an ability. Write 1 or 0 to indicate if list continues.

These are fairly simple, and both will work in this case.

When you try to save a large set of complex classes that each point to each other you have fewer options. If you need to save such a beast then you need to do something like the following.


when saving,

Clear your list of saved items.
For each class you''re about to write, check with your saved list.
If you don''t find it,
add it to the list. It''s position in this list is used when it''s next referenced.
Write the data for the class.
Else, you did find this object,
store it''s index.

when loading,

Clear list
If you have an index rather than data,
you use the list to find the pointer to the actual object.
else, you have data,
create a class,
add it to the list
read data for class

Share this post


Link to post
Share on other sites
Just write each item as-is, including the "next" pointer.

When loading, check if the "next" pointer is NULL. If so, stop loading (a NULL pointer writes correctly to disk on all CPUs you care about). If not, then allocate the next record, patch the next pointer to point to the next record, and read that from disk.

However, I''d much rather store an internal table with triplets like "entity property value" and key that on entityroperty, and use that to look up property values at runtime. To save, just write the entire table in one fell swoop. Or a few, if you implement the table as a rope. You can store the index/tree separately, or in-line, and re-generate after load.

Share this post


Link to post
Share on other sites
hplus

Your suggestion sounds intriguing. But I''m not familiar with the method you are talking about. Could you descripe a triplet, or rope, for me?

Perhapse some sample code?

Thanks.

Share this post


Link to post
Share on other sites
It''s simple. Traverse the list sequentially, writing each record to a buffer or file as you go.

So when you load it again, each record needs to be linked to the next one that comes in the file. All you have to do is put them in a temp array, and update all the pointers after loading.

Share this post


Link to post
Share on other sites
quote:
Original post by Promit
It''s simple. Traverse the list sequentially, writing each record to a buffer or file as you go.

So when you load it again, each record needs to be linked to the next one that comes in the file. All you have to do is put them in a temp array, and update all the pointers after loading.


I thought of that too, but on closer inspection, this will not work. Each element needs to be malloc()ed individually or else it will not be possible to free individual elements of the list.

Share this post


Link to post
Share on other sites
Well,

right now Im thinking about giving each element of the linked list a unique Id. Writting it with that, ID, as well as saving the order of the ID''s.

When realoading, I simply recreate all the elements by following the order of the ids, and reasigning the data.

Does this make sense?

Share this post


Link to post
Share on other sites
There isn''t much point in storing a pointer or a null pointer in a file. There''s no guaranteeing that the pointer will point to valid memory during the next invocation of the program - and a null pointer is just zero and will bloat your database.

Promit has the answer. Store the data values in the file in the order that you want preserved. For example, store the data from each node on a separate line, with the contents of the root node on the first line and so on until the list is empty. To restore the list, read the file line by line, storing the information from each line in a newly created node. When you reach the end of the file, the list is reconstituted.

Yes, each element needs to be malloced again. With most linked lists that''s unavoidable.

One alternative would be to have each record store the offset to the next record - rather than a pointer - and then use that offset with some pointer arithmetic to reconsitute the links.


Share this post


Link to post
Share on other sites
there is a pretty good reason to store the pointers and adresses of the elements. its just the same as all the "store an id"-methods, just that there isnt any point in making up some unique id for the elements when your pointers/adresses already ARE perfectly unique ids. not necessary for a list, as pointed out the order of the elements is enough to reconstruct the list, but for trees or other more or less complex situations with lots of stuff pointing at other stuff... well

Share this post


Link to post
Share on other sites