85 int old_bucket_id(int i,int j,bucket_list_t bucket_list)  in old_bucket_id()  argument
90   pivot = bucket_list->pivot;  in old_bucket_id()
91   n = bucket_list->nb_buckets;  in old_bucket_id()
92   val = bucket_list->tab[i][j];  in old_bucket_id()
114 int bucket_id(int i,int j,bucket_list_t bucket_list)  in bucket_id()  argument
119   pivot_tree = bucket_list->pivot_tree;  in bucket_id()
120   val = bucket_list->tab[i][j];  in bucket_id()
124   for( k = 0 ; k < bucket_list->max_depth ; k++){  in bucket_id()
155 void display_pivots(bucket_list_t bucket_list)  in display_pivots()  argument
158   for( i = 0 ; i < bucket_list->nb_buckets-1 ; i++)  in display_pivots()
159     printf("pivot[%d]=%f\n",i,bucket_list->pivot[i]);  in display_pivots()
163 void display_bucket_list(bucket_list_t bucket_list)  in display_bucket_list()  argument
170   for(i = 0 ; i < bucket_list->nb_buckets ; i++){  in display_bucket_list()
171     inf = bucket_list->pivot[i];  in display_bucket_list()
172     sup = bucket_list->pivot[i-1];  in display_bucket_list()
175     if( i == bucket_list->nb_buckets - 1 )  in display_bucket_list()
179       display_bucket(bucket_list->bucket_tab[i]);  in display_bucket_list()
182     check_bucket(bucket_list->bucket_tab[i],bucket_list->tab,inf,sup);  in display_bucket_list()
187 void add_to_bucket(int id,int i,int j,bucket_list_t bucket_list)  in add_to_bucket()  argument
192   bucket = bucket_list->bucket_tab[id];  in add_to_bucket()
196     N = bucket_list->N;  in add_to_bucket()
197     n = bucket_list->nb_buckets;  in add_to_bucket()
238 void  built_pivot_tree(bucket_list_t bucket_list)  in built_pivot_tree()  argument
243   pivot = bucket_list->pivot;  in built_pivot_tree()
244   n = bucket_list->nb_buckets;  in built_pivot_tree()
246   bucket_list->max_depth = (int)CmiLog2(n) - 1;  in built_pivot_tree()
248   dfs(1,1,n-1,pivot,pivot_tree,0,bucket_list->max_depth);  in built_pivot_tree()
255   bucket_list->pivot_tree = pivot_tree;  in built_pivot_tree()
264 void fill_buckets(bucket_list_t bucket_list)  in fill_buckets()  argument
268   N = bucket_list->N;  in fill_buckets()
272       id = bucket_id(i,j,bucket_list);  in fill_buckets()
273       add_to_bucket(id,i,j,bucket_list);  in fill_buckets()
294   bucket_list_t bucket_list;  in partial_sort()  local
318   bucket_list = (bucket_list_t)MALLOC(sizeof(_bucket_list_t));  in partial_sort()
319   bucket_list->tab = tab;  in partial_sort()
320   bucket_list->N = N;  in partial_sort()
344   global_bl = bucket_list;  in partial_sort()
369   bucket_list->pivot = pivot;  in partial_sort()
370   bucket_list->nb_buckets = nb_buckets;  in partial_sort()
371   built_pivot_tree(bucket_list);  in partial_sort()
373   bucket_list->bucket_tab = (bucket_t**)MALLOC(nb_buckets*sizeof(bucket_t*));  in partial_sort()
375     bucket_list->bucket_tab[i] = (bucket_t*)CALLOC(1,sizeof(bucket_t));  in partial_sort()
377   fill_buckets(bucket_list);  in partial_sort()
381   bucket_list->cur_bucket = 0;  in partial_sort()
382   bucket_list->bucket_indice = 0;  in partial_sort()
386   *bl = bucket_list;  in partial_sort()
389 void next_bucket_elem(bucket_list_t bucket_list,int *i,int *j)  in next_bucket_elem()  argument
391   bucket_t *bucket = bucket_list->bucket_tab[bucket_list->cur_bucket];  in next_bucket_elem()
396   while( bucket->nb_elem <= bucket_list->bucket_indice ){  in next_bucket_elem()
397     bucket_list->bucket_indice = 0;  in next_bucket_elem()
398     bucket_list->cur_bucket++;  in next_bucket_elem()
399     bucket = bucket_list->bucket_tab[bucket_list->cur_bucket];  in next_bucket_elem()
401       printf("### From bucket %d to bucket %d\n",bucket_list->cur_bucket-1,bucket_list->cur_bucket);  in next_bucket_elem()
402 …m: %d, indice: %d, bucket_id: %d\n",(int)bucket->nb_elem,bucket_list->bucket_indice,bucket_list->c…  in next_bucket_elem()
407     global_bl = bucket_list;  in next_bucket_elem()
412   *i = bucket->bucket[bucket_list->bucket_indice].i;  in next_bucket_elem()
413   *j = bucket->bucket[bucket_list->bucket_indice].j;  in next_bucket_elem()
414   bucket_list->bucket_indice++;  in next_bucket_elem()
509 void free_bucket_list(bucket_list_t bucket_list)  in free_bucket_list()  argument
512   free_tab_bucket(bucket_list->bucket_tab,bucket_list->nb_buckets);  in free_bucket_list()
513   FREE(bucket_list->pivot);  in free_bucket_list()
514   FREE(bucket_list->pivot_tree);  in free_bucket_list()
515   FREE(bucket_list);  in free_bucket_list()
541   bucket_list_t bucket_list;  in bucket_grouping()  local
557   partial_sort(&bucket_list,mat,N);  in bucket_grouping()
562     display_pivots(bucket_list);  in bucket_grouping()
574       next_bucket_elem(bucket_list,&i,&j);  in bucket_grouping()
586       next_bucket_elem(bucket_list,&i,&j);  in bucket_grouping()
602     next_bucket_elem(bucket_list,&i,&j);  in bucket_grouping()
675     printf("Bucket: %d, indice:%d\n",bucket_list->cur_bucket,bucket_list->bucket_indice);  in bucket_grouping()
678   free_bucket_list(bucket_list);  in bucket_grouping()