diff options
author | Pau Espin Pedrol <pespin@sysmocom.de> | 2021-03-29 11:29:22 +0200 |
---|---|---|
committer | Pau Espin Pedrol <pespin@sysmocom.de> | 2021-03-31 17:39:50 +0200 |
commit | 222f6741167044c2bb965a73cec0afeb5ca5302e (patch) | |
tree | af09f31c75b69b4ed123927edd2d49b278a15716 | |
parent | 54e6450293f2b5880004f49e76dc4d6f4645c299 (diff) |
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
-rw-r--r-- | src/pdch_ul_controller.c | 15 |
1 files changed, 9 insertions, 6 deletions
diff --git a/src/pdch_ul_controller.c b/src/pdch_ul_controller.c index 3f3776db..e6e22a20 100644 --- a/src/pdch_ul_controller.c +++ b/src/pdch_ul_controller.c @@ -66,16 +66,19 @@ struct pdch_ulc *pdch_ulc_alloc(struct gprs_rlcmac_pdch *pdch, void *ctx) 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; } |