root/ompi/mca/io/romio321/romio/adio/common/heap-sort.c

DEFINITIONS

1. parent
2. left
3. right
4. ADIOI_Heap_create
5. ADIOI_Heap_free
6. build_heap
7. heapify
8. ADIOI_Heap_insert
9. ADIOI_Heap_extract_min
10. print_heap

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
   2 /* 
   3  *
   4  *   Copyright (C) 2008 University of Chicago. 
   5  *   See COPYRIGHT notice in top-level directory.
   6  */
   7 
   8 #include "heap-sort.h"
   9 #include <assert.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <math.h>
  13 
  14 #define NOEXP2
  15 
  16 static void heapify(heap_t *heap, int i);
  17 
  18 /* From Introduction To Algorithms by Cormen, Leiserson, and Rivest */
  19 
  20 static inline int parent(int i) {
  21     return (i/2);
  22 }
  23 
  24 static inline int left(int i) {
  25     return (2*i);
  26 }
  27 
  28 static inline int right(int i) {
  29     return (2*i + 1);
  30 }
  31 
  32 int ADIOI_Heap_create(heap_t *heap, int size) {
  33     heap->size = size;
  34     heap->nodes = (heap_node_t *) ADIOI_Calloc (size, sizeof(heap_node_t));
  35     if (heap->nodes == NULL)
  36         return 1;
  37     else
  38         return 0;
  39 }
  40 
  41 void ADIOI_Heap_free(heap_t *heap) {
  42     ADIOI_Free(heap->nodes);
  43 }
  44 
  45 /* should suppress unused warnings on GCC */
  46 static void build_heap(heap_t *heap) ATTRIBUTE((unused, used));
  47 
  48 static void build_heap(heap_t *heap)
  49 {
  50     int i;
  51     for (i=(heap->size/2-1); i >= 0; i--)
  52         heapify(heap, i);
  53 }
  54 
  55 static void heapify(heap_t *heap, int i) {
  56     int l, r, smallest;
  57     heap_node_t *nodes;
  58     heap_node_t tmp_node;
  59 
  60     nodes = heap->nodes;
  61 
  62     l = left(i);
  63     r = right(i);
  64 
  65     if ((l <= heap->size) && (nodes[l].offset < nodes[i].offset))
  66         smallest = l;
  67     else
  68         smallest = i;
  69 
  70     if ((r <= heap->size) && (nodes[r].offset < nodes[smallest].offset))
  71         smallest = r;
  72 
  73     if (smallest != i) {
  74         tmp_node = nodes[i];
  75         nodes[i] = nodes[smallest];
  76         nodes[smallest] = tmp_node;
  77         heapify(heap, smallest);
  78     }
  79 }
  80 
  81 void ADIOI_Heap_insert(heap_t *heap, ADIO_Offset offset, int proc,
  82                  ADIO_Offset reg_max_len) {
  83     heap_node_t *nodes;
  84     int i;
  85     nodes = heap->nodes;
  86     i = ++heap->size - 1;
  87     while ((i > 0) && (nodes[parent(i)].offset > offset)) {
  88         nodes[i] = nodes[parent(i)];
  89         i = parent(i);
  90     }
  91     nodes[i].offset      = offset;
  92     nodes[i].proc        = proc;
  93     nodes[i].reg_max_len = reg_max_len;
  94 }
  95 
  96 void ADIOI_Heap_extract_min(heap_t *heap, ADIO_Offset* offset, int *proc,
  97                       ADIO_Offset *reg_max_len) {
  98     heap_node_t *nodes;
  99     nodes = heap->nodes;
 100     
 101     assert (heap->size > 0);
 102     *offset = nodes[0].offset;
 103     *proc = nodes[0].proc;
 104     *reg_max_len = nodes[0].reg_max_len;
 105     nodes[0] = nodes[heap->size-1];
 106     heap->size--;
 107     heapify(heap, 0);
 108 }
 109 
 110 /* should suppress unused warnings on GCC */
 111 static void print_heap(heap_t *heap) ATTRIBUTE((unused, used));
 112 
 113 static void print_heap(heap_t *heap)
 114 {
 115 #ifndef NOEXP2
 116     int i;
 117     double level = 0;
 118     int next_level_idx = 1;
 119 
 120     printf ("heap->size = %d\n", heap->size);
 121     printf ("offsets:\n");
 122     for (i=0; i < heap->size; i++) {
 123         printf ("%lld ", heap->nodes[i].offset);
 124         
 125         if ((i+1) == next_level_idx) {
 126             printf ("\n");
 127             next_level_idx += (int) exp2(level+1);
 128             level++;
 129         }
 130     }
 131     printf ("\n");
 132 #endif
 133 }