[Runtime][Hip] Inefficient O(n) and Potentially Incorrect Implementation of lower_bound and upper_bound in `runtime/src/iree/hal/drivers/hip/util/tree.c`

[swote-git]

What happened?

The implementations of iree_hal_hip_util_tree_lower_bound and iree_hal_hip_util_tree_upper_bound in runtime/src/iree/hal/drivers/hip/util/tree.c have issues with correctness and performance. I think these need to be fixed.

Problem 1: upper_bound Returns Incorrect Results

The current implementation violates the definition of upper_bound : L518-539

iree_hal_hip_util_tree_node_t* iree_hal_hip_util_tree_upper_bound(
    const iree_hal_hip_util_tree_t* tree, iree_host_size_t key) {
    // ...
    if (key == node->key) {
      return node; // this should be return NEXT node, not current node
    // ...

we can check definition in tree.h : L131

// Returns the first node in the tree that has a key that is > |key| or NULL;
iree_hal_hip_util_tree_node_t* iree_hal_hip_util_tree_upper_bound(
    const iree_hal_hip_util_tree_t* tree, iree_host_size_t key);

Expected : upper_bound(key) should return the first element strictly greater than key.
Actual : When key exists in the tree, it returns that node instead of the next one.

For example,
when tree has {10, 20, 30}.
lower_bound(20) should be 20.
upper_bound(20) should be 30. (but current returns 20)

Problem 2: upper_bound Has O(n) Worst-Case

After the initial BST traversal, upper_bound uses a while loop:

while (last && last->key <= key) {
  last = iree_hal_hip_util_tree_node_next(last);
}

Worst-case scenario:

Tree: {1, 2, 3, ..., 1000}
Query: upper_bound(999)

If initial search ends at node with key=1:
- Iteration 1: next(1) → 2, continue while 2 ≤ 999
- Iteration 2: next(2) → 3, continue while 3 ≤ 999
- ...
- Iteration 998: next(998) → 999, continue while 999 ≤ 999
- Iteration 999: next(999) → 1000, exit

Total: ~999 iterations × O(log n) per next() = O(n log n)

This defeats the purpose of using a balanced tree structure.

Unnecessary next() Calls in Both Functions (refactor)

Both functions rely on iree_hal_hip_util_tree_node_next() calls after BST traversal, instead of tracking the answer during traversal.

// lower_bound (O(log n) but still unnecessary)
if (!last || last->key > key) {
  return last;
}
return iree_hal_hip_util_tree_node_next(last);  // we can remove that.

// upper_bound - O(n)
while (last && last->key <= key) {
  last = iree_hal_hip_util_tree_node_next(last);  // related problem 2
}

In my opinion, we can eliminate all next() calls by tracking the answer during traversal.

Steps to reproduce your issue

1. Go to '...'
2. Click on '....'
3. Scroll down to '....'
4. See error

What component(s) does this issue relate to?

No response

Version information

b98c1b9

Additional context

No response

[swote-git]

I'm planning to open my PR right away.