On Fri, 10 Dec 2021 at 06:07, Conor McCarthy <cmccarthy(a)codeweavers.com> wrote:
@@ -2199,7 +2200,13 @@ bool vkd3d_gpu_descriptor_allocator_register_range(struct vkd3d_gpu_descriptor_a return false; }
- allocation = &allocator->allocations[allocator->allocation_count++]; + for (i = 0; i < allocator->allocation_count; ++i) + if (base < allocator->allocations[i].base) + break; + We could use a binary search here...
+ allocation = &allocator->allocations[i]; + memmove(allocation + 1, allocation, (allocator->allocation_count++ - i) * sizeof(*allocation)); + "&allocation[1]", arguably.
+/* We could use bsearch() or recursion here, but it probably helps to omit + * all the extra function calls. */ +static struct vkd3d_gpu_descriptor_allocation *vkd3d_gpu_descriptor_allocator_binary_search( + const struct vkd3d_gpu_descriptor_allocator *allocator, const struct d3d12_desc *desc) +{ The fact that this is using a binary search is really just an implementation detail; callers wouldn't care if this e.g. used an rbtree instead. Something like vkd3d_gpu_descriptor_allocator_find()/_search()/_get() seems more appropriate.
+ struct vkd3d_gpu_descriptor_allocation *allocations = allocator->allocations; + const struct d3d12_desc *base; + size_t centre, count; + + for (count = allocator->allocation_count; count > 1; ) + { + centre = count >> 1; + base = allocations[centre].base; + if (base <= desc) + { + allocations += centre; + count -= centre; + } + else + { + count = centre; + } + } + + return (desc >= allocations->base && desc < allocations->base + allocations->count) ? allocations : NULL; +} + "allocations->base + allocations->count" probably can't overflow because of other constraints, but by convention, we'd probably want that check to be "desc - allocations->base < allocations->count".