#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <pthread.h>
struct Params
{
int *start;
size_t len;
int depth;
};
// only used for synchronizing stdout from overlap.
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
// forward declare our thread proc
void *merge_sort_thread(void *pv);
// a simple merge algorithm. there are *several* more efficient ways
// of doing this, but the purpose of this exercise is to establish
// merge-threading, so we stick with simple for now.
void merge(int *start, int *mid, int *end)
{
int *res
= malloc((end
- start
)*sizeof(*res
)); int *lhs = start, *rhs = mid, *dst = res;
while (lhs != mid && rhs != end)
*dst++ = (*lhs < *rhs) ? *lhs++ : *rhs++;
while (lhs != mid)
*dst++ = *lhs++;
// copy results
memcpy(start
, res
, (rhs
- start
) * sizeof *res
); }
// our multi-threaded entry point.
void merge_sort_mt(int *start, size_t len, int depth)
{
if (len < 2)
return;
if (depth <= 0 || len < 4)
{
merge_sort_mt(start, len/2, 0);
merge_sort_mt(start+len/2, len-len/2, 0);
}
else
{
struct Params params = { start, len/2, depth/2 };
pthread_t thrd;
pthread_mutex_lock(&mtx);
printf("Starting subthread...\n"); pthread_mutex_unlock(&mtx);
// create our thread
pthread_create(&thrd, NULL, merge_sort_thread, ¶ms);
// recurse into our top-end parition
merge_sort_mt(start+len/2, len-len/2, depth/2);
// join on the launched thread
pthread_join(thrd, NULL);
pthread_mutex_lock(&mtx);
printf("Finished subthread.\n"); pthread_mutex_unlock(&mtx);
}
// merge the partitions.
merge(start, start+len/2, start+len);
}
// our thread-proc that invokes merge_sort. this just passes the
// given parameters off to our merge_sort algorithm
void *merge_sort_thread(void *pv)
{
struct Params *params = pv;
merge_sort_mt(params->start, params->len, params->depth);
return pv;
}
// public-facing api
void merge_sort(int *start, size_t len)
{
merge_sort_mt(start, len, 2); // 4 is a nice number, will use 7 threads.
}
int main()
{
static const unsigned int N = 15;
int *data
= malloc(N
* sizeof(*data
)); unsigned int i;
for (i=0; i<N; ++i)
{
if ((i+1)%8 == 0)
}
// invoke our multi-threaded merge-sort
merge_sort(data, N);
for (i=0; i<N; ++i)
{
if ((i+1)%8 == 0)
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8cHRocmVhZC5oPgogCiAKc3RydWN0IFBhcmFtcwp7CiAgICBpbnQgKnN0YXJ0OwogICAgc2l6ZV90IGxlbjsKICAgIGludCBkZXB0aDsKfTsKIAovLyBvbmx5IHVzZWQgZm9yIHN5bmNocm9uaXppbmcgc3Rkb3V0IGZyb20gb3ZlcmxhcC4KcHRocmVhZF9tdXRleF90IG10eCA9IFBUSFJFQURfTVVURVhfSU5JVElBTElaRVI7CiAKLy8gZm9yd2FyZCBkZWNsYXJlIG91ciB0aHJlYWQgcHJvYwp2b2lkICptZXJnZV9zb3J0X3RocmVhZCh2b2lkICpwdik7CiAKIAovLyBhIHNpbXBsZSBtZXJnZSBhbGdvcml0aG0uIHRoZXJlIGFyZSAqc2V2ZXJhbCogbW9yZSBlZmZpY2llbnQgd2F5cwovLyAgb2YgZG9pbmcgdGhpcywgYnV0IHRoZSBwdXJwb3NlIG9mIHRoaXMgZXhlcmNpc2UgaXMgdG8gZXN0YWJsaXNoCi8vICBtZXJnZS10aHJlYWRpbmcsIHNvIHdlIHN0aWNrIHdpdGggc2ltcGxlIGZvciBub3cuCnZvaWQgbWVyZ2UoaW50ICpzdGFydCwgaW50ICptaWQsIGludCAqZW5kKQp7CiAgICBpbnQgKnJlcyA9IG1hbGxvYygoZW5kIC0gc3RhcnQpKnNpemVvZigqcmVzKSk7CiAgICBpbnQgKmxocyA9IHN0YXJ0LCAqcmhzID0gbWlkLCAqZHN0ID0gcmVzOwogCiAgICB3aGlsZSAobGhzICE9IG1pZCAmJiByaHMgIT0gZW5kKQogICAgICAgICpkc3QrKyA9ICgqbGhzIDwgKnJocykgPyAqbGhzKysgOiAqcmhzKys7CiAKICAgIHdoaWxlIChsaHMgIT0gbWlkKQogICAgICAgICpkc3QrKyA9ICpsaHMrKzsKIAogICAgLy8gY29weSByZXN1bHRzCiAgICBtZW1jcHkoc3RhcnQsIHJlcywgKHJocyAtIHN0YXJ0KSAqIHNpemVvZiAqcmVzKTsKICAgIGZyZWUocmVzKTsKfQogCi8vIG91ciBtdWx0aS10aHJlYWRlZCBlbnRyeSBwb2ludC4Kdm9pZCBtZXJnZV9zb3J0X210KGludCAqc3RhcnQsIHNpemVfdCBsZW4sIGludCBkZXB0aCkKewogICAgaWYgKGxlbiA8IDIpCiAgICAgICAgcmV0dXJuOwogCiAgICBpZiAoZGVwdGggPD0gMCB8fCBsZW4gPCA0KQogICAgewogICAgICAgIG1lcmdlX3NvcnRfbXQoc3RhcnQsIGxlbi8yLCAwKTsKICAgICAgICBtZXJnZV9zb3J0X210KHN0YXJ0K2xlbi8yLCBsZW4tbGVuLzIsIDApOwogICAgfQogICAgZWxzZQogICAgewogICAgICAgIHN0cnVjdCBQYXJhbXMgcGFyYW1zID0geyBzdGFydCwgbGVuLzIsIGRlcHRoLzIgfTsKICAgICAgICBwdGhyZWFkX3QgdGhyZDsKIAogICAgICAgIHB0aHJlYWRfbXV0ZXhfbG9jaygmbXR4KTsKICAgICAgICBwcmludGYoIlN0YXJ0aW5nIHN1YnRocmVhZC4uLlxuIik7CiAgICAgICAgcHRocmVhZF9tdXRleF91bmxvY2soJm10eCk7CiAKICAgICAgICAvLyBjcmVhdGUgb3VyIHRocmVhZAogICAgICAgIHB0aHJlYWRfY3JlYXRlKCZ0aHJkLCBOVUxMLCBtZXJnZV9zb3J0X3RocmVhZCwgJnBhcmFtcyk7CiAKICAgICAgICAvLyByZWN1cnNlIGludG8gb3VyIHRvcC1lbmQgcGFyaXRpb24KICAgICAgICBtZXJnZV9zb3J0X210KHN0YXJ0K2xlbi8yLCBsZW4tbGVuLzIsIGRlcHRoLzIpOwogCiAgICAgICAgLy8gam9pbiBvbiB0aGUgbGF1bmNoZWQgdGhyZWFkCiAgICAgICAgcHRocmVhZF9qb2luKHRocmQsIE5VTEwpOwogCiAgICAgICAgcHRocmVhZF9tdXRleF9sb2NrKCZtdHgpOwogICAgICAgIHByaW50ZigiRmluaXNoZWQgc3VidGhyZWFkLlxuIik7CiAgICAgICAgcHRocmVhZF9tdXRleF91bmxvY2soJm10eCk7CiAgICB9CiAKICAgIC8vIG1lcmdlIHRoZSBwYXJ0aXRpb25zLgogICAgbWVyZ2Uoc3RhcnQsIHN0YXJ0K2xlbi8yLCBzdGFydCtsZW4pOwp9CiAKLy8gb3VyIHRocmVhZC1wcm9jIHRoYXQgaW52b2tlcyBtZXJnZV9zb3J0LiB0aGlzIGp1c3QgcGFzc2VzIHRoZQovLyAgZ2l2ZW4gcGFyYW1ldGVycyBvZmYgdG8gb3VyIG1lcmdlX3NvcnQgYWxnb3JpdGhtCnZvaWQgKm1lcmdlX3NvcnRfdGhyZWFkKHZvaWQgKnB2KQp7CiAgICBzdHJ1Y3QgUGFyYW1zICpwYXJhbXMgPSBwdjsKICAgIG1lcmdlX3NvcnRfbXQocGFyYW1zLT5zdGFydCwgcGFyYW1zLT5sZW4sIHBhcmFtcy0+ZGVwdGgpOwogICAgcmV0dXJuIHB2Owp9CiAKLy8gcHVibGljLWZhY2luZyBhcGkKdm9pZCBtZXJnZV9zb3J0KGludCAqc3RhcnQsIHNpemVfdCBsZW4pCnsKICAgIG1lcmdlX3NvcnRfbXQoc3RhcnQsIGxlbiwgMik7IC8vIDQgaXMgYSBuaWNlIG51bWJlciwgd2lsbCB1c2UgNyB0aHJlYWRzLgp9CiAKaW50IG1haW4oKQp7CiAgICBzdGF0aWMgY29uc3QgdW5zaWduZWQgaW50IE4gPSAxNTsKICAgIGludCAqZGF0YSA9IG1hbGxvYyhOICogc2l6ZW9mKCpkYXRhKSk7CiAgICB1bnNpZ25lZCBpbnQgaTsKIAogICAgc3JhbmQoKHVuc2lnbmVkKXRpbWUoMCkpOwogICAgZm9yIChpPTA7IGk8TjsgKytpKQogICAgewogICAgICAgIGRhdGFbaV0gPSByYW5kKCkgJSAxMDI0OwogICAgICAgIHByaW50ZigiJTRkICIsIGRhdGFbaV0pOwogICAgICAgIGlmICgoaSsxKSU4ID09IDApCiAgICAgICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKIAogICAgLy8gaW52b2tlIG91ciBtdWx0aS10aHJlYWRlZCBtZXJnZS1zb3J0CiAgICBtZXJnZV9zb3J0KGRhdGEsIE4pOwogICAgZm9yIChpPTA7IGk8TjsgKytpKQogICAgewogICAgICAgIHByaW50ZigiJTRkICIsIGRhdGFbaV0pOwogICAgICAgIGlmICgoaSsxKSU4ID09IDApCiAgICAgICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKIAogICAgZnJlZShkYXRhKTsKIAogICAgcmV0dXJuIDA7CiAKfQ==