CSE 330 - Operating Systems Project #1

Overview:

For this project you are to write routines that perform standard queuing functions. The functions work on multiple queues, and structure each queue as a doubly linked, circular list (without the header/dummy element).

Data Structures:

A queue consists of a head-pointer and a set of q-elements. A q-element is a structure, consisting of a prev and next pointer, and a payload consisting of 1 integer.

The queue must be a circular doubly linked consisting of q-elements. The header is a pointer to the first element of the queue. The header is null if the q is empty.

See the figure for a better explanation. In this figure, the Q contains 4 elements, numbered 1, 2, 3, 4. 1 is at the head (added first).

Functions:

The functions that you implement are:

1. item = NewItem(); // returns a pointer to a new q-element

2. InitQueue( &head) // creates an empty queue, pointed to by the variable head.

3. AddQueue(&head, item) // adds a queue item, pointed to by item, to the queue pointed to by head.

4. item = DelQueue(&head) // deletes an item from head and returns a pointer to the deleted item. If this is the last element..

5. RotateQ(&head) // Moves the header pointer to the next element in the queue. This is equivalent to AddQ(&head, DeleteQ(&head)), but is simpler to use and more efficient to implement.

Note: All the routines work on pointers. They do not copy q-elements. Also they do not allocate/deallocate space (except NewItem()). You may choose to implement a FreeItem(item) function optional.

Implementation:

The routines should be implemented in C under the Linux operating system. If you are not familiar with Linux and/or do not have it installed. Please use an Ubuntu Virtual Machine. For more details/questions post requests on the discussion board.

All the above routines and data structures are to be placed in 1 file, called q.h. Do not include other files into this file. The test routines can be in proj-1.c and this will include q.h and other standard header files.

Note: Please add the following two lines to the q.h file for some complex compatibility reasons:

#include

#define _GNU_SOURCE

Testing

Write test routines that thoroughly test the queue implementation. Write a print routine that takes a head pointer and prints all the values of the payload field of the queue.

Use multiple queues. Pay special attention to deleting the last element of a q. One suggested test case: Add three elements to queue Q1, and then add 3 more to queue Q2. Delete elements from each q, one by one and print values till the queues are empty. Also, print the contents of the queues at each step. Make sure the Qs are empty. Repeat the above test again.

Further warning: Bugs in the Q routines have been the #1 cause for strange errors in the project, always.

Submission and Grading:

SUBMIT

Your project must consist of 2 files. (Usage of C is encouraged but if you use C++ the instructions would be similar)

1. q.h -- the functions defined above should be here, both definitions and body of the functions.

2. proj_1.c (to test q.h)

Make sure the compile command, gcc proj_1.c does the correct

compilation.

The two files are to be ZIPPED into one zip or gzip file. The name of this file should reflect the name(s) of the people submitting (abbreviated, do not make it too long).

Upload to canvas. Make sure your names are in comments in your code.

Note: Grading will be done on Ubuntu. The entire project has already been tested for compatibility on Redhat (general), Ubuntu 18 and earlier, and the same code works.