# Report

## Node initialization

After a process is created, it will take the `argv` (friend_info) and use simple string manipulation to store `friend_name` and `friend_value`.

If the process is not Not_Tako, it has to return status code to its parent (will elaborate later).

The process will initialize a `child` linked list, each `child` struct contains `pid`, `readfd`, `writefd` and `next` like such, the childlist will be `NULL` at initialize (no child).

```c
typedef struct child {
    pid_t pid;
    int readfd;
    int writefd;
    struct child *next;
} Child;

typedef Child* ChildList;

ChildList childlist = NULL;
```

### Command parsing

After the initialization, the root node (Not_Tako) will read from `stdin`, others will read from `PARENT_READ_FD`. The command will be parse to an array of string `cmd_argv`.

## Command passing

Take meet as example, first `Not_Tako` received a command `Meet [parent] [child]`, and will recursively pass down the command (pre-order) to its children by writing to their writefd, and then waits for chlid to reply meet status (blocking). If the current `friend_info` is parent, it will initialize the chlid and wait for status code, after that all of them will recursively pass the code upward to tell parents they're done, and finally up to root, which can proceed the next command.

Every other command has the similar mechanism.

## Implementations

I choose to explain command `Check` and `Adopt` since they were pretty fun to implement.

### Meet

Node will pass the command `Check [parent]` recursively until current friend_name is parent, and waits for their return status, and send status back to parent.

When it's parent node, it will call a function `send_subtree_info(0, 0, NULL)`, and then send complete status to its parent if is not `Not_Tako`.

```c
int check(char* parent) {
    if (strcmp(friend_name, parent) == 0) {
        // BFS check each child
        fprintf(stderr, "BFSing\n");
        send_subtree_info(0, 0, NULL);
        if (!is_Not_Tako()) {
            char msg = 1;
            if (write(PARENT_WRITE_FD, &msg, 1) != 1)
                ERR_EXIT("error telling parent check is complete");
        }
    } else {
        ChildList p = childlist;
        char msg;
        while (p != NULL) {
            char buf[MAX_CMD_LEN];
            sprintf(buf, "Check %s", parent);
            if (write(p->writefd, buf, strlen(buf)) != strlen(buf))
                ERR_EXIT("error passing check to child");

            // wait for child
            fprintf(stderr, "%s waiting for child's check status...\n", friend_info);
            if (read(p->readfd, &msg, 1) != 1)
                ERR_EXIT("error receiving check status from child");
            if (msg == 1)
                break;
            p = p->next;
        }
        if (p == NULL) {
            // check failed since parent was not found
            if (is_Not_Tako()) {
                print_fail_check(parent);
            } else {
                msg = 0;
                if (write(PARENT_WRITE_FD, &msg, 1) != 1)
                    ERR_EXIT("error telling parent check failed");
            }
            return -1;
        } else { // parent is found somewhere down
            if (!is_Not_Tako()) {
                msg = 1;
                if (write(PARENT_WRITE_FD, &msg, 1) != 1)
                    ERR_EXIT("error telling parent check succeeded");
            }
        }
    }
    return 0;
}
```

The important part is `send_subtree_info` so I'll explain more on this.

```c
void send_subtree_info(int depth, int save, char* savebuf); 
// depth: current depth relative to node that called 
// send_subtree_info(0, ...)
// save: save the result in savebuf? if true then at 
// the root node (depth == 0) it won't print (this is for Adopt command)
```


This function will first add the current node's `friend_info` to a buffer,

```c
char info[MAX_TREEINFO_LEN] = {0};
int bytes_printed = 0;
bytes_printed += sprintf(info + bytes_printed, (depth == 0) ? "%s %d" : ":%s %d", friend_info, depth);
```

and recursively pass down a command `subtree [depth + 1]` to its children, and call `read` to wait for children's report. After it received the tree info from chlid, it will add it to the buffer.

Node information contains the `friend_info` and the depth of the node relative to parent node in `check` command,
 node information is separated by colon.

```c
ChildList p = childlist;
while (p != NULL) {
    char buf[MAX_CMD_LEN];
    sprintf(buf, "subtree %d", depth + 1);
    if (write(p->writefd, buf, strlen(buf)) != strlen(buf))
        ERR_EXIT("error passing subtree to child");

    char inf[MAX_TREEINFO_LEN] = {0};
    if (read(p->readfd, inf, MAX_TREEINFO_LEN) == -1)
        ERR_EXIT("error receiving subtree info from child");
    fprintf(stderr, "%s receive subtree info from child = %d: %s\n", friend_info, p->pid, inf);
    bytes_printed += sprintf(info + bytes_printed, "%s", inf);
    p = p->next;
}
if (depth != 0 && bytes_printed > 0) {
    fprintf(stderr, "%s is sending back tree info back to parent\ninfo = %s\n", friend_info, info);
    if (write(PARENT_WRITE_FD, info, strlen(info)) != strlen(info)) ERR_EXIT("error sending subtree info to parent");
} else {
    // depth is 0, we need to decode and print (if param `print` is true)
}

```

Node that received the command `subtree [depth]` will recursively call the function `send_subtree_info` and pass in the param `depth` from command. At the leaf node, it will simply sent back the current node's `friend_info`.

At the root node (depth == 0), after it done receiving the tree infos of children, if `save` is not true, it will decode the infos and print to stdout, like such (comment will explain)

```c
if (save == 0) {  // we are root, decode shits and print
    fprintf(stderr, "check is decoding treeinfo = %s\n", info);
    // save nodes in a map of different levels
    char map[MAX_DEPTH][MAX_NODES][MAX_FRIEND_INFO_LEN] = {0};
    // maintain the count of nodes of each level
    int map_count[MAX_DEPTH] = {0};
    char* curr = strtok(info, ":");
    while (curr != NULL) {
        char curr_info[MAX_FRIEND_INFO_LEN]; int d;
        sscanf(curr, "%s %d", curr_info, &d);
        strcpy(map[d][map_count[d]++], curr_info);
        curr = strtok(NULL, ":");
    }
    // print out infos
    for (int i = 0; i < MAX_DEPTH; i++) {
        for (int j = 0; j < map_count[i]; j++) {
            fprintf(stdout, "%s%c", map[i][j], " \n"[j==map_count[i] - 1]);
        }
    }
} else { // we are root but don't print but save into savebuf
    strcpy(savebuf, info);
}
```

Since the command passing is pre-order, and a node will not pass the command to next chlid if current child is not finish, all nodes will garanteed to appear in tree info in the order of left-to-right. Combine with the level map, the result printed will be correct.

### Adopt

When the root (Not_Tako) received the command `Adopt [parent] [child]`, it first call a function `check_parent_in_child(parent, child)` and check the return value, this function will check if `parent` is a descendent of `chlid`. Returns 1 if true, 0 if false.

```c
int check_parent_in_child(char* parent, char* child);
```

The function will pass the command `Checkin [parent] [child]` recursively to its children and waits for their return status, stop when receiving `1` (found parent in chilld's tree), and then send status back to parent.

```c
ChildList p = childlist;
char msg = 0;
while (p != NULL) {
    char buf[MAX_CMD_LEN];
    sprintf(buf, "Checkin %s %s", parent, child);
    if (write(p->writefd, buf, strlen(buf)) != strlen(buf))
        ERR_EXIT("error passing checkin to child");

    // wait for child
    fprintf(stderr, "name = %s, waiting for child...\n", friend_info);
    if (read(p->readfd, &msg, 1) != 1)
        ERR_EXIT("error receiving checkin status from child");
    if (msg == 1)
        break;
    p = p->next;
}
if (!is_Not_Tako()) {
    if (write(PARENT_WRITE_FD, &msg, 1) != 1)
        ERR_EXIT("error telling parent checkin status");
}
return msg;
```

If current node's name is child's name in the `Checkin` command, it will call `send_subtree_info(0, 1, buf)` to get tree information of this node and save it into a buffer.

After that checking if parent's name is in this tree is pretty straight forward.

```c
if (strcmp(friend_name, child) == 0) {
    char buf[MAX_TREEINFO_LEN] = {0};
    send_subtree_info(0, 1, buf);
    // fprintf(stderr, "checkin treeinfo = %s\n", buf);
    char* ptrinfo;
    char* curr = strtok_r(buf, ":", &ptrinfo);
    int msg = 0;
    while (curr != NULL) {
        // parse and compare to parent name
        char* name = strtok(curr, "_");
        if (strcmp(parent, name) == 0) msg = 1;
        curr = strtok_r(NULL, ":", &ptrinfo);
    }
    // if (msg == 1) fprintf(stderr, "%s is in treeinfo\n", parent);

    if (!is_Not_Tako()) {
        if (write(PARENT_WRITE_FD, &msg, 1) != 1)
            ERR_EXIT("error telling parent checkin status");
    }
    return msg;
} else {
    // not child, pass command
}
```

Note that when checking if a name is in a given tree, we cannot use `strstr`, because if some parent is named `N` and child is named `NNN`, it will miss judge (`N` is in `NNN` but it may not be a descendent of `NNN`).

Back to `Adopt`, after checking if parent is not a descendent of chlid, we can finally call `adopt(parent, child)`.

The `adopt` function will, once again, recursively pass down the command `Adopt [parent] [child]` to its children and waits for the return status, and returns the status to its parent. The command passing will stop when the current node is the chlid (because parent under child is invalid).

Note that we only have two layout of parent and child:

1. Parent and chlid is in different trees
2. Parent and child is in same tree (child is descendent of parent)

So I use 2 bit to encode the layout into status code, set first bit when parent is in this tree, set second bit when child is in this tree, when status code is `0` this means neither parent nor child is in this tree.

If status code != `0`, we need to wait for them to finish adopting, so I have a `waitlist[2]` to save the fd of parent tree and chlid tree, parent in `[0]`, child in `[1]`.

```c
Child* deadchlid = NULL, *deadchildprev = NULL; // for killing purpose, will explain later
ChildList p = childlist, prev = NULL;
char msgs = 0, msg = -1;
int is_child = 0, is_parent = 0, waitlist[2] = {-1, -1};
if (strcmp(friend_name, parent) == 0) msgs += 1, is_parent = 1;
if (strcmp(friend_name, child) == 0) msgs += 2, is_child = 1;
while (p != NULL && !is_child) {
    char buf[MAX_CMD_LEN];
    sprintf(buf, "Adopt %s %s", parent, child);
    if (write(p->writefd, buf, strlen(buf)) != strlen(buf))
        ERR_EXIT("error passing adopt to child");

    // wait for child
    fprintf(stderr, "%s is waiting for child adopt status...\n", friend_info);
    if (read(p->readfd, &msg, 1) != 1)
        ERR_EXIT("error receiving adopt status from child");
    if (msg) {
        fprintf(stderr, "%s received child adopt status = %d\n", friend_info, msg);
        msgs += msg;
        if (msg == 1 || msg == 3) // parent
            waitlist[0] = p->readfd;
        if (msg == 2) { // child
            waitlist[1] = p->readfd;
            deadchlid = p, deadchildprev = prev; // will explain later
        }
    }
    if (msgs == 3) break;
    prev = p;
    p = p->next;
}
if (!is_Not_Tako()) { // send back status
    if (write(PARENT_WRITE_FD, &msgs, 1) != 1)
        ERR_EXIT("error telling parent adopt status");
}
```

If current node is parent or is child, we're going to open a FIFO.

The child will call `send_subtree_info(0, 1, buf)` to save its tree info into a buffer, and send the info through the FIFO. 

The parent will read from FIFO and get the tree info, and then unlinks (deletes) the FIFO.

```c
char buf[MAX_TREEINFO_LEN] = {0};
if (is_child || is_parent) {
    if (mkfifo(FIFO_NAME, 0666) == -1 && errno != EEXIST) ERR_EXIT("mkfifo error");

    fprintf(stderr, "%s is opening fifo to write...is_child = %d, is_parent = %d\n", friend_info, is_child, is_parent);
    if (is_parent) {
        int read_fd;
        if ((read_fd = open(FIFO_NAME, O_RDONLY)) == -1) ERR_EXIT("open read fifo error");
        if (read(read_fd, buf, MAX_TREEINFO_LEN) == -1) ERR_EXIT("read fifo error");

        fprintf(stderr, "%s read info from fifo = %s\n", friend_info, buf);

        close(read_fd);
        if (unlink(FIFO_NAME) == -1) ERR_EXIT("unlink fifo");
    } else if (is_child) {
        int write_fd;
        if ((write_fd = open(FIFO_NAME, O_WRONLY)) == -1) ERR_EXIT("open write fifo error");

        fprintf(stderr, "Getting tree info of %s...\n", child);
        send_subtree_info(0, 1, buf);
        fprintf(stderr, "Got tree info of %s\n", buf);

        fprintf(stderr, "%s is sending treeinfo through fifo...\n", friend_info);
        if (write(write_fd, buf, strlen(buf)) != strlen(buf)) ERR_EXIT("write fifo error");
        close(write_fd);
    }
}
```

And then the parent will decode the tree info into another map, taking advantage of pre-order traversal again, this time we wanna maintain the latest node of each level (it will always be the parent of the newest node in the next level).

Also don't forget to mod the new `friend_value`.

As for child, we just need to die, I have a function `kill_myself()` that recursively kills all of the descendents and then self, and sends back suicide signal (msg = 2).

```c
if (is_parent) {
    // decode to a map
    fprintf(stderr, "%s is decoding buf = %s\n", friend_info, buf);
    // maintain newest parent of each level
    char map[MAX_DEPTH][MAX_NODES][MAX_FRIEND_INFO_LEN] = {0};
    int newest_parent[MAX_DEPTH]; for (int i = 0; i < MAX_DEPTH; i++) newest_parent[i] = -1;
    char* ptrinfo;
    char* curr = strtok_r(buf, ":", &ptrinfo);
    while (curr != NULL) {
        char curr_info[MAX_FRIEND_INFO_LEN]; int d, new_value = -1;
        sscanf(curr, "%s %d", curr_info, &d);
        fprintf(stderr, "   old friend_info = %s\n", curr_info);

        char* name, *value, new_info[MAX_FRIEND_INFO_LEN] = {0};
        name = strtok(curr_info, "_"), value = strtok(NULL, "_");
        new_value = atoi(value) % friend_value;
        sprintf(new_info, "%s_%02d", name, new_value);
        fprintf(stderr, "   new friend_info = %s\n", new_info);

        char* new_parent;
        if (d == 0) new_parent = parent; // at depth 0, the parent is the [parent] of adopt
        else {
            new_parent = map[d - 1][newest_parent[d - 1]]; // else the parent will be the latest node of previous level
        }
        strcpy(map[d][++newest_parent[d]], curr_info);
        fprintf(stderr, "%s is meeting %s...\n", new_parent, new_info);
        meet(new_parent, new_info, 0);

        curr = strtok_r(NULL, ":", &ptrinfo);
    }
}
if (is_child) {
    kill_myself(); // this will send back msg = 2
}
```

If the curent node is not parent nor chlid, but has either parent or child as their descendent, we need to wait for the finish adopting signal. Here I use `1` as adopt succeeded (should be send by parent), `2` as the child is dead (should be send by child).

if signal is `2`, the child is dead and we need to clean up their resourses, that's why I save `deadchild` and `deadchildprev`. I have a function `clean_child()` that calls `waitpid` on the child, close its fds and then free it.

```c
char c = -1;
if (waitlist[0] != -1) { // has parent in subtree
                         // fprintf(stderr, "%s is waiting parent to finish adopting...\n", friend_info);
    if (read(waitlist[0], &c, 1) != 1) ERR_EXIT("error waiting parent finish adopt"); // 1 for success
    fprintf(stderr, "%s received parent finish adopting\n", friend_info);
}
if (waitlist[1] != -1) { // has child in subtree
                         // 1 for success, 2 for direct child needs cleaning (he died)
    if (read(waitlist[1], &c, 1) != 1) ERR_EXIT("error waiting child finish adopt");
    fprintf(stderr, "%s received child adopting c = %d\n", friend_info, c);
    if (c == 2) {
        fprintf(stderr, "%s received child is killing himself\n", friend_info);
        if (deadchildprev == NULL) childlist = deadchlid->next;
        else deadchildprev->next = deadchlid->next;
        clean_child(deadchlid);
    } else if (c == 1) fprintf(stderr, "%s received child done reaping\n", friend_info);
}
```

If the current node is not parent nor child and does not have parent or child as their descendent, we simply return (because the parent is not waiting for any signal).

If current node is `Not_Tako`, we print_success_adopt.

```c
if (waitlist[0] == -1 && waitlist[1] == -1 && !(is_child || is_parent)) return; // unrelated people just return
if (is_Not_Tako()) {
    print_success_adopt(parent, child);
} else {
    c = 1;
    // fprintf(stderr, "%s is telling parent we're done adopting...\n", friend_info);
    if (write(PARENT_WRITE_FD, &c, 1) != 1) ERR_EXIT("error telling parent we're done adopting");
    fprintf(stderr, "%s told parent we've done adopting\n", friend_info);
}
```