Review my Vector Code? 2

[Guest42]

Alright. As sort of an experiment I wanted to see if I could make a Vector (expandable array) in C, kinda like the Vector class in Java, only this one holds a specific type of structure. It appears to be fairly successful, although it is very simple at this point. Anyway, I was hoping someone could review it for me, tell me if there are any dangerous leaks, or if there are ways to make the code better. It can be found here:

http://cyberworld.kicks-ass.net/comic/main.c

Basically it functions similar to a linked-list, but instead of individual node holding a single struct, each VECTOR_NODE has an array of structs. This makes it quicker to jump through nodes to get the the item you need, if you have a lot of item.

Two other things I am interested in (though they might only be clear once you see the code):
The getItem(int n) function has an inner if statement in it because the initial node has a different capacity from added nodes. Even though it might be less efficient, I'd like to see if there's a way to linearize this function (thus getting rid of the inner if statement). I just have a facination with linearization.

Second, I didn't finish the removeItem() function because I can't think of the most efficient way to do it, although I reckon that the 'addItem()' function will also have to be changed.

So yeah, if someone could take a look at it for me, I'd appreciate it. Thanks for your time.

 

[xwb]

A bit strange: a doubly linked list of vectors. Possible crash in freeVector

   free(*v);  /* was free(v); */

Your method has pros and cons.

Pro: as the vector grows, it doesn't take longer and longer to add stuff.

Con: access is exponentially slow. Most implementations normally use realloc to keep the list contiguous.

You could simplify a lot of the code by removing one level of indirection. eg

void addObject(struct VECTOR_NODE *v, struct game_object **g)
{
    v->go[v->subtotal] = *g;
    ++(v->subtotal);
}

 

[Guest42]

Well, you probably know better than I, but I think that sending it through like that makes a copy of the the argument, rather than just dereferencing your pointer, which is what I need to do. Like, if you want to dereference int n, you need *int, and if you want to dereference int *n, you need **int

 

[Guest42]

Actually, scratch that, as making a copy of the pointer wouldn't make a difference, since I'm going to end up with the same space used, ultimately pointing to the same spot. Duh.

Anyway, you say access will be exponentially slower? If you have a lot of little nodes, this would certainly be true, but does arr[100] take much longer to access than arr[5]? I would think that if you're going to have a larger number of objects (and therefor larger nodes) then it would be quicker, because you jump through less loops to get to the right node, where you can pick anyone of n objects right away.

 

[xwb]

Say each node has 10 items. Accessing 0-9 will be faster than 10-19 because it has to go to the next node. If you access 99, it will have to go through 10 nodes. You could be clever about it. Instead of something like

getItem (vect, 100)->x = 1 - getItem(vect,100)->x;

You could use

int* gix = &getItem (vect, 100)->x;
*gix = 1 - *gix;

As you said you can have larger nodes but if it is generic, how large do the nodes have to be? Also, optimally, you need them to be within one or two pages.

 

[cpjust]

I'd probably implement it as a void* to let it hold any type, then use realloc() to grow the array. I'd implement functions like push_back(), push_front(), pop_back(), pop_front()... Basically try to model the vector class in C++, but since it's C it would obviously be much more clumsy to use.

 

[Guest42]

I suppose I ought to take a look at a C++ vector then. The reason that I didn't think about realloc() was because I didn't know it existed until this thread I also didn't realize you could implement void like that, though I realized there must be some way to do in C what you can do with templates in C++.

Just out of curiousity, say you use realloc() to grow a single array arr[], but when it comes time to allocate more memory for arr[] there's not enough contiguous space, so it has to allocate more memory elsewhere. Won't it have to free up arr[]s spot and copy arr[] somewhere else entirely? Which would mean if you have a large array of complicated structs or objects, it would be taxing to cause the array to grow, rather, but keep quick access to all of your elements, right? I just want to make sure I understand if that's how it works.

 

[Guest42]

So using realloc(), this seems to do the same thing that the made-up-out-of-my-head struct does, in a much less complicated way:

http://cyberworld.kicks-ass.net/comic/VectorRealloc.c

The only problem is that trying to access v->go[0]->x brings up a memory address rather than the value of x, although the rest of v->go[n] works just fine. What am I missing here?

 

[cpjust]

If you're worried about realloc() having to do a lot of memory moving each time you add an element, you can implement your VECTOR_ARRAY functions to work even more like a C++ vector by doubling the amount of memory each time it needs more room.
The STL vector keeps track of how much memory it has allocated, and if someone tries to push_back() an item when the memory is full, then it will reallocate itself to twice the size it was before.
Ex. If a vector starts with 256 elements, you can push_back() 256 times before it does a realloc(). When that happens, it requests 512 * sizeof( type ). Once you fill up the 512 it requests 1024...

It would be a lot of work, since you'd have to keep track of how many elements are used, manually move all elements yourself if someone deletes an element from the front...

 

[xwb]

Another method, instead of doubling is to increase by a percentage, say 20%. Alternatively, increase by a fixed amount, say 256 every time.

 

[Guest42]

Right. Not a real big concern, just wanted to make sure I understood how it works. There's still the problem that, in the program, v->go[0]->x returns some address rather than the value of x, where as the rest of v->go[n]->x return the value of x. I can't figure out what's up with that....

 

[cpjust]

I'm not sure why it's doing that. If you post some code that shows how you get the problem to happen, we can investigate.

Now that I have more time to look at your VectorRealloc.c code, I found some problems:

In initVector(), you have a memory leak. I'm not sure why, but you have this line:

v->go = (struct game_object**)malloc(v->capacity * sizeof(struct game_object*));

but the length is set to 0, so once someone calls addItem(), the pointer to that memory will be lost.
I would just remove that line from initVector().

You should always check the return values of malloc() & realloc() to see if they actually worked. If they return NULL, they couldn't allocate enough memory and you should handle it properly (like printing an error message and return a fail condition from your function).

That gets into another point - functions like addItem() should return a value to indicate if they failed or succeeded (maybe 0 = false, 1 = true).

For lines like:

++v->length;

you should use parentheses to separate operations.
I don't have all the order of operations memorized, and I'm pretty sure there's nothing wrong with that line, but someone else looking at the code might wonder if you meant

(++v)->length;

or

++(v->length);

When you start writing even longer, more complex expressions, it becomes even easier for subtle bugs to creep into your code if you aren't careful about the order of operations. It's good to get into the habit of using parentheses to explicitely show what order you want the expression to be executed.

In addItem(), I would change the else clause from

v->capacity += v->addSize;
realloc(v->go, (v->capacity * sizeof(struct game_object*)));
v->go[v->length] = g;
++v->length;

to

v->capacity += v->addSize;
realloc(v->go, (v->capacity * sizeof(struct game_object*)));
addItem( v, g );

That way, it ensures that if you ever change the way addItem() works by updating the if clause, you don't have to remember to also change the else clause...

Lastly, just an over all design point. I'm wondering why you're storing game_object pointers in your VECTOR_ARRAY instead of storing the whole game_object structs? I probably would have designed it to add game_object structs instead of game_object pointers.

 

[Guest42]

Actually, the line:

v->go = (struct game_object**)malloc(v->capacity * sizeof(struct game_object*));

Isn't determined by the length variable (which is the current number of elements stored), but by capacity, which isn't zero. Perhaps my naming system could be better, but this line is necessary to initially allocate memory for the game_object array 'go'.

As far as things like error checking and parenthesis,I will certainly add them in.

When it comes to the problem stated in my previous post, the VectorRealloc.c program produces the unwanted results, so if you run that, it should do it

And lastly, the reason it holds pointers is as following. If at any given point in time you want to spawn a bunch of objects into your game, you create them once, and send the pointers over. That way there is no copying of objects. This is even better if you want to keep track of your objects in more than one array. For example, one Vector might point to all of your game objects, while another smaller array might store only your monster objects. I think it's just more efficient and easier to organize with pointers.

 

[cpjust]

Oh yeah, now I see why that malloc() is needed...

I tried compiling your code. You were missing the #include directives for <malloc.h> and <stdlib.h>. When I ran it, instead of getting the problem you were seeing, mine just crashed.
I think the stack might be getting corrupted somewhere, but I haven't been able to see where exactly.

I also noticed that in getItem() I had to change

return v->go[n];

to

return (game_object*)(v->go + n * sizeof(game_object));

to get it to work right. Otherwise it was only returning the first 4 bytes of the vector and then crashing when trying to access that invalid pointer.
Now it's crashing in addItem() after it expands the size of the vector a couple times.

Maybe ArkM or Salem would have better luck in figuring out why it's crashing?

 

[Guest42]

Well, I just fixed the program. I found out I can just say:
realloc(v->go, (v->capacity * sizeof(struct game_object*)));

Instead I have to do this:
v->go = realloc(v->go, (v->capacity * sizeof(struct game_object*)));
Or else v->go might not get moved to the correct spot.

Also, I had to include the stdlib.h. It seems I was using a version of realloc() that is in a library that my compiler automatically links to the program. However, that version doesn't work right because it returns an integer instead of a pointer.

 

[Salem]

> Also, I had to include the stdlib.h. It seems I was using a version of realloc() that
Which is exactly the problem you have by casting malloc and realloc in the first place.

http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1047673478&id=1043284351

If you cast the result, the compiler CANNOT tell you that you failed to include the correct header file.

By failing to include the header file, the compiler implicitly declares it as returning int. You then have an unchecked cast of an integer to a pointer. If your int and pointer are of different sizes, the code is broken.

You might want to adopt the
[tt]p = malloc ( n * sizeof *p );[/tt]
approach to working out the size. It saves you an awful lot of working out what the size should be (let the compiler do the work). If you mis-count the number of stars you need in say sizeof(struct game_object*), or worse, you change the pointer type without changing the malloc, your code will be wrong in hard to find ways.


> v->go = realloc(v->go, (v->capacity * sizeof(struct game_object*)));
Better, but still weak.
If realloc fails, it returns NULL, but does NOT free the old block. But you've trashed your only pointer and now you have a memory leak.
Always use a temporary variable with realloc

void *temp = realloc(v->go, (v->capacity * sizeof(struct game_object*)));
if ( temp != NULL ) {
  v->go = temp;
} else {
  // v->go is still valid
  // report error, save data, continue with no more additions
  // or some other action favourable to the user
}

> struct VECTOR_ARRAY* initVector(int _initSize, int _addSize)
Symbol names which begin with _ are reserved by the implementation (ie, all global but private symbols used by the compiler and standard library).

--