Skip to content

Instantly share code, notes, and snippets.

@changyuheng
Created Mar 3, 2013
Embed
What would you like to do?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <pthread.h>
#include <assert.h>
#define CANDSIZE 1024
// #define BUFSIZE 8 * 1024 * 1024
#define WORK_LEN 8
#define WORKER_NUM 32
#define W_IDLE 0
#define W_WORK 1
#define W_DONE 2
#define TIME_LIMIT (10*1000000)
// #define TIME_LIMIT (102*100000)
const char* c1 = "018";
const char* c21 = "01689";
const char* c22 = "01986";
typedef struct {
int id;
volatile int status;
volatile char cand[CANDSIZE];
volatile int pos;
volatile int len;
volatile char* buf;
volatile int bufpos;
volatile int cnt; // For debuging
pthread_t thread;
pthread_mutex_t produce_mutex;
pthread_mutex_t work_mutex;
pthread_mutex_t consume_mutex;
} worker;
pthread_t goodbye_thread;
pthread_t generator_thread;
struct timeval start_time, now_time;
volatile int bye;
worker workers[WORKER_NUM];
volatile int worker_idx;
volatile int consume_idx;
void rec(volatile char* cand, int pos, int len, worker* w) {
int limit = len/2;
const char *cs, *cs2;
#define IT_CS2 \
for (cs=c21, cs2=c22; *cs; ++cs, ++cs2) {\
if (pos==0 && *cs=='0') continue;\
cand[pos] = *cs;\
cand[len-pos-1] = *cs2;\
rec(cand, pos+1, len, w);\
}
#define OUTPUT_BUF \
char* buf = w->buf;\
memcpy((void*)buf+w->bufpos, (void*)cand, len);\
buf[w->bufpos+len] = '\n';\
w->bufpos += (len+1);\
w->cnt++;
if (w==NULL) {
if (limit-pos+1<=WORK_LEN) {
worker* nw = workers+worker_idx;
pthread_mutex_lock(&nw->produce_mutex);
assert(nw->status==W_IDLE);
memcpy((void*)nw->cand, (void*)cand, len+1);
nw->pos = pos;
nw->len = len;
nw->bufpos = 0;
nw->cnt = 0;
// printf("%d, LEN=%d\n", pos, len);
nw->status = W_WORK;
++worker_idx;
worker_idx %= WORKER_NUM;
pthread_mutex_unlock(&nw->work_mutex);
return;
}
}
if (len%2) {
// even
if (pos==limit) {
for (cs=c1; *cs; ++cs) {
if (pos==0 && *cs=='0') continue;
cand[pos] = *cs;
rec(cand, pos+1, len, w);
}
} else if (pos>limit) {
// printf("%s, w=%x\n", cand, w);
OUTPUT_BUF;
// printf("%s\n", cand);
} else {
IT_CS2;
}
} else {
// odd
if (pos>=limit) {
OUTPUT_BUF;
// printf("%s\n", cand);
} else {
IT_CS2;
}
}
}
void* start_worker(void* arg) {
worker* w = (worker*)(arg);
while (1) {
pthread_mutex_lock(&w->work_mutex);
assert(w->status==W_WORK);
rec(w->cand, w->pos, w->len, w);
w->status = W_DONE;
pthread_mutex_unlock(&w->consume_mutex);
}
return 0;
}
void* start_generator(void* arg) {
char cand[CANDSIZE];
int len = 1;
while(1) {
cand[len] = 0;
rec(cand, 0, len, NULL);
++len;
// if (len>10) return 0;
}
}
void* goodbye_timer(void* arg) {
long long int diff;
while(1) {
usleep(500000);
gettimeofday(&now_time, 0);
diff = now_time.tv_sec * 1000000 + now_time.tv_usec;
diff -= start_time.tv_sec * 1000000 + start_time.tv_usec;
// printf("%lld\n", diff);
if (diff>TIME_LIMIT) {
bye = 1;
break;
}
}
return 0;
}
int main() {
int i, bufsize;
gettimeofday(&start_time, 0);
bye = 0;
worker_idx = 0;
consume_idx = 0;
// Determine buffer size
bufsize = 30; // Single result won't exceed 30 characters
for (i=0; i<WORK_LEN; ++i) {
bufsize *= 5;
}
// fprintf(stderr, "Buffer size: %d\n", bufsize);
printf("0\n");
for (i=0; i<WORKER_NUM; ++i) {
worker *w = workers+i;
w->id = i;
w->status = W_IDLE;
w->buf = malloc(bufsize);
pthread_mutex_init(&w->produce_mutex, NULL);
pthread_mutex_init(&w->work_mutex, NULL);
pthread_mutex_init(&w->consume_mutex, NULL);
// pthread_mutex_lock(&w->produce_mutex);
pthread_mutex_lock(&w->work_mutex);
pthread_mutex_lock(&w->consume_mutex);
pthread_create(&w->thread, NULL, start_worker, w);
}
pthread_create(&goodbye_thread, NULL, goodbye_timer, NULL);
pthread_create(&generator_thread, NULL, start_generator, NULL);
while(1) {
worker* w = workers+consume_idx;
// fprintf(stderr, "LEN=%d, BUFPOS=%d CNT=%d\n", w->len, w->bufpos, w->cnt);
pthread_mutex_lock(&w->consume_mutex);
assert(w->status==W_DONE);
fwrite(w->buf, w->bufpos, 1, stdout);
w->status = W_IDLE;
consume_idx++;
consume_idx %= WORKER_NUM;
pthread_mutex_unlock(&w->produce_mutex);
if (bye) exit(0);
}
// QnkgbWlhb3V0MTcgMDkyMjE3MTcyMQ==
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment