User Tools

Site Tools


Sidebar

projects

haas:spring2014:data:projects:sll_rewrite

Corning Community College

CSCS2320 Data Structures

~~TOC~~

Project: SLL rewrite

Overview

As promised, here is one of your code rewriting opportunities for the semester- rewriting your singly-linked list code into a multi-file codebase with a Makefile to aid in our compiling efforts.

Obtain

For this project, you'll need to obtain a specially assembled source tree. By default, these instructions will copy that code into ~/src/data/sll1/; if you have been placing your Data Structures code in a different location, you'll have to manually run a copy.

Step 0. Change into project directory

The code is located in the Public Directory for the class:

lab46:~$ cd /var/public/data/spring2014/sll1
lab46:/var/public/data/spring2014/sll1$ 

Step 1a. Use the Makefile to copy your code

lab46:/var/public/data/spring2014/sll1$ make copy

Step 1b. Manually copy code to specified location

Let's say you've been putting your code under ~/src/dataStruct:

lab46:/var/public/data/spring2014/sll1$ cd ..
lab46:/var/public/data/spring2014$ cp -a sll1 $HOME/src/dataStruct/

Layout

This project codebase has a number of directories, which you should explore and familiarize yourself with their contents:

  • inc - project-specific header files
  • lib - compiled and archived libraries will go here (empty by default)
  • src - source code for the node and list operations
    • node - source code for node stuff
    • list - source code for list stuff
  • testing - various unit tests helping to verify correct implementation

There are files by the name of 'Makefile' floating around in several of these directories. For now, you shouldn't have any need to modify them. We're merely going to use them.

Note that, unless there is some typo or other errata issued, the header files will need no modification- use them for reference only.

Operating

To make this whole thing work for us, we use the make utility, from the base of the project tree.

help

To see a list of options:

lab46:~/src/data/sll1$ make help

****************[ Data Structures List Implementation ]*****************
** make                     - build everything                        **
** make debug               - build everything with debug symbols     **
**                                                                    **
** make testing             - build unit tests                        **
** make testing-debug       - build unit tests with debugging symbols **
** make libs                - build all supporting libraries          **
** make libs-debug          - build all libraries with debug symbols  **
**                                                                    **
** make clean               - clean; remove all objects/compiled code **
** make help                - this information                        **
************************************************************************
lab46:~/src/data/sll1$ 

To build

To build everything, simply typing make (or “make debug”) from the base of the project directory.

Watch for any warnings/errors… especially with debug, there should be plenty of on-screen information to indicate where problems may be.

To test

From within the testing/ subdirectory, running make (or make debug) will compile the various testing programs.

Note that, in order for these to compile successfully, the prerequisite node and list libraries must have been successfully compiled and library files stored in lib/

A new way to look at lists

Unlike your previous implementation, where a list was more a loose collection of node pointers, we're going to do for lists what we did for nodes: make a list struct.

struct list {
    struct node *start;
    struct node *end;
    int qty;
};

As you implement your list functions, you'll want to make use of the List pointer that is passed in, and be sure to maintain the correctness of start, end, and qty (qty is merely a count– whenever you insert() or append(), qty should increase by 1; when you getNode(), it should go down by 1– this will be quite useful in the coming projects).

You'll also want to avoid reinventing the wheel– rely on the other node/list functions to aid you in accomplishing the various tasks at hand (for example, you should have to do no further calls to malloc()– the mknode() and mklist() functions should handle it).

Task

Your task will be to correctly define all the listed functions (as prototyped in the various header files in the inc/ subdirectory), so that the various unit tests in the testing/ directory will function as intended.

Look under the src/ subdirectory, in node/ and list/, and edit each file to implement the functions therein.

Updating

Should any typos be identified and fixes released, or additional code included after you have obtained your original copy, you can synchronize your copy with the main version by doing the following:

lab46:~/src/data/sll1$ make update

If there are any issued updates, you'll see output indicating them being applied. If any existing files are changed, a best effort is made to make backup copies, so risk of losing any work will hopefully be minimal (you should still be tracking this whole thing in version control just in case).

Errata

05/03/2014

  • Further tweaks:
    • Makefile updates
    • testing/unit-insert.c
    • testing/unit-append.c
    • testing/palindrome.c unused variable removed
    • some comment clean-up

03/22/2014

  • Fixed a typo in src/list/cp.c

03/17/2014

  • Updated Makefiles to support upgrading to sll2 project
  • warning-free testing/nodetest.c should now be copied over

03/09/2014

  • Added testing/palindrome.c for further list testing
  • Dropped connections may leave stale vi swap files laying about; Makefiles have been updated to remove any swapfiles that are present (unrelated to SLL1)
  • Added “make update” listing to main Makefile's help display
  • testing/nodetest.c compiled with a warning; resolved by changing out %x with %p

03/05/2014

  • src/list/pos.c:setpos() had an incorrect return value; should be Node * (as prototyped in inc/list.h)

Submission

To successfully complete this project, the following criteria must be met:

  • All code must compile cleanly (no warnings or errors)
  • Code must be nicely and consistently indented (you may use the indent tool)
  • Code must be commented
  • Resulting libraries must be operational and functionally correct
    • node and list functions must operate as described, conforming to provided function prototypes
    • code must make use of the other node/list functions as appropriate- do not reinvent the wheel
    • evaluations of libraries using various unit tests will be an assessment criteria
  • Track/version the source code in a repository
  • Submit a copy of your source code to me using the submit tool.

To submit this program to me using the submit tool, run the following command at your lab46 prompt:

$ submit data sll1 sll1-20140228-13.tar.gz
Submitting data project "sll1":
    -> sll1-20140228-13.tar.gz(OK)

SUCCESSFULLY SUBMITTED

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

Preparing the archive

To submit the project, you will need to create an archive and submit that using the submit tool:

lab46:~/src/data/sll1$ make clean
...
lab46:~/src/data/sll1$ make save
Archiving the project ...
Compressing the archive ...
Setting permissions ...
lab46:~/src/data/sll1$ cd ..
lab46:~/src/data$ ls sll*gz
sll1-20140221-17.tar.gz
lab46:~/src/data$ 

That would be the file you want to submit.

haas/spring2014/data/projects/sll_rewrite.txt · Last modified: 2014/05/03 13:42 by wedge