Change in osmo-pcu[master]: pdch_ulc: Optimize rbtree FN search

[pespin]

pespin has submitted this change. ( https://gerrit.osmocom.org/c/osmo-pcu/+/23519 )

Change subject: pdch_ulc: Optimize rbtree FN search
......................................................................

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
---
M src/pdch_ul_controller.c
1 file changed, 9 insertions(+), 6 deletions(-)

Approvals:
  Jenkins Builder: Verified
  fixeria: Looks good to me, approved
  laforge: Looks good to me, but someone else must approve



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;
 }

-- 
To view, visit https://gerrit.osmocom.org/c/osmo-pcu/+/23519
To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings

Gerrit-Project: osmo-pcu
Gerrit-Branch: master
Gerrit-Change-Id: I2843aedb5ce74c909bde82d29269d0f956e9a093
Gerrit-Change-Number: 23519
Gerrit-PatchSet: 3
Gerrit-Owner: pespin <pespin at sysmocom.de>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: fixeria <vyanitskiy at sysmocom.de>
Gerrit-Reviewer: laforge <laforge at osmocom.org>
Gerrit-Reviewer: pespin <pespin at sysmocom.de>
Gerrit-MessageType: merged
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osmocom.org/pipermail/gerrit-log/attachments/20210331/0d85d234/attachment.htm>