# 2019q1 Homework1 (lab0)
contributed by < `tfliao` >

## Environment

$ uname -a
Linux debian 4.9.0-7-amd64 #1 SMP Debian 4.9.110-3+deb9u2 (2018-08-13) x86_64 GNU/Linux

## Requirement
Implement queue using singly linked-list, each queue element stores a C string, support new, free, two different push (FIFO and LIFO), pop, size, and reverse. All operations except free and reverse must in constant time O(1).

## Implementation
### Data Structure
To achieve Constant push() and size(), we need to add two extra variables in `queue_t`, a pointer to last element and size_t store number of element in queue.
### Details
Two extra functions to manage `list_ele_t`.
* list_ele_t *alloc_ele(char *s);
* Since we have two push function, extract `list_ele_t` allocation can reduce maintenance efforts.
* This functiona will allocate element and copy string, and clear everything if any failure.
* void free_ele(list_ele_t *node);
* Also, both pop and free need to free element, thus we extract this function.

About maintaining the pointer to first and last element, we need explicitly handle the case of empty queue when pushing element, or poping last element in queue.

## How auto grade system works
According to Makefile, `make test` will build qtest and run driver.py under scripts folder.
In driver.py, it will run `./qtest -v <verbLevel> -f <testscript>` on each testscript under tests/

### Magic in qtest
#### Harness on standard libraries
In `queue.c`, it include `harness.h`, without INTERNAL defined, it will replace `malloc`, `free`, `strdup` to another version for deep inspection.
* test_malloc
1. Reject malloc if in `noallocate_mode`
2. Allocate failure with probability
3. Allocate extra memory before and after size it requested, poison them to check memory leak and double free.
* test_free
1. Reject free if in `noallocate_mode`
2. If free a NULL pointer, perform no operation.
3. Check header/footer, alarm if footer incorrect.
* test_strdup
* Replacing this function is to avoid strdup bypass test_malloc checks.
#### Use signal to catch Time Limit Exceeded case
* define of signal handler
* In function `queue_init`, `qtest` setup signal handler for `SIGSEGV` and `SIGALRM`.
* `SIGSEGV` will be triggerred when invalid memeory segment is accessed.
* `SIGALRM` will be triggerred by [`alarm(2)`](http://man7.org/linux/man-pages/man2/alarm.2.html), which trigger `SIGALRM` after given timeout.
* setup time limit before queue function call
* In `harness.c`, `exception_setup` set time limit using `alarm(2)`, if next operation doesn't complete before timeout, `SIGALRM` will be triggerred. besides, a jump tag is set here using [`sigsetjmp(3)`](https://linux.die.net/man/3/sigsetjmp).
* In case of `SIGSEGV` or `SIGALRM` triggerred, our custom signal handler pass error message through `trigger_exception()`, use long jump to the jump tag we set in `exception_setup()`.