Outline#

  • Deadline: 16 August 2024, 11:59 pm
  • Assessment template: link
  • Specification: keep reading 🙂
  • Weighting: 5%
  • Marked out of: _ / 5

Time Until Deadline (16 August 2024, 11:59 pm):#

...

Rules and Policies#

  • this is an individual assessment task, ensure you fork your repo as private fork guide
  • you may re-use code from your labs
  • late submission is not permitted without an extension

Introduction#

Complete src/books.c to the following specifications.

Your task is to write a program in C that reads in data and commands from stdin to build a book library. The file src/books.c contains some template code for you to complete to the following specification.

The data received from stdin consists of commands to process.

Provided Functions#

You are provided the following functions already implemented:

  • flush_buffer()
    • flushes the buffer until it hits a \n character (and consumes it)
    • useful to remove leftovers by a scanf call before using a fgets call
  • new_line_to_null_termination(char *text)
    • turns the first new line character into a null termination character in a char*, starting from the character pointed to by the text.
    • useful to ensure that the first newline character is turned into a null termination

Required to Implement#

You will need to complete the following functions:

  • book_entry *find_entry(unsigned int id)
    • This function will return a pointer to the first entry in the linked list with the matching id. If the given id is not in the linked list, it should return NULL.
  • void insert_entry(book_entry *book)
    • This function will need to insert a newly-created book at the end of the linked list.
  • void delete_entry(book_entry *book);
    • This function will remove the book entry book from the linked list and free any memory it is using.
  • void print_book(book_entry *book);
    • This function will print the values of the given book entry.
  • void print_all(void);
    • This function will print every book in the linked list, starting at the head. The head is stored in the global variable HEAD.
  • book_entry *read_entry_input(void);
    • This function will read input from stdin and create a new book_entry to be added to the linked list.
  • size_t book_size(book_entry *entry);
    • This function will return the total size in bytes of the book_entry and all of it’s associated data.

More detail on each of these functions and the commands that should invoke them are given below.

You are free to implement any additional helper functions you may need.

Doubly Linked Lists#

Your program will read data from stdin to add book entries to the doubly linked list, starting off by inserting the first book at HEAD and then inserting each following book after the previous one.

You created a singly linked list in Lab 2. If you have not completed this task, we recommend completing it before starting this checkpoint.

In a singly linked list each element has a pointer (next) to the next element in the list. In a doubly linked list each element also has a pointer prev to the previous element. This simplifies several operations on a linked list.

For example, a doubly linked list with three elements will look as follows:

Doubly Linked List Example

Your task for this checkpoint is to populate a linked list with book data.

Book Struct#

The nodes of your linked list is a book_entry struct, already defined for you in books.c. This struct contains the following information:

  • id: An unsigned int id, representing the unique id of the book. You are not required to ensure the uniqueness of this value.
  • title: A char * that points to a dynamically allocated variable length string representing the title of the book.
  • author: A char * that points to a dynamically allocated variable length string representing the author of the book.
  • blurb: A char * that points to a dynamically allocated variable length string representing a summary of the book.
  • price: A double representing the price of the book.
  • prev: A pointer to the previous book in the linked list (NULL if it does not exist).
  • next: A pointer to the next book in the linked list (NULL if it does not exist).

Main Program Loop#

Your program will need to read in commands from stdin in a loop, until it reaches the “end of file/input” indicator. Each line of input will either be a command name followed by zero or more arguments, or an INSERT command followed by lines dictating the values of a new book entry to insert into the list.

There are several commands you will need to implement. Each of these commands has a command name and will take either 0, 1, or 2 unsigned integer arguments, representing the id(s) of the book entry(s) to operate on. INSERT and PRINT_ALL will take no identifier.

This is a summary of the different commands you need to implement:

Command Action
INSERT Reading the fields from stdin, insert this entry into the list.
PRINT id Print the book entry using the print_book function.
PRINT_ALL Print all book entries in the list in order.
PRINT_SIZE id Print the size in bytes of all data associated with this book entry.
DELETE id Delete this book entry.
SWAP id1 id2 Swap the position of two items in the list.

Each of these commands are described in more detail below. If your program receives an invalid command (e.g. any string that isn’t one of the listed command names) you should perform no action on the linked list.

Think about the appropriate format specifiers you should use with scanf to be able to read in each command.

Once you have used scanf to get the name of the command you should perform, you can use strcmp (included in the string.h header file) to determine which function(s) you will need to call.

Insert#

The insert command inserts a new book entry to the end of the list. The fields of the book entry are entered into stdin after the INSERT command, using the specific format described below.

When processing an insert command you will need to use malloc to reserve enough space for:

  1. The book_entry struct itself.
  2. The title string
  3. The author string
  4. The blurb string

If a call to malloc fails, you should print an appropriate error message and call exit(1) to terminate your program.

You will need to complete:

  1. The read_entry_input function, which will read from stdin and return a pointer to a new book_entry struct with the fields set to the correct values.

  2. The insert_entry function, which should insert the book_entry into the linked list. If the linked list is currently empty (i.e. HEAD is NULL), you will need to update HEAD as well.

Insert Format#

The lines following an “INSERT” command are ordered as follows:

  1. The book id, followed by a newline.
  2. The number of characters in the title, followed by a newline. You should use this number to determine how many bytes you need to request from malloc for the title string.
  3. The book title string, followed by a newline.
  4. The number of characters in the author’s name, followed by a newline. You should use this number to determine how many bytes you need to request from malloc for the author string.
  5. The author string, followed by a newline.
  6. The number of characters in the blurb, followed by a newline. You should use this number to determine how many bytes you need to request from malloc for the blurb string.
  7. The blurb string, followed by a newline.
  8. The price, followed by a newline. HINT: You should use the %lg format specifier to parse and print the price string.

Keep in mind that the specified string lengths do not include the final newline, and when allocating space for the three dynamically allocated strings you need to include space for the null terminator.

Your title, author and blurb inputs will involve spaces. This means that scanf isn’t going to work! For the title and author, you can use the fgets function. For the blurb, you will have to determine a way to read n characters from stdin that preserves whitespace characters.

You may assume that the number of characters specified for a field in this format is correct. This means you will not need to handle cases where an INSERT command specifies a title length of 20 but enters 50 characters on the following line, for example. Similarly, you may assume that the id and price entered are a valid unsigned int and double, respectively.

An example of the format is illustrated as below:

Insert Format

If you have correctly parsed the input, the fields of the resulting struct will look like this:

Insert Format

Write code in your main loop to process INSERT commands, and complete the read_entry_input and insert_entry functions.

On Windows devices, there may be potential issues with line endings. See later in the Testing section for advice.

Print#

The PRINT command takes an unsigned integer id. The first book entry in the linked list with a matching id should be printed in the following format:

ID: _
  - TITLE: _
  - AUTHOR: _
  - BLURB: _
  - PRICE: _
  - NEXT: X
  - PREV: Y

Where:

  1. Each _ is replaced by the book entry’s data.
  2. X and Y are the id’s of the previous and next book entries, or NULL if they do not exist.

Complete the print_book function, and add code to your main loop to process PRINT commands.

The PRINT_ALL command is similar to the PRINT command, but will print every entry in linked list, starting at the HEAD.

Complete the print_all function, and add code to your main loop to process PRINT_ALL commands.

This will be easy to implement once you have implemented the print_book function — you will simply need to iterate through the linked list and call print_book on each item.

The PRINT_SIZE command takes an unsigned integer id. The first book entry in the linked list with a matching id should have it’s total size printed to stdout. The total size is defined as:

  1. The memory used by the book_entry struct itself.
  2. The total size used by the title, author and blurb strings, including the null termination character.

Remember you can use sizeof to find the size of a struct. Try and think of a way to get the length of the dynamically allocated strings.

Complete the print_size function, and add code to your main loop to process PRINT_SIZE commands.

If there is no book entry with a matching id, you should not print anything.

Delete#

The DELETE command takes an unsigned integer id. The first book entry in the linked list with a matching id should be removed from the linked list, and all dynamically allocated memory used to create the entry should be free‘d. If there is no book entry with a matching id, no changes to the linked list should be made.

Recall that singly linked list delete involved changing the previous node’s next pointer to skip past the item, then freeing it. Having a doubly linked list makes navigating to the previous node easier, but also means deleting the node requires updating the next node’s prev pointer too. See the below diagram for a an example where the second entry is deleted.

Deletion Example Deletion Example

Also note:

  • Deleting the head of the linked list will require updating the HEAD variable as well.
  • Deleting an item that doesn’t exist does nothing.

Complete the delete_entry function, and add code to your main loop to process DELETE commands. Remember to free any memory used by node you are deleting!

Swap#

The SWAP command takes two unsigned integers id1 and id2. The first book entries matching each ID should have their positions swapped in the list. If either id1 or id2 are not present, no changes to the list should occur.

As an example, here is the state of the linked list before and after executing the command “SWAP 78 1234”

Before a "SWAP 78 1234" command

After a "SWAP 78 1234" command

There are different ways of implementing swap. One way is to update both node’s prev and next pointers. Another way is to preserve both node’s prev and next pointers and instead swap the individual fields of the struct. It is up to you to choose how you implement the swap_entry function.

Complete the swap_entry function, and add code to your main loop to process SWAP commands.

Testing Your Code#

You can test your program locally using text files present in the tests directory like so:

./books < tests/test-1-input.txt

The < tests/test-1-input.txt part of this command will treat the contents of test-1-input.txt as if you had typed them in manually yourself.

You can verify your program’s output by comparing each test-X-input.txt with the corresponding test-X-output.txt file in the same directory. Rather than comparing manually, you can redirect your program’s stdout to another file, and compare them using cmp or diff.

./books < tests/test-1-input.txt > output 2>&1
diff output tests/test-1-output.txt

The > output part of the command will create a file named output and write the contents of stdout to it. The 2>&1 part of the command will combine stderr into stdout and write it to output as well.

Note that passing these five tests does not mean your implementation is correct. There may be additional edge cases or aspects of this specification they do not cover. It is a good idea to consider writing additional test cases yourself!

Marking#

Your code will be entirely auto-marked based on two sets of tests:

  1. The five test cases provided in the CI. The input used for these five test cases are the same as the tests you are given to run locally.
  2. Additional test cases not provided to you, to both verify that you have read this specification carefully and have not hardcoded the intended behaviour.

Each of the five test cases present in the CI will award 0.5 marks for passing, and 0 for failing.

Depending on the specifics of your machine, it may be the case that test cases which pass locally fail on the CI. Therefore it is very important that you check the CI results of your checkpoint, as failing tests will not be awarded partial marks.

Hints#

If you’ve read the above and feel like you have no idea where to start, we offer the following advice:

  1. Complete the “Linked List With Dynamic Memory” exercise from Lab 2. This exercise will teach you how to use dynamic memory, how to build a singly linked list and how to process commands entered in via stdin.
  2. Focus on one task at a time! It will be much easier to handle the trickier commands once you have ensured you are reading the input data correctly. We recommend the following order to get started:
    1. Complete the print_book function. Re-read the printf section from Lab 1 for a refresher on the different format specifiers you will need to use.
    2. Complete the print_all function. Once you have completed print_book, this will be a simple matter of iterating through the linked list starting at HEAD and calling print_book on each entry.
    3. Complete the read_book_data function. Make sure you pay close attention to the specification of how this data is fed into the program.
    4. Add the code to your main loop to process the INSERT and PRINT_ALL commands.

    After this, you can verify you are processing the input data correctly by running test-1 - this will only insert a single book entry to the linked list before requesting the entire list be printed.

    You should then tackle the remaining commands in order of easiest to hardest. Which command you consider “easiest” will be subjective, but we recommend the following order:

    1. PRINT_SIZE
    2. DELETE
    3. SWAP

  3. Use helper functions to avoid having repetitive code. You will notice that many of the commands will involve looking for an entry in the linked list with a matching id - you should implement and re-use the find_entry function, rather than doing this separately for each command.

  4. Use a debugger!

  5. Push your work to GitLab frequently - this will help you determine whether your is correct and a great way to ensure you can still submit something if you encounter any last-minute Git issues.

Common Bugs#

If you are using Windows, be aware of the potential issues that arise from different line endings. If you open the test input files in Windows it will potentially modify the length of each line, causing your program to expect each line to contain an inaccurate number of characters. Read the linked page for advice on how to avoid this issue.

Completion Checklist#

  • you have completed the code in the files provided and have not renamed or moved them
  • you have run your files against local test(s) and they pass successfully
  • you have created your own tests for your files and they pass successfully
  • you have saved, committed and pushed your files to gitlab
  • you have filled out, committed, and pushed your statement of originality
  • you have checked the gitlab ci tests, and they are passing

The instructions for checking the results of the CI are identical to those from Lab 1.

GitLab CI Job Status

FAQ#

My code don’t work, can I email you for help?#

Sorry, you won’t get help over email or Teams. We provide a course forum which is the only way we are able to help outside of labs.

Forum posts related to your assessment submission must be “private” if they contain code or other sensitive information (as for any individual assessment task).

It’s [5 minutes, 60 minutes, 12 hours] before the deadline and my CI Jobs aren’t finishing!#

Unfortunately on the day that an assessment is due, when many students are pushing updates at once, the CI servers can’t keep up. You may not see your CI jobs finish before the deadline. You will just have to manually check that your files have been submitted correctly and that you are passing tests locally.

The best way to avoid this issue is to start early and finish early 😇

If there’s any issues with your git repository, please let us know through a private forum post and there may be something we can do.

How do I know my assessment has been submitted?#

If:

  1. the files in your fork of the assessment are correct (i.e., the files you intend to submit) when checking on the gitlab website
  2. the time is before the deadline

then your assessment has been submitted (well done!).

Please don’t ask us to “check”, we would be just doing exactly the same thing as the above steps which you can do yourself.

bars search times