//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;
};Saving linked lists in standard ANSI C
Author
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:
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.
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:
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:
formating and [ i ] problems <br><br><SPAN CLASS=editedby>[edited by - Melekor on January 16, 2004 10:52:41 PM]</SPAN>
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.
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 listIf 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
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 entity
roperty, 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.
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 entity
roperty, 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.
Author
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.
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.
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.
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.
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.
Author
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?
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?
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
