Doubly-linked Circular List in C

[ This content is protected and may not be shared, uploaded, or distributed. ]

This spec is private (i.e., only for students who took or are taking CSCI 402 at USC).0You do not have permissions to display this spec at a public place (such as a public bitbucket/github).0You also do not have permissions to display the code you write to implementation this spec at a public place0since your code was written to implement a private spec. (If a prospective employer asks you to post your0code, please tell them that you do not have permissions to do so; but you can send them a private copy.)

Assignment

(Please check out the Warmup 1 FAQ before0sending your questions to the TAs, the course producers, or the instructor.)

The main purpose of this assignment is to develop an0efficient doubly-linked circular list from scratch in C.

Electronic submissions only.

For the first part of the assignment, you need to implement a doubly-linked circular list.0You need to create "my402list.c" to work with0"my402list.h".0You would also need "cs402.h".0You must not alter the files provided on this web page.0For the meaning of the functions, please0see function definition below.0After you have successfully implemented the doubly-linked circular list,0you must use it to implement the sort command specified below.

We will not go over the lecture slides for this0assignment in class. Although it's important that you are familiar with it. Please read it over. If you have questions, please e-mail the instructor.

Compiling

Please use a Makefile so that when the grader simply enters:

make warmup1

an executable named warmup1 is created.0Please make sure that your submission conforms to0other0general compilation requirements and README requirements.


Commandline Syntax & Program Output

The commandline syntax (also known as "usage information") for warmup1 is as follows:

warmup1 sort [tfile]

Square bracketed items are optional.0If tfile is not specified, your program should0read from stdin.0Unless otherwise specified, output of your program must go to stdout0and error messages must go to stderr.

The meaning of the commands are:

sort : Produce a sorted transaction history for the transaction records in tfile0(or stdin) and compute balances.0The input file should be in the tfile format.

The output for various commands are as follows.

sort : Your job is to read in a tfile one line at0a time. For each line, you need to check if it has the correct format.0If the line is malformed, you should print an error message and quit your
program.0Otherwise, you should convert the line into an internal object/data structure,0and insert the object/data structure into a list, sorted by the timestamp.0If there is another object/data structure with identical timestamp, you should0print an error message and quit your program.

After all the input lines are processed, you should output all the transactions0in ascending order, according to their timestamps. The output must conform0to the following format (please do not print the first 3 lines below, they0are only for illustration purposes):

000000000111111111122222222223333333333444444444455555555556666666666777777777780
123456789012345678901234567890123456789012345678901234567890123456789012345678900
0
+
-----------------
+--------------------------
+----------------
+
----------------
+0
|
Date

| Description
|
Amount |
Balance
|0
+
-----------------
+--------------------------
+----------------
+
----------------
+0
| Thu Aug 21
2008
| ...
|
1,723.00
|
1,723.00
|0
| Wed Dec 31
2008
| ...
| (
45.33)
|
1,677.67
|0
| Mon Jul 13
2009
| ...
|
10,388.07
|
12,065.74
|0
| Sun Jan 10
2010
| ...
| (
654.32)
|
11,411.42
|0
+
-----------------
+--------------------------
+----------------
+
----------------
+

Each line is exactly 80 characters long (followed by a single "\n" character).0The Date field spans characters 3 through 17.0Please use ctime() to format the timestamp and remove unnecessary characters to make it look like what's in the table above.0The Description field (shown as "..." above to mean whatever that's appropriate)0spans characters 21 through 44. (If a description is too long, you must truncate it.)0The Amount field spans characters 48 through 61.0It must contain a decimal point with at least one digit to the0left of the decimal point and exactly two digits to the right of the decimal point.0If the number to the left of the decimal point is not 0, the first digit of this number must not be a 0.0For a withdrawal, a pair of paranthesis must be used as indicated.0If the amount of a transaction is more than or equal to 10 million, please0print ?,???,???.?? (or (?,???,???.??)) in the Amount field0to indicate that the amount is too large to fit in the display area.0The Balance field spans characters 65 through 78.0If a balance is negative, a pair of paranthesis must be used.0If the absolute value of a balance is more than or equal to 10 million, please0print ?,???,???.?? (or (?,???,???.??)) in the Balance field0to indicate that the balance is too large to fit in the display area.

Pleaes output reasonable and useful error messages if the command0is malformed or file does not exist or inaccessible.

My402List

A traditional doubly-linked list of length 4 looks like the following:

















A corresponding My402List would look like the following:












The functions you need to implement has the0following meaning (note that, for readability, all the functions are missing "My402List" before the name, and0all of them are missing (My402List*) as the first argument as compare to what's in the0actual header file, "my402list.h"; furthermore, other than the Init() function,0you must assume that for all other functions, the first argument is a valid list; for the Init() function,0you must assume that the first argument points to sizeof(My402List) bytes of valid memory):

int Length()
Returns the number of elements in the list.

int Empty()
Returns TRUE if the list is empty. Returns FALSE otherwise.

int Append(void *obj)
If list is empty, just add obj to the list.0Otherwise, add obj after Last().0This function returns TRUE if the operation is performed successfully and returns FALSE otherwise.

int Prepend(void *obj)
If list is empty, just add obj to the list.0Otherwise, add obj before First().0This function returns TRUE if the operation is performed successfully and returns FALSE otherwise.

void Unlink(My402ListElem *elem)
Unlink and free() elem from the list.0Please do not free() the object pointed to by elem and do not check if elem is on the list.

void UnlinkAll()
Unlink and free() all elements from the list and make the list empty.0Please do not free() the objects pointed to by the list elements.

int InsertBefore(void *obj, My402ListElem *elem)
Insert obj between elem and elem->prev.0If elem is NULL, then this is the same as Prepend(). This function returns TRUE if the operation is performed successfully and returns FALSE otherwise.0Please do not check if elem is on the list.

int InsertAfter(void *obj, My402ListElem *elem)
Insert obj between elem and elem->next.0If elem is NULL, then this is the same as Append(). This function returns TRUE if the operation is performed successfully and returns FALSE otherwise.0Please do not check if elem is on the list.

My402ListElem *First()
Returns the first list element or NULL if the list is empty.

My402ListElem *Last()
Returns the last list element or NULL if the list is empty.

My402ListElem *Next(My402ListElem *elem)
Returns elem->next or NULL if elem is0the last item on the list.0Please do not check if elem is on the list.

My402ListElem *Prev(My402ListElem *elem)
Returns elem->prev or NULL if elem is0the first item on the list.0Please do not check if elem is on the list.

My402ListElem *Find(void *obj)
Returns the list element elem such that elem->obj == obj.0Returns NULL if no such element can be found.

int Init()
Initialize the list into an empty list.0Returns TRUE if all is well and returns FALSE if there is an error initializing the list.

Assuming that you have a list of (Foo*) objects,0a typical way to traverse the list from first to last is as follows:

void Traverse(My402List *list)0
{0
My402ListElem *elem=NULL;0
0
for (elem=My402ListFirst(list);0
elem != NULL;0
elem=My402ListNext(list, elem)) {0
Foo *foo=(Foo*)(elem->obj);0
0
/* access foo here */0
}
}

Your implementation of My402List must allow your list to be0traversed in the above way. Please use0listtest0to verify that your implementation is correct.0Please understand that it is your job to read and understand the code in "listtest.c"0and figure out how you must write the code in "my402list.c" so that listtest compiles and runs perfectly.

If you are not familiar with pointers in C, please take a look at my review on pointers.

tfile Format

A tfile (transaction file) is an ASCII text file. Each line in a tfile0contains 4 string fields with <TAB> characters being the delimeters (i.e, each line contains exactly 30<TAB> characters.)0Each line (includingn the last line) in a tfile must end with a "\n" character. As a result, the last character of a valid tfile must always be a "\n" character.0The fields are:

Transaction type (single character: "+" for deposit or "-" for withdrawal).


Transaction time (a UNIX timestamp, please see man -s 2 time on your 32-bit Ubuntu 16.04 system). The value of this field must be > 0 and < the timestamp that correspond to the current time.0Also, since this is a number, the first digit must not be zero.0(Since the largest unsigned integer is 4,294,967,295, if the length of the string of this field0is more than or equal to 11, you can safely assume that the timestamp is bad.)

Transaction amount (a number followed by a period followed by two digits; if the number is not zero, its first digit must not be zero).0The number to the left of the decimal point can be at most 7 digits (i.e., < 10,000,000).0The transaction amount must have a positive value.

Transaction description (textual description, cannot be empty).0A description may contain leading space characters, but you must remove them before proceeding.0After leading space characters have been removed, a transaction description must not be empty.


The lines are not sorted in any order.0Furthermore, if a line is longer than 1,024 characters (including the '\n' at the end of a line),0it is considered an error.

If you encounter an error when you process the input file,0you should print an error message and quit your program.0You must not process additional input lines.0Please also note that a valid file must contain at least one transaction.

A sample tfile is provided here as test.tfile.

Testing Your Doubly-linked Circular List

To make sure that your implementation of the doubly-linked circular list is correct,0we have provided a test program, listtest.c and a corresponding Makefile:

listtest.c


Makefile


Put these files together with your implementation of0my402list.c and the provided0my402list.h and0cs402.h and type "make".0You should get an executable named listtest.

If you do:

./listtest

no output must be produced. You can also run:

./listtest -debug
to have the program output some debugging information.

Sample Printout

If you download the sample tfile, i.e., test.tfile and run:

./warmup1 sort test.file

You should get the following printout (indented so it's easier to read):

+
-----------------
+--------------------------
+----------------
+
----------------
+0
|
Date

| Description
|
Amount |
Balance
|0
+
-----------------
+--------------------------
+----------------
+
----------------
+0
| Thu Aug 21
2008
| Initial deposit
|
1,723.00
|
1,723.00
|0
| Wed Dec 31
2008
| Phone bill
| (
45.33)
|
1,677.67
|0
| Mon Jul 13
2009
| Dear parents
|
10,388.07
|
12,065.74
|0
| Sun Jan 10
2010
| Beemer monthly payment
| (
654.32)
|
11,411.42
|0
+
-----------------
+--------------------------
+----------------
+
----------------
+

The above printout is provided in test.tfile.out (648 bytes in size).0Please understand that your printout must be identical to test.tfile.out, down to every byte.0Also, please be careful when you download test.tfile.out with a web browser. Your web browser may0modify this file! For example, if you are on Windows, since Windows text files are different from Unix text files, Windows may add invisible0characters to this file to make it into a Windows text file. Therefore, you should inspect the file size after you have it downloaded. If the0file size is not 648 bytes, then you need to dowload it using a different method (for example, right click on test.tfile.out0and select "Save Link As").

Grading Guidelines

The grading guidelines and grading data (in w1data.tar.gz)0have been made available.0Please understand that the grading guidelines is part of the spec and the grader will stick to it when grading.0Please run the scripts in the guidelines on a standard 32-bit Ubuntu 16.04 system.0You should read the scripts to understand exactly how your assignment will be graded.0It is possible that there are bugs in the guidelines. If you find bugs, please let the instructor know as soon as possible.

The grading guidelines is the only grading procedure we will use to grade your program.0No other grading procedure will be used.0To the best of our effort, we will only change the testing data for grading but not the commands.0(We may make minor changes if we discover bugs in the script or things that we forgot to test.)0It is strongly recommended that you run your code through the scripts in the grading guidelines.

A copy of the grading scripts are made available here (the .out files are what the output suppose to look like):

section-A.csh    section-A.out0

section-B.csh    section-B.out

After you have download the above ".csh" files, please put them in the same directory0as warmup1 and run the following command:

chmod 755 section-?.csh

Please also follow the beginning part of the grading guidelines to unpack0the grading data file (i.e., w1data.tar.gz)0so that the script can work properly.

By the way, please do not run these grading scripts in a shared folder.0For unknown reasons, running the grading scripts from within a shared folder may not work correctly!

Miscellaneous Requirements and Hints

Please read the general programming FAQ if you0need a refresher on file I/O and bit/byte manipulications in C.


You must NOT use any external code segments0to implement this assignment.0You must implement all these functionalities from scratch.


You must not use any arrays to implement list functionalities.0You must dynamically allocate all elements in a list.


For the sort command,0you must use the doubly-linked circular list developed in this0assignment.


If the size of the input file is large, you must not read the0whole file into a large memory buffer and then process the file data.0You must read the file incrementally.

It's important that every byte of your data is read and written0correctly. You will lose a lot of points if one byte of data is0generated incorrectly! The grading of this assignment will be harsh0and you must make your code to work according to the posted0grading guidelines.


Please follow the UNIX convention that, when your output is an ASCII0file (such as the output of the sort command),0append '\n' in the last line of the output if it's not a0blank line. (This way, you don't get the commandline prompt appearing at0the wrong place on the screen.)


String I/O functions such as fgets(), scanf(), and0printf() are really meant for inputing/outputing strings.0Do not use them to input/output binary data!0Do not use them to input/output binary data (unless you are sure what you are doing)!


Start working on this early! Please don't complain0to the instructor that this assignment is too tedious or0it takes too much work just to parse the commandline.0Get it done early and get it done right!


Submission

All assignments are to be submitted electronically (including0the required "README" file). To submit your work, you must first0tar all the files you want to submit into a "tarball" and0gzip it to create a gzipped tarfile named0warmup1.tar.gz. Then you upload0warmup1.tar.gz to the0Bistro system.0The command you can use to create a gzipped tarfile is:

tar cvzf warmup1.tar.gz MYLISTOFFILES0

ls -l warmup1.tar.gz

Where MYLISTOFFILES is a list of file names that you are submitting0(you can also use wildcard characters if you are sure that it will pick up only the right files).0DO NOT submit your compiled code, just your source code and README file. Two point will be deducted for each0binary file included in your submission (e.g., warmup1, .o,
.gch, core, etc.).0The last command shows you how big the created "warmup1.tar.gz" file is.0If "warmup1.tar.gz" is larger than 1MB in size, the submission server will not accept it.

Please note that the 2nd commandline argument of the tar command above0is the output filename of the tar command. So, if you omit0warmup1.tar.gz above, you may accidentally replace one of your files with0the output of the tar command and there is no way to recover the lost file (unless you have made a backup copy).0So, please make sure that the first commandline argument is cvzf and the 2nd commandline argument0is

warmup1.tar.gz.

A w1-README.txt template file is provided here.0You must save it as your w1-README.txt file and0follow the instructions in it to fill it out with appropriate information and include it in your submission.0You must not delete a single line from w1-README.txt.0Please make sure that you satisfy all the README requirements.

Here is an example commands for creating your warmup1.tar.gz file:

tar cvzf warmup1.tar.gz Makefile *.c *.h w1-README.txt

If you use an IDE, you need to modify the commands above so that you include ALL0the necessary source files and subdirectories and make sure you have not forgotten to0include a necessary file in order for the grader to compile your code on a "clean" system.

You should read the output of the above commands carefully to make sure0that warmup1.tar.gz is created properly.0If you don't understand the output of the above commands, you need to learn0how to read it! It's your responsibility to ensure that0warmup1.tar.gz is created properly.

To check the content of warmup1.tar.gz, you can use the following command:

tar tvzf warmup1.tar.gz

Please read the output of the above command carefully to see what files were included in warmup1.tar.gz0and what are their file sizes and make sure that they make sense.

Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button0and locate and select your submission file (i.e., warmup1.tar.gz).0Then click on the Upload button to submit your warmup1.tar.gz.0(Be careful what you click! Do NOT submit the wrong file!)0If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure.0If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address.

When this web page was last loaded, the time at the submission server (merlot.usc.edu) was030Aug2022-15:57:53.0Reload this web page to see the current time on merlot.usc.edu.

USC E-mail:   @usc.edu

Submission PIN:

Event ID (read-only):    merlot.usc.edu_80_1557931083_236


Submission File Full Path:    Choose File    No file chosen


Upload

If the command is executed successfully and if everything checks out,0a ticket will be issued to you to let you know "what" and "when"0your submission made it to the Bistro server. The next web page you0see would display such a ticket and the ticket should look like the sample shown in the submission web page0(of course, the actual text would be different, but the format should be similar).0Make sure you follow the Verify Your Ticket instructions0to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file.0Also, an e-mail (showing the ticket) will be sent to your USC e-mail address.0Please read the ticket carefully to know exactly "what" and "when"0your submission made it to the Bistro server.0If there are problems, please contact the instructor.


It is extreme important that you also verify your submission0after you have submitted warmup1.tar.gz electronically to make0sure that every you have submitted is everything you wanted us to grade.0If you don't verify your submission and you ended up submit the wrong files, please understand that due to our fairness policy,0there's absolutely nothing we can do.

Finally, please be familiar with the Electronic Submission Guidelines0and information on the bsubmit web page.





[Last updated Sun Aug 21 2022] regarding copying.]




0[Please see copyright




[0Home0|0Description0|0Lectures0|0Videos0|0Discussions |0Projects0|0Forum0]