Operating Systems Project 1 C Programming and Makefile

Introduction

The purpose of this project is to refresh your C programming skills, using command line, and writing a Makefile.

You must do this assignment by yourself (and members of your team if you have a team). You may discuss the problem or solutions with your classmates or instructor, but you may not share code with anyone. You may not directly use code from the Internet. Please read all instructions carefully, and don’t wait till last minute to work on projects.

Project submission

For each project, please create a zip file containing the following items, and submit it to Canvas.

    1. A report called README.txt that includes (1) the (printed) full names of the project members, and the statement: We have neither given nor received unauthorized assis-tance on this work; (2) the directory and name of your virtual machine (VM), and the password for the account (regular user or root account) that can successfully run your code; and (3) a brief description about how you solved the problems and what you learned (more details on page 4).

    2. Your source code and Makefile: please do not include compiled output. Even though you have your code in your VM, submitting code in Canvas will provide a backup if we have issues accessing your VM.

Project

Part 0: Preparation

First, Update and Reboot

After you successfully installed CentOS 7, and logged into your new VM, first run the following command as root (note that the # prompt indicates that the command requires

1


root privilege. $ indicates regular user privilege):

# yum update -y

If you don’t include the “-y” option, then make sure to read the messages on the screen. If it asks something like “Total size 747M, is this ok [y/d/N]?” Make sure to type “y” and hit enter. If you just hit enter, it won’t update at all. When it’s updating, it will take a


while so feel free to take a  break.

After update is complete, please reboot the VM by typing reboot or click the UI to reboot, and log into the newer version. You will see a new option at boot time (you will only see it after yum update and reboot), and go ahead to select the new one (should be chosen by default):








Once logged in, you can verify the kernel version using the following command (either as root or normal user):


    • uname -r

You should see the exact string, e.g., 3.10.0-1160.76.1.el7.x86 64 as the version you choose at boot time.1


Second, Install Tools

Install some development tools like the compiler gcc by running this command as root:

# yum install -y gcc ncurses-devel make wget perl

Now your environment should be ready to go. Before going forward, please find the following resources that you may find useful:

    1. If you need some help with C, you should definitely check out http://cslibrary. stanford.edu/ especially “Essential C”, “Pointers and Memory”, “Linked List Ba-sics”, and “Linked List Problems”. If you need help with using *nix for software development then you should go through the “Unix Programming Tools”.

    2. Some helpful C functions are strlen, strncmp, printf, strncpy, strdup, malloc, free (man these functions on command line or Google if necessary. Pay attention to return values.)

    3. Makefile tutorial: https://www.cs.colby.edu/maxwell/courses/tutorials/maketutor/

Part 1: Writing C Code (60 points)

Create a linked list data structure in C, where each node in the list stores a character string called item, and a pointer called next pointing to the next node in the list (line 2 – 7 in the code below). Use a header file (list.h) and separate source file (list.c) for all functions, and make a test filelist test.c that tests your list implementation.


You need to implement all the functions listed in the snippet below, as well as define the struct(s) necessary for your list to work correctly. Note:


    • If you updated to a newer version than this figure above, you will be fine. Just make sure you choose the newest version, and uname -r shows the same version as the one you choose at boot time.

2

    1. Please do not use arrays, and do not declare arrays.

    2. Please do not use functions from the C++ Standard Template Library, i.e., you should implement the following functions by yourself. Do not use cin or cout.


    3. You will lose points of you change the struct or function definition shown below.

1
/∗  D e c l a r i n g  a l l  t h e  s t r u c t s  ∗/
2
t y p e d e f
s t r u c t  Node  node ;
3

Node {
4
s t r u c t


    • c h a r  ∗ item ;
    • node  ∗ next ;

    • } ;

8

9    t y p e d e f    s t r u c t    L i s t  {
    10 node  ∗ head ;

    11 }  l i s t ;

12
























13
/∗
A l l o c a t e
s p a c e
f o r
a
new
l i s t
and
s e t
i t s
head  t o NULL.




14
∗
Returns
t h e
c r e a t e d
l i s t
i f
s u c c e s s f u l ,
NULL
o t h e r w i s e .
∗/



15
l i s t ∗  c r e a t e  l i s t (  ) ;


















16
























17
/∗
A l l o c a t e s
a
new node
and
c o p i e s  t h e
s t r i n g
from
item
t o
t h i s
node

18
∗
( u s e  malloc ,
s t r l e n ,
and  s t r n c p y ;
o r
t r y
s t r d u p ) .  Adds  t h i s
new
node
19
∗
t o  end  o f
t h e
l i s t
l l .
Returns
0
i f
s u c c e s s f u l ,
non−z e r o
o t h e r w i s e .  ∗/
20
i n t
a d d  t o
l i s t ( l i s t ∗
l l ,
c h a r ∗
item ) ;











21
























22
/∗
Removes  t h e  head  o f
t h e
l i s t
l l ,
e x t r a c t s
t h e  s t r i n g
s t o r e d
i n
t h e
head ,
23
∗
and  r e t u r n s
a  p o i n t e r
t o
t h i s  s t r i n g .
Also
f r e e s
t h e
removed
head
node .  ∗/
24
c h a r ∗  r e m o v e f r o m l i s t ( l i s t ∗  l l ) ;













25
























26
/∗
P r i n t s  e v e r y
s t r i n g
i n
each
node
o f
t h e
l i s t
l l ,
with  a
new
l i n e

27
∗
c h a r a c t e r
a t
t h e  end
o f
each
s t r i n g
∗/










28
v o i d  p r i n t  l i s t ( l i s t  ∗ l l ) ;















29
























30
/∗
F l u s h e s
( c l e a r s )  t h e
e n t i r e
l i s t
and
re− i n i t i a l i z e s
t h e
l i s t .  The
p a s s e d
31
∗
p o i n t e r
l l
s h o u l d
s t i l l
p o i n t
t o
a  v a l i d ,
empty
l i s t
when  t h i s
f u n c t i o n
32
∗
r e t u r n s .
Any
memory
a l l o c a t e d
t o
s t o r e
nodes
i n
t h e
l i s t
s h o u l d
be
f r e e d .

    33 ∗/
34
v o i d
f l u s h  l i s t ( l i s t ∗  l l ) ;




35










36
/∗
De−a l l o c a t e s
a l l
data
f o r
t h e  l i s t .
Ensure  a l l  memory
a l l o c a t e d
f o r  l i s t
37
∗
l l  i s  f r e e d ,
i n c l u d i n g
any
a l l o c a t e d
s t r i n g s  and  l i s t
l l  i t s e l f .
∗/
38
v o i d
f r e e  l i s t ( l i s t
∗ l l ) ;







Requirements: Please place any struct definitions, typedef and the above function prototypes in a header filelist.h and function bodies (implementations) in a source file list.c. Your source code must use Unix style end-of-line (EOL) characters \n, not DOS style \n\r. You could write code on Windows (I don’t recommend), but you will have to convert it to Unix text files before submitting. Thedos2unix command may be useful for this.

Make a test filelist test.c that tests your list implementation. Your test file should try various combinations of your create list, add to list, remove from list, flush list, print list, and free list functions. Note the difference betweenflush list and free list:



3


after calling flush list, your list ll still points to a valid, empty list (like a brand new list whose head points to NULL); after calling free list, ll itself becomes NULL. You should check return values on any function that can possibly fail.


Part 2: Makefile and README (40 points)

Makefile (30 points)

Write a Makefile that compiles list.c and list test.c to create a binary executable named list test. A simple Makefile tutorial can be found here: https://www.cs.colby. edu/maxwell/courses/tutorials/maketutor/


If your project does not make with your Makefile, sorry we won’t fix it for you or grade it. Your program should compile without any warnings or errors when using all standard gcc warnings, i.e., CFLAGS should include -Wall in your Makefile.

README.txt (10 points)

Write a plain text (i.e., not WYSIWYG/Word processed) README.txt file that explains how to build and run your program, gives a brief description of the pieces of your assign-ment, identifies any challenges you overcame, and any notes about resources you used or discussions you had with others. I suggest starting on your assignment with this file and maintaining it as you work.

PLEASE COMMENT YOUR CODE. If something doesn’t work, you will get partial credit if your comments show that you were on the right track. Document any places where you received help from others.

Important elements of the grading will be the quality and coverage (number of cases) that are tested and the cleanliness of your implementation and documentation, and (last but not the least) for correctness and efficiency.






























4