root/ompi/mca/fcoll/base/fcoll_base_sort.c

DEFINITIONS

1. ompi_fcoll_base_sort_iovec

   1 /* -*- Mode: C; c-basic-offset:4 ; -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2007 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2008-2016 University of Houston. All rights reserved.
  14  * Copyright (c) 2017      IBM Corporation. All rights reserved.
  15  * $COPYRIGHT$
  16  *
  17  * Additional copyrights may follow
  18  *
  19  * $HEADER$
  20  */
  21 
  22 #include "ompi_config.h"
  23 #include "base.h"
  24 #include "ompi/mca/common/ompio/common_ompio.h"
  25 
  26 
  27 int ompi_fcoll_base_sort_iovec (struct iovec *iov,
  28                            int num_entries,
  29                            int *sorted)
  30 {
  31     int i = 0;
  32     int j = 0;
  33     int left = 0;
  34     int right = 0;
  35     int largest = 0;
  36     int heap_size = num_entries - 1;
  37     int temp = 0;
  38     unsigned char done = 0;
  39     int* temp_arr = NULL;
  40 
  41     if (0 == num_entries) {
  42         return OMPI_SUCCESS;
  43     }
  44 
  45     temp_arr = (int*)malloc(num_entries*sizeof(int));
  46     if (NULL == temp_arr) {
  47         opal_output (1, "OUT OF MEMORY\n");
  48         return OMPI_ERR_OUT_OF_RESOURCE;
  49     }
  50     temp_arr[0] = 0;
  51     for (i = 1; i < num_entries; ++i) {
  52         temp_arr[i] = i;
  53     }
  54     /* num_entries can be a large no. so NO RECURSION */
  55     for (i = num_entries/2-1 ; i>=0 ; i--) {
  56         done = 0;
  57         j = i;
  58         largest = j;
  59 
  60         while (!done) {
  61             left = j*2+1;
  62             right = j*2+2;
  63             if ((left <= heap_size) &&
  64                 (iov[temp_arr[left]].iov_base > iov[temp_arr[j]].iov_base)) {
  65                 largest = left;
  66             }
  67             else {
  68                 largest = j;
  69             }
  70             if ((right <= heap_size) &&
  71                 (iov[temp_arr[right]].iov_base >
  72                  iov[temp_arr[largest]].iov_base)) {
  73                 largest = right;
  74             }
  75             if (largest != j) {
  76                 temp = temp_arr[largest];
  77                 temp_arr[largest] = temp_arr[j];
  78                 temp_arr[j] = temp;
  79                 j = largest;
  80             }
  81             else {
  82                 done = 1;
  83             }
  84         }
  85     }
  86 
  87     for (i = num_entries-1; i >=1; --i) {
  88         temp = temp_arr[0];
  89         temp_arr[0] = temp_arr[i];
  90         temp_arr[i] = temp;
  91         heap_size--;
  92         done = 0;
  93         j = 0;
  94         largest = j;
  95 
  96         while (!done) {
  97             left =  j*2+1;
  98             right = j*2+2;
  99 
 100             if ((left <= heap_size) &&
 101                 (iov[temp_arr[left]].iov_base >
 102                  iov[temp_arr[j]].iov_base)) {
 103                 largest = left;
 104             }
 105             else {
 106                 largest = j;
 107             }
 108             if ((right <= heap_size) &&
 109                 (iov[temp_arr[right]].iov_base >
 110                  iov[temp_arr[largest]].iov_base)) {
 111                 largest = right;
 112             }
 113             if (largest != j) {
 114                 temp = temp_arr[largest];
 115                 temp_arr[largest] = temp_arr[j];
 116                 temp_arr[j] = temp;
 117                 j = largest;
 118             }
 119             else {
 120                 done = 1;
 121             }
 122         }
 123         sorted[i] = temp_arr[i];
 124     }
 125     sorted[0] = temp_arr[0];
 126 
 127     if (NULL != temp_arr) {
 128         free(temp_arr);
 129         temp_arr = NULL;
 130     }
 131     return OMPI_SUCCESS;
 132 }