On Fri, 10 Dec 2021 at 06:07, Conor McCarthy cmccarthy@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".