File content as of revision 1:39e36a5c11e0:

#include "mbed.h"
#include "rtos.h"
#include <queue>


//#define DELAY_INSIDE
//#define DELAY_BTWN
#define DELAY_DISPLAY

#define DELAY_INSIDE_TIME  1000    
#define DELAY_BTWN_TIME   311   
#define DELAY_DISPLAY_TIME   100   


#define ARRAY_SIZE   16
#define THREAD_ARRAY_SIZE   10
 
typedef struct{
   int tid;
   int pid;
   int cap;
   int weights[ARRAY_SIZE];
   int values[ARRAY_SIZE];
   int ts_begin;   
   int ts_end;
   int proc_time;
   int n;
}problema;

typedef struct{
   int tid;
   int pid;
   int cap;
   int weights[ARRAY_SIZE];
   int values[ARRAY_SIZE];
   int ts_begin;   
   int ts_end;
   int proc_time;
   int opt;  
}solucion;


Timer t;
DigitalOut led1(LED1);  // Red
DigitalOut led2(LED2);  // Green
DigitalOut led3(LED3);  // Blue

osMutexDef (mutex_leds);//mutex for LEDs
osMutexDef (mutex_p);   //problem queue mutex
osMutexDef (mutex_s);   //solution queue mutex 


osMutexId  (mutex_leds_id); // LED mutex ID
osMutexId  (mutex_p_id);    // problem queue mutex ID
osMutexId  (mutex_s_id);    // solution queue mutex ID


queue <problema> problem_q;
queue <solucion> solution_q;

Serial pc(USBTX, USBRX);

#ifdef DEBUG 
int printP(problema p){
    int i;
    printf("\n#P \t#T \tCap \t#items");
    printf("\n%i \t%i \t%i \t%i\n",p.pid,p.tid,p.cap,p.n);
    printf("  Weights \tValues\n");
    printf("  ------- \t------\n");
    i=0;
    while (p.weights[i]>-5 && p.values[i]>-5 && i<30){ 
        printf("%i.    %i \t%i\n", i+1, p.weights[i],p.values[i]);
        i++;
    }
    printf("\n");
    return 1;
}

int printS(solucion s){
    int i;
    printf("\n#S \t#T \tCap \tOpt Val \tBegin \t\tEnd \t\tProc");
    printf("\n%i \t%i \t%i \t%i \t\t%ius \t%ius \t%ius\n", s.pid, s.tid, s.cap, s.opt, s.ts_begin, s.ts_end, s.proc_time);
    printf("  Weights \tValues \t(included items)\n");
    printf("  ------- \t------\n");
    i=0;
    while (s.weights[i]>-5 && s.values[i]>-5 && i<30){ 
        printf("%i.    %i \t%i\n", i+1, s.weights[i],s.values[i]);
        i++;
    }
    printf("\n");
    return 1;
}

#else
#endif

int printF(solucion s){
    int i;
    printf("\n#");
    printf("%i,", s.tid);
    printf("%i,", s.pid);
    printf("%i", s.cap);
    i=0;
    while (s.weights[i]>=0 && s.values[i]>=0 && i<30){ 
        printf(",%i,%i", s.weights[i],s.values[i]);
        i++;
    }
    printf(",%i", s.ts_begin);
    printf(",%i", s.ts_end);
    printf(",%i", s.proc_time);
    printf("*");
    return 1;
}

int my_atoi(char *str) {
    int res = 0; // Initialize result
    // Iterate through all characters of input string and update result
    for (int i = 0; str[i] != '\0'; ++i)
        res = res*10 + str[i] - '0';
    return res;
}

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
solucion knapSackP(problema p, int t){
   solucion s;
   s.ts_begin=t;//t.read_us();
   int i, w,index=0;
   int K[p.n+1][p.cap+1];
   // Build table K[][] in bottom up manner
   for (i = 0; i <= p.n; i++){
       for (w = 0; w <= p.cap; w++){
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (p.weights[i-1] <= w)
               K[i][w] = max(p.values[i-1] + K[i-1][w-p.weights[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
   s.opt = K[p.n][p.cap];
     
   w = p.cap;
   for (i=p.n; i>0; i--){
       if(K[i][w] != K[i-1][w]){
          //printf("(p.weights=%i,val=%i)-> ",p.weights[i-1],val[i-1]);
          s.weights[index]=p.weights[i-1];
          s.values[index++]=p.values[i-1];
          w=w-p.weights[i-1];
       }
   }
   s.weights[index]=-5;
   s.values[index]=-5;
   
   
   return s;
}
 
void led_func(uint32_t n){
    uint32_t temp = ~((n%7)+1);
    led3 = temp&(uint32_t)1;
    led2 = (temp&(uint32_t)2)>>1;
    led1 = (temp&(uint32_t)4)>>2;   
}

void led_thread(void const *argument)
{
    uint32_t cont =0;
    while (true) {
        osMutexWait(mutex_leds_id, osWaitForever); //request lock
        led_func(cont);
        osMutexRelease(mutex_leds_id);              //unlock
        Thread::wait((uint32_t)argument );
        cont++;
    }
}

void worker_thread(void const *argument){
     problema p;
     solucion s;    
     
     while (true) {
        osMutexWait(mutex_p_id, 1000);
        if (!problem_q.empty()){
                p = problem_q.front();
                problem_q.pop();
                osMutexRelease(mutex_p_id);
                
                #ifdef DEBUG 
                    p.tid = (uint32_t)argument;
                    printf("-------------------------------------------------------");
                    printP(p);
                #endif
                
                //printf("\nT1:%i\n",t.read_us()); 
                s = knapSackP(p,t.read_us());
                s.ts_end=t.read_us();
                //printf("\nT2:%i\n",t.read_us());
                s.proc_time=s.ts_end-s.ts_begin;
                s.tid = (uint32_t)argument;
                s.pid = p.pid;
                s.cap = p.cap;
                
                #ifdef DEBUG 
                    printS(s);
                #endif

                osMutexWait(mutex_s_id, 1000);
                    solution_q.push(s);
                osMutexRelease(mutex_s_id);  
                
                osMutexWait(mutex_leds_id, 1000); //request lock
                    led_func((uint32_t)argument);
                osMutexRelease(mutex_leds_id);    //unlock     
                
            }else{
                osMutexRelease(mutex_p_id);
            }
        
        osThreadYield();
        #ifdef DELAY_INSIDE
            Thread::wait(DELAY_INSIDE_TIME);
        #endif
    }
}

int main(){
    t.start();
    problema *problemas_array;          //array to store the parsed problems
    Thread *threads_array[THREAD_ARRAY_SIZE]; //array to instance the threads
    char buffer[4];                 //buffer to atoi convertion
    solucion s;             // var to pop the solutions from solution queue
    char input_char;    //received char form serial input
    char stage = 0;    //State of the parsing loop
    char parseFlag =1;  //flag to exit the input loop
    char displayFlag =1;   //flag to exit the display solution loop 
    int i;                  //used to indexing alog the differents arrays
    int number_threads;     //number of threads recived
    int number_threads_temp;  //used to verify if we have recived the number of threads
    char problema_counter;     //problem counter
    char item_counter;          //
    char buffer_counter;        //used to indexing the buffer used to atoi convertion
    pc.baud (115200);   //Baudrate
    
    
    while (true) {
        problemas_array =(problema *) malloc(10*sizeof(problema)) ;
        problema_counter=0;
        number_threads=0;
        item_counter=0;
        buffer_counter=0;
        buffer[0]='\0';
        buffer[3]='\0';
        i=0;
        parseFlag=1;
        displayFlag =1;
        stage = 0;
         
        while(parseFlag){               //input loop       
            input_char = getchar();     //receive char from Serial
            //Parsing the message
            if (input_char=='&'){   //start of message
                buffer[0]='\0';
                buffer_counter=0;
                problema_counter=0;
                item_counter=0;
                number_threads=0;
                stage = 1;
                //printf("Stage %i\n", stage);
            }else if (input_char=='#'){    //end of threads number
                buffer[0]='\0';
                buffer_counter=0;
                stage = 2;
                //printf("Stage %i\n", stage);
            }else if (input_char >= '0' && input_char <= '9'){ //number received
                buffer[buffer_counter++]=input_char;
                buffer[buffer_counter]='\0';
            }else if (input_char=='*'){             //end of line
                if (stage==1){
                     number_threads_temp = my_atoi(&buffer[0]);
                     number_threads = (number_threads_temp>0 && number_threads_temp<=10)? number_threads_temp: 5;
                    //printf("Number of threads = %i\n", number_threads);
                    //printf("Problema = %i\n", problema_counter);
                    buffer[0]='\0';
                    buffer_counter=0;
                }else if (stage==4){
                    problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
                    problema_counter++;
                    item_counter=0;
                    //printf("4Problema = %i\n", problema_counter);
                }else if (stage==5){
                    problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
                    problemas_array[problema_counter].values[item_counter]=-5;
                    problemas_array[problema_counter].weights[item_counter]=-5;
                    problemas_array[problema_counter].n=item_counter;
                    problema_counter++;
                    item_counter=0;
                    //printf("Problema = %i\n", problema_counter);
                }  
                
            }else if (input_char==','){         //delimiter do the message
                if (stage==2){
                    problemas_array[problema_counter].pid = my_atoi(&buffer[0]);
                    stage=3;
                    //printf("Stage %i\n", stage);
                }else if (stage==3){
                    problemas_array[problema_counter].cap = my_atoi(&buffer[0]);
                    stage=4;
                    //printf("Stage %i\n", stage);
                } else if (stage==4){
                    problemas_array[problema_counter].weights[item_counter]=my_atoi(&buffer[0]);
                    stage=5;
                    //printf("Stage %i\n", stage);
                }else if (stage==5){
                    problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
                    stage=4;
                    //printf("Stage %i\n", stage);
                }
                buffer[0]='\0';
                buffer_counter=0;
            }else if (input_char=='\n'){    //newline received
                buffer[0]='\0';
                buffer_counter=0;
            }else if (input_char=='X'){    //end of message
                buffer[0]='\0';
                buffer_counter=0;
                stage=0;
                //printf("\nNumber of threads = %i\n", number_threads);
                fflush(stdout);
                fflush(stdin);
                parseFlag =0;               //exit form input loop
            }
        }
        //printf("\nNumber of threads = %i", number_threads);
        //printf("\nNumber of problems = %i", problema_counter);
        printf("\n Parse Finished \n");
        
        osMutexWait(mutex_p_id, osWaitForever);         //request lock
        for (i=0; i<problema_counter; i++){     
            problem_q.push(problemas_array[i]);
        }
        osMutexRelease(mutex_p_id);                    //unlock
        
        free(problemas_array);
        
        i=0;
        while (i<number_threads){
            threads_array[i]= new Thread(worker_thread,(void *)(i));
                #ifdef DELAY_BTWN
            Thread::wait(DELAY_BTWN_TIME);
            #endif
            i++;
        }
        
        #ifdef DELAY_DISPLAY
            Thread::wait(DELAY_DISPLAY_TIME);
        #endif
        
                
        while(displayFlag){
                displayFlag=0;
                printf("\n&%i*",number_threads);
                
                while(!solution_q.empty()){
                    osMutexWait(mutex_s_id, osWaitForever);
                        if (!solution_q.empty()){
                            s = solution_q.front();
                            solution_q.pop();
                            printF(s);
                        }    
                        osMutexRelease(mutex_s_id);
                }
                  
                
        }
        
      
        //i=0;
        //while (i<number_threads) threads_array[i];
        free(threads_array);
        
        //osMutexWait(mutex_leds_id, osWaitForever); //request lock
          //  led_func(6);
        //osMutexRelease(mutex_leds_id);              //unlock
    }
}