listrank.c

/**********************************************************************************
 NOTES:  This listranking code is modified to return the prefix value of the last element in the list after the List Ranking operation is done. This prefix value is the total no of leaves for the rake operation. It does not return the list head pointer.

Last changed July 30 2002

**********************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "listrank.h"
#include "alg_random.h"

typedef struct master_d
{
  LISTRANK_TYPE prefix;
  LDATA succ;
  LDATA index;
} master_t;


LDATA list_ranking(LDATA n, int k, list_t *List, THREADED)
{
  
  register LDATA i, j, s, target, current, prev;
  register LISTRANK_TYPE val;
  LDATA 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;
  LDATA *Succ;
  master_t *s_master_ptr;
  list_t *list_ptr, *s_list_ptr, *f_list_ptr;
  LDATA list_head_ptr;
  //added to listrank.c code to determine total no leaves in the tree.
  LDATA *totalnoleaves;

  s = k * THREADS;
  list_head_ptr = -1;
  
  Sums = (LDATA *) node_malloc((THREADS)*sizeof(LDATA), TH);
  Master = (master_t *) node_malloc((s+1)*sizeof(master_t),TH); 
  Succ = (LDATA *) node_malloc(n*sizeof(LDATA),TH);
  totalnoleaves = (LDATA *) node_malloc(sizeof(LDATA),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 = ((LDATA) floor((log((double) group)/log((double) 2))+0.1));
  group_m1 = group - 1;
  
  times = (LDATA) 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);
    //added to listrank.c code to determine total no leaves in the tree.
    if(s_list_ptr -> succ < 0)
      *totalnoleaves = s_list_ptr->prefix;
  } 

  node_free(Sums, TH);
  node_free(Master, TH);
  node_free(Succ, TH);

  //return(node_Bcast_l(list_head_ptr,TH));
  //added to listrank.c code to return total no leaves in the tree.
  return(*totalnoleaves);   
}