Description
1. Overview Your first C++ program will familiarize you with the basics of the language,aswell as the standard library,whichcontains many classes whichmake data structures problems very easy.You will maintain a tree structure with a simple hierarchy, maintained by a map of functions.Programming will be done C++ style,not C style, as shown in the following table.
Do not use:Instead, use: char* strings Header files:Include only C++11 header files and facilities where feasable,and use namespace std.Include 2. Program Specification
The program specification is given in terms of a Unix man(1) page.
NAME yshell — in memory simulated tree shell
SYNOPSIS yshell [-@ flags]
DESCRIPTION This shell reads commands from stdin and write output to stdout, with errors being set to stderr.Eachline read by the shell is parsed into words by splitting using space characters,with any number of spaces between words.There mayalso be leading and trailing spaces.The first word on any line is a command to be simulated, and the rest are operands to that command. If either stdin or stdout is not a tty,eachline from stdin is echoed to stdout.
The commands modify an inode tree,where eachinode is either a file or a directory.Files contain data and directories contain inodes.Aninode is specified by means of a pathname.Apathname consists of a sequence of characters separated by slash (/)characters.
The inode tree has a root, whichisaspecial node,and also a current inode as well. Whenever apathname is decoded, if the first character is a slash (/), decoding begins at the root, otherwise it begins with the current directory. Whenever a pathname component is a dot (.), it refers to the current directory. If a component is a double dot (..)itrefers to the parent of the current directory.Every directory has both of these entries,with the root being its own
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 2 of 7
parent. Multiple adjacent slashes are treated as a single slash. Trailing slashes are permitted only on directories.
Every inode has three attributes:aninode number,whichisuniquely assigned, starting from 1 for the root;contents,whichisa map from filenames to inodes for a directory,and text for a file;and a size,whichisthe byte count for text, and the number of sub-inodes for a directory.
OPERANDS None.All input comes from stdin.
OPTIONS The -@ option is followed by a sequence of flags to enable debug output, written to stderr.
COMMANDS The following commands are interpreted. Error messages are printed and nothing is done in the case of invalid operands.
# string If the first non-space character on a line is a hash, the line is a comment and is ignored.
cat pathname . . . The contents of eachfile is copied to stdout.An error is reported if no files are specified, a file does not exist, or is a directory.
cd [pathname] The current directory is set the the pathname given. If no pathname is specified, the root directory (/) is used. It is an error if the pathname does not exist or is a plain file,orifmore than one operand is given.
echo [words . . .] The string,whichmay beempty,isechoed to stdout on a line by itself.
exit [status] Exit the program with the given status.Ifthe status is missing,exit with status 0. If a non-numeric argument is given, exit with status 127.
ls [pathname . . .] Adescription of the files or directories are printed to stdout. It is an error if any of the file or directory does not exist. If no pathname is specified, the current working directory is used. If a pathname specified is a directory,then the contents of the directory are listed. Adirectory listed within a directory is shown by a terminating slash. Elements of a directory are listed lexicographically.
Foreachfile listed, output consists of the inode number,then the size, then the filename.Output is lined up into columns and eachcolumn is separated from the next by two spaces.The numeric fields are exactly 6 characters wide and the units position in a column must be aligned.
lsr [pathname . . .] As for ls,but a recursive depth-first preorder traversal is done for subdirectories.
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 3 of 7
make pathname [words . . .] The file specified is created and the rest of the words are put in that file. If the file already exists,anew one is not created, but its contents are replaced. It is an error to specify a directory.Ifthere are no words,the file is empty.
mkdir pathname Anew directory is created. It is an error if a file or directory of the same name already exists,orifthe complete pathname to the parent of this new directory does not already exist. Two entries are added to the directory,namely dot (.)and dotdot (..). Directory entries are alwayskept in sorted lexicographic order.
prompt string Set the prompt to the words specified on the command line.Eachword is separated from the next by one space and the prompt itself is terminated by an extra space.The default prompt is a single percent sign and a space (% ).
pwd
Prints the current working directory.
rm pathname The specified file or directory is deleted (removed from its parent’slist of files and subdirectories). It is an error for the pathname not to exist. If the pathname is a directory,itmust be empty.
rmr pathname Arecursive removal is done,using a depth-first postorder traversal.
EXIT STATUS
0Noerrors were detected.
1Error messages were printed to cerr.
3. A Sample Run
The following table shows a sample run. Eachinteraction with the shell is listed in aseparate box with shell output in Courier Roman and user input in Courier Bold typeface.Acommentary about what is happening is opposite in the right column.
% pwd /
Initially the cwd is the root directory.
% ls /:
12. 12..
The absence of an operand to ls means that dot is used as its operand, which is currently the root. Directories alwayscontain at least two items, namely dot and dotdot. The inode number of the root is alwaysinode #1. The parent of dotdot is itself.
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 4 of 7
% make foo this is a test Make a file called foo whichcontains the string ‘‘this is a test’’,whichis 14 characters.Aninode is allocated, namely inode #2. % make bar test a is this Another file,similarly created, with inode #3. % ls /: 14. 14.. 314bar 214foo Same as the previous output of ls, except with two more files.Note that files are kept in lexicographic order,so bar is listed before foo. % cat food cat: food: No such file or directory An error message is printed, causing the return code from the shell eventually to be 1 rather than 0. Note the error format:command followed by object causing the problem followed by the reason for the failure. % cat foo this is a test Files can consist of only one line, namely a string. % echo O for a muse of fire Ofor a muse of fire Arguments to echo are simply written to the standard output. % prompt = The prompt is changed to the characters ‘‘=’’ followed by a space.Multiple words would have been permitted. = rm bar The file bar is deleted and the size of the root directory is reduced by 1. = make baz foo bar baz Anew file is created with inode #4. = mkdir test Inode #5 is created as a directory called test.This directory is a child of the root and contains the two usual entries,dot and dotdot. = prompt % The prompt is changed backtoa% followed by a space. % ls / /: 15. 15.. 411baz 214foo 52test/ Just checking the contents of the root. % cd test The cwd is now test. % pwd /test Yes, itis.
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 5 of 7
% cd Without arguments cd goes backtothe root directory. % pwd / OK. % cd test Go to a directory called test whichisa subdirectory of the cwd, whose alias name is alwaysdot. % pwd /test % cd .. Dotdot is alwaysanalias for the parent of the cwd. % pwd / % cd test % make me me me me This would have errored out if test were not a directory or did not exist. The next available inode is #6. % cat me me me me % cd .. % cd test % cat me me me me % cd % lsr / /: 15. 15.. 411baz 214foo 53test/ /test: 53. 15.. 68me Recursive directory listing.This is done using a preorder traversal. Withing a given level, lexicographic ordering is used. Recursion will go through all subdirectories at all levels. % cd test % mkdir foo % cd foo % mkdir bar % cd bar % mkdir baz % cd baz Note that foo uses inode #7, bar uses inode #8, and baz uses inode #9. % ls . .: 92. 83.. At this point dot is baz and dotdot is bar.
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 6 of 7
% cd / % lsr test /test: 54. 15.. 73foo/ 68me /test/foo: 73. 54.. 83bar/ /test/foo/bar: 83. 73.. 92baz/ /test/foo/bar/baz: 92. 83..
Arather large test showing inode numbers,file and directory sizes,and filenames.Note that directory names are indicated in the listing with a trailing slash. Again, the size of a file is the number of characters in it and the size of a directory is the sum of the number of files The subdirectory count is not recursive.
% ^D End of file or Control/D causes the shell to exit.
4. A Tour of the Code
Begin by studying the code provided in the code/ subdirectory.There are four modules arranged into a header (.h)file and an implementation (.cpp)file,the main program in main.cpp,and, of course,aMakefile.Notice that comments are in the header for when specifying general functionality,and only in the implementation as away ofexplaining how something works.
Makefile Study the various targets all, ${EXECBIN}, %.o, ci, lis, clean, spotless, submit, verify,and deps,whichperform their usual functions.
debug.{h,cpp} The debug module is already written for you. It is useful in tracing through your code.Other parts of the code maywant to have more DEBUGF and DEBUGS calls added. Note that you should also use gdb to trackdown bugs.Use valgrind to check for invalid memory references and memory leak.
util.{h,cpp} The util module is just a collection of independent functions whichare herded together.Itisamodule without any cohesion, but a useful place to park various random functions.
main.cpp The main program is mostly complete.Itscans options,then loops reading and executing commands.
commands.{h,cpp} Note that the functions are provided but do not do more than print a trace.Eachfunction as a inode_state argument, passed by reference,whichitmight update,and a wordvec arlgument. words[0] is the name of the command itself,sothe first argument is words[1].This will take the most work, but commands can be added one at a time,byaddition to the
CMPS-109 • Winter 2015 • Program 1 • Function pointers, a shell 7 of 7
organization that is already there.You mayadd private functions is you need to.This is the major execution engine.
inode.{h,cpp} The inode,orfile system, module is the main data structure that you are working on. As you implement commands,also implement the functions of this module as well.
5. What to Submit
Submit the files Makefile, README,and all C++ header and source files.All header files must end with .h,and source files must end with either .cpp or .cc as the suffix. You must be consistent and use one or the other suffix for all files.
Run gmake to verify that the build is possible.And when you run submit, do so from the Makefile target of that name.That way you won’t forget to submit a file.Ifyou forget to submit a file,orsubmit the wrong version, you will lose at least 50% of your program’svalue.Make sure that you do not get any warnings from g++ and that checksource does not complain about anything.Donot submit any file that is built by the Makefile.
If you are doing pair programming,follow the additional instructions in: /afs/cats.ucsc.edu/courses/cmps012b-wm/Syllabus/pair-programming/
The code must compile and run using g++ on unix.ucsc.edu,regardless of whether it runs elsewhere.Asofthe time of formatting this document, that was :
bash-1$ g++ –version | head -1 g++ (GCC) 4.8.2 20140120 (Red Hat 4.8.2-15) bash-2$ uname -srp Linux 2.6.32-504.12.2.el6.x86_64 x86_64 bash-3$ hostname unix1.lt.ucsc.edu
Forasummary of C++11 support in GCC,refer to: https://gcc.gnu.org/projects/cxx0x.html
