It seems that the isLast check is inexpensive (on par with null check), so I’d suggest making ptr non-nullable and check if the end has been reached on each call to next. I’d write it out as follows:
The defer statement here does the post-increment (see Zig defer Patterns).
In general, storing one-past-the-end pointers in iterators is common practice and is simpler as the mechanism for breaking at the last element is not needed.
No. [*] are, by design, not allowed to be null. Note that this doesn’t cost you anything, as optional pointers are special cased such that null is 0. You could point your pointer to some other address, like 1, to signify null, but you would not get anything out of this, only lose, as checking for 0 is faster than checking for any other number.
But the trouble with that is that you would need a pre-sentinel (sentinel node that is before the first node) that is in contiguous memory before the start of the array, which has .is_last set to false, otherwise the first element of the list is never yielded.
With linked lists the iterator could hold a dummy node that points to the first element and with that it would work, but I don’t know how to make it work with contiguous arrays, except having an extra element at the beginning.
If the to be iterated list has some sort of header struct, it might be possible to design the header in such a way that its memory layout happens to work as that dummy node.
Then all the pointer arithmetic depends on curr and prev can point anywhere you want on the first iteration.
On the last iteration curr might point to an invalid memory location but that shouldn’t be a problem since you never dereference or return it.
It is null once iteration stops.
I haven’t compared speed, but I like it because the code seems simpler, it also needs less memory.
I find the naming of
confusing when it is an index, I think child or child_id or child_idx would be better, or maybe even first_child, that way it would make more sense in combination with is_last.
Also I don’t think your init_or_null method makes a lot of sense, it should just be init and always return the ChildIterator (because I don’t see a good reason to make empty into a special case when it could just be the empty sequence, where the iterator’s next yields null immediately):
Using the else with while to do something once the iterator is done, is also useful.
If you need to write separate code for nodes that don’t have children, I think the intent would be more clear with something like parent.hasChildren() and branching on that, instead of making the iterator creation conditional (and less clear because it serves different purposes (iterator creation vs child-existence-check)).
Thanks. Yes, I was not 100% satisfied with the childptr name.
At the moment of writing or_null seemed the clearest to me. Not sure yet!
It reminds me of the std hash where there was (i believe) some ...OrNull and the name was changed.
In general I like one-liners
True but I think more cpu time. I need every inch of that.
But you also very right. the pre-check in my code node.has_chidren() is probably better.
this
// Try rack.
... else if (rack.len > 0)
{
var iter = self.graph.get_child_iterator_or_null(node) orelse return;
while (iter.next()) |child| {} // do my thing
}
i could change to
// Try rack.
... else if (rack.len > 0 and node.has_children())
{
var iter = self.graph.get_child_iterator(node);
while (iter.next()) |child| {} // do my thing
}
One thing you could do here if you know that your nodes are always align>1 is storing is_last in the LSB of ptr to half the size of the non-optional ChildIterator version like this:
I’m not sure if this could mess with the prefetcher in a bad way (maybe somebody here knows more about such things) but if not this might be faster than the optional version because there is only one very predictable branch per next() call and it takes up the same amount of memory.