Diff: main.cpp

Revision:

3:8647bf7682b2

Parent:

0:e1c215fe231c

Child:

4:8a7e0bc98db0

--- a/main.cpp	Mon Apr 07 20:33:11 2014 +0000
+++ b/main.cpp	Thu Oct 29 22:29:08 2015 +0000
@@ -1,137 +1,280 @@
+#include <stdio.h>
 #include "mbed.h"
 #include "SDFileSystem.h"
+#include "rtos.h"
 
-SDFileSystem sd(PTE3, PTE1, PTE2, PTE4, "sd"); // MOSI, MISO, SCK, CS
+#define CTIME   50
+#define WTIME   150
+
+SDFileSystem sd(PTE3, PTE1, PTE2, PTE4, "sd"); 
 Serial pc(USBTX, USBRX);
-FILE *fp;
+DigitalOut ledr(LED_RED);
+DigitalOut ledg(LED_GREEN);
+DigitalOut ledb(LED_BLUE);
+Timer ProgramTimer;
+
+int n_threads = 0;
+int i = 0;
+int j = 0;
+int k = 0;
+int l = 0;
+int n = 0;
+
+typedef struct {
+  int id;
+  int cap;
+  int n_objects;
+  int weight[32];
+  int value[32];
+} knapsack;
+
+typedef struct {
+  int tid;
+  int led;
+  int pid;
+  int cap;
+  int optimal;
+  int n_solutions;
+  int weight[32];
+  int value[32];
+  unsigned long ts_begin;
+  unsigned long ts_end;
+} solution;
+
+char *temp;
+int *ttemp;
+int *vsol;
+int *wsol;
+int sol = 0;
+
+int phead, ptail;
+int shead, stail;
+knapsack *knapsacks;
+knapsack *pQueue;
+knapsack salida;
+solution *solutions;
+solution output;
+
+Thread *threads[10];
+
+Mutex mutex_p;
+Mutex mutex_s;
 
-int file_copy(const char *src, const char *dst)
-{
-    int retval = 0;
-    int ch;
- 
-    FILE *fpsrc = fopen(src, "r");   // src file
-    FILE *fpdst = fopen(dst, "w");   // dest file
+int max(int a, int b);
+solution KnapSack(int W, int wt[], int val[], int n);
+void init_pQueue(void);
+void init_sQueue(void);
+int ispEmpty();
+int issEmpty();
+void pEnqueue(knapsack p);
+void sEnqueue(solution s);
+knapsack pDequeue();
+solution sDequeue();
+
+void worker(void const *args);
+
+int main(){
+    ledr=1; ledg=1; ledb=1; 
+    FILE *ptr_file;
+    char *plinea = (char *)malloc(128*sizeof(char));
+    char *linea = (char *)malloc(128*sizeof(char));
+    char *temp = (char *)malloc(4*sizeof(char));
+    int *ttemp = (int *)malloc(128*sizeof(int));
+    knapsacks = (knapsack *)malloc(32*sizeof(knapsack));
+    pQueue = (knapsack *)malloc(32*sizeof(knapsack));
+    solutions = (solution *)malloc(32*sizeof(solution));
+    
+    pc.baud(115200);
+    pc.printf("\n\rInitializing\n\r");
+    pc.printf("============ \n\r");
+    wait(0.5f);
     
-    while (1) {                  // Copy src to dest
-        ch = fgetc(fpsrc);       // until src EOF read.
-        if (ch == EOF) break;
-        fputc(ch, fpdst);
+    ProgramTimer.start(); 
+    ptr_file = fopen("/sd/test.txt","r");
+    
+    fgets(plinea,512,ptr_file);
+    n_threads = plinea[1]-'0';
+    init_pQueue();
+    init_sQueue();
+    
+    n=0;
+    while( !feof(ptr_file) ){
+        fgets(linea,512,ptr_file);
+        i=1; j=0; l=0;
+        while(linea[i]!='*'){
+            if (linea[i]!=','){
+                temp[j]=linea[i];
+                j++;
+            } else {
+                temp[j]='\0';
+                ttemp[l]=atoi(temp);
+                j=0; l++;
+            }
+            ttemp[l]=atoi(temp);
+            i++;
+        }
+        for(k=0;k<=l;k++){
+            if(k==0) knapsacks[n].id=ttemp[k];
+            if(k==1) knapsacks[n].cap=ttemp[k];
+            if((k>1)&&((k%2)==0)) knapsacks[n].weight[k/2-1]=ttemp[k];
+            if((k>2)&&((k%2)!=0)) knapsacks[n].value[k/2-1]=ttemp[k];
+        }
+        knapsacks[n].n_objects=l/2;
+        pEnqueue(knapsacks[n]);
+        n++;
     }
-    fclose(fpsrc);
-    fclose(fpdst);
-  
-    fpdst = fopen(dst, "r");     // Reopen dest to insure
-    if (fpdst == NULL) {          // that it was created.
-        retval = -1;           // Return error.
-    } else {
-        fclose(fpdst);
-        retval = 0;              // Return success.
+    
+    pc.printf("id\tcap\tn\titems\n\r");
+    for(i=0;i<n;i++){
+        pc.printf("%d\t%d\t%d\t",knapsacks[i].id,knapsacks[i].cap,knapsacks[i].n_objects);
+        for(j=0;j<knapsacks[i].n_objects;j++) pc.printf("%d,%d ",knapsacks[i].weight[j],knapsacks[i].value[j]);
+        pc.printf("\n\r");
     }
-    return retval;
-}
-
-uint32_t do_list(const char *fsrc)
-{
-    DIR *d = opendir(fsrc);
-    struct dirent *p;
-    uint32_t counter = 0;
-
-    while ((p = readdir(d)) != NULL) {
-        counter++;
-        printf("%s\n", p->d_name);
+    pc.printf("\n\r");
+    
+    fclose(ptr_file);
+    free(plinea);
+    free(linea);
+    free(temp);
+    free(ttemp);
+    
+    /*pc.printf("No Thread Solution\n\r");
+    pc.printf("==================\n\r");
+    pc.printf("#tid\t#pid\tcap\tsol\titems\n\r");
+    for(j=0;j<n;j++){
+        solutions[j] = KnapSack(knapsacks[j].cap,knapsacks[j].weight,knapsacks[j].value,knapsacks[j].n_objects);
+        pc.printf("main\t%d\t%d\t%d\t",j+1,knapsacks[j].cap,solutions[j].optimal);
+        for(i=0;i<solutions[j].n_solutions;i++) pc.printf("%d,%d,",solutions[j].weight[i],solutions[j].value[i]);
+        pc.printf("\n\r");
+    }*/
+    pc.printf("\n\r");   
+    pc.printf("Thread Solution\n\r");
+    pc.printf("===============\n\r");
+    
+    for(i=0;i<n_threads;i++){
+       threads[i] = new Thread(worker,(void *)(i+1));
+       Thread::wait(CTIME);
     }
-    closedir(d);
-    return counter;
+    pc.printf("&%d*\n\r",n_threads);
+    
+    while(1){
+        if(!issEmpty()){
+            mutex_s.lock();
+            output = sDequeue();
+            mutex_s.unlock();
+            pc.printf("#%d(%d),%d,%d,",output.led,output.tid,output.pid,output.cap);
+            for(i=0;i<output.n_solutions;i++) pc.printf("%d,%d,",output.weight[i],output.value[i]);
+            pc.printf("%.3f,%.3f,%.3f*\n\r",output.ts_begin/1000.0f,output.ts_end/1000.0f,(output.ts_end-output.ts_begin)/1000.0f);
+            ledr = !(output.led/2/2);
+            ledg = !(output.led/2%2);
+            ledb = !(output.led%2);
+        } else{
+            free(knapsacks);
+            free(pQueue);
+            free(solutions);
+        }
+        Thread::wait(1000);
+    }
 }
 
-// bool is_folder(const char *fdir)
-// {
-//     DIR *dir = opendir(fdir);
-//     if (dir) {
-//         closedir(dir);
-//     }
-//     return (dir != NULL);
-
-// }
 
-// bool is_file(const char *ffile)
-// {
-//     FILE *fp = fopen(ffile, "r");
-//     if (fp) {
-//         fclose(fp);
-//     }
-//     return (fp != NULL);
-// }
+solution KnapSack(int cap, int weight[], int value[], int n){
+    solution s;
+    int i, w;
+    int j = 0;
+    int sol = 0;
+    int K[n+1][cap+1];
+    s.ts_begin = ProgramTimer.read_us();
+    for(i=0;i<=n;i++){
+        for(w=0;w<=cap;w++){
+            if(i==0||w==0) K[i][w]=0;
+            else if(weight[i-1]<=w) K[i][w]=max(value[i-1]+K[i-1][w-weight[i-1]],K[i-1][w]);
+            else K[i][w]=K[i-1][w];
+        }
+    }
+    w=cap;
+    for(i=n;i>0;i--){
+        if(K[i][w]!=K[i-1][w]){
+            s.value[j] = value[i-1];
+            s.weight[j] = weight[i-1];
+            w=w-weight[i-1];
+            sol++;
+            j++;
+        }
+    }
+    s.ts_end = ProgramTimer.read_us();
+    s.optimal = K[n][cap];
+    s.n_solutions = sol;
+    return s;
+}
 
-void do_remove(const char *fsrc)
-{
-    DIR *d = opendir(fsrc);
-    struct dirent *p;
-    char path[30] = {0};
-    while((p = readdir(d)) != NULL) {
-        strcpy(path, fsrc);
-        strcat(path, "/");
-        strcat(path, p->d_name);
-        remove(path);
-    }
-    closedir(d);
-    remove(fsrc);
+int max(int a, int b){
+    return (a>b)?a:b;
+}
+
+void init_pQueue(void){
+    phead = ptail = -1;
+}
+
+int ispEmpty(){
+    return (phead == ptail);
+}
+
+void pEnqueue(knapsack p){
+    ptail++;
+    pQueue[ptail] = p;
 }
 
-int main()
-{
-    pc.printf("Initializing \n");
-    wait(2);
-
-    do_remove("/sd/test1"); /* clean up from the previous Lab 5 if was executed */
-    if (do_list("/sd") == 0) {
-        printf("No files/directories on the sd card.");
-    }
-
-    printf("\nCreating two folders. \n");
-    mkdir("/sd/test1", 0777);
-    mkdir("/sd/test2", 0777);
+knapsack pDequeue(){
+    knapsack p;
+    phead++;
+    p = pQueue[phead];
+    return p;
+}
 
-    fp = fopen("/sd/test1/1.txt", "w");
-    if (fp == NULL) {
-        pc.printf("Unable to write the file \n");
-    } else {
-        fprintf(fp, "1.txt in test 1");
-        fclose(fp);
-    }
+void init_sQueue(void){
+    shead = stail = -1;
+}
 
-    fp = fopen("/sd/test2/2.txt", "w");
-    if (fp == NULL) {
-        pc.printf("Unable to write the file \n");
-    } else {
-        fprintf(fp, "2.txt in test 2");
-        fclose(fp);
-    }
-
-    printf("\nList all directories/files /sd.\n");
-    do_list("/sd");
-
-    printf("\nList all files within /sd/test1.\n");
-    do_list("/sd/test1");
+int issEmpty(){
+    return (shead == stail);
+}
 
 
-    printf("\nList all files within /sd/test2.\n");
-    do_list("/sd/test2");
+void sEnqueue(solution s){
+    stail++;
+    solutions[stail] = s;
+}
+
+solution sDequeue(){
+    solution s;
+    shead++;
+    s = solutions[shead];
+    return s;
+}
 
-    int status = file_copy("/sd/test2/2.txt", "/sd/test1/2_copy.txt");
-    if (status == -1) {
-        printf("Error, file was not copied.\n");
+void worker(void const *args){
+    solution temp;
+    knapsack doc;
+    osThreadId id;
+    while (true) {
+        if(!ispEmpty()){
+            mutex_p.lock();
+            doc = pDequeue();
+            mutex_p.unlock();      
+            temp = KnapSack(doc.cap,doc.weight,doc.value,doc.n_objects);
+            temp.pid = doc.id;
+            temp.cap = doc.cap;
+            temp.tid = (uint32_t)osThreadGetId();
+            temp.led = (uint32_t)args;
+            mutex_s.lock();
+            sEnqueue(temp);
+            mutex_s.unlock();
+        } else{
+            id = osThreadGetId();
+            osThreadTerminate(id);
+        }
+        Thread::wait(WTIME);
+        osThreadYield();
     }
-    printf("Removing test2 folder and 2.txt file inside.");
-    remove("/sd/test2/2.txt");
-    remove("/sd/test2");
-
-    printf("\nList all directories/files /sd.\n");
-    do_list("/sd");
-
-    printf("\nList all files within /sd/test1.\n");
-    do_list("/sd/test1");
-
-    printf("\nEnd of complete Lab 5. \n");
 }