aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2006-12-03 11:53:27 -0500
committerArnaldo Carvalho de Melo <acme@mandriva.com>2006-12-03 11:53:27 -0500
commit2bbf29acd8f7adcf161de7e5d891b4095687a59f (patch)
tree955b15fa3bcdee1f879949d8639c5e9d5b82e84e /net
parent44158306d756c88272c8faf243ca68897498e219 (diff)
[DCCP] tfrc: Binary search for reverse TFRC lookup
This replaces the linear search algorithm for reverse lookup with binary search. It has the advantage of better scalability: O(log2(N)) instead of O(N). This means that the average number of iterations is reduced from 250 (linear search if each value appears equally likely) down to at most 9. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz> Signed-off-by: Arnaldo Carvalho de Melo <acme@mandriva.com>
Diffstat (limited to 'net')
-rw-r--r--net/dccp/ccids/lib/tfrc_equation.c38
1 files changed, 24 insertions, 14 deletions
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index 0a4a3d2feba5..ddac2c511e2f 100644
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -594,6 +594,21 @@ static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
594 { 243315981, 271305 } 594 { 243315981, 271305 }
595}; 595};
596 596
597/* return largest index i such that fval <= lookup[i][small] */
598static inline u32 tfrc_binsearch(u32 fval, u8 small)
599{
600 u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1;
601
602 while (low < high) {
603 try = (low + high) / 2;
604 if (fval <= tfrc_calc_x_lookup[try][small])
605 high = try;
606 else
607 low = try + 1;
608 }
609 return high;
610}
611
597/** 612/**
598 * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448 613 * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448
599 * 614 *
@@ -656,8 +671,7 @@ EXPORT_SYMBOL_GPL(tfrc_calc_x);
656 */ 671 */
657u32 tfrc_calc_x_reverse_lookup(u32 fvalue) 672u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
658{ 673{
659 int ctr = 0; 674 int index;
660 int small;
661 675
662 if (fvalue == 0) /* f(p) = 0 whenever p = 0 */ 676 if (fvalue == 0) /* f(p) = 0 whenever p = 0 */
663 return 0; 677 return 0;
@@ -672,18 +686,14 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
672 return 1000000; 686 return 1000000;
673 } 687 }
674 688
675 if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) 689 if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) {
676 small = 1; 690 index = tfrc_binsearch(fvalue, 1);
677 else 691 return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
678 small = 0; 692 }
679 693
680 while (fvalue > tfrc_calc_x_lookup[ctr][small]) 694 /* else ... it must be in the coarse-grained column */
681 ctr++; 695 index = tfrc_binsearch(fvalue, 0);
682 696 return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;
683 if (small)
684 return (ctr + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
685 else
686 return (ctr + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;
687} 697}
688 698
689EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup); 699EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);