An warning: Don't do this:
Code:
nodes = realloc( nodes, *capacity * sizeof( Node ) );
reallod() can fail (returning NULL). In that case, you'll loose the address contained in nodes pointer and get a memory leakage in your hands. It is safer to use an intermediary pointer, as in:
Code:
Node *p;
p = realloc( nodes, *capacity * sizeof( Node ) );
if ( ! p ) { ... deal with the failure here - nodes will not be affected... }
...
nodes = p; // if everything is ok, then you update the 'nodes' pointer.
But remember: 'nodes' cannot be changed between function calls. Your 'increase_nodes_capacity()' should be something like this (assuming the code is correct):
Code:
// Now you must pass a pointer to the node pointer, so you can change it.
int increase_nodes_capacity( Node **nodespp, size_t *capacity, size_t needed )
{
if ( needed > *capacity )
{
Node *p;
size_t new_capacity;
// No floating point needed - Store new_capacity to discard it in case of allocation error.
// For x86-64 (for example), size_t is 64 bits long, so the constant is 1ULL.
// ceil(log2(needed)) is the same as the position of the leading 1 bit.
// and pow(2,n) is the same as shifting 1 'n' bits to the left.
new_capacity = 1ULL << ( sizeof ( size_t ) - __builtin_clz( needed ) - 1);
// 'new_capacity' can overflow, so this test is important.
if ( ! new_capacity )
return 0; // 0 means error.
// Tries to allocate the new buffer.
p = realloc( *nodespp, new_capacity * sizeof( Node ) );
if ( ! p )
return 0; // 0 means error!
// Everything OK, update the pointer and the capacity.
*capacity = new_capacity;
*nodespp = p;
}
return 1; // 1 means OK.
}