pdch_ulc: Optimize rbtree FN search
Use logarithmic lookup algo to find if FN is available instead of
iterating over the whole tree.
Change-Id: I2843aedb5ce74c909bde82d29269d0f956e9a093
diff --git a/src/pdch_ul_controller.c b/src/pdch_ul_controller.c
index 3f3776d..e6e22a2 100644
--- a/src/pdch_ul_controller.c
+++ b/src/pdch_ul_controller.c
@@ -66,16 +66,19 @@
struct pdch_ulc_node *pdch_ulc_get_node(struct pdch_ulc *ulc, uint32_t fn)
{
- struct rb_node *node;
+ struct rb_node *node = ulc->tree_root.rb_node;
struct pdch_ulc_node *it;
int res;
- for (node = rb_first(&ulc->tree_root); node; node = rb_next(node)) {
- it = container_of(node, struct pdch_ulc_node, node);
+
+ while (node) {
+ it = rb_entry(node, struct pdch_ulc_node, node);
res = fn_cmp(it->fn, fn);
- if (res == 0) /* it->fn == fn */
- return it;
if (res > 0) /* it->fn AFTER fn */
- break;
+ node = node->rb_left;
+ else if (res < 0) /* it->fn BEFORE fn */
+ node = node->rb_right;
+ else /* it->fn == fn */
+ return it;
}
return NULL;
}