Draft: vkd3d-shader: Replace shader instruction array with rbseq.
This MR displays how to replace the current vkd3d_shader_instruction_array implementation from an array to a variant of rbtree where each node has a count field of the nodes under it, and elements in the tree are accessed via their index instead of an arbitrary comparison function.
This data structure has
O(log n) access cost on arbitrary indices. O(log n) insertion cost on an arbitrary index. O(1) amortized _prev() and _next() cost. i.e. While the worst scenario is O(log n), a whole traversal is O(n) so these operations are O(1) on average.
For the sake of simplicity, every instruction node is allocated individually, but it is possible to allocate several at the same time, potentially making the structure more efficient, by using a scheme like the one used by vkd3d_shader_param_allocator.
Patches 1-4/6 show step-by-step how rbseq.h is obtained from rbtree.h.
The replacement of the data structure happens in 5/6.
6/6 implements vsir_program_iterator_at() which moves an iterator to a specific position by index, even though we don't have use cases for that right now.