diff options
| author | Dan McDonald <danmcd@mnx.io> | 2022-06-29 13:55:19 -0400 |
|---|---|---|
| committer | Dan McDonald <danmcd@mnx.io> | 2022-06-29 13:55:19 -0400 |
| commit | 7190ec3767d4ac1a525d0801318ad2b10f6824d9 (patch) | |
| tree | 71a6de53ec7a82c9bde81c40d10e759f642550cd /usr/src/common | |
| parent | fd7948755fd156e375263ea9fb2742dbf6e210bc (diff) | |
| parent | 08848a83914f59a64a6b5a37f068bbb69b0604b0 (diff) | |
| download | illumos-joyent-release-20220630.tar.gz | |
[illumos-gate merge]release-20220630
commit 08848a83914f59a64a6b5a37f068bbb69b0604b0
13919 dladm show-vnic truncates link speed for 100Gbps
commit 99e2a6f8e952fd927a72b75323d3e56bcbcda40a
14743 new vioscsi driver
commit 028c45646327b08802a29b76d1abea8907a57f17
14752 AVL: Remove obsolete branching optimizations
Conflicts:
usr/src/cmd/dladm/dladm.c
Diffstat (limited to 'usr/src/common')
| -rw-r--r-- | usr/src/common/avl/avl.c | 24 |
1 files changed, 4 insertions, 20 deletions
diff --git a/usr/src/common/avl/avl.c b/usr/src/common/avl/avl.c index 0411afb4c5..ed752bde3d 100644 --- a/usr/src/common/avl/avl.c +++ b/usr/src/common/avl/avl.c @@ -105,21 +105,6 @@ #include <sys/cmn_err.h> /* - * Small arrays to translate between balance (or diff) values and child indices. - * - * Code that deals with binary tree data structures will randomly use - * left and right children when examining a tree. C "if()" statements - * which evaluate randomly suffer from very poor hardware branch prediction. - * In this code we avoid some of the branch mispredictions by using the - * following translation arrays. They replace random branches with an - * additional memory reference. Since the translation arrays are both very - * small the data should remain efficiently in cache. - */ -static const int avl_child2balance[2] = {-1, 1}; -static const int avl_balance2child[] = {0, 0, 1}; - - -/* * Walk from one node to the previous valued node (ie. an infix walk * towards the left). At any given node we do one of 2 things: * @@ -274,8 +259,7 @@ avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) #endif return (AVL_NODE2DATA(node, off)); } - child = avl_balance2child[1 + diff]; - + child = (diff > 0); } if (where != NULL) @@ -528,7 +512,7 @@ avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) * Compute the new balance */ old_balance = AVL_XBALANCE(node); - new_balance = old_balance + avl_child2balance[which_child]; + new_balance = old_balance + (which_child ? 1 : -1); /* * If we introduced equal balance, then we are done immediately @@ -708,7 +692,7 @@ avl_remove(avl_tree_t *tree, void *data) * choose node to swap from whichever side is taller */ old_balance = AVL_XBALANCE(delete); - left = avl_balance2child[old_balance + 1]; + left = (old_balance > 0); right = 1 - left; /* @@ -792,7 +776,7 @@ avl_remove(avl_tree_t *tree, void *data) */ node = parent; old_balance = AVL_XBALANCE(node); - new_balance = old_balance - avl_child2balance[which_child]; + new_balance = old_balance - (which_child ? 1 : -1); parent = AVL_XPARENT(node); which_child = AVL_XCHILD(node); |