[PATCH vkd3d 2/6] vkd3d: Use a binary search for matching a descriptor to an allocation.

[Henri Verbeet]

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