?
Solved

i'm trying to write a parallel algorithm for sorting a list of words.  using fork() and pipe().

Posted on 2004-11-18
11
Medium Priority
?
228 Views
Last Modified: 2010-04-15
i have written this code and i'm not sure why it isn't working. if anyone has any ideas i'd be very grateful.
the program takes in a list of words from a file and sorts them. it is then supposed to output the list to another file but my output list is the
same as my input list.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXCHAR 20 // This is the maximum number of characters allowed
//in a filename.
#define MAXNOWORDS 300 // This is the maximum number of words allowed


// Function declarations
void error_exit(char *s);
int file_length(FILE *file);
int fget_cell(FILE *cell_file, int max, char *cell);
int read_data_file(FILE *datafile, char *p[]);
int print(FILE *datafile, char *p[], int n);
char downify(char c);
void downstring(char *str);
void swap(char **l, char **s);
void bubble_sort(char* p[], int n);
int my_compare(char* p[], int i, int j);

int main(void){
      // Variable declarations
      char* p[MAXNOWORDS];
      char *array[MAXNOWORDS],*a[MAXNOWORDS],*b[MAXNOWORDS],*v[1];
      int i,n,outwords,flag[2][2],value=1,c=0,d=0;
      FILE *datafile;
      char filename[MAXCHAR ];
      printf("Welcome to the Word Sort program!\n");

      
      // Open data file for reading of unsorted wordlist
      datafile=NULL;
      while(datafile==NULL)
      {
            printf("Please enter data input filename (list.txt): ");
            scanf("%s", filename);
            
            datafile=fopen(filename, "r");
            
      }
      
      n=read_data_file(datafile,array);
      fclose(datafile);
      v[1] = calloc(strlen(array[1])+1,sizeof(char));
      v[1]="g";
      
      
      
      for (i=0;i<n;i++)
      {printf("word %d=%s",i,array[i]);
      if (strcmp(v[1],array[i]) > 0)
      {
            a[c]=calloc(strlen(array[i])+1, sizeof(char));
            strcpy(a[c],array[i]);
            c++;
      }
      else
      {
            b[d]=calloc(strlen(array[i])+1, sizeof(char));
            strcpy(a[d],array[i]);
            d++;
      }
      }
      for(i=0; i<c;i++)
      printf("Hi %s ",a[c]);
      printf(" \n");
      for(i=0; i<d;i++)
      printf("Hi %s ",b[d]);
      printf(" \n");

      // If the file contained too many words to load print an error message and
//exit.
      if(n > MAXNOWORDS)
      {
            printf("\n\tError: sorry but your file contains %d words\n\tbut this rogram can only sort %d words.\nExiting.\n", n, MAXNOWORDS);

            return 1; // This means the program exits and an error code is sent to the
//shell.
      }

      // Setup an array of pointers to the words this will improve speed of
//sorting.
      for(i=0;i<n;i++)
      {
            p[i] = array[i];
      }

      for( i = 0; i<2; i++){
            if (pipe(flag[i]) == -1)                                /* create a pipe
*/
                  error_exit("pipe(1,i) failed");
      }
      // Call the actual sorting algorithm
      
      
      
      
      
      for(i=0;i<1;i++){
            value = fork();
            if(value == 0){
                  bubble_sort(p,n);
                  
                  
                  printf("i=%d :: %s, %s, %s, %s\n",i,p[i*4],p[i*4+1],p[i*4+2],p[i*4+3]);
                  exit(0);
            }
            printf("value=%d, i=%d, %s, %s, %s, %s\n",value,i,p[i*4],p[i*4+1],p[i*4+2],p[i*4+3]);

      }

      printf("Sleeping...\n");
      sleep(10);
      for(i=0;i<2;i++){
            printf("value=%d, i=%d, %s, %s, %s, %s\n",value,i,p[i*4],p[i*4+1],p[i*4+2],p[i*4+3]);

      }
      // Open data file for output of sorted wordlist.
      datafile=NULL;
      while(datafile==NULL)
      {
            printf("\nPlease enter data output filename (if the file already exists\nit will be overwritten): ");

            scanf("%s", filename);
            datafile=fopen(filename, "w");
      }
      outwords=print(datafile,p,n);
      fclose(datafile);
      if(outwords!=n)
      {
            printf("\nAn error occurred while printing the sorted wordlist to a file.\n");

            printf("%d words were outputted while %d words were to be sorted.\n",outwords, n);

            return 1;
      }

      // Exit successfully
      return 0;
}

// Prints the sorted list of words to a file, one entry per line.
int print(FILE *datafile, char *p[], int n)
{
      int i;

      for (i=0;i<n;++i)
      {
            fprintf(datafile,"%s\n", p[i]);
      }

      return i;
}

// This function reads each word from the input file into dynamically
//allocated memory
// and returns the number of words in the file.
int read_data_file(FILE *datafile, char* array[])
{
      int n, row, i, newline;
      char c;

      // Find no of rows in file
      n = file_length(datafile);

      printf("Loading word list file....");
      for (row=0; (row < n) && (row < MAXNOWORDS); row++)
      {
            array[row]=(char *)calloc(1,sizeof(char[MAXCHAR ]));
            fscanf(datafile,"%s\n",array[row]);
            printf("word %d=%s",row,array[row]);
      }

      return n;
}

// This function counts the number of words in the file.
int file_length(FILE *file)
{
      int lines;
      char dummy[100];

      rewind(file);

      lines=0;
      while( fgets(dummy, 100, file) != NULL)
      lines++;

      rewind(file);

      return(lines);
}

// This is the bubble sort algorithm. It repeatedly traverses the list of
//words
// bringing the alphabetically last eg 'zzzz' element to the end of the list
//then
// the second last to the second last place etc until all elements have been
//sorted.
void bubble_sort(char *p[], int n)
{
      int i,j;

      
      for (i=0;i<(n-1);++i)
      
            
            for (j=0;j<n-1-i;j++)
            for(j=i+1; j<n; ++j)
            if(strcmp(p[i], p[j])>0)
            swap(&p[i], &p[j]);
      

}
// This function compares two strings alphabetically and returns 1 if the
//second string
// should precede the first string. It works on both upper and lower case
//strings by
// converting them all first to lower case strings.
int my_compare(char *p[], int i, int j)
{
      char str1[MAXCHAR],str2[MAXCHAR];
      int compare;

      // Use temporary variables for strings so converting them to lower case
      // doesn't affect the original string.
      strcpy(str1,p[i]);
      strcpy(str2,p[j]);
      // Convert both strings to lower case so case distinction won't matter
      // when comparing them.
      downstring(str1);
      downstring(str2);

      compare = strcmp(str1,str2);

      if(compare <= 0) // In this case str1 alphabetically precedes str2 or they
//are equal
            return 0;
      else
            return 1; // In this case str2 alphabetically precedes str1
}

// This function converts a string to its lower case equivalent.
void downstring(char *str)
{
  int i;

  for(i=0; *(str+i)!='\0';i++)
  {
  str[i]=downify(str[i]);
  }
}

// This function converts a character to its lower case equivalent
char downify(char c)
{
  if ((c >= 'A') && (c <= 'Z'))
    return (c + 'a' - 'A');
  else
    return (c);
}

// This function swaps two strings
void swap(char **l, char **s)
{
      char *tmp;

      tmp =*l;
      *l=*s;
      *s=tmp;

      //return;
}

void error_exit(char *s)
{
   fprintf(stderr, "\nERROR: %s - bye!\n", s);
   exit(1);
}

0
Comment
Question by:ronanh09
  • 4
  • 4
9 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12618954

A quick look suggests that you're mixing tasks and threads.

The sorted list that is generated in the spawned task does not share memory with the original task.  When it completes the sort, the data is available only to that task.


Kent
0
 
LVL 22

Expert Comment

by:grg99
ID: 12618962
{
          b[d]=calloc(strlen(array[i])+1, sizeof(char));
          strcpy(a[d],array[i]);
          d++;
     }


dont you mean:   strcpy( b[d], ...  ?
0
 

Author Comment

by:ronanh09
ID: 12624419
dont you mean:   strcpy( b[d], ...  ?

ya just changed that but it didn't make a diference . thanks anyway.


"A quick look suggests that you're mixing tasks and threads.

The sorted list that is generated in the spawned task does not share memory with the original task.  When it completes the sort, the data is available only to that task.Kent"

thanks kent. how would i go about sorting this out?



0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12624725

Are you familiar with threads?  They are a very commonly used functionality that you'll undoubted see.  (You can't program an effective GUI application without them.)  Threads are nothing more than a way for one program to have multiple execution points.  Tasks are really separate programs.

If you want to keep using pipes, you'll have to use shared memory to contain the shared buffers, or use pipes to transfer data between the threads.


Kent
0
 

Author Comment

by:ronanh09
ID: 12625311
ya i'm familiar with threads. i have to keep using pipes though cause it's part of an assignment.
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 12625413
Are you using Windows or linux?

0
 

Author Comment

by:ronanh09
ID: 12625609
linux.
0
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 2000 total points
ID: 12625688

You could declare a shared region using mmap().  This would be my approach.

But if your assignment calls for using pipes to transfer the data between tasks, you'd better follow that lead.

After spawning the sort thread, the main pipe should read the sorted data from the sort task.  The sort task, of course, needs to write the sorted data to it's output pipe.


Kent
0
 

Author Comment

by:ronanh09
ID: 12625746
i thought i'd done that. what in the program can be altered to do this? sorry but i'm only really a beginner at c!
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question