C does not have a yield operator like Python, so you cannot separate the action from the iteration. Simply put, you just need to do the array assignment in your tree iterator.
To do that, I would supply the pointer to the dynamically allocated array of node pointers, a pointer to the size of that array (in node pointers), the number of node pointers already in the array, and the tree:
For example,
Code:
int node_array_assign(node ***const arrayptr, size_t *const sizeptr, size_t *const usedptr, node *const tree)
{
int error;
if (tree->left) {
error = node_array_assign(arrayptr, sizeptr, usedptr, tree->left);
if (error)
return error;
}
if (*usedptr >= *sizeptr) {
const size_t size = 16 + (*usedptr * 5) / 4;
node **temp;
temp = realloc(*arrayptr, size * sizeof (*temp));
if (!temp)
return ENOMEM;
*arrayptr = temp;
*sizeptr = size;
}
(*arrayptr)[(*usedptr)++] = tree;
if (tree->right) {
error = node_array_assign(arrayptr, sizeptr, usedptr, tree->right);
if (error)
return error;
}
return 0;
}
To make it a bit easier for the programmer, I'd add a wrapper, perhaps
Code:
size_t node_array(node ***const arrayptr, size_t *const sizeptr, node *const tree)
{
size_t used;
int result;
if (!arrayptr || !sizeptr) {
errno = EINVAL;
return 0;
}
if (!*sizeptr)
*arrayptr = NULL;
if (!tree) {
errno = 0;
return 0;
}
result = node_array_assign(arrayptr, sizeptr, &used, tree);
if (result) {
errno = result;
return 0;
}
return used;
}
The allocation logic is similar to the POSIX.1-2008 getline() function: you can initialize the value pointed to by sizeptr to zero, and it will dynamically allocate a large enough buffer. Or you can provide a preallocated array, in which case it will only be reallocated if not large enough yet.
It is, however, "three star code", which is not a compliment.. The array is specified as node ** , i.e. as a pointer to pointer (outer pointer being the array, inner pointer to the node). In order for the functions to reallocate the array when necessary, we need a pointer to the array pointer, i.e. node ***.
Eww. It is ugly and hard to read; pretty much an indication that something is wonky with this approach.
I'm sure I'm going to get flamed for this post and the above code, but it is undeserved, I assure you. If you want an array of pointers to a binary search tree nodes, the above is the most straightforward and simple code I can think offhand. (You can simplify it by traversing the tree twice: first to obtain the number of nodes, then allocating the array to that precise size, then to copy the pointer to each node. However, traversing any sufficiently large binary search tree will be limited by memory accesses, so that approach will be basically half as fast as this one, for large enough trees. Not a good tradeoff in my opinion.)
However, your particular case has a feature that makes another solution much better: Your nodes are fixed-size and small, with just a key and a data pointer. So, instead of filling in an array of pointers to tree nodes, you could instead copy the node contents into the array. For example, using
Code:
typedef struct {
void *key;
void *data;
} pair_t;
and have the node_array() instead take a pointer to a pair_t pointer. This will only use twice the memory compared to the array of pointers to each node, but it will be independent of the tree, and you won't need to do the extra indirection; thus, it would be significantly faster for larger tree sizes.
In this case, the functions could be for example
Code:
int tree_pairs_copy(pair_t **const listptr, size_t *const sizeptr, size_t *const usedptr, node *const tree);
size_t tree_pairs(pair_t **const listptr, size_t *const sizeptr, node *const tree);
Ah, that looks much more sane to me; this indeed is the way I'd implement this, I think.
There are only minor differences to the node_array_assign() and node_array() functions I showed earlier, so you should be able to write them yourself.
Any questions?