Questions about lists

 
Post new topic   Reply to topic    mudlab.org Forum Index -> Newbie
View previous topic :: View next topic  
Author Message
paan



Joined: 20 Nov 2007
Posts: 13

PostPosted: Tue Nov 20, 2007 3:24 pm    Post subject: Questions about lists Reply with quote

Hi.. I lurked around here a lot lately..
I'm not totaly newbie at coding but I am new in C. So if this sounds stupid/silly or anything please feel free to correct me..

A little background
I'm designing a data structure.
It's a simple map data sturcture.
I have a terrain structure that contains info on the terrain type. and also a list of items on the particular tile
so the basic structure is like this
Code:

typedef struct{
    TERRAIN *terrain;
    ITEMS *items;
}TERRAIN_DATA;


with terrain is the data structure of the terrain that (will) contains the movement tables etc etc..
So, moving on..
the way I initialize the data is that I don't use a real linked list(with next pointing to the next item).
Instead I increament the pointer to the items each time I add an item and assign the head of the item to the struct. Example: this is my init code

Code:

TERRAIN_DATA *terrain_data=malloc(sizeof(TERRAIN_DATA));
terrain_data->terrain=newTerrain("plain");
ITEM *head =NULL;

ITEM *item=malloc(sizeof(ITEM));
head=item;
item->id="01"
item->name="Car";
item++;
item->id="13";
item->name="A sick brahmin";

terrain_data->items=head;


All fine and dandy..
when reading the data i did the same thing..

terrain->item++
then reads the content

The only problem now is that while reading the data,
Code:
terrain->item==NULL

always evaluate to false.. so I don't know when my list ends..
I did some digging around .. and it seems that the increment opereator (++) allocates memory to the variable.. and so the variable is not considered NULL anymore..

I know i can avoid this by doing a proper linked list..(Doctor it hurts when I do this. Don't do that). But is it possible to make my approach work? Or am I reinventing the wheel with this? Any tips on the correct way I should approach this? Or am I doing this all wrong?

Sorry if the post is long winded and/or stupid..
Laughing
Back to top
View user's profile Send private message
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Tue Nov 20, 2007 4:27 pm    Post subject: Reply with quote

Well, the fundamental problem is you are incrementing a 32-bit pointer; not changing its value to the next of a sequence of possible pointers (those consisting of the list you are creating, implicitly).

Code:
ITEM *item=malloc(sizeof(ITEM)); head=item;


Here you've created a non-initialized ITEM and set both item and head to point to it...

Code:
item->id="01"; item->name="Car";


item and head now both point to an ITEM with an id of "01" and a name of "Car" (nothing funny happening yet)

Code:
item++;item->id="13";item->name="A sick brahmin";


You increment the address item points to... but we don't (from your code) know what this next block of memory contains. Whichever address you now point to, you attempt to set the "id" portion of that bitspace to "13" and the "name" portion to "a sick brahmin." You didn't create or necessarily modify a real ITEM object.

Code:
terrain_data->items=head;


You set the item member variable of our new terrain data structure to the address of our first ITEM object we had malloc'd and initialized.

I'm guessing you've assumed incrementing the item pointer causes it to point to a new or pre-existing item object (and if one doesn't exist, it becomes "invalid" -> NULL). Unfortunately, C isn't that "smart." What you've actually done is taken the address stored in item (say... 0x42220000) and incremented it by the size of ITEM (8 - two 32-bit pointers). Now item points to 0x42220008 - this may or may not be anything valid. Even if you'd malloc'd this object just a second ago, there is no guarantee that you'd point to the old object - memory allocations are not required to be consecutive (or, for that matter, follow any pattern at all).

The "next" pointer in most linked-list data structures (in C) are there because the objects may be anywhere in memory and we need to store their location to later find them. When no more objects follow a given linked-list object, that is why the next pointer is NULL - we've assigned a special value (0x00000000) to indicate there are no more objects.

Hope this helps you Very Happy


edit: to clarify, item will never = NULL because it is constantly increasing in value (0x44 => 0x45 => 0x46 ... => 0xFF). Using these intermediate values will cause illegal memory access (and likely corrupt memory). If they're never written/read, eventually the pointer would overflow and could become 0x00000000.
Back to top
View user's profile Send private message Send e-mail AIM Address
Author Message
paan



Joined: 20 Nov 2007
Posts: 13

PostPosted: Fri Nov 23, 2007 9:26 am    Post subject: Reply with quote

Thanks for the reply.

Yeah. I get what you mean..

Based on what you said I did a little more digging and it seems that a list is a bad way to put it.. My data structure is more array-ish if anything..
I did find out, however, that a malloc-ed pointer will increment the pointer for the amount of memory that we specify (in my example the size of the ITEM data structure) and initialize the value for each of the member as null. So in my example what happened was. The pointer will not bu NULL because it is infact pointing to an ITEM data structure that have all it's member as NULL.

So like you said, this could lead to some bad thing like illegal memory access and such.
I could do the checking on the member values instead and if they are NULL, halt the operation. But this wouldn't be good since I will use a memory area to actually store a 'nothing'.
Or instead, what I can do is that if there is no more things to add, free the pointer and then assign it to NULL. But I would have to assign the space. Then free it afterwards if I have nothing to add. Which is not so good either.

Did I get that right? What is the norm when handling a list things with unknown amount like this?
Back to top
View user's profile Send private message
Author Message
Drey



Joined: 15 May 2005
Posts: 24
Location: Livonia, MI

PostPosted: Mon Nov 26, 2007 2:41 pm    Post subject: Reply with quote

paan wrote:
What is the norm when handling a list things with unknown amount like this?


The norm in that situation is to actually use a linked list. Alternately, I suppose you could malloc a block of memory to use as an array and everytime it gets too small, malloc a new larger block and copy everything over to it.
Back to top
View user's profile Send private message Visit poster's website
Author Message
elanthis



Joined: 13 Apr 2006
Posts: 10

PostPosted: Mon Nov 26, 2007 6:50 pm    Post subject: Reply with quote

Quote:
I did find out, however, that a malloc-ed pointer will increment the pointer for the amount of memory that we specify (in my example the size of the ITEM data structure) and initialize the value for each of the member as null.


This is not correct.

malloc() does not "increment" anything. It returns a pointer to a block of memory of exactly the requested size (in your example, the size is a single structure).

Also, malloc() does not initialize anything. It returns a pointer to a block of memory reserved for your use, but the data in that memory is essentially random - it's whatever was in that block the last time it was used. You are responsible for initializing the memory. Alternatically, you could use callac() which would initialize the returned memory to contain all 0 bytes (which would result in any pointers stored in the block to be NULL), but in many cases it's often more efficient to just use malloc() and initialize the structure fields manually.

You can also use memset to manually initialize a block of memory to 0 bytes, if you want. calloc() essentially just calls malloc() and that calls memset() on the allocated memory to clear it to 0 bytes.

To form an array-like set of memory, you need to call malloc() and give it the total size you need. If you want to store 10 copies of struct ITEM (replace ITEM with whatever structure you're actually using, of course), you'd do (struct ITEM*)malloc(sizeof(struct ITEM) * 10); You could then use the returned pointer exactly as if it were an array of 10 elements (all which are unitialized).

If you do not know the number of elements you will have ahead of time, a linked list will be far easier to write and use, although it may not be as efficient. There are correct places to use arrays, correct places to use linked lists, and correct places to use other data structures. Knowing which data structure is appropriate for which task is one of the most (if not THE most) fundamental skills of programming. I'm not really sure on your specific use case which would be best; I'm going to guess that for a terrain setup you might be better off with a 2d array. So, if you have terrain elements over a grid X spaces wide and Y spaces tall, you'd allocate a block of memory equal to sizeof(struct ITEM)*X*Y. You would then access the element at position (x,y) in that array using an index of [y*Y+x].

However, for very large grids, a straight array would not be best for various reasons. That goes back to understand data structures and knowing when to use each, and isn't something that can readily be explained in a few paragraphs. There are countless excellent books on the subject, so you might want to peruse your local bookstore for books on C data structures (and maybe pick up an introductory C book to help you get the hang of pointers and malloc() and other things you wouldn't ever deal with in most other languages).
Back to top
View user's profile Send private message
Author Message
paan



Joined: 20 Nov 2007
Posts: 13

PostPosted: Tue Nov 27, 2007 2:24 am    Post subject: Reply with quote

Maybe I word it wrongly . But what I was trying to say that if I increment a malloc-ed pointer it will return to me the block of memory that is the "next" requested size. Malloc does not however assign any values to it, and the fact that my toy code return null maybe just a coincidence.

I do agree however that a good data structure is important, and since I am an average coder at best, hence this thread, asking for comments and critisism. I did get some books. And I am starting to get a more clear understanding of pointers as a whole..

Back to the topic at hand, the structure is for a map display.. Where the main structure is the whole map. Which will be mostly a fixed size.(or at least a known size) Which I will represent using a 2D array. And in each of the member of the of the array (which correcpoind to a position in the map), I will then have a structure that will store a list of items that will be on the specific loacation on the map. This will include any items dropped by players and/or mobs and also any terrain objects (obstructions, covers, or just terrain dodads). I am reluctant to use linked list because I plan for the player to be able to see an tile and see a list of items on it , and be able to take it , examine it or what not, and I don't want the to have to walk through the list to get to an item. I want some thing that would allow me random access to the items if possible.

So basicly that is what I'm trying to acheive.
Back to top
View user's profile Send private message
Author Message
paan



Joined: 20 Nov 2007
Posts: 13

PostPosted: Tue Nov 27, 2007 2:55 am    Post subject: Reply with quote

Drey wrote:
Alternately, I suppose you could malloc a block of memory to use as an array and everytime it gets too small, malloc a new larger block and copy everything over to it.


I'll look into this.. seems like the way to go..
Back to top
View user's profile Send private message
Author Message
Kelson



Joined: 18 May 2005
Posts: 71
Location: SC

PostPosted: Tue Nov 27, 2007 5:32 am    Post subject: Reply with quote

paan wrote:
Maybe I word it wrongly . But what I was trying to say that if I increment a malloc-ed pointer it will return to me the block of memory that is the "next" requested size. Malloc does not however assign any values to it, and the fact that my toy code return null maybe just a coincidence.


Diverge yourself of the notion that malloc does anything to your pointer; the malloc function returns the address of a block of memory allocated for use by your program. When you assign this value to your pointer, your pointer now has the value of the allocated memory (ie, 'points' to it). When you increment your pointer, you are essentially saying: item = item + sizeof(ITEM). Now, if item currently pointed to the third element of a ten element array - yes, this would point to the 'next' element - number four. If it pointed to the tenth element though, incrementing it would make it point to a non-existent eleventh element. This is where it becomes a bit more tricky.

That next block of memory may or may not have been allocated to you. If it isn't allocated and you dereference the pointer (ie, read/write the memory at the address it points to) your program will crash with an illegal memory access. If it was allocated, the computer will keep on happily chugging away with no mind to your false assumption that memory location X is an ITEM, not actually part of a CHARACTER structure in use by Snuffy the Super Warrior Neanderthal. Since we don't know what data we're actually looking at, we have no way to verify whether this block of data is what we should be looking for. Furthermore, we have no idea what the effects of writing to this memory are - for all we know, it might be storing some dynamically loaded room descriptions. One second, the players are running through Voldemorte's Castle, the next they're running through Vol%@`\([][]. Or perhaps Snuffy will suddenly have 999999 of 100 hp... or -25435345.

If you want to use an array, allocate it as such and use the [] operator for member access.
Back to top
View user's profile Send private message Send e-mail AIM Address
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Newbie All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign