Jump to content
  • Advertisement
Sign in to follow this  
DarkMatter2008

List functionality in C

This topic is 3406 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello All, I know that C doesn't come with anysort of list functionality, but I have come towards a situation where a list would be really handy. Does anybody know any tricks? Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Well, I guess it depends on what you mean by list. If you mean something on par with C++'s std::list, no, of coarse not. If you mean something on par with no, but you can write your own, why of coarse!

First, what do you mean by list?
Second, how much experience do you have? (Can you write your own?)
Lastly, are you coming from another language like Python that had something it called a list without requiring you to know what it really was?

Also, what's wrong with plain old array?
Also also, any reason not C++? Much better at this type of thing (the aforementioned std::list, but there's also std::vector (resizable array) and plenty more).

Share this post


Link to post
Share on other sites
I've come from OO languages like Java, C# and C++, I'm using C at the moment because I have been instructed to by my tutor, there's no getting out of it I'm afraid. I can write a list in OO languages easily enough. The only reason why I wouldn't initially use array over a list is a situation when the required dimenisons of the array are unknown, i.e. loading data in from a file.

Share this post


Link to post
Share on other sites
They keyword would be linked list. In C this involves having nodes with a pointer to the next (and optionally a previous node).

You still could use a dynamic array with malloc. Once the size needs to increase, malloc a new buffer of the size of the previous buffer plus the new data, copy stuff over and free the old buffer.

Share this post


Link to post
Share on other sites
Quote:
Original post by Endurion
Once the size needs to increase, malloc a new buffer of the size of the previous buffer plus the new data, copy stuff over and free the old buffer.
Idiomatic C uses realloc() to do this in one step.



Share this post


Link to post
Share on other sites
I'm having a bit of nightmare implementing realloc


// Initialized in a loop somewhere else

vectors.refs = malloc(sizeof(Poly *));

// Later on

Poly* polyArr;

ptr.v1 = &vectors[poly[one]];
polyArr = (Poly *) ptr.v1->refs;
size = sizeof(Poly *)*(ptr.v1->refCount+2);
polyArr[ptr.v1->refCount] = ptr;
vectors[poly[one]].refs = realloc(vectors[poly[one]].refs, size); // Crashes here
ptr.v1->refCount++;

HEAP[gp.exe]: Heap block at 00933290 modified at 009332C0 past requested size of 28
Windows has triggered a breakpoint in gp.exe.

Share this post


Link to post
Share on other sites
Quote:
Original post by DarkMatter2008
I'm having a bit of nightmare implementing realloc


vectors[poly[one]].refs = realloc(vectors[poly[one]].refs, size); // Crashes here


Does vectors[poly[one]].refs refer to memory that was allocated with malloc/calloc/realloc? I would recommend simplifying your code here as it's likely that you have slipped up in this regard.

Also, the way you're using realloc is not quite correct. If it returns NULL, you have no way of free()ing the memory that vectors[poly[one]].refs was previously pointing to. Some people dismiss malloc/realloc/calloc failures as more-or-less impossible and so ignore such things, but I'm not one of those people :)

Edd

Share this post


Link to post
Share on other sites
Quote:
Original post by DarkMatter2008
HEAP[gp.exe]: Heap block at 00933290 modified at 009332C0 past requested size of 28
Windows has triggered a breakpoint in gp.exe.


This error is indicative of a buffer overrun. The debug heap will check the memory when you free it, or when you call realloc, to see whether you've written past the end of it - and it looks like that's what you've done here.

Share this post


Link to post
Share on other sites
Believe me, I am trying to make it simple :)

Here's in essance what I'm trying to do:-


struct Vector
{
void * refs; // Needs to store Polys that have referenced this;
int refsCount;
};

struct Poly
{
Vector * vector;
};

struct Model
{
Poly * polys;
};

Vector vectors [10];

// Initialize Vectors
for(int i = 0; i < 10; i++)
{
vectors.refs = malloc(sizeof(Poly *));
vectors.refCount = 0;
}

Model someModel;
someModel.polys = malloc(sizeof(Poly*)*10);

Poly * ptr = someModel.polys;

for(int i = 0; i < 10; i++)
{
ptr->vector = vectors;
vectors.refs[vectors.refCount] = ptr; // Need to say what poly referenced it;
vectors.refCount++;
vectors.refs = realloc(vectors.refs, sizeof(*Poly))*vectors.refCount+1); // Need to resize refs incase another poly referecnes this vector

ptr++
}

Share this post


Link to post
Share on other sites
Quote:
Original post by DarkMatter2008
struct Vector
{
void * refs; // Needs to store Polys that have referenced this;
int refsCount;
};


Why are you using void? Are you going to have references to structs other than Poly? If not, forward declare Poly and use pointers to Poly. Also, you need to decide between arrays and linked lists here. The typical way of doing a linked list in C would be to add a "Poly *next;" to the Poly struct and then refs should be a pointer to the first Poly in the list. If you're using arrays, then you'll want refs to be a pointer to pointer to Poly (Poly **refs;) so that you can point to an array of Poly structs.

And, for what it's worth, // comments are only valid in C++ and C99 not C89.

Quote:

struct Poly
{
Vector * vector;
};


This shouldn't compile in C since you don't get the automatic typedef's. You should write:
typedef struct Poly_ Poly;
strut Poly_ {
// ...
};


You should actually put the typedef line before you define Vector to forward declare Poly for use in Vector.

Quote:

for(int i = 0; i < 10; i++)


Defining a variable in the for statement like this is, again, a feature of C++ and C99. If you're using C89 it shouldn't compile.

Quote:

vectors.refs = malloc(sizeof(Poly *));


It's generally a good idea to write:
var = malloc(sizeof *var);
since it's a bit more robust in the face of changing the type or typename of the variable var.

Quote:

Model someModel;


Mixing variable declarations with code is, again, only for C++ and C99, not C89.


Other than that, and a few typos, it compiles as C99 code, looks right (although it's a little strange to allocate for space+1 instead of allocating the +1 when you need it), and doesn't crash for me.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!