PROJECT: Nodes - Doubly-Linked Nodes (DLN0)

OBJECTIVE

To begin our journey on doubly-linked data structures, and collaboratively authoring and documenting the project and its specifications.

OVERVIEW

We have been focusing on singly-linked data structures for the past few weeks. We now start delving into the realm of doubly-linked data structures. And we will start by reimplementing some of the same base data structures (specifically, nodes and lists), this project: doubly-linked nodes.

GRABBING

We are doing a fresh start this week, reimplementing our data structure infrastructure from scratch. So, to obtain the project files for this project, we will be doing an initial grabit.

Simply go into your DESIG organizational/staging directory, and run:

lab46:~/src/SEMESTER/DESIG$ grabit data dln0

EDIT

You will want to go here to edit and fill in the various sections of the document:

https://lab46.g7n.org/notes/data/fall2022/projects/dln0

BACKGROUND

Following our exploration into nodes, linked lists, and groups of linked lists. From this point forward our node library has been restarted. We are recoding all the nodes and lists functions from start, but we are now moving into doubly linked nodes. Doubly linked nodes will further our learning into dealing with double pointers, passing by reference, and unions.

Once you grab dln0, you will find a new header file called data.h. In this header file, you will find a type of data called union:

union info {
    signed char value;
    struct node *data;
    void *other;
};

Furthermore, we have made some changes to our Node structure to include a pointer to left and right. It can be seen below:

struct node {
     union info     payload;
     struct node   *left;
     struct node   *right;
};

A union is a type of data that allows to store different types of data in the same memory location. A union can contain different members/properties, but only one member can contain a value at a time. Unions allocate the memory necessary to contain the largest member, the member with the type of data that requires the most memory.

If you recall from the sll project, info is the contents of the node. Info now has the potential to hold different types of data, not just an unsigned char, BUT it still only holds one at a time. The type of data it could hold is an unsigned char value, point to another Node anywhere else (could be in another group, on another list, so on), and a pointer that could point to any other type of pointer (only pointers though). In this project, we only need to worry about the node's left and right, and payload.

Remember that there can only be one return statement per function, I suggest having a variable that contains the exit code and change that along with the flow of the program in case of errors.

SPECIFICATIONS

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash

PROGRAM

dln0 has three different functions. These are:

mk.c
cp.c
rm.c

The general order you should complete them in is mk.c first, followed by rm.c, and cp.c last.

Some general advice for each function:
mknode() - don't forget about the left and right pointers, explore into /inc/ to see what each node contains
cpnode() - make sure to copy the entire payload, union has different types of different sizes so don't just copy the smallest one. It may be a good idea to use your previously created mk function. Remember, do not reinvent the wheel
rmnode() - not too much needed for this one, make sure you have the sufficient error checks, set to NULL after deallocation

Recommended order of creation

1.Mknode
2.Rmnode
3.Cpnode

DEBUGGING

Useful tools for debugging issues are gdb and examining the test files themselves. to utilize gdb, run the test program with the gdb command (not make check), with a command that might look like “gdb ./bin/unit-lobtain”. Once in gdb the “run” command with start the program, and “break (line number)” will cause the program to stop at the specified line number. Once you have hit the breakpoint you can use “display (variable name)” to see the value of a variable at every step, “n” to step to the next line, and “continue” to continue running the program until the next breakpoint. Note that if you encounter a seg fault the program will tell the where the seg fault occurs, and you can use “run” again to restart the program.

OUTPUT SPECIFICATIONS

All functions will return a status code, of type code_t. These codes will use bitwise operators, specifically the or operator.

UNIT TESTS

Unit tests for this project are unit-mknode, unit-rmnode, and unit-cpnode. There are 33 total tests, 12 for mknode, 4 for rmnode, and 17 for cpnode. To get a general view of your entire project, run make check to see how many tests pass. To get a more detailed view of what tests are failing, ./bin/unit-(DESIRED_TEST). If you are getting segmentation faults, consider the use of gdb. If things aren't compiling correctly, it may be helpful to check the errors file as well.

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Project must be submit on time, by the deadline.
- Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
All code must compile cleanly (no warnings or errors)
- Compile with the -Wall and –std=gnu18 compiler flags
- all requested functionality must conform to stated requirements (either on this document or in a comment banner in source code files themselves).
Executed programs must display in a manner similar to provided output
- output formatted, where applicable, must match that of project requirements
Processing must be correct based on input given and output requested
Output, if applicable, must be correct based on values input
Code must be nicely and consistently indented
Code must be consistently written, to strive for readability from having a consistent style throughout
Code must be commented
- Any “to be implemented” comments MUST be removed
  - these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
  - Sufficient comments explaining the point of provided logic MUST be present
No global variables (without instructor approval), no goto statements, no calling of main()!
Track/version the source code in your lab46 semester repository
Submit a copy of your source code to me using the submit tool (make submit on lab46 will do this) by the deadline.

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following:

lab46:~/src/SEMESTER/DESIG/PROJECT$ make submit

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.

RUBRIC

I'll be evaluating the project based on the following criteria:

65:dln0:final tally of results (65/65)
*:dln0:obtained project by the Sunday prior to duedate [6/6]
*:dln0:clean compile, no compiler messages [13/13]
*:dln0:implementation passes unit tests [13/13]
*:dln0:adequate modifications to code from template [13/13]
*:dln0:program operations conform to project specifications [13/13]
*:dln0:code tracked in lab46 semester repo [7/7]

Pertaining to the collaborative authoring of project documentation

each class member is to participate in the contribution of relevant information and formatting of the documentation
- minimal member contributions consist of:
  - near the class average edits (a value of at least four productive edits)
  - near the average class content change average (a value of at least 256 bytes (absolute value of data content change))
  - near the class content contribution average (a value of at least 1kiB)
  - no adding in one commit then later removing in its entirety for the sake of satisfying edit requirements
- adding and formatting data in an organized fashion, aiming to create an informative and readable document that anyone in the class can reference
- content contributions will be factored into a documentation coefficient, a value multiplied against your actual project submission to influence the end result:
  - no contributions, co-efficient is 0.50
  - less than minimum contributions is 0.75
  - met minimum contribution threshold is 1.00

Additionally

Solutions not abiding by spirit of project will be subject to a 50% overall deduction
Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
Solutions not utilizing indentation to promote scope and clarity or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction

Lab46 Wiki

Sidebar

Table of Contents

PROJECT: Nodes - Doubly-Linked Nodes (DLN0)

OBJECTIVE

OVERVIEW

GRABBING

EDIT

BACKGROUND

SPECIFICATIONS

PROGRAM

Recommended order of creation

DEBUGGING

OUTPUT SPECIFICATIONS

UNIT TESTS

SUBMISSION

Submit Tool Usage

RUBRIC

Pertaining to the collaborative authoring of project documentation

Additionally

Lab46 Wiki

User Tools

Site Tools

Sidebar

Table of Contents

PROJECT: Nodes - Doubly-Linked Nodes (DLN0)

OBJECTIVE

OVERVIEW

GRABBING

EDIT

BACKGROUND

SPECIFICATIONS

PROGRAM

Recommended order of creation

DEBUGGING

OUTPUT SPECIFICATIONS

UNIT TESTS

SUBMISSION

Submit Tool Usage

RUBRIC

Pertaining to the collaborative authoring of project documentation

Additionally

Page Tools