Homework answers / question archive / Lab: Interface and Implementation Using Opaque Pointers Topics and references Linked lists - see class handouts for Lecture 5

Lab: Interface and Implementation Using Opaque Pointers Topics and references Linked lists - see class handouts for Lecture 5

Computer Science

Share With

---

Lab: Interface and Implementation

Using Opaque Pointers

Topics and references

• Linked lists - see class handouts for Lecture 5.
• Interface and implementation methodology - see class handouts for Lecture 6.
• Val grind to debug memory leaks and errors - see class handout for Lectures 1 and 2.

Learning Outcomes

• Practice interface/implementation methodology using opaque pointers to encapsulate implementation details from interface.
• Practice programming linked-lists.
• Gain practice in debugging memory leaks and errors using Valgrind
• Read and understand code

Overview

Modern software development consists of using software libraries or application programming interfaces (APIs) such as Google Maps API, Facebook API, Twitter API, IBM Watson API, and hundreds of other interfaces to develop new software components. Game development is almost entirely based on interfacing with APIs such as Vulkan, OpenGL, Direct3D, Autodesk Maya, UDK, Unity, Photoshop, and so on. Embedded software developers use a variety of APIs for developing software for smart cars, internet-of-things, and consumer devices such as phones, alarm systems, and refrigerators.

A software library comes in two parts: its interface and its implementation. The interface specifies what the library does while the implementation specifies how the library accomplishes the purpose advertised by its interface. Software designers develop libraries and APIs using the concepts of abstraction and encapsulation. Abstraction specifies the essential features of something that must be made visible through an interface and which information should be hidden as part of the implementation. Encapsulation provides techniques for packaging an interface and its implementation in such a way as to hide what should be hidden and to make visible what should be visible. Programming languages provide varying support to the concepts of abstraction and encapsulation. By design C++ provides greater support than C.

In software development, a client is a piece of code that uses a software component only through an interface. Indeed, clients should only have access to an implementation's object code and no more.

Recall that a data type is a set of values and the set of operations that can be applied on these values. In C++, built-in data types include characters, integers, and floating-point numbers. Structures and classes in C++ define new data types and can be used to form higher-level data types, such as linked lists, trees, lookup tables, and more. We abstract a high-level data type using an interface that identifies the legal operations on values of that type while hiding the details of the type's representation in an implementation. Ideally, the operations should not reveal representation details on which clients might implicitly depend. Thus, an abstract data type, or ADT, is an interface created using data abstraction and encapsulation that defines a high-level data type and operations on values of that type.

Task

In this exercise, we'll combine class discussions on linked lists, abstraction, encapsulation, and interface/implementation methodology to implement a singly-linked list ADT. The only legal operations that clients can perform on the singly-linked list type is specified by the following interface declared in sllist.h:

1 sllist* construct_list(Q); // IMPLEMENTED

2 void destruct_list(sllist *ptr_s11);

3 size_t sizeCsllist const* ptr_sll);

4 void push_front(sllist *ptr_sl1l, int value); // IMPLEMENTED

5 void push_back(sllist *ptr_sIl, int value)

6 void print(Csllist const* ptr_sl1); // IMPLEMENTED

7 node* find(sllist const* ptr_sl1, int value);

8 void remove_first(sllist *ptr_sll, int value);

9 void insert(sllist *ptr_sll, int value, size_t position);

Functions marked IMPLEMENTED are already implemented; you've to implement the other functions in sllist.cpp.

How are the representation details of the singly-linked list type hidden from clients? The strategy used will be similar to the implementation of FILE* presented in <cstdio> by the C standard library. The singly-linked list ADT is specified by type sllist that is not defined in interface file sllist.h but is instead defined in implementation file sllist.cpp. Encapsulation is achieved by using a feature of C/C++ that allows a structure to be declared without defining it. Such a declaration of the singly-linked list type is added to interface file sllist.h:

1 struct sllist;

This declaration, called a forward declaration, introduces name sllist into the program and indicates that sllist referstoa struct type. Since clients never see the definition of sllist (because it is defined in an inaccessible implementation file sllist.cpp ), itis an incomplete type clients know that sllist isa struct type but they don't know what members that type contains. An incomplete type can be used in only limited ways since the compiler is unable to deduce the amount of memory that must be put aside when objects of the incomplete type are defined: we can define pointers or references to such types, and we can declare (but not define) functions that use an incomplete type as a parameter or a return type. The implementation is hidden because clients can represent a singly-linked list by a pointer to structure sllist* but the pointer says nothing about what structure sllist looks like. sllist* is called an opaque pointer type; clients can manipulate such pointers freely, but they can’t dereference them; that is, they can't look at the internals of the structure pointed to by them. Only the implementation in sllist.cpp has that privilege.

Implementation details

The singly-linked list type sllist and the node type are defined in sllist.cpp:

1 struct node {

2 int value; // data portion

3 node *next; // pointer portion

4 }:

5

6 struct sllist {

7 node “head;

8 }:

                                         individual node objects of S11ist

                  head             value  next           value next               value next   nuIIptr       

           S11ist object

In class discussions, we used a plain node* to point to the first linked list element. In this exercise, we define a struct type called sllist to contain the node* plus additional data members (Such as size) that will be added at a later date. The use of type sllist is illustrated in the following code fragment that defines function push_front and function print:

1 // allocate and initialize sllist object on free store

2 sllist* construct_listQ) {

3 return new sllist {nullptr};

4 }

5

6 // add element to front of linked list

7 void push_front(sllist *ptr_sll, int value) {

8 if C(ptr_sll) f{

9 ptr_sll->head = construct_node(value, ptr_—sll->head) ;

10   }

11  }

12

13. // visit each element and print its value

14. void print(Csllist const *ptr_sll1) {

15 node const *head = ptr_sl1->head;

16 while Chead) {

17 Std: :cout << head->value << " "s

18 head = head->next;

19  }

20 std::cout << "\n";

21  }

Since clients cannot define objects of type sllist, they have to first call function construct_list to construct an unnamed object of type sllist on the free store:

1 hlp2::sllist *list = hlp2::construct_listQ;

Using pointer list, the client can add elements to the list and then traverse each element in the

list:

1 hlp2::push_frontClist, 10);

2 hlp2::push_frontClist, 20);

3 hlp2::push_front (list, 30);

4 hlp2::print(list);

causing the following values to be written to the free store:

1  30 20 10

To avoid memory leaks, the memory allocated to the list elements and the list object sllist must be deallocated by making a call to function destruct_list:

1 // you must implement this function!!!

2 hlp2::destruct_listClist);

The definition of function destruct_list is similar to print with two notable differences:

• The code must keep a pointer p for the element after the element to be deleted. The element is deleted and using p, the traversal continues to the element pointed to by p.
• After deleting all the elements in the list, the object of type sllist that was allocated by construct_list must be deleted.

The function remove_first(sllist *ptr_sll, int val) deletes the first element encountered with the same value as the second parameter. First, the function should check if the list is empty in which case, there is nothing to remove. Second, If head 's value ( ptr_s11->head->value ) is the same as val, the first element is deleted. In the third scenario, suppose the program needs to delete the second element in the list with value 4.

After calling remove_first, the first and third element must remain in the list. The first element's next must point to the third (now second) element. How to implement remove_first ? First, the function creates a new pointer p that points to the same memory address as head.

If pointer p advances to element with value 4, it will be impossible to locate the one-before- removal-element with value 6. The trick is to use a second pointer q sothat p and q point to consecutive elements with p always pointing to the element before the element pointed to by q.

This means that pointer q will be used to find the element to be removed. When q points to the removal node, p will point to the one-before-removal-node.

Once q points to the removal element, modify p->next to bypass the removal element:

soe | 4 | = 9 | pul ptrr

PL qf

Delete the memory pointed to by q:

pL aL

The insert function is left as an exercise.

Be particularly careful about managing memory to avoid memory leaks and errors. Since there are multiple objects in memory, allocation and deallocation is a complex process. If the TA finds a memory leak or error in your submission, you will receive a maximum grade of D.

Submission Details

Please read the following details carefully and adhere to all requirements to avoid unnecessary deductions.

Header file

You will not be submitting the interface file sllist.h and therefore do not make any changes to this file.

Source file

A partially filled implementation file is provided. Complete the necessary definitions and upload to the submission server. Remember, to frequently check your code for memory leaks and errors with Valgrind. Also note that if your submission has even a single memory leak or error, D will be the maximum possible grade. You're warned!!!

Compiling, executing, and testing

Download sllist-driver.cpp, makefile, anda correct input file output.txt for the unit tests in the driver.

Run make with the default rule to bring program executable sllist.out up to date:

1 $ make

Or, directly test your implementation by running make with target test:

1 $ make test

If the diff command inthe test rule is not silent, then one or more of your function definitions is incorrect and will require further work.

Documentation

This module will use Doxygen to tag source and header files for generating html-based documentation. Matters relating to documentation were discussed and described in Lab 1. Here's the abbreviated version. Every source and header file must begin with file-level documentation block. Every function that you declare and define and submit for assessment must contain function-level documentation. This documentation should consist of a description of the function, the inputs, and return value.

Submission and automatic evaluation

1. In the course web page, click on the appropriate submission page to submit sllist.cpp.

2. Please read the following rubrics to maximize your grade. Your submission will receive:

• F grade if your sllist.cpp doesn't compile with the full suite of g++ options.
• F grade if your sllist.cpp doesn't link to create an executable.
• Your implementation's output doesn't match correct output of the grader (you can see the inputs and outputs of the auto grader's tests). The auto grader will provide a proportional grade based on how many incorrect results were generated by your submission. A+ grade if output of function matches correct output of auto grader.
• A maximum of D grade if Valgrind detects even a single memory leak or error. A teaching assistance will check you submission for such errors.
• A deduction of one letter grade for each missing documentation block in sllist.cpp. Your submission must have one file-level and six function-level documentation blocks. A teaching assistant will physically read submitted source files to ensure that these documentation blocks are authored correctly. Each missing or incomplete or copy- pasted (with irrelevant information from some previous assessment) block will result in a deduction of a letter grade. For example, if the automatic grader gave your submission an A+ grade and one documentation block is missing, your grade will be later reduced from A+ to B+. Another example: if the automatic grade gave your submission a C’ grade and the two documentation blocks are missing, your grade will be later reduced from C to E.