text: #include <stdio.h>
  #include <stdlib.h>
  #include <math.h>
  #include "listrank.h"
  #include "alg_random.h"
  
  typedef struct master_d
  {
    LISTRANK_TYPE prefix;
    int succ;
    int index;
  } master_t;
  
  
  int list_ranking(int n, int k, list_t *List, THREADED)
  {
    
    register int i, j, s, target, current, prev;
    register LISTRANK_TYPE val;
    int block, start, finish, group, group_log, group_m1, times,
      shift, div, rem, master_tail, result, v, *succ_ptr, succ, seed,error,
      *Sums,tot,initial;
    master_t *Master;
    int *Succ;
    master_t *s_master_ptr;
    list_t *list_ptr, *s_list_ptr, *f_list_ptr;
    int list_head_ptr;
  
    s = k * THREADS;
    list_head_ptr = -1;
    
    Sums = (int *) node_malloc((THREADS)*sizeof(int), TH);
    Master = (master_t *) node_malloc((s+1)*sizeof(master_t),TH); 
    Succ = (int *) node_malloc(n*sizeof(int),TH);
    
    node_Barrier();
    
    /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
    /* FIND THE HEAD */
  
    block = n/THREADS;
    start = block * MYTHREAD;
    finish = start + block;
    if (MYTHREAD == THREADS-1) finish = n;
  
    tot = 0;
    
    for (i=start ; i<finish ; i++) {
      tot += (Succ[i] = List[i].succ);
  
      if (List[i].succ < 0) {
        tot = tot - List[i].succ;
        List[i].succ = -(s + 1);
      }
    }
    
    Sums[MYTHREAD] = tot; 
   
    /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
    /* IDENTIFY THE  MASTERS */
    
    s_master_ptr = Master + k * MYTHREAD;
    
    group = n/s;
    group_log = ((int) floor((log((double) group)/log((double) 2))+0.1));
    group_m1 = group - 1;
    
    times = (int) 31/group_log;
    shift = 31 - times*group_log;
    div = k/times;
    rem = k - (times*div);
    start = start - group;
    current = -(k*MYTHREAD);
    
    for (i=0 ; i<div ; i++) {
      v = rrandom_th(TH);
      target = ((v = (v >> shift)) & group_m1) + (start += group);
      (++s_master_ptr) -> index = target;
      s_master_ptr -> succ = List[target].succ;
      List[target].succ = --current; 
      for (j=1;j<times;j++) {
        target = ((v >>= group_log) & group_m1) + (start += group);
        (++s_master_ptr) -> index = target;
        s_master_ptr -> succ = List[target].succ;
        List[target].succ = --current;
      }
    }
    
    v = rrandom_th(TH);
    v = (v >> shift);
    for (i=0;i<rem;i++) {
      target = ((v >>= group_log) & group_m1) + (start += group);
      (++s_master_ptr) -> index = target;
      s_master_ptr -> succ = List[target].succ;
      List[target].succ = --current;
    }
    
    node_Barrier();
  
    on_one {
      tot = 0;
        
      for (i=0 ; i<THREADS ; i++) {
        tot += Sums[i];  
      }
      list_head_ptr = (((n - 1)*n)/2) - tot;
  
      if (List[list_head_ptr].succ < 0) {
        Master -> succ = initial = -List[list_head_ptr].succ;
        Master -> prefix = Master[initial].prefix = LISTRANK_IDENTITY;
      }
      else {
        initial = 0;
        Master -> prefix = LISTRANK_IDENTITY;
        Master -> index = list_head_ptr;
        Master -> succ = List[list_head_ptr].succ;
        List[list_head_ptr].succ = 0;
      } 
    }
    
    node_Barrier();
  
    /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
    /* TRAVERSE THE SUBLISTS */
  
    start = (k * MYTHREAD) + 1;
    finish = start + k;
    if ((MYTHREAD == 0) && (initial == 0))
      start = 0;
    
    for (i = start; i < finish; i++) {
      current = Master[i].index;
      val     = List[current].prefix;    
      current = Master[i].succ;
      if (current >= 0) { /* We aren't at the end of the list */
        target = List[current].succ;
        while (target >= 0) {
          val = List[current].prefix = (val LISTRANK_OPERATOR List[current].prefix);
  	List[current].succ = - i;
  	current            = target;
  	target             = List[current].succ;
        }
        if (target > (- s - 1)) { /* We are at a new sublist */
          Master[- target].prefix = val;
  	Master[i].succ =  -target;
        }
        else { /* We are at the end of the list */
          List[current].prefix = (val LISTRANK_OPERATOR List[current].prefix);
  	List[current].succ = - i;
        }
      }
    } 
    
    node_Barrier();
  
    /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */  
    /* RANK THE MASTERS: */
  
    on_one {
      succ = Master -> succ; 
      current = 0;
        
      for (i=0 ; i<s ; i++) {
        Master[succ].prefix =
  	(Master[succ].prefix LISTRANK_OPERATOR Master[current].prefix);
        current = succ;
        succ = Master[current].succ;  
      } 
        
    }
    
    node_Barrier();
  
    /* +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */
    /* COMPLETE THE RANK OF EVERY ELEMENT: */
  
    s_list_ptr = List + (block * MYTHREAD) -1;
    f_list_ptr = s_list_ptr + block;
    if (MYTHREAD == THREADS - 1) f_list_ptr = List + n - 1;
    succ_ptr = Succ + (block * MYTHREAD) - 1;
    
    while ((++s_list_ptr) <= f_list_ptr) {
      s_list_ptr->prefix = s_list_ptr->prefix LISTRANK_OPERATOR 
        Master[-s_list_ptr->succ].prefix;
      s_list_ptr -> succ =  *(++succ_ptr);
    } 
  
    node_free(Sums, TH);
    node_free(Master, TH);
    node_free(Succ, TH);
  
    return(node_Bcast_i(list_head_ptr,TH));
  }
  
  
  
  