Hi guys,

I know C doesn't support templates, but this seems to be the closest thing I've seen. It seems like I could make it insert characters rather tahn integers, so it will sort things like
"abde deod sodce eoeee" rather than "1433 24445 3343 55435" Is this possible?

The book I took this from said it can, both sort numbers and characters....but I'm not sure how to test this out with characters.
This program will sort the list in parellel using MPI. But you dont need to worry about the MPI parts.


I'm pasting the whole code incase I'm missing somthing important but I was curious if there was an easy way to transform this to put characters rather than random numbers in the list.


Here is the important parts I think that need to be modified to insert random characters rather than random numbers:
Code:
/*********************************************************************/
void Get_local_keys(LOCAL_LIST_T* local_keys) {
    int i;

    /* Seed the generator */
    srand(my_rank);

    for (i = 0; i < List_size(local_keys);  i++)
        Insert_key(rand() &#37; KEY_MOD, i, local_keys);
} /* Get_local_keys */


/*********************************************************************/
void Insert_key(KEY_T key, int i, 
    LOCAL_LIST_T* local_keys) {
    List_key(local_keys, i) = key;
} /* Insert_key */


Code:
/* sort_4.c -- level 4 version of sort program
 * 2.  Add fake Get_list_size 
 * 2.  Return scalars in Allocate_list
 * 2.  Add fake Get_local_keys
 * 3.  Definition of Redistribute keys.
 * 3.  Finish Allocate_list.
 * 3.  Add Insert.
 * 3.  Add Local_sort.
 * 3.  Add Print_list.
 * 4.  Add Find_alltoall_send_params.
 * 4.  Add Find_cutoff
 * 4.  Add Find_recv_displacements
 * 4.  Allow input for list size in Get_list_size
 *
 * Input: 
 *     list_size: global size of list to be sorted.
 *
 * Output: contents of list before and after sorting.
 *
 */
#include <stdio.h>
#include <string.h>
#include "mpi.h"
#include "cio.h"
#include "sort_4.h"

int       p;
int       my_rank;
MPI_Comm  io_comm;

/*********************************************************************/
main(int argc, char* argv[]) {
    LOCAL_LIST_T  local_keys;
    int           list_size;
    int           error;

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &p);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Comm_dup(MPI_COMM_WORLD, &io_comm);
    Cache_io_rank(MPI_COMM_WORLD, io_comm);

    list_size = Get_list_size();

    /* Return negative if Allocate failed */
    error = Allocate_list(list_size, &local_keys);
    if (error < 0) {
        printf("Process %d > Can't allocate list\n", my_rank);
        printf("Process %d > Quitting\n", my_rank);
        MPI_Abort(MPI_COMM_WORLD, -1);
    }

    Get_local_keys(&local_keys);
    Print_list(io_comm, &local_keys);

    Redistribute_keys(&local_keys);

    Local_sort(&local_keys);
    Print_list(io_comm, &local_keys);

    MPI_Finalize();
} /* main */


/*********************************************************************/
int Get_list_size(void) {
    int size;

    Cscanf(io_comm,"How big is the list?","%d",&size);
    return size;
} /* Get_list_size */


/*********************************************************************/
/* Return value negative indicates failure */
int Allocate_list(
        int           list_size  /* in  */, 
        LOCAL_LIST_T* local_keys /* out */) {

    List_allocated_size(local_keys) = list_size/p;
    List_size(local_keys) = list_size/p;
    List(local_keys) = (KEY_T*) 
        malloc(List_allocated_size(local_keys)*sizeof(KEY_T));
    if (List(local_keys) == (KEY_T*) NULL)
        return -1;
    else
        return 0;
} /* Allocate_list */


/*********************************************************************/
void Get_local_keys(LOCAL_LIST_T* local_keys) {
    int i;

    /* Seed the generator */
    srand(my_rank);

    for (i = 0; i < List_size(local_keys);  i++)
        Insert_key(rand() % KEY_MOD, i, local_keys);
} /* Get_local_keys */


/*********************************************************************/
void Insert_key(KEY_T key, int i, 
    LOCAL_LIST_T* local_keys) {
    List_key(local_keys, i) = key;
} /* Insert_key */


/*********************************************************************/
void Redistribute_keys(
         LOCAL_LIST_T* local_keys  /* in/out */) {
    int new_list_size, i, error = 0;
    int* send_counts;
    int* send_displacements;
    int* recv_counts;
    int* recv_displacements;
    KEY_T* new_keys;
    
    /* Allocate space for the counts and displacements */
    send_counts = (int*) malloc(p*sizeof(int));
    send_displacements = (int*) malloc(p*sizeof(int));
    recv_counts = (int*) malloc(p*sizeof(int));
    recv_displacements = (int*) malloc(p*sizeof(int));

    Local_sort(local_keys);
    Find_alltoall_send_params(local_keys, 
        send_counts, send_displacements);

    /* Distribute the counts */
    MPI_Alltoall(send_counts, 1, MPI_INT, recv_counts,
        1, MPI_INT, MPI_COMM_WORLD);

    /* Allocate space for new list */
    new_list_size = recv_counts[0];
    for (i = 1; i < p; i++)
        new_list_size += recv_counts[i];
    new_keys = (KEY_T*) 
        malloc(new_list_size*sizeof(KEY_T));

    Find_recv_displacements(recv_counts, recv_displacements);

    /* Exchange the keys */
    MPI_Alltoallv(List(local_keys), send_counts, 
        send_displacements, key_mpi_t, new_keys, 
        recv_counts, recv_displacements, key_mpi_t,
        MPI_COMM_WORLD);

    /* Replace old list with new list */
    List_free(local_keys);
    List_allocated_size(local_keys) = new_list_size;
    List_size(local_keys) = new_list_size;
    List(local_keys) = new_keys;

    /* Free temporary storage */
    free(send_counts);
    free(send_displacements);
    free(recv_counts);
    free(recv_displacements);

} /* Redistribute_keys */


/******************************************************************/
void Find_alltoall_send_params(
         LOCAL_LIST_T* local_keys         /* in  */,
         int*          send_counts        /* out */, 
         int*          send_displacements /* out */) {
    KEY_T cutoff;
    int i, j;

    /* Take care of process 0 */
    j = 0;
    send_displacements[0] = 0;
    send_counts[0] = 0;
    cutoff = Find_cutoff(0);
    /* Key_compare > 0 if cutoff > key */
    while ((j < List_size(local_keys)) &&
           (Key_compare(&cutoff,&List_key(local_keys,j)) 
                > 0)) {
        send_counts[0]++;
        j++;
    }

    /* Now deal with the remaining processes */
    for (i = 1; i < p; i++) {
        send_displacements[i] = 
            send_displacements[i-1] + send_counts[i-1];
        send_counts[i] = 0;
        cutoff = Find_cutoff(i);
        /* Key_compare > 0 if cutoff > key */
        while ((j < List_size(local_keys)) &&
               (Key_compare(&cutoff,&List_key(local_keys,j)) 
                   > 0)) {
            send_counts[i]++;
            j++;
        }
    }
} /* Find_alltoall_send_params */


/*********************************************************************/
int Find_cutoff(int i) {
    return (i+1)*(KEY_MAX + 1)/p;
}  /* Find_cutoff */


/*********************************************************************/
void Find_recv_displacements(int recv_counts[],
    int recv_displacements[]){
    int i;

    recv_displacements[0] = 0;
    for (i = 1; i < p; i++)
        recv_displacements[i] =
            recv_displacements[i-1]+recv_counts[i-1];
} /* Find_recv_displacements */


/*********************************************************************/
void Local_sort(LOCAL_LIST_T* local_keys) {
    
    qsort(List(local_keys), List_size(local_keys), sizeof(KEY_T), 
        (int(*)(const void*, const void*))(Key_compare));
} /* Local_sort */


/*********************************************************************/
int Key_compare(const KEY_T* p, const KEY_T* q) {

    if (*p < *q)
        return -1;
    else if (*p == *q)
        return 0;
    else /* *p > *q */
        return 1;

}  /* Key_compare */


/*********************************************************************/
void Print_list(MPI_Comm io_comm, LOCAL_LIST_T* local_keys) {
    char list_string[LIST_BUF_SIZE];
    char key_string[MAX_KEY_STRING];
    int  i;

    list_string[0] = '\0';
    for (i = 0; i < List_size(local_keys); i++) {
        sprintf(key_string,"%d ", List_key(local_keys,i));
        strcat(list_string, key_string);
    }
    Cprintf(io_comm,"Contents of the list", "%s", list_string);
} /* Print_list */

Code:
/* sort_4.h -- header file for sort_4.c
 * 2. New definition of LOCAL_LIST_T and member access macros
 * 2. Add prototype for Insert_key 
 * 3. Complete definition of LOCAL_LIST_T
 * 3. Add new list macros and def of key_mpi_t
 * 3. Add prototype for Key_compare
 * 3. Add macro for LIST_BUF_SIZE and MAX_KEY_STRING
 * 4. Add prototype for Find_cutoff
 */
#ifndef SORT_H
#define SORT_H

#define KEY_MIN 0
#define KEY_MAX 32767
#define KEY_MOD 32768
#define LIST_BUF_SIZE 128
#define MAX_KEY_STRING 10

typedef int KEY_T;
typedef struct {
    int allocated_size;
    int local_list_size;
    KEY_T* keys;
} LOCAL_LIST_T;

/* Assume list is a pointer to a struct of type
 * LOCAL_LIST_T */
#define List_size(list) ((list)->local_list_size)
#define List_allocated_size(list) ((list)->allocated_size)
#define List(list) ((list)->keys)
#define List_free(list) {free List(list);}
#define List_key(list,i) (*((list)->keys + i))

#define key_mpi_t MPI_INT

int Get_list_size(void);
int Allocate_list(int list_size,
    LOCAL_LIST_T* local_keys);
void Get_local_keys(LOCAL_LIST_T* local_keys);
void Insert_key(KEY_T key, int i,  
    LOCAL_LIST_T* local_keys);
void Redistribute_keys(LOCAL_LIST_T* local_keys);
void Find_alltoall_send_params(LOCAL_LIST_T* local_keys, 
        int send_counts[], int send_displacements[]);
int Find_cutoff(int i);
void Find_recv_displacements(int recv_counts[],
         int recv_displacements[]);
void Local_sort(LOCAL_LIST_T* local_keys);
int Key_compare(const KEY_T* p, const KEY_T* q);
void Print_list(MPI_Comm io_comm, LOCAL_LIST_T* local_keys);
#endif