bigcat

#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;
}