I am trying to determine whether an element exits in a vector using N processes and if true, return all its positions. Each process receives an index and a step. The index is from 0 to "numberOFProcesses -1" and each process check element starting from index, incremented by step.
How it works: Let us assume we have 4 processes. Process 0 checks elements 0,4,8..., process 1 checks 1,5,9... etc.
How did I implement this: I got 2 pipes: one pipes is used for positions; the second pipe is to store the number of occurrences of the target. Whenever a process find the target it increments the number of occurrences and writes the index to the "index" pipe and, finally, upon exiting job, it writes to "occurrences" pipe the number of occurrences, if any, and return true or false. I initially wanted to directly return the number of occurrences but I realized that "WEXITSTATUS" uses only 8 bits and that might be an issue.
The problem: Attempting to read a chunk of size "occurrences" fails or gives invalid results. Reading a value at a time seems to work fine. I have also checked it using valgrind and gdb, but I cannot seem to find the problem. Valgrind reports a ton of issues when attempting to read the chunk, but 0 errors when reading one at time. The reading of occurrences is done only if the process has found the target.
P.S. I know I can leave it like that, but it wouldn't make sense reading multiple times.
Now, for some code:
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <wait.h>
#include <sys/signal.h>
#include <sys/types.h>
/**
* @brief basic defines
*
*/
#define MAX_RAND 100
#define TRUE 1
#define FALSE 0
#define CHILDREN 0
#define READ 0
#define WRITE 1
int size = 13;
int *array;
int target;
int index_pipe[2];
int occurences_pipe[2];
/**
* @brief this populates the array with random number
*
* @param array the given array
* @param size the size of the array
*/
void populate(int *array, int size)
{
for (int i = 0; i < size; i++)
{
array[i] = rand() % MAX_RAND;
}
}
/**
* @brief this determines whether an elements occurs in an array and writes to pipes the number
* of occurences and the the indexes on which resides the target
*
* @param target the value we are looking for
* @param index the index of the process, i.e. the process id
* @param step the step, i.e. the number of processes
* @return int the search status. This returns true if "target occurs", FALSE otherwise
*/
int search(int target, int index, int step)
{
int i = index;
int numberOfOccurences = 0;
/**
* @brief each process will start at position index and will check values starting with index, incrementing with step
* ex: process 0 will check 0,4,8,12..
* process 1 will check 1,5,9,13...
*/
while (i < size)
{
if (target == array[i])
{
/**
* @brief if the target occues increment the number of occurences and write an index to pipe
*
*/
numberOfOccurences++;
write(index_pipe[WRITE], &i, sizeof(int));
}
i += step;
}
/**
* @brief write occurences to pipe if, and only if, the number of occurences is not 0,
* i.e. we have found the target at least once and return TRUE or FALSE
*
*/
if (numberOfOccurences != 0)
{
write(occurences_pipe[WRITE], &numberOfOccurences, sizeof(int));
return TRUE;
}
return FALSE;
}
/**
* @brief this prints a given array
*
* @param array the array we want to print
* @param size the size of the array
*/
void printArray(int *array, int size)
{
printf("Array: \n");
for (int i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
/**
* @brief entry point
*
* @return int EXIT_SUCCESS
*/
int main()
{
/**
* @brief initialize and allocate memory
*
*/
size = 13;
array = (int *)malloc(sizeof(int) * size);
pipe(index_pipe);
pipe(occurences_pipe);
int numerOfProccesses = 3;
int target = 15;
int totalOccurences = 0;
int status = -1;
int exit_status = -1;
int occurences = -1;
populate(array, size);
array[size - 1] = target;
printArray(array, size);
size_t processes[numerOfProccesses];
/**
* @brief create childrens and put them to work
*
*/
for (int i = 0; i < numerOfProccesses; i++)
{
processes[i] = fork();
if (CHILDREN == processes[i])
{
/**
* @brief get the search status and exit
*
*/
int exit_status = search(target, i, numerOfProccesses);
exit(exit_status);
}
}
/**
* @brief wait for children to exit
*
*/
for (int i = 0; i < numerOfProccesses; i++)
{
/**
* @brief wait for each children. If a children is done AND it has found taget, i.e. returned TRUE,
* then read the number of occurrences from pipe
*
*/
wait(&status);
if (WIFEXITED(status))
{
exit_status = WEXITSTATUS(status);
if (exit_status == TRUE)
{
read(occurences_pipe[READ], &occurences, sizeof(int));
totalOccurences += occurences;
}
}
}
/**
* @brief if the number of occurrences is 0, then we have'nt found target
*
*/
if (totalOccurences == 0)
{
printf("%d not found \n", target);
}
else
{
/**
* @brief else allocate memory for an array of size "occurrences" and read from index pipe
*
*/
printf("Found %d on %d positions\n", target, totalOccurences);
int *indexes = (int *)malloc(sizeof(int) * 3);
// for (int i = 0; i < totalOccurences; i++)
// {
// int value;
// read(index_pipe[READ], &value, sizeof(int));
// printf("Read %d \n", value);
// }
int pipe_status;
pipe_status = read(index_pipe[READ], indexes, totalOccurences);
printf("Pipe read %d bytes\n", pipe_status);
printArray(indexes, totalOccurences);
}
return 0;
}
Expected output:
Array:
83 86 77 15 93 35 86 92 49 21 62 27 15
Found 15 on 2 positions
Read 3
Read 12
Array:
3 12
I get this when reading a chunk at a time:
Array:
83 86 77 15 93 35 86 92 49 21 62 27 15
Found 15 on 2 positions
Pipe read 2 bytes
Array:
3 0
P.S. I wrote this on a linux machine. I compiled this using: gcc -g -o search search.c -Wextra
