src/util/range_minimum_query.c

/*
 * Copyright 2025 Valve Corporation
 * SPDX-License-Identifier: MIT
 */

#include "range_minimum_query.h"

#include "macros.h"
#include "ralloc.h"
#include "u_math.h"

void
range_minimum_query_table_resize(struct range_minimum_query_table *table,
                                 void *mem_ctx, uint32_t width)
{
   const uint64_t height = util_logbase2_64(width) + 1;
   const uint64_t size = width * height;
   assert(size < UINT32_MAX);

   table->table = reralloc_array_size(mem_ctx, table->table,
                                      sizeof(uint32_t), size);
   table->width = width;
   table->height = height;
}

static void
elementwise_minimum(uint32_t *restrict out,
                    uint32_t *const a,
                    uint32_t *const b,
                    uint32_t count)
{
   for (uint32_t i = 0; i < count; i++) {
      out[i] = MIN2(a[i], b[i]);
   }
}

/**
 * For a given level (row) of the table, how many input values is the
 * minimum computed over?
 *
 * Each row of the table has (table->width - rmq_distance(level) + 1)
 * valid elements.
 */
static uint32_t
rmq_distance(int32_t level)
{
   return 1 << level;
}

void
range_minimum_query_table_preprocess(struct range_minimum_query_table *table)
{
   for (uint32_t i = 1; i < table->height; i++) {
      uint32_t in_distance = rmq_distance(i - 1);
      uint32_t out_distance = rmq_distance(i);
      uint32_t *in_row = table->table + table->width * (i - 1);
      uint32_t *out_row = table->table + table->width * i;
      /*
       * This reads elements [0, x) from in_row, where x is:
       *    in_distance + table->width - out_distance + 1
       *    in_distance + table->width - (2 * in_distance) + 1
       *    table->width - in_distance + 1
       * which is the number of valid elements in in_row
       */
      elementwise_minimum(out_row, in_row, in_row + in_distance,
                          table->width - out_distance + 1);
   }
}

uint32_t
range_minimum_query(struct range_minimum_query_table *const table,
                    uint32_t left_idx, uint32_t right_idx)
{
   assert(left_idx < right_idx);
   assert(right_idx <= table->width);
   const uint32_t distance = right_idx - left_idx;

   uint32_t level = util_logbase2(distance);
   assert(rmq_distance(level) <= distance);
   assert(distance < 2 * rmq_distance(level));
   assert(level < table->height);

   /*
    * Since right_idx <= table->width by precondition, we know
    *    right_idx - rmq_distance(level) <= table->width - rmq_distance(level)
    *    right_idx - rmq_distance(level) < table->width - rmq_distance(level) + 1
    * which means that the read for `right` is in bounds.
    *
    * The read for `left` is then in bounds because
    *    left_idx == right_idx - width <= right_idx - rmq_distance(level)
    */
   uint32_t *const row = table->table + table->width * level;
   uint32_t left = row[left_idx];
   uint32_t right = row[right_idx - rmq_distance(level)];
   return MIN2(left, right);
}