CSAPP LAB

int func4(int edi, int esi, int edx)
{
    int eax = edx;
    eax -= esi;
    int ecx = eax;
    ecx >>= 31;
    eax += ecx;
    eax >>= 1;
    ecx = eax + esi;
    if (ecx > edi)
    {
        edx = ecx - 1;
        eax = func4(edi, esi, edx);
        eax *= 2;
        return eax;
    }
    else
    {
        eax = 0;
        if(ecx < edi)
        {
            esi = ecx + 1;
            eax = func4(edi, esi, edx);
            eax = eax * 2 + 1;
            return eax;
        }
        else
            return eax;
    }
}

int func4 (int edi, int esi, int edx)
{
    eax = edx - esi;
    eax = (eax + (eax >> 31)) >> 1;
    ecx = eax + exi;
    if(edi < ecx) 
        return  2 * func4(edi, esi, edx - 1);
    else if (edi > ecx)
        return  2 * func4(edi, esi + 1, edx) + 1;
    else
        return  0;
}

int func4(int edi, int esi, int edx)
{
    int eax = edx - esi;
    if (eax < 0)
      eax -= 1;
    eax /= 2;

    int ecx = eax + esi;
    if (ecx > edi)
        return func4(edi, esi, ecx - 1) * 2;
    else if (ecx < edi)
        return func4(edi, ecx + 1, edx) * 2 + 1;
    else
        return 0;
}

void touch2(unsigned val)
{
    vlevel = 2; /* Part of validation protocol */ 
    if (val == cookie) {
        printf("Touch2!: You called touch2(0x%.8x)\n", val);
        validate(2);
    } else {
        printf("Misfire: You called touch2(0x%.8x)\n", val);
        fail(2);
    }
    exit(0);
}

#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <string.h>
#include "cachelab.h"

typedef __uint64_t uint64_t;

enum {
    kHit = 0,
    kMiss,
    kEvication,
};

#define TRUE 1
#define FALSE 0

int verbose = 0, s = 0, E = 0, b = 0, S = 0, B = 0;
FILE* traceFile = NULL;

uint64_t curTimeStamp = 0;

typedef struct {
    uint64_t tag;
    uint64_t timeStamp;
} CacheLine;

typedef CacheLine* CacheSet;
typedef CacheSet* Cache;

Cache cache;

typedef struct {
    int hit;
    int miss;
    int eviction;
} Result;

Result result = {0, 0, 0};

// 打印帮助信息
void printUsage();
int getArguments(int argc, char** argv);

void initCache();
void release();
void getCache(uint64_t tag, int setIndex);

int main(int argc, char** argv)
{
    int ret = getArguments(argc, argv);
    if (ret == FALSE) {
        return -1;
    }

    initCache();

    char operator;
    uint64_t address;
    int size;

    int isFist=TRUE;

    while (fscanf(traceFile, " %c %lx,%d\n", &operator, &address, &size) == 3)
    {
        if (operator == 'I')
            continue;

        int setIndex = (address >> b) % (1 << s);
        uint64_t tag = address >> (b + s);

        if (verbose)
        {
            if (!isFist) {
                printf("\n");
            }
            isFist = FALSE;
            fprintf(stdout, "%c %lx,%d ", operator, address, size);
        }

        if (operator == 'L' || operator == 'S') {
            getCache(tag, setIndex);
        }
        else if (operator == 'M') {
            getCache(tag, setIndex);
            getCache(tag, setIndex);
        }
    }

    if (verbose) {
        printf("\n");
    }

    release();
    
    printSummary(result.hit, result.miss, result.eviction);

    return 0;
}

void printUsage()
{
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n");
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n");
    printf("\n");
    printf("Examples:\n");
    printf("  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n");
    printf("  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}

int getArguments(int argc, char** argv)
{
    int ch;

    int ret = TRUE;

    while ((ch = getopt(argc, argv, "hvsEbt")) != EOF)
    {
        switch(ch)
        {
            case 'h':
                printUsage();
                break;
            case 'v':
                verbose = TRUE;
                break;
            case 's':
                s = atoi(argv[optind]);
                if (s <= 0) {
                    ret = FALSE;
                    printUsage();
                }
                S = 1 << s;
                break;
            case 'E':  // 每一组的行数
                E = atoi(argv[optind]);
                if (E <= 0) {
                    ret = FALSE;
                    printUsage();
                }
                break;
            case 'b':
                b = atoi(argv[optind]);
                if (b <= 0) {
                    ret = FALSE;
                    printUsage();
                } else {
                    B = (1 << b);
                }
                break;
            case 't':
                traceFile = fopen(argv[optind], "r");
                if (!traceFile) {
                    ret = FALSE;
                    printUsage();
                }
                break;
            default:
                ret = FALSE;
                printUsage();
                break;
        }
    }

    return ret;
}

void initCache()
{
    cache = (CacheSet*)malloc(sizeof(CacheSet) * S);
    for (int i = 0; i < S; ++i) {
        cache[i] = (CacheLine*)malloc(sizeof(CacheLine) * E);
        for (int j = 0; j < E; ++j) {
            cache[i][j].tag = -1;
            cache[i][j].timeStamp = 0;
        }
    }
}

void release()
{
    for (int i = 0; i < S; ++i) {
        free(cache[i]);
    }
    free(cache);

    if (traceFile) {
        fclose(traceFile);
    }
}

void getCache(uint64_t tag, int setIndex)
{
    int emptyLineIndex = -1;
    int minTimeStampIndex = 0;

    ++curTimeStamp;

    for (int i = 0; i < E; ++i)
    {
        if (cache[setIndex][i].tag == tag) {
            if (verbose) {
                printf("hit ");
            }
            ++result.hit;
            cache[setIndex][i].timeStamp = curTimeStamp;
            return;
        }

        if (cache[setIndex][i].timeStamp == 0 && emptyLineIndex < 0) {
            emptyLineIndex = i;
        }

        if (cache[setIndex][minTimeStampIndex].timeStamp > cache[setIndex][i].timeStamp) {
            minTimeStampIndex = i;
        }
    }

    if (verbose) {
        printf("miss ");
    }
    ++result.miss;

    if (emptyLineIndex >= 0) {
        cache[setIndex][emptyLineIndex].tag = tag;
        cache[setIndex][emptyLineIndex].timeStamp = curTimeStamp;
    }
    else {
        if (verbose) {
            printf("eviction ");
        }
        cache[setIndex][minTimeStampIndex].tag = tag;
        cache[setIndex][minTimeStampIndex].timeStamp = curTimeStamp;
        ++result.eviction;
    }
}

/* 
 * tsh - A tiny shell program with job control
 * 
 * <Put your name and login ID here>
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <errno.h>

/* Misc manifest constants */
#define MAXLINE    1024   /* max line size */
#define MAXARGS     128   /* max args on a command line */
#define MAXJOBS      16   /* max jobs at any point in time */
#define MAXJID    1<<16   /* max job ID */

/* Job states */
#define UNDEF 0 /* undefined */
#define FG 1    /* running in foreground */
#define BG 2    /* running in background */
#define ST 3    /* stopped */

/* 
 * Jobs states: FG (foreground), BG (background), ST (stopped)
 * Job state transitions and enabling actions:
 *     FG -> ST  : ctrl-z
 *     ST -> FG  : fg command
 *     ST -> BG  : bg command
 *     BG -> FG  : fg command
 * At most 1 job can be in the FG state.
 */

/* Global variables */
extern char **environ;      /* defined in libc */
char prompt[] = "tsh> ";    /* command line prompt (DO NOT CHANGE) */
int verbose = 0;            /* if true, print additional output */
int nextjid = 1;            /* next job ID to allocate */
char sbuf[MAXLINE];         /* for composing sprintf messages */

struct job_t {              /* The job struct */
    pid_t pid;              /* job PID */
    int jid;                /* job ID [1, 2, ...] */
    int state;              /* UNDEF, BG, FG, or ST */
    char cmdline[MAXLINE];  /* command line */
};
struct job_t jobs[MAXJOBS]; /* The job list */
/* End global variables */


/* Function prototypes */

/* Here are the functions that you will implement */
void eval(char *cmdline);
int builtin_cmd(char **argv);
void do_bgfg(char **argv);
void waitfg(pid_t pid);

void sigchld_handler(int sig);
void sigtstp_handler(int sig);
void sigint_handler(int sig);

/* Here are helper routines that we've provided for you */
int parseline(const char *cmdline, char **argv); 
void sigquit_handler(int sig);

void clearjob(struct job_t *job);
void initjobs(struct job_t *jobs);
int maxjid(struct job_t *jobs); 
int addjob(struct job_t *jobs, pid_t pid, int state, char *cmdline);
int deletejob(struct job_t *jobs, pid_t pid); 
pid_t fgpid(struct job_t *jobs);
struct job_t *getjobpid(struct job_t *jobs, pid_t pid);
struct job_t *getjobjid(struct job_t *jobs, int jid); 
int pid2jid(pid_t pid); 
void listjobs(struct job_t *jobs);

void usage(void);
void unix_error(char *msg);
void app_error(char *msg);
typedef void handler_t(int);
handler_t *Signal(int signum, handler_t *handler);

/*
 * main - The shell's main routine 
 */
int main(int argc, char **argv) 
{
    char c;
    char cmdline[MAXLINE];
    int emit_prompt = 1; /* emit prompt (default) */

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1, 2);

    /* Parse the command line */
    while ((c = getopt(argc, argv, "hvp")) != EOF) {
      switch (c) {
        case 'h':             /* print help message */
            usage();
	          break;
        case 'v':             /* emit additional diagnostic info */
            verbose = 1;
	          break;
        case 'p':             /* don't print a prompt */
            emit_prompt = 0;  /* handy for automatic testing */
	          break;
	      default:
            usage();
	    }
    }

    /* Install the signal handlers */

    /* These are the ones you will need to implement */
    Signal(SIGINT,  sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    Signal(SIGQUIT, sigquit_handler); 

    /* Initialize the job list */
    initjobs(jobs);

    /* Execute the shell's read/eval loop */
    while (1) {

      /* Read command line */
      if (emit_prompt) {
          printf("%s", prompt);
          fflush(stdout);
      }
      if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
          app_error("fgets error");
      if (feof(stdin)) { /* End of file (ctrl-d) */
          fflush(stdout);
          exit(0);
      }

      /* Evaluate the command line */
      eval(cmdline);
      fflush(stdout);
      fflush(stdout);
    } 

    exit(0); /* control never reaches here */
}
  
/* 
 * eval - Evaluate the command line that the user has just typed in
 * 
 * If the user has requested a built-in command (quit, jobs, bg or fg)
 * then execute it immediately. Otherwise, fork a child process and
 * run the job in the context of the child. If the job is running in
 * the foreground, wait for it to terminate and then return.  Note:
 * each child process must have a unique process group ID so that our
 * background children don't receive SIGINT (SIGTSTP) from the kernel
 * when we type ctrl-c (ctrl-z) at the keyboard.  
*/
void eval(char *cmdline) 
{
    char* argv[MAXARGS];
    char buf[MAXLINE];
    int bg;
    pid_t pid;

    sigset_t mask_all, prev_all;

    strcpy(buf, cmdline);

    bg = parseline(cmdline, argv);
    if (argv[0] == NULL) {
        return;
    }

    if (builtin_cmd(argv)) {
        return;
    }

    sigfillset(&mask_all);
    // 阻塞所有信号
    sigprocmask(SIG_BLOCK, &mask_all, &prev_all);

    if ((pid = fork()) == 0) 
    {
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        // 重新设置gpid，因为当按下ctrl+c给子进程发送终止消息时，
        // 如果shell和子进程的进程组号相同，它们都会收到SIGINT，都会终止
        setpgid(0, 0);

        if (execve(argv[0], argv, environ) < 0) {
            printf("%s: Command not found\n", argv[0]);
            exit(0);
        }
    }

    // execve调用成功，不会返回，所以子进程不会执行到这里
    if (!bg) {
        // 前台进程
        addjob(jobs, pid, FG, cmdline);
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        waitfg(pid);
    }
    else {
        // 后台进程
        addjob(jobs, pid, BG, cmdline);
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        // 直接输出相关信息，不等待进程结束
        printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline);
    }

    return;
}

/* 
 * parseline - Parse the command line and build the argv array.
 * 
 * Characters enclosed in single quotes are treated as a single
 * argument.  Return true if the user has requested a BG job, false if
 * the user has requested a FG job.  
 */
int parseline(const char *cmdline, char **argv) 
{
    static char array[MAXLINE]; /* holds local copy of command line */
    char *buf = array;          /* ptr that traverses command line */
    char *delim;                /* points to first space delimiter */
    int argc;                   /* number of args */
    int bg;                     /* background job? */

    strcpy(buf, cmdline);
    buf[strlen(buf)-1] = ' ';  /* replace trailing '\n' with space */
    while (*buf && (*buf == ' ')) /* ignore leading spaces */
	    buf++;

    /* Build the argv list */
    argc = 0;
    if (*buf == '\'') {
	    buf++;
	    delim = strchr(buf, '\'');
    }
    else {
	    delim = strchr(buf, ' ');
    }

    while (delim) {
      argv[argc++] = buf;
      *delim = '\0';
      buf = delim + 1;
      while (*buf && (*buf == ' ')) /* ignore spaces */
        buf++;

      if (*buf == '\'') {
        buf++;
        delim = strchr(buf, '\'');
      }
      else {
        delim = strchr(buf, ' ');
      }
    }
    argv[argc] = NULL;
    
    if (argc == 0)  /* ignore blank line */
      return 1;

    /* should the job run in the background? */
    if ((bg = (*argv[argc-1] == '&')) != 0) {
      argv[--argc] = NULL;
    }
    return bg;
}

/* 
 * builtin_cmd - If the user has typed a built-in command then execute
 *    it immediately.  
 */
int builtin_cmd(char **argv) 
{
    // "quit", "jobs", "bg", "fg"
    if (!strcmp(argv[0], "quit")) {
        exit(0);
    }

    if (!strcmp(argv[0], "jobs")) {
        listjobs(jobs);
        return 1;
    }

    if (!strcmp(argv[0], "fg") || !strcmp(argv[0], "bg")) {
        do_bgfg(argv);
        return 1;
    }

    // 不处理单独的'&'
    if (!strcmp(argv[0], "&")) {
        return 1;
    }

    return 0;     /* not a builtin command */
}

/* 
 * do_bgfg - Execute the builtin bg and fg commands
 */
void do_bgfg(char **argv) 
{
    /*
    bg：通过向作业发送SIGCONT信号来使它重启并放在后台运行
    fg：通过向作业发送SIGCONT信号来使它重启并放在前台运行
    输入时后面的参数有%则代表jid，没有则代表pid
    */

    if (argv[1] == NULL) {
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return;
    }

    sigset_t mask_all, prev_all;
    sigfillset(&mask_all);
    // 阻塞信号，访问全局数组
    sigprocmask(SIG_BLOCK, &mask_all, &prev_all);

    struct job_t* job;
    int jid = 0;
    int pid = 0;

    // 获取jid or pid
    if (argv[1][0] == '%') {
        jid = atoi(argv[1] + 1);
    }
    else {
        pid = atoi(argv[1]);
    }

    // 处理非法输入jid或pid的情况
    if ((jid == 0 && argv[1][0] == '%') || (pid == 0 && argv[1][0] != '%'))
    {
        printf("%s: argument must be a PID or %%jobid\n", argv[0]);
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        return;
    }

    if (jid == 0) {
        jid = pid2jid(pid);
    }
    job = getjobjid(jobs, jid);
    if (!job) {
        if (argv[1][0] != '%') {
            printf("(%s): ", argv[1]);
        }
        else {
            printf("%s: ", argv[1]);
        }
        printf("No such %s\n", argv[1][0] == '%' ? "job" : "process");    
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        return;    
    }

    if (strcmp(argv[0], "bg") == 0) 
    {
        job->state = BG;
        printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
        kill(-(job->pid), SIGCONT);
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
    }
    else 
    {
        if (job->state == ST) {
            kill(-(job->pid), SIGCONT);
        }
        job->state = FG;
        sigprocmask(SIG_SETMASK, &prev_all, NULL);
        waitfg(job->pid);
    }

    return;
}

/* 
 * waitfg - Block until process pid is no longer the foreground process
 */
void waitfg(pid_t pid)
{
    sigset_t mask_all, prev_all;
    sigfillset(&mask_all);

    while (1)
    {
        // 访问全局变量需阻塞相关信号
        sigprocmask(SIG_BLOCK, &mask_all, &prev_all);
        struct job_t* foreground_job = getjobpid(jobs, pid);
        sigprocmask(SIG_SETMASK, &prev_all, NULL);

        // 如果找不到前台进程，或者前台进程已经挂起，则退出循环
        if (!foreground_job || foreground_job->state != FG) {
            break;
        }

        sleep(1);
    }

    return;
}

/*****************
 * Signal handlers
 *****************/

/* 
 * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
 *     a child job terminates (becomes a zombie), or stops because it
 *     received a SIGSTOP or SIGTSTP signal. The handler reaps all
 *     available zombie children, but doesn't wait for any other
 *     currently running children to terminate.  
 */
void sigchld_handler(int sig) 
{
    // 对于全局变量errno，注意保存和恢复
    int olderrno = errno;
    int status;

    sigset_t mask_all, prev_all;
    pid_t pid;

    sigfillset(&mask_all);

    // WNOHANG | WUNTRACED: 立即返回，如果等待集合中的子进程都没有被停止或终止，则返回0；
    // 如果有一个停止或终止，则返回该子进程的PID。
    while((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
        sigprocmask(SIG_BLOCK, &mask_all, &prev_all);

        if (WIFEXITED(status)) {
            // 子进程通过调用exit或者return正常终止
            deletejob(jobs, pid);
        }
        else if (WIFSIGNALED(status)) {
            // 子进程因为一个未被捕获的信号终止
            printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
            deletejob(jobs, pid);
        }
        else if (WIFSTOPPED(status)) {
            // 子进程是停止的
            printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, WSTOPSIG(status));
            struct job_t* job = getjobpid(jobs, pid);
            job->state = ST;
        }

        sigprocmask(SIG_SETMASK, &prev_all, NULL);
    }

    errno = olderrno;
    return;
}

/* 
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.  
 */
void sigint_handler(int sig) 
{
    // 对于全局变量errno，注意保存和恢复
    int olderrno = errno;

    sigset_t mask_all, prev_all;
    sigfillset(&mask_all);
    // 阻塞所有信号
    sigprocmask(SIG_BLOCK, &mask_all, &prev_all);

    // 获取前台进程
    pid_t pid = fgpid(jobs);
    if (pid != 0) {
        // -pid而不是pid，保证信号能够被传递给整个子进程组，因为shell fork出来的子进程可能还会fork出子进程
        kill(-pid, SIGINT);
    }

    sigprocmask(SIG_SETMASK, &prev_all, NULL);
    errno = olderrno;
    return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.  
 */
void sigtstp_handler(int sig) 
{
    // 对于全局变量errno，注意保存和恢复
    int olderrno = errno;

    sigset_t mask_all, prev_all;
    sigfillset(&mask_all);
    // 阻塞所有信号
    sigprocmask(SIG_BLOCK, &mask_all, &prev_all);

    // 获取前台进程
    pid_t pid = fgpid(jobs);
    if (pid != 0) {
        // -pid而不是pid，保证信号能够被传递给整个子进程组，因为shell fork出来的子进程可能还会fork出子进程
        kill(-pid, SIGTSTP);
    }

    sigprocmask(SIG_SETMASK, &prev_all, NULL);
    errno = olderrno;
    return;
}

/*********************
 * End signal handlers
 *********************/

/***********************************************
 * Helper routines that manipulate the job list
 **********************************************/

/* clearjob - Clear the entries in a job struct */
void clearjob(struct job_t *job) {
    job->pid = 0;
    job->jid = 0;
    job->state = UNDEF;
    job->cmdline[0] = '\0';
}

/* initjobs - Initialize the job list */
void initjobs(struct job_t *jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
	clearjob(&jobs[i]);
}

/* maxjid - Returns largest allocated job ID */
int maxjid(struct job_t *jobs) 
{
    int i, max=0;

    for (i = 0; i < MAXJOBS; i++)
	if (jobs[i].jid > max)
	    max = jobs[i].jid;
    return max;
}

/* addjob - Add a job to the job list */
int addjob(struct job_t *jobs, pid_t pid, int state, char *cmdline) 
{
    int i;
    
    if (pid < 1)
	    return 0;

    for (i = 0; i < MAXJOBS; i++) {
      if (jobs[i].pid == 0) {
          jobs[i].pid = pid;
          jobs[i].state = state;
          jobs[i].jid = nextjid++;
          if (nextjid > MAXJOBS)
        nextjid = 1;
          strcpy(jobs[i].cmdline, cmdline);
            if(verbose){
              printf("Added job [%d] %d %s\n", jobs[i].jid, jobs[i].pid, jobs[i].cmdline);
                }
                return 1;
      }
    }
    printf("Tried to create too many jobs\n");
    return 0;
}

/* deletejob - Delete a job whose PID=pid from the job list */
int deletejob(struct job_t *jobs, pid_t pid) 
{
    int i;

    if (pid < 1)
	    return 0;

    for (i = 0; i < MAXJOBS; i++) {
      if (jobs[i].pid == pid) {
          clearjob(&jobs[i]);
          nextjid = maxjid(jobs)+1;
          return 1;
      }
    }
    return 0;
}

/* fgpid - Return PID of current foreground job, 0 if no such job */
pid_t fgpid(struct job_t *jobs) {
    int i;

    for (i = 0; i < MAXJOBS; i++)
      if (jobs[i].state == FG)
          return jobs[i].pid;
    return 0;
}

/* getjobpid  - Find a job (by PID) on the job list */
struct job_t *getjobpid(struct job_t *jobs, pid_t pid) {
    int i;

    if (pid < 1)
	    return NULL;
    for (i = 0; i < MAXJOBS; i++)
      if (jobs[i].pid == pid)
          return &jobs[i];
    return NULL;
}

/* getjobjid  - Find a job (by JID) on the job list */
struct job_t *getjobjid(struct job_t *jobs, int jid) 
{
    int i;

    if (jid < 1)
	    return NULL;
    for (i = 0; i < MAXJOBS; i++)
      if (jobs[i].jid == jid)
          return &jobs[i];
    return NULL;
}

/* pid2jid - Map process ID to job ID */
int pid2jid(pid_t pid) 
{
    int i;

    if (pid < 1)
	    return 0;
    for (i = 0; i < MAXJOBS; i++)
      if (jobs[i].pid == pid) {
          return jobs[i].jid;
      }
    return 0;
}

/* listjobs - Print the job list */
void listjobs(struct job_t *jobs) 
{
    int i;
    
    for (i = 0; i < MAXJOBS; i++) {
      if (jobs[i].pid != 0) {
          printf("[%d] (%d) ", jobs[i].jid, jobs[i].pid);
          switch (jobs[i].state) {
        case BG: 
            printf("Running ");
            break;
        case FG: 
            printf("Foreground ");
            break;
        case ST: 
            printf("Stopped ");
            break;
          default:
            printf("listjobs: Internal error: job[%d].state=%d ", 
            i, jobs[i].state);
          }
          printf("%s", jobs[i].cmdline);
      }
    }
}
/******************************
 * end job list helper routines
 ******************************/


/***********************
 * Other helper routines
 ***********************/

/*
 * usage - print a help message
 */
void usage(void) 
{
    printf("Usage: shell [-hvp]\n");
    printf("   -h   print this message\n");
    printf("   -v   print additional diagnostic information\n");
    printf("   -p   do not emit a command prompt\n");
    exit(1);
}

/*
 * unix_error - unix-style error routine
 */
void unix_error(char *msg)
{
    fprintf(stdout, "%s: %s\n", msg, strerror(errno));
    exit(1);
}

/*
 * app_error - application-style error routine
 */
void app_error(char *msg)
{
    fprintf(stdout, "%s\n", msg);
    exit(1);
}

/*
 * Signal - wrapper for the sigaction function
 */
handler_t *Signal(int signum, handler_t *handler) 
{
    struct sigaction action, old_action;

    action.sa_handler = handler;  
    sigemptyset(&action.sa_mask); /* block sigs of type being handled */
    action.sa_flags = SA_RESTART; /* restart syscalls if possible */

    if (sigaction(signum, &action, &old_action) < 0)
	    unix_error("Signal error");
    return (old_action.sa_handler);
}

/*
 * sigquit_handler - The driver program can gracefully terminate the
 *    child shell by sending it a SIGQUIT signal.
 */
void sigquit_handler(int sig) 
{
    printf("Terminating after receipt of SIGQUIT signal\n");
    exit(1);
}

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))


#define WSIZE 4 /* word and header/footer size(bytes)*/
#define DSIZE 8 /* Double word size(bytes)*/
#define CHUNKSIZE (1<<12)

#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p) (*(unsigned int*)(p))
#define PUT(p, val) (*(unsigned int*)(p) = val)

/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))


/* Heap prologue block pointer */
static void *heap_listp;


/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    /* 申请4个字节的空间 */
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1)
        return -1;

    /* 双字边界对齐的不使用的填充字 */
    PUT(heap_listp, 0);

    /* 序言块, 8个字节的已分配块, 只由一个头部和一个脚部组成 */
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));

    /* 结尾块, 大小为0的已分配块 */
    PUT(heap_listp + (3*WSIZE), PACK(0, 1));

    /* 指向有效载荷, 序言块的中间 */
    heap_listp += (2*WSIZE);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

    return 0;
}

void *extend_heap(size_t words)
{
    /* bp总是指向有效载荷 */
    char *bp;
    size_t size;

    /* aligment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;

    /* HDRP(bp) 指向原结尾块 */
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));  /* 新结尾块 */

    /* 判断相邻块是否是空闲块, 进行合并 */
    return coalesced(bp);
}

void *find_fit(size_t asize)
{
    void *p;

    for (p = heap_listp; GET_SIZE(HDRP(p)) > 0; p = NEXT_BLKP(p)) {
        if (!GET_ALLOC(HDRP(p)) && (asize <= GET_SIZE(HDRP(p)))) {
            return p;
        }
    }

    return NULL;
}


/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    /*
    int newsize = ALIGN(size + SIZE_T_SIZE);
    void *p = mem_sbrk(newsize);
    if (p == (void *)-1)
	return NULL;
    else {
        *(size_t *)p = size;
        return (void *)((char *)p + SIZE_T_SIZE);
    }
    */
    
    /* 对齐, 查找有无合适的空闲块, 如果没有则申请扩展堆 */
    size_t asize;  /* Adjusted block size */
    size_t extendsize;

    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);

    /* 寻找合适的空闲块 */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    /* 找不到则扩展堆 */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp=extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesced(ptr);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    /*
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
    */
    
    void *oldptr = ptr;
    void *newptr;
    void *nextptr;

    size_t blocksize;
    size_t extendsize;
    size_t asize;
    size_t sizesum;

    if (ptr == NULL) {
        return mm_malloc(size);
    } 

    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }

    if (size <= DSIZE)
        asize = 2*DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);


    blocksize = GET_SIZE(HDRP(ptr));

    if (asize == blocksize)
        return ptr;

    if (asize < blocksize) {
        place(ptr, asize);
        return ptr;
    }

    /* asize > blocksize*/
    nextptr = NEXT_BLKP(ptr);
    sizesum = GET_SIZE(HDRP(nextptr)) + blocksize;
    if (!GET_ALLOC(HDRP(nextptr)) && sizesum >= asize) {
        PUT(HDRP(ptr), PACK(sizesum, 0));
        place(ptr, asize);
        return ptr;
    }

    /* Next block is allocated or size is not enough */
    newptr = find_fit(asize);
    if (newptr == NULL) {
        extendsize = MAX(asize, CHUNKSIZE);
        if ((newptr = extend_heap(extendsize / WSIZE)) == NULL) {
            return NULL;
        }
    }

    place(newptr, asize);
    memcpy(newptr, oldptr, blocksize - 2*WSIZE);
    mm_free(oldptr);
    return newptr;
}

/* 分离空闲块 */
void place(void *bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));
    if (size - asize >= 2 * DSIZE) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));

        bp = NEXT_BLKP(bp);

        PUT(HDRP(bp), PACK(size - asize, 0));
        PUT(FTRP(bp), PACK(size - asize, 0));
    }
    else {
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
    }
}

/* 合并空闲块 */
void *coalesced(void *ptr)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));

    size_t size = GET_SIZE(HDRP(ptr));

    if (prev_alloc && next_alloc) {
        return ptr;
    }
    else if (!prev_alloc && next_alloc) {
        size += GET_SIZE(FTRP(PREV_BLKP(ptr)));
        PUT(FTRP(ptr), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    else if (prev_alloc && !next_alloc) {
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        PUT(HDRP(ptr), PACK(size, 0));  /* 先修改头 */
        PUT(FTRP(ptr), PACK(size, 0));  /* 根据头部中的大小来定位尾部 */
    }
    else if (!prev_alloc && !next_alloc) {
        size += (GET_SIZE(FTRP(PREV_BLKP(ptr))) + GET_SIZE(HDRP(NEXT_BLKP(ptr))));
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
        ptr = PREV_BLKP(ptr);
    }
    return ptr;
}

#include <stdio.h>

extern int mm_init (void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);
extern void *mm_realloc(void *ptr, size_t size);

extern void *extend_heap(size_t words);
extern void *find_fit(size_t asize);
extern void place(void *bp, size_t asize);
extern void *coalesced(void *ptr);

/* 
 * Students work in teams of one or two.  Teams enter their team name, 
 * personal names and login IDs in a struct of this
 * type in their bits.c file.
 */
typedef struct {
    char *teamname; /* ID1+ID2 or ID1 */
    char *name1;    /* full name of first member */
    char *id1;      /* login ID of first member */
    char *name2;    /* full name of second member (if any) */
    char *id2;      /* login ID of second member */
} team_t;

extern team_t team;

#include <stdio.h>
#include "csapp.h"

/* Recommended max cache and object sizes */
#define MAX_CACHE_SIZE 1049000
#define MAX_OBJECT_SIZE 102400

/* You won't lose style points for including this long line in your code */
static const char *user_agent_hdr = "User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.3) Gecko/20120305 Firefox/10.0.3\r\n";
static const char *conn_hdr = "Connection: close\r\n";
static const char *proxy_hdr = "Proxy-Connection: close\r\n";

void doit(int fd);
int parse_uri(char* uri, char* hostname, char* filename, char* port);
void build_request(rio_t *real_client, char *new_request, char *hostname, char *port);
void clienterror(int fd, char *cause, char *errnum, char *shortmsg, char *longmsg);

int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];

    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <port>\n", argv[0]);
        exit(1);
    }

    listenfd = Open_listenfd(argv[1]);
    while (1) {
        clientlen = sizeof(clientaddr);
        connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen);

        Getnameinfo((SA*)&clientaddr, clientlen, hostname, MAXLINE, port, MAXLINE, 0);
        printf("Accepted connection from (%s, %s)\n", hostname, port);

        doit(connfd);
        Close(connfd);
    }

    return 0;
}

void doit(int fd)
{
    int servfd;

    char buf[MAXLINE], method[MAXLINE], uri[MAXLINE], version[MAXLINE];
    char hostname[MAXLINE], filename[MAXLINE], port[MAXLINE];

    rio_t rio, server_rio;

    Rio_readinitb(&rio, fd);
    if (!Rio_readlineb(&rio, buf, MAXLINE))
        return;

    sscanf(buf, "%s %s %s", method, uri, version);

    if (strcasecmp(method, "GET")) {
        clienterror(fd, method, "501", "Not Implemented", "Tiny does not implement this method");
        return;
    }
    
    parse_uri(uri, hostname, filename, port);

    /* 建立与服务器的连接 */
    servfd = Open_clientfd(hostname, port);
    if (servfd < 0) {
        printf("connection failed\n");
        return;
    }

    /* 将从客户端收到的请求转发给服务端 */
    char new_request[MAXLINE];
    sprintf(new_request, "GET %s HTTP/1.0\r\n", filename);
    build_request(&rio, new_request, hostname, port);
    Rio_writen(servfd, new_request, strlen(new_request));

    /* 将从服务端收到的数据转发给客户端 */
    Rio_readinitb(&server_rio, servfd);
    size_t n;
    while ((n = Rio_readlineb(&server_rio, buf, MAXLINE)) != 0) {
        Rio_writen(fd, buf, n);
    }
    Close(servfd);
}

void build_request(rio_t *real_client, char *new_request, char *hostname, char *port) 
{
    char temp_buf[MAXLINE];

    // 获取client的请求报文
    while (Rio_readlineb(real_client, temp_buf, MAXLINE) > 0) {
        if (strstr(temp_buf, "\r\n")) break;  // end

        // 忽略以下几个字段的信息
        if (strstr(temp_buf, "Host:")) continue;
        if (strstr(temp_buf, "User-Agent:")) continue;
        if (strstr(temp_buf, "Connection:")) continue;
        if (strstr(temp_buf, "Proxy Connection:")) continue;

        sprintf(new_request, "%s%s", new_request, temp_buf);
        printf("%s\n", new_request);
        fflush(stdout);
    }
    sprintf(new_request, "%sHost: %s:%s\r\n", new_request, hostname, port);
    sprintf(new_request, "%s%s%s%s", new_request, user_agent_hdr, conn_hdr, proxy_hdr);
    // every HTTP request is terminated by an empty line: "\r\n"
    sprintf(new_request, "%s\r\n", new_request);
}

int parse_uri(char* uri, char* hostname, char* filename, char* port)
{
    char* hostname_pos, *filename_pos, *port_pos;

    char* http_pos = strstr(uri, "//");
    if (!http_pos) {
        hostname_pos = uri;
    }
    else {
        hostname_pos = http_pos + 2;
    }

    port_pos = strstr(hostname_pos, ":");
    if (!port_pos) {
        strcpy(port, "80");
        filename_pos = strstr(hostname_pos, "/");
        strcpy(filename, filename_pos);
        *filename_pos = '\0';
    }
    else {
        int portnum;
        sscanf(port_pos + 1, "%d%s", &portnum, filename);
        sprintf(port, "%d", portnum);
        *port_pos = '\0';
    }

    strcpy(hostname, hostname_pos);

    return 0;
}

void clienterror(int fd, char *cause, char *errnum, char *shortmsg, char *longmsg) 
{
    char buf[MAXLINE];

    /* Print the HTTP response headers */
    sprintf(buf, "HTTP/1.0 %s %s\r\n", errnum, shortmsg);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "Content-type: text/html\r\n\r\n");
    Rio_writen(fd, buf, strlen(buf));

    /* Print the HTTP response body */
    sprintf(buf, "<html><title>Tiny Error</title>");
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf,
            "<body bgcolor="
            "ffffff"
            ">\r\n");
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "%s: %s\r\n", errnum, shortmsg);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "<p>%s: %s\r\n", longmsg, cause);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "</p><hr><em>The Tiny Web server</em>\r\n");
    Rio_writen(fd, buf, strlen(buf));
}

int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];

    pthread_t tid;

    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <port>\n", argv[0]);
        exit(1);
    }

    listenfd = Open_listenfd(argv[1]);
    while (1) {
        clientlen = sizeof(clientaddr);
        connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen);

        Getnameinfo((SA*)&clientaddr, clientlen, hostname, MAXLINE, port, MAXLINE, 0);
        printf("Accepted connection from (%s, %s)\n", hostname, port);

        Pthread_create(&tid, NULL, thread, (void*)&connfd);
    }

    return 0;
}

void thread(void* v)
{
    int fd = *(int*)v;
    Pthread_detach(pthread_self());
    doit(fd);
    close(fd);
}

#define NTHREADS 4
#define SBUFSIZE 16

typedef struct {
    int* buf;    /* Buffer array */
    int n;       /* Maximum number of slots */
    int front;   /* buf[(front+1) % n] is first item */
    int rear;    /* buf[rear % n] is last item */
    sem_t mutex; /* Protects access to buf */
    sem_t slots; /* Counts available slots */
    sem_t items; /* Counts available items */
} sbuf_t;

sbuf_t sbuf;     /* Shared buffer of connected descriptors */


int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];

    pthread_t tid;

    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <port>\n", argv[0]);
        exit(1);
    }

    listenfd = Open_listenfd(argv[1]);

    subf_init(&sbuf, SBUFSIZE);

    for (int i = 0; i < NTHREADS; ++i) {
        Pthread_create(&tid, NULL, thread, NULL);
    }

    while (1) {
        clientlen = sizeof(clientaddr);
        connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen);

        Getnameinfo((SA*)&clientaddr, clientlen, hostname, MAXLINE, port, MAXLINE, 0);
        printf("Accepted connection from (%s, %s)\n", hostname, port);

        sbuf_insert(&sbuf, connfd);
    }

    return 0;
}

void thread(void* v)
{
    Pthread_detach(pthread_self());

    while (1) {
        int connfd = sbuf_remove(&sbuf);
        doit(connfd);
        close(connfd);
    }
}

void subf_init(sbuf_t *sp, int n)
{
    sp->buf = calloc(n, sizeof(n));
    sp->n = n;
    sp->front = 0;
    sp->rear = 0;

    Sem_init(&sp->mutex, 0, 1);
    Sem_init(&sp->slots, 0, n);
    Sem_init(&sp->items, 0, 0);
}

void subf_deinit(sbuf_t *sp)
{
    Free(sp->buf);
}

void sbuf_insert(sbuf_t *sp, int item)
{
    P(&sp->slots);                                /* Wait for available slot */
    P(&sp->mutex);                                /* Lock the buffer */
    sp->buf[(++sp->rear) % (sp->n)] = item;       /* Insert the item */
    V(&sp->mutex);                                /* Unlock the buffer */
    V(&sp->items);                                /* Announce available item */
}

int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);                                /* Wait for available item */
    P(&sp->mutex);
    item = sp->buf[(++sp->front) % (sp->n)];      /* Remove the item */
    V(&sp->mutex);
    V(&sp->slots);                                /* Announce available slot */
    return item;
}

#include <stdio.h>
#include "csapp.h"

/* Recommended max cache and object sizes */
#define MAX_CACHE_SIZE 1049000
#define MAX_OBJECT_SIZE 102400
#define MAX_CHCHE 10

#define NTHREADS 4
#define SBUFSIZE 16

#define TRUE  1
#define FALSE 0

/* You won't lose style points for including this long line in your code */
static const char *user_agent_hdr = "User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.3) Gecko/20120305 Firefox/10.0.3\r\n";
static const char *conn_hdr = "Connection: close\r\n";
static const char *proxy_hdr = "Proxy-Connection: close\r\n";

typedef struct {
    char uri[MAXLINE];
    char obj[MAX_OBJECT_SIZE];

    time_t t;
} Cache;

Cache cache[MAX_CHCHE];

typedef struct {
    int read_cnt;  // 读者数量
    sem_t w;
    sem_t mutex;
} RWLock;

RWLock rwLock;

typedef struct {
    int* buf;    /* Buffer array */
    int n;       /* Maximum number of slots */
    int front;   /* buf[(front+1) % n] is first item */
    int rear;    /* buf[rear % n] is last item */
    sem_t mutex; /* Protects access to buf */
    sem_t slots; /* Counts available slots */
    sem_t items; /* Counts available items */
} sbuf_t;

sbuf_t sbuf;     /* Shared buffer of connected descriptors */

void doit(int fd);
int parse_uri(char* uri, char* hostname, char* filename, char* port);
void build_request(rio_t *real_client, char *new_request, char *hostname, char *port);
void clienterror(int fd, char *cause, char *errnum, char *shortmsg, char *longmsg);
void thread(void* v);

void subf_init(sbuf_t *sp, int n);
void subf_deinit(sbuf_t *sp);
void sbuf_insert(sbuf_t *sp, int item);
int sbuf_remove(sbuf_t *sp);

void init_cache();
char* get_cache(const char* uri);
void update_cache(const char* uri, const char* buf);

int main(int argc, char **argv)
{
    int listenfd, connfd;
    char hostname[MAXLINE], port[MAXLINE];

    pthread_t tid;

    socklen_t clientlen;
    struct sockaddr_storage clientaddr;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <port>\n", argv[0]);
        exit(1);
    }

    init_cache();

    listenfd = Open_listenfd(argv[1]);

    subf_init(&sbuf, SBUFSIZE);

    for (int i = 0; i < NTHREADS; ++i) {
        Pthread_create(&tid, NULL, thread, NULL);
    }

    while (1) {
        clientlen = sizeof(clientaddr);
        connfd = Accept(listenfd, (SA*)&clientaddr, &clientlen);

        Getnameinfo((SA*)&clientaddr, clientlen, hostname, MAXLINE, port, MAXLINE, 0);
        printf("Accepted connection from (%s, %s)\n", hostname, port);

        sbuf_insert(&sbuf, connfd);
    }

    return 0;
}

void thread(void* v)
{
    Pthread_detach(pthread_self());

    while (1) {
        int connfd = sbuf_remove(&sbuf);
        doit(connfd);
        close(connfd);
    }
}

void subf_init(sbuf_t *sp, int n)
{
    sp->buf = calloc(n, sizeof(n));
    sp->n = n;
    sp->front = 0;
    sp->rear = 0;

    Sem_init(&sp->mutex, 0, 1);
    Sem_init(&sp->slots, 0, n);
    Sem_init(&sp->items, 0, 0);
}

void subf_deinit(sbuf_t *sp)
{
    Free(sp->buf);
}

void sbuf_insert(sbuf_t *sp, int item)
{
    P(&sp->slots);                                /* Wait for available slot */
    P(&sp->mutex);                                /* Lock the buffer */
    sp->buf[(++sp->rear) % (sp->n)] = item;       /* Insert the item */
    V(&sp->mutex);                                /* Unlock the buffer */
    V(&sp->items);                                /* Announce available item */
}

int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);                                /* Wait for available item */
    P(&sp->mutex);
    item = sp->buf[(++sp->front) % (sp->n)];      /* Remove the item */
    V(&sp->mutex);
    V(&sp->slots);                                /* Announce available slot */
    return item;
}

void doit(int fd)
{
    int servfd;

    char buf[MAXLINE], method[MAXLINE], uri[MAXLINE], version[MAXLINE];
    char hostname[MAXLINE], filename[MAXLINE], port[MAXLINE];

    rio_t rio, server_rio;

    Rio_readinitb(&rio, fd);
    if (!Rio_readlineb(&rio, buf, MAXLINE))
        return;  

    sscanf(buf, "%s %s %s", method, uri, version);

    if (strcasecmp(method, "GET")) {
        clienterror(fd, method, "501", "Not Implemented", "Tiny does not implement this method");
        return;
    }

    char uri_copy[MAXLINE];
    strcpy(uri_copy, uri);
    char* ret = get_cache(uri_copy);
    if (ret) {
        Rio_writen(fd, ret, strlen(ret));
        free(ret);
        return;
    }
    
    parse_uri(uri, hostname, filename, port);

    /* 建立与服务器的连接 */
    servfd = Open_clientfd(hostname, port);
    if (servfd < 0) {
        printf("connection failed\n");
        return;
    }

    /* 将从客户端收到的请求转发给服务端 */
    char new_request[MAXLINE];
    sprintf(new_request, "GET %s HTTP/1.0\r\n", filename);
    build_request(&rio, new_request, hostname, port);
    Rio_writen(servfd, new_request, strlen(new_request));

    /* 将从服务端收到的数据转发给客户端 */
    Rio_readinitb(&server_rio, servfd);
    size_t total = 0;
    size_t n;
    char newcache[MAX_OBJECT_SIZE];
    while ((n = Rio_readlineb(&server_rio, buf, MAXLINE)) != 0) {
        Rio_writen(fd, buf, n);
        total += n;
        strcat(newcache, buf);
    }

    if (total < MAX_OBJECT_SIZE) {
        update_cache(uri_copy, newcache);
    }
    Close(servfd);
}

void build_request(rio_t *real_client, char *new_request, char *hostname, char *port) 
{
    char temp_buf[MAXLINE];

    // 获取client的请求报文
    while (Rio_readlineb(real_client, temp_buf, MAXLINE) > 0) {
        if (strstr(temp_buf, "\r\n")) break;  // end

        // 忽略以下几个字段的信息
        if (strstr(temp_buf, "Host:")) continue;
        if (strstr(temp_buf, "User-Agent:")) continue;
        if (strstr(temp_buf, "Connection:")) continue;
        if (strstr(temp_buf, "Proxy Connection:")) continue;

        sprintf(new_request, "%s%s", new_request, temp_buf);
        printf("%s\n", new_request);
        fflush(stdout);
    }
    sprintf(new_request, "%sHost: %s:%s\r\n", new_request, hostname, port);
    sprintf(new_request, "%s%s%s%s", new_request, user_agent_hdr, conn_hdr, proxy_hdr);
    // every HTTP request is terminated by an empty line: "\r\n"
    sprintf(new_request, "%s\r\n", new_request);
}

int parse_uri(char* uri, char* hostname, char* filename, char* port)
{
    char* hostname_pos, *filename_pos, *port_pos;

    char* http_pos = strstr(uri, "//");
    if (!http_pos) {
        hostname_pos = uri;
    }
    else {
        hostname_pos = http_pos + 2;
    }

    port_pos = strstr(hostname_pos, ":");
    if (!port_pos) {
        strcpy(port, "80");
        filename_pos = strstr(hostname_pos, "/");
        strcpy(filename, filename_pos);
        *filename_pos = '\0';
    }
    else {
        int portnum;
        sscanf(port_pos + 1, "%d%s", &portnum, filename);
        sprintf(port, "%d", portnum);
        *port_pos = '\0';
    }

    strcpy(hostname, hostname_pos);

    return 0;
}

void clienterror(int fd, char *cause, char *errnum, char *shortmsg, char *longmsg) 
{
    char buf[MAXLINE];

    /* Print the HTTP response headers */
    sprintf(buf, "HTTP/1.0 %s %s\r\n", errnum, shortmsg);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "Content-type: text/html\r\n\r\n");
    Rio_writen(fd, buf, strlen(buf));

    /* Print the HTTP response body */
    sprintf(buf, "<html><title>Tiny Error</title>");
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf,
            "<body bgcolor="
            "ffffff"
            ">\r\n");
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "%s: %s\r\n", errnum, shortmsg);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "<p>%s: %s\r\n", longmsg, cause);
    Rio_writen(fd, buf, strlen(buf));
    sprintf(buf, "</p><hr><em>The Tiny Web server</em>\r\n");
    Rio_writen(fd, buf, strlen(buf));
}

void init_cache()
{
    for (int i = 0; i < MAX_CHCHE; ++i) 
    {
        cache[i].t = 0;
    }
    rwLock.read_cnt = 0;
    Sem_init(&rwLock.w, 0, 1);
    Sem_init(&rwLock.mutex, 0, 1);
}

char* get_cache(const char* uri)
{
    char* ret = NULL;

    P(&rwLock.mutex);
    rwLock.read_cnt++;
    if (rwLock.read_cnt == 1) {
        P(&rwLock.w);
    }
    V(&rwLock.mutex);

    time_t curt = time(0);
    for (int i = 0; i < MAX_CHCHE; ++i)  
    {
        if (!strcasecmp(cache[i].uri, uri))
        {
            cache[i].t = curt;
            int len = strlen(cache[i].obj);
            ret = (char*)Malloc(len);
            strcpy(ret, cache[i].obj);
            break;
        }
    }

    P(&rwLock.mutex);
    rwLock.read_cnt--;
    if (rwLock.read_cnt == 0) {
        V(&rwLock.w);
    }
    V(&rwLock.mutex);

    return ret;
}

void update_cache(const char* uri, const char* buf)
{
    P(&rwLock.w);

    int minTIndex = 0;
    for (int i = 1; i < MAX_CHCHE; ++i) {
        if (cache[i].t < cache[minTIndex].t) {
            minTIndex = i;
        }
    }

    cache[minTIndex].t = time(0);
    strcpy(cache[minTIndex].uri, uri);
    strcpy(cache[minTIndex].obj, buf);

    V(&rwLock.w);
}