// remember to CC -lpthread #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <pthread.h> int * randomlist(int n) { int * arr = (int *)malloc(n * sizeof(int)); int i; for (i=0; i<n; i+=1) arr[i] = i; for (i=0; i<10*n; i+=1) { int r = random() % n; int t = arr[0]; arr[0] = arr[r]; arr[r] = t; } return arr; } void printlist(int * a, int n) { int i; printf("%d", a[0]); for (i=1; i<n; i+=1) printf(",%d", a[i]); printf("\n"); } typedef struct _tree { int data; struct _tree * left, * right; } tree; tree * treeadd(tree * t, int x) { if (t == NULL) { t = (tree *)malloc(sizeof(tree)); t->data = x; t->left = NULL; t->right = NULL; } else if (x < t->data) t->left = treeadd(t->left, x); else t->right = treeadd(t->right, x); return t; } tree * treefromlist(int * a, int n) { tree * t = NULL; int i; for (i=0; i<n; i+=1) t = treeadd(t, a[i]); return t; } void treeprint(tree * t) { if (t == NULL) return; printf("("); treeprint(t->left); printf("%d", t->data); treeprint(t->right); printf(")"); } typedef struct _squeue { int size, first, last, num; pthread_mutex_t * semaphore; int * items; } squeue; squeue * makesqueue(int s) { squeue * q = (squeue *)malloc(sizeof(squeue)); q->size = s; q->num = 0; q->first = 0; q->last = 0; q->items = (int *)malloc(s * sizeof(int)); pthread_mutex_init(q->semaphore, NULL); return q; } void add_to_squeue(squeue * q, int x) { while (1) { pthread_mutex_lock(q->semaphore); if (q->num < q->size) break; pthread_mutex_unlock(q->semaphore); usleep(100); } q->items[q->last] = x; q->last += 1; if (q->last == q->size) q->last = 0; q->num += 1; pthread_mutex_unlock(q->semaphore); } int get_from_squeue(squeue * q) { int x; while (1) { pthread_mutex_lock(q->semaphore); if (q->num > 0) break; pthread_mutex_unlock(q->semaphore); usleep(100); } x = q->items[q->first]; q->first += 1; if (q->first == q->size) q->first = 0; q->num -= 1; pthread_mutex_unlock(q->semaphore); return x; } typedef struct { char * name; tree * tr; squeue * out; pthread_t id; } treethreadinfo; treethreadinfo * maketreethread(char * n, tree * t, squeue * q) { treethreadinfo * i = (treethreadinfo *)malloc(sizeof(treethreadinfo)); i->name = n; i->tr = t; i->out = q; return i; } typedef struct { char * name; squeue * in1, * in2; pthread_t id; } comparethreadinfo; comparethreadinfo * makecomparethread(char * n, squeue * q1, squeue * q2) { comparethreadinfo * i = (comparethreadinfo *)malloc(sizeof(comparethreadinfo)); i->name = n; i->in1 = q1; i->in2 = q2; return i; } void treeout(treethreadinfo * info, tree * t) { if (t == NULL) return; treeout(info, t->left); add_to_squeue(info->out, t->data); printf("%s adding %d\n", info->name, t->data); usleep(500000); treeout(info, t->right); } void * treeouter(void * a) { int i; treethreadinfo * info = (treethreadinfo *)a; treeout(info, info->tr); } void * comparer(void * a) { } int main() { const int size = 100; int * list1 = randomlist(size), * list2 = randomlist(size); tree * tree1 = treefromlist(list1, size), * tree2 = treefromlist(list2, size); squeue * q1 = makesqueue(10), * q2 = makesqueue(10); treethreadinfo * thr1 = maketreethread("tree1", tree1, q1), * thr2 = maketreethread("tree2", tree2, q2); comparethreadinfo * thr3 = makecomparethread("comparer", q1, q2); printf("tree 1: "); treeprint(tree1); printf("\n"); printf("tree 2: "); treeprint(tree2); printf("\n"); pthread_create(& thr1->id, NULL, treeouter, & thr1); pthread_create(& thr2->id, NULL, treeouter, & thr2); pthread_create(& thr3->id, NULL, comparer, & thr3); void * x; pthread_join(thr1->id, & x); pthread_join(thr2->id, & x); pthread_join(thr3->id, & x); printf("\ndone\n"); }