Lab03 - Linked Lists and Project01

Deliverables due Tue Feb 18 by 11:59pm in your Lab03 GitHub repo

• A copy of xv6 with a linked list implementations that pass the Lab02 Autograder tests
  • The sort command
  • The tail command
• Note that because you will doing Lab02 work in your Project01 repo you will to run the tests like this:

  $ grade test -p lab03
  

• Passing the first test of Project01
• You source code should conform to xv6 formatting conventions.
  • You can use uncrustify to help automate formatting
  • https://github.com/uncrustify/uncrustify
  • VS Code Extension for Uncrustify
  • Here is an Uncrustify config file for xv6: xv6-format.cfg
• Your solutions should pass the autograder tests
• I will provide a starter repo with some added files and a script for the autograder
• Use can use Aider, Roo Code, and other coding assistants, but your are responsible for understand any code you submit. You are also responsible for understanding the existing code you modify.

sort

You need to reimplement the sort command using the linked list implementation provided in the starter code (list.h and list.c). Your implementation should use the list_sort() function.

tail

The tail command is the opposite of the head command. It prints the last count lines of a file or stdin, where count is 10 by default:

$ tail README
(kaashoek,rtm@mit.edu).  The main purpose of xv6 is as a teaching
operating system for MIT's 6.1810, so we are more interested in
simplifications and clarifications than new features.

BUILDING AND RUNNING XV6

You will need a RISC-V "newlib" tool chain from
https://github.com/riscv/riscv-gnu-toolchain, and qemu compiled for
riscv64-softmmu.  Once they are installed, and in your shell
search path, you can run "make qemu".
$

Tail can also read from stdin and accept the option -n count to print the last count lines:

$ cat README | tail -n 3
https://github.com/riscv/riscv-gnu-toolchain, and qemu compiled for
riscv64-softmmu.  Once they are installed, and in your shell
search path, you can run "make qemu".
$

You are required to use the provided linked list implementation for you tail.c soluiton. You can start with your Lab02 sort.c implementation. The basic idea is the following:

• Read each line of the file one at a time
• Create a list of count lines
  • That is, once you have read count, adding the next line will remove the first line from the list
• At the end of reading all the lines in the file you end up with a list of count lines or less (in the case where the file has less than count lines)
• Print the resulting list
• Free all the elements of the list

Note that a real implementation of tail would not need to read every line in the file in order to print the last count lines. Instead, real Unix/Linux kernels support an lseek() function that can move the file position to the end and then read backward to find the last count lines. We will examine how to add support for this to xv6 later in the semester.