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), 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).
  • 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().