[ofa-general] [PATCH 3/4] Replaced qsort by enhanced bubble sort
Nicolas Morey Chaisemartin
nicolas.morey-chaisemartin at ext.bull.net
Tue Mar 10 06:59:53 PDT 2009
Signed-off-by: Nicolas Morey-Chaisemartin <nicolas.morey-chaisemartin at ext.bull.net>
---
opensm/opensm/osm_ucast_ftree.c | 107 ++++++++++++++++++++++++++-------------
1 files changed, 72 insertions(+), 35 deletions(-)
diff --git a/opensm/opensm/osm_ucast_ftree.c b/opensm/opensm/osm_ucast_ftree.c
index 0ba4999..bfefa0f 100644
--- a/opensm/opensm/osm_ucast_ftree.c
+++ b/opensm/opensm/osm_ucast_ftree.c
@@ -81,7 +81,6 @@ typedef enum {
** Forward references
**
***************************************************/
-
struct ftree_sw_t_;
struct ftree_hca_t_;
struct ftree_port_t_;
@@ -174,6 +173,7 @@ typedef struct ftree_sw_t_ {
boolean_t is_leaf;
unsigned down_port_groups_idx;
uint32_t min_counter_down;
+ boolean_t counter_up_changed;
} ftree_sw_t;
/***************************************************
@@ -1901,7 +1901,7 @@ static void __osm_ftree_set_sw_fwd_table(IN cl_map_item_t * const p_map_item,
p_sw->p_osm_sw);
}
-static void
+static inline void
__osm_ftree_recalculate_min_counter_down(ftree_sw_t *p_sw){
uint32_t min= (1<<30);
uint32_t i;
@@ -1914,23 +1914,16 @@ __osm_ftree_recalculate_min_counter_down(ftree_sw_t *p_sw){
return;
}
-static uint32_t
+static inline uint32_t
__osm_ftree_find_lowest_loaded_group_on_sw(ftree_sw_t *p_sw){
- /*uint32_t min= (1<<30);
- uint32_t i;
- for(i=0;i < p_sw->down_port_groups_num; i++) {
- if(p_sw->down_port_groups[i]->counter_down < min){
- min = p_sw->down_port_groups[i]->counter_down;
- }
- }*/
return p_sw->min_counter_down;
}
/* This is for downgoing_by_going_up.
* If load are equals, let's have a look at the remote switches and find the less loaded one */
-static int
-__osm_ftree_port_group_compare_load_down(const void* p1,const void* p2){
- int temp = (*((ftree_port_group_t**)p1))->counter_down -(*((ftree_port_group_t**)p2))->counter_down ;
+static inline int
+__osm_ftree_port_group_compare_load_down(const ftree_port_group_t *p1,const ftree_port_group_t *p2){
+ int temp = p1->counter_down -p2->counter_down ;
if(temp > 0)
return 1;
if(temp < 0)
@@ -1938,32 +1931,78 @@ __osm_ftree_port_group_compare_load_down(const void* p1,const void* p2){
/* Find the less loaded remote sw and choose this one */
do{
- uint32_t load1=__osm_ftree_find_lowest_loaded_group_on_sw((*((ftree_port_group_t**)p1))->remote_hca_or_sw.p_sw);
- uint32_t load2=__osm_ftree_find_lowest_loaded_group_on_sw((*((ftree_port_group_t**)p2))->remote_hca_or_sw.p_sw);
+ uint32_t load1=__osm_ftree_find_lowest_loaded_group_on_sw(p1->remote_hca_or_sw.p_sw);
+ uint32_t load2=__osm_ftree_find_lowest_loaded_group_on_sw(p2->remote_hca_or_sw.p_sw);
temp = load1-load2;
if(temp > 0)
return 1;
- if(temp < 0)
- return -1;
+ return 0;
}while(0);
- /* If they are both equal, choose the biggest GUID */
- if(((*((ftree_port_group_t**)p1)))->remote_port_guid > ((*((ftree_port_group_t**)p2)))->remote_port_guid)
- return 1;
+}
- return -1;
+static inline void
+__osm_ftree_bubble_sort_up(ftree_port_group_t **p_group_array, uint32_t nmemb)
+{
+ uint32_t i = 0; /* Indice de répétition du tri */
+ uint32_t j = 0; /* Variable de boucle */
+ ftree_port_group_t *tmp = p_group_array[0]; /* Variable de stockage temporaire et de fin de tri*/
+ if(tmp->hca_or_sw.p_sw->counter_up_changed == FALSE){
+ return;
+ }
+ /* Boucle de répétition du tri et le test qui
+ arrête le tri dès que le tableau est ordonné */
+ for(i = 0 ; tmp ; i++)
+ {
+ /* Supposons le tableau ordonné */
+ tmp = NULL;
+ /* Vérification des éléments des places j et j-1 */
+ for(j = 1 ; j < (nmemb - i) ; j++)
+ {
+ /* Si les 2 éléments sont mal triés */
+ if( p_group_array[j]->counter_up < p_group_array[j-1]->counter_up)
+ {
+ /* Inversion des 2 éléments */
+ tmp = p_group_array[j-1];
+ p_group_array[j-1] = p_group_array[j];
+ p_group_array[j] = tmp;
+
+ }
+ }
+ }
+ p_group_array[0]->hca_or_sw.p_sw->counter_up_changed = FALSE;
}
-/* This is for upgoing_by_going_down. There is not much equilibration to do so don't bother looking at the next rank */
-static int
-__osm_ftree_port_group_compare_load_up(const void* p1,const void* p2){
- int temp = (*((ftree_port_group_t**)p1))->counter_up -(*((ftree_port_group_t**)p2))->counter_up ;
- if(temp > 0)
- return 1;
- if(temp < 0)
- return -1;
- return 0;
+static inline void
+__osm_ftree_bubble_sort_down(ftree_port_group_t **p_group_array, uint32_t nmemb)
+{
+ uint32_t i = 0; /* Indice de répétition du tri */
+ uint32_t j = 0; /* Variable de boucle */
+ ftree_port_group_t *tmp = p_group_array[0]; ; /* Variable de stockage temporaire et de fin de tri*/
+
+ /* Boucle de répétition du tri et le test qui
+ arrête le tri dès que le tableau est ordonné */
+ for(i = 0 ; tmp ; i++)
+ {
+ /* Supposons le tableau ordonné */
+ tmp = NULL;
+ /* Vérification des éléments des places j et j-1 */
+ for(j = 1 ; j < (nmemb - i) ; j++)
+ {
+ /* Si les 2 éléments sont mal triés */
+ if( __osm_ftree_port_group_compare_load_down(p_group_array[j],p_group_array[j-1]) < 0 )
+ {
+ /* Inversion des 2 éléments */
+ tmp = p_group_array[j-1];
+ p_group_array[j-1] = p_group_array[j];
+ p_group_array[j] = tmp;
+
+ }
+ }
+ }
}
+
+
/***************************************************
***************************************************/
@@ -2009,10 +2048,7 @@ __osm_ftree_fabric_route_upgoing_by_going_down(IN ftree_fabric_t * p_ftree,
return FALSE;
/* foreach down-going port group (in indexing order) */
-
- qsort(p_sw->down_port_groups,p_sw->down_port_groups_num,sizeof(*(p_sw->down_port_groups)), __osm_ftree_port_group_compare_load_up);
-
-
+ __osm_ftree_bubble_sort_up(p_sw->down_port_groups,p_sw->down_port_groups_num);
for (k = 0; k < p_sw->down_port_groups_num; k++) {
p_group = p_sw->down_port_groups[k];
@@ -2154,6 +2190,7 @@ __osm_ftree_fabric_route_upgoing_by_going_down(IN ftree_fabric_t * p_ftree,
if(routed)
p_min_port->counter_up++;
p_group->counter_up++;
+ p_group->hca_or_sw.p_sw->counter_up_changed = TRUE;
}
/* done scanning all the down-going port groups */
@@ -2253,7 +2290,7 @@ __osm_ftree_fabric_route_downgoing_by_going_up(IN ftree_fabric_t * p_ftree,
/* We should generate a list of port sorted by load so we can find easily the least
* going port and explore the other pots on secondary routes more easily (and quickly) */
- qsort(p_sw->up_port_groups,p_sw->up_port_groups_num,sizeof(*(p_sw->up_port_groups)), __osm_ftree_port_group_compare_load_down);
+ __osm_ftree_bubble_sort_down(p_sw->up_port_groups,p_sw->up_port_groups_num);
p_min_group = p_sw->up_port_groups[0];
--
1.6.2-rc2.GIT
More information about the general
mailing list