Searching-Algorithms-using-Multithreading/SearchingAlgorithms.h at main · khubaibalam2000/Searching-Algorithms-using-Multithreading · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <pthread.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <omp.h>

struct Args{
	int *arr;
    int key;
    int start;
    int end;
    int choice;
    int keyFound;
};

    float timespent[15];
    float arraySize[8] = {16,256,4096,65536,1048576,16777216,67108864,100000000};

    float LST1PT[8], LST1OMP[8];
    float LST2PT[8], LST2OMP[8];
    float LST4PT[8], LST4OMP[8];

    float BST1PT[8], BST1OMP[8];
    float BST2PT[8], BST2OMP[8];
    float BST4PT[8], BST4OMP[8];

	float TST1PT[8], TST1OMP[8];
    float TST2PT[8], TST2OMP[8];
    float TST4PT[8], TST4OMP[8];

	float JST1PT[8], JST1OMP[8];
    float JST2PT[8], JST2OMP[8];
    float JST4PT[8], JST4OMP[8];

   	float IST1PT[8], IST1OMP[8];
    float IST2PT[8], IST2OMP[8];
    float IST4PT[8], IST4OMP[8];

#define INT2VOIDP(i) (void*)(uintptr_t)(i)

void* LinearSearchUsingPthreads(void *receivedArgs){
    struct Args *struct_ptr = (struct Args*) receivedArgs;
    int j;

    for(j=struct_ptr->start; j<struct_ptr->end; j++){
        if(struct_ptr->key == struct_ptr->arr[j]){
            struct_ptr->keyFound = j;
            if(struct_ptr->choice == 2){
                pthread_exit(NULL);
            } else {
                break;
            }
        }
    }
    if(struct_ptr->choice == 2) pthread_exit(NULL);
    return 0;
}

void* BinarySearchUsingPthreads(void *receivedArgs){
    struct Args *struct_ptr = (struct Args*) receivedArgs;
    if(struct_ptr->choice == 2 && struct_ptr->end < struct_ptr->key){
        pthread_exit(NULL);
    }
    if (struct_ptr->end >= struct_ptr->start) {
        int mid = struct_ptr->start + (struct_ptr->end - struct_ptr->start) / 2;

        if (struct_ptr->arr[mid] == struct_ptr->key){
            struct_ptr->keyFound = mid;
            if(struct_ptr->choice == 2){
                pthread_exit(NULL);
            } else {
                void* val = INT2VOIDP(mid);
                return val;
            }
        }
        if (struct_ptr->arr[mid] > struct_ptr->key){
            struct_ptr->end = mid - 1;
            return BinarySearchUsingPthreads(receivedArgs);
        }
        else{
            struct_ptr->start = mid + 1;
            return BinarySearchUsingPthreads(receivedArgs);
        }
    }
    return 0;
}

void* TernarySearchUsingPthreads(void *receivedArgs){
    struct Args *struct_ptr = (struct Args*) receivedArgs;
    if(struct_ptr->choice == 2 && struct_ptr->end < struct_ptr->key) pthread_exit(NULL);
    if (struct_ptr->end >= struct_ptr->start) {

        int mid1 = struct_ptr->start + (struct_ptr->end - struct_ptr->start) / 3;
        int mid2 = struct_ptr->end - (struct_ptr->end - struct_ptr->start) / 3;

        if (struct_ptr->arr[mid1] == struct_ptr->key){
            struct_ptr->keyFound = mid1;
            if(struct_ptr->choice == 2){
                pthread_exit(NULL);
            } else {
                void* val = INT2VOIDP(mid1);
                return val;
            }
        }

        if (struct_ptr->arr[mid2] == struct_ptr->key){
            struct_ptr->keyFound = mid2;
            if(struct_ptr->choice == 2){
                pthread_exit(NULL);
            } else {
                void* val = INT2VOIDP(mid2);
                return val;
            }
        }

        if (struct_ptr->arr[mid1] > struct_ptr->key){
            struct_ptr->end = mid1 - 1;
            return TernarySearchUsingPthreads(receivedArgs);
        }
        else if (struct_ptr->arr[mid2] < struct_ptr->key){
            struct_ptr->start = mid2 + 1;
            return TernarySearchUsingPthreads(receivedArgs);
        }
        else{
            struct_ptr->start = mid1 + 1;
            struct_ptr->end = mid2 - 1;
            return TernarySearchUsingPthreads(receivedArgs);
        }
    }
    return 0;
}