# PD1 Homework11

## DeadLine: 12/28 23:59:59

## Submission

- Login the system by your personal account. (Use the ssh command)
- Create an directory with name “HW11” in your home directory.
- You can use the “pwd” command to confirm your current directory.
- The “mkdir [name]” command can create a directory with the name
[name]
- In HW11 directory, you need to create 1 files with name “hw11.c”
- You need to compile your program by yourself, and create 1 executable files with the filenames “hw11”
- gcc hw11.c -o hw11

## General Goals
- read file
- linked list
- analyze clock cycles
### Total: 100 points

| Task | Score | Note |
| -------- | -------- |-------- |
| hw11.c | 50 | Submit on server |
| report average numbers of clock | 50 | Submit on Moodle|

## Data file
1. Routing_table
2. inserted_prefixes
3. delete_prefixes
4. trace_file
## Readme
※clock.c為計算clock的function使用範例

在input中包含一些prefix是沒有length的
x.0.0.0 這種prefix表示length是8
x.y.0.0 length是16
x.y.z.0 lenght是24
x.y.z.w length是32

In the input file，some of the prefix has no length means that
x.0.0.0 is of length 8,
x.y.0.0 is of length 16,
x.y.z.0 is of length 24,
x.y.z.w is of length 32
## IP address
* The first part `a.b.c.d` is a 32-bit IP address. `a.b.c.d` are decimal numbers which can be expressed as 8 bits binary numbers.

Prefix/length  binary format (* = mask = don’t care)
10.0.0.0/8	00001010  *
9.1.0.0/16	00001001  00000001  *
8.2.3.0/24	00001000  00000010  00000011  *
1.2.3.240/28	00000001  00000010  00000011  1111*

## Function
### Function1 input(..)
* write a function input(..) to read all the prefixes from the input file.
### Function2 length_distribution(..)
* write a function length_distribution(..) to compute the number of prefixes with prefix length i, for i = 0 to 32.
* For example:

1.0.0.0/8
2.0.0.0/8
4.1.18.0/24
4.2.62.0/24
4.2.124.0/24
4.2.124.0/22
4.6.0.0/22
4.6.0.0/16

the number of prefixes with prefix length 8 = 2
the number of prefixes with prefix length 16 = 1
the number of prefixes with prefix length 22 = 2
the number of prefixes with prefix length 24 = 3

### Function3 segment(..)
* Assume d >= 8.
* write a function segment(int d) to divide the prefixes of length >= d into 2^d groups such that the prefixes in the same group have the same first d bits.
* the prefix of length < d are put in a special group.
* For example:

10.0.0.0/8	00001010  *
10.1.1.1/16	00001010  00000001  *
9.1.0.0/16	00001001  00000001  *
9.2.0.0/8	00001001  *
8.2.3.0/24	00001000  00000010  00000011  *
1.2.3.240/28	00000001  00000010  00000011  1111*

| 00000000 | 
| 00000001 | ---> | 1.2.3.240 |
|    :     |
| 00001000 | ---> | 8.2.3.0 |
| 00001001 | ---> | 9.1.0.0 | ---> | 9.2.0.0 |
|    :     |
| 00001010 | ---> | 10.0.0.0 | ---> | 10.1.1.1 |
| 00001011 |
|    :     |
| 11111110 |
| 11111111 |

## Output Format
1. print out the total number of prefixes in the input file.
2. printout the number of prefixes in group i for i = 0 to 2^d^ – 1.

The total number of prefixes in the input file is : %d.
The number of prefixes in group 0 = %d.
The number of prefixes in group 1 = %d.
                           .
                           .
                           .
The number of prefixes in group 2^d-1 = %d.

## Execution Command

./hw11 /share/HW11/routing_table.txt /share/HW11/inserted_prefixes.txt /share/HW11/delete_prefixes.txt /share/HW11/trace_file.txt 8

- The first argument is the path of the routing_table file.
- The second argument is the path of the inserted_prefixes file.
- The third argument is the path of the delete_prefixes file.
- The fourth argument is the path of the trace_file file.
- The fifth argument is d.

You need to use argc and argv to obtain the file path, and then read the data using fopen.

Recommend using `hw11` command to check whether the output of your code is correct.

:::warning
### Notice

Print out the number of prefixes in the group before performing insert and delete operations.
:::
### Function4 prefix_insert(..)
* write a function prefix_insert() to insert a prefix in a one-by-one fashion in the increasing order of the unsigned numbers of the prefixes. A file named inserted_prefixes contains some prefixes that will be inserted after the segments are built from the file routing_table.
### Function5 prefix_delete(..)
* write a function prefix_delete() to delete a prefix. The prefixes to be deleted after inserting all the prefixes from files routing_table and inserted_prefixes are from a file called deleted_prefixes.
### Function6 search(..)
* write a function search() by giving an IP address to report if the search is successful or failed. The IP addresses to be searched are contained in a file called trace_file.

## Clock.c
* you have to report average numbers of clock cycles to perform a search, an insertion, or a deletion and draw three figures as follows. How to measure the search/insertion/deletion in cycles is illustruated in clock.c.
* three figures: insertion, deletion, and search
* Please upload these three figures to Moodle.