Review

This lab is about structures, pointers and dynamic memory allocation of arrays.

Structures

A structure is, in general, a collection of heterogeneous objects - different kinds of objects. (c.f. an array which is a collection of homogeneous objects.)

Pointers

A pointer is a variable that stores the address of another variable. Also, it provides a way to pass large non-primitive data-type objects as arguments to functions. In addition, it is the essentials of dynamic memory allocation. The following shows some pointer operators.

Operator	Functions
*	Pointer declaration: To declare a variable as a pointer. Dereference: To reference the variable pointed by a pointer variable.
&	Address of: Use it before a variable to get the address of it. Reference variable declaration: Used for passing arguments by reference.
->	Member selection operator: Dereferences the pointer, then accesses its members. p->member is equivalent to (*p).member.

Dynamic Memory Allocation of Arrays

C++ allows you to create an array of objects - dynamic objects - on the fly at runtime. The memory of dynamic objects has to be allocated at runtime explicitly by you using the operator new. The dynamic objects will persist even after the object goes out of scope. Also, they have to be deallocated at runtime explicitly by you using the operator delete. Dynamic objects are managed using a data structure called heap.



The following gives an example demonstrating how to do dynamic memory allocation to create an array of pointers to objects, and all the objects. Also, it demonstrates how to deallocate the objects and array to avoid memory leak.

#include <iostream>
using namespace std;

struct Integer {
  int x;
};

int main() {
  int n;
  cout << "Number of objects: ";
  cin >> n;

  // Dynamically allocate an array of n Integer pointers and then
  // dynamically allocate n Integer objects, both using operator new

  cout << "Dynamically allocate memory ..." << endl;
  Integer** array = new Integer*[n];
  for(int i=0; i<n; ++i) {
    array[i] = new Integer;
    array[i]->x = i + 1;
  }

  cout << "Processing ..." << endl;

  // Deallocate n Integer objects and then deallocate the array of n
  // Integer pointers, both using operator delete

  cout << "Deallocate memory ..." << endl;
  for(int i=0; i<n; ++i)
    delete array[i];
  delete [] array;

  return 0;
}

New Concepts

Separate Compilation

In the labs and assignment so far you might have only seen examples of single source file, which can be compiled and run directly. In this lab, however, you'll need to combine multiple source files to build a single executable.

C++ allows you to separate code into multiple source and header files, compile them separately, and link them together to form a functioning executable, as long as you deal with the inclusion and scopes properly. Read the slides for more information. (Download: Full / 4-Page)

Queue (Abstract Data Type)

A queue is a first-in-first-out (FIFO) data structure, in the sense that the first element added to the queue will also be the first one to be removed. This behaviour resembles a queue in reality and explains its naming.

A queue usually supports the following basic operations:

• enqueue - adding an element to the back of the queue
• dequeue - removing an element from the front of the queue
• front - return the element at the front of the queue
• is empty - return whether the queue is empty

Queues are fundamental data structures and are commonly seen in many algorithms and programs. Some typical examples include BFS (breadth-first search) and buffers. One of its variants - priority queue, is also commonly used and you'll learn its possible implementation later.
Usually queues are implemented using dynamic arrays or linked-lists. In this lab you will implement a queue using a circular buffer.

Introduction

In this lab, you will simulate a transmission/receiving ring buffer for ethernet frames. It's very likely that you will see a similar structure in your operating system's network driver. Of course, this lab greatly simplifies the details to give you a rough flavour.

EthernetFrame

This structure is a simplified version of real ethernet frames.

                    
                        enum EtherType {
                            IPV4,
                            IPV6,
                            ARP
                        };

                        struct EthernetFrame {
                            EtherType type;
                            string source;
                            string destination;
                            string payload;
                        };
                    
                

We only retain the frame type, source, destination, and payload information from a full ethernet frame. To further lower the workload, we simply use strings (read the slides for more information: Full / 4-Page) for the latter three, and use an enumeration to represent a subset of real EtherTypes. You don't need to really understand the meaning of these types.

Queue

We implement a queue which contains nodes of type EthernetFrame in its internal array.

                    
                        struct Queue {
                            EthernetFrame** ring = nullptr;
                            unsigned int head = 0;
                            unsigned int size = 0;
                            unsigned int capacity = 0;
                        };
                    
                

• ring - a pointer to the internal dynamic array holding pointers to EthernetFrame

• head - index of the front element in the queue

• size - number of elements in the queue

• capacity - current size of the internal array (ring). Don't confuse it with size. A queue with capacity 10 may contains only one element or is completely empty.

The queue is implemented in a circular fashion indicating that the successor of the last element in the array is the first element in the array. Considering a queue with capacity 10, head at index 7, and size equals 4. Then the back of the queue is at index (7 + 4 - 1) mod 10 = 0.

Lab Work

Task 1 - Initialize & Swap EthernetFrame

                    
                        void initFrame(EthernetFrame& frame, const string& source, const string& destination,
                                       const string& payload, EtherType type);

                        void initFrame(EthernetFrame* frame, const string& source, const string& destination,
                                       const string& payload, EtherType type);
                    
                

Initialize a given reference or pointer to EthernetFrame with given contents. If the given pointer is null in the second function, do nothing and return.

                    
                        void swapFrames(EthernetFrame& frame1, EthernetFrame& frame2);

                        void swapFrames(EthernetFrame* frame1, EthernetFrame* frame2);
                    
                

Swap the contents of two EthernetFrame.
In the second function, do nothing and return if (1) one of the given pointers is null or (2) two pointers are identical.

Task 2 - Create & Free EthernetFrame

                    
                        EthernetFrame* createFrame(const string& source, const string& destination, const string& payload,
                                                   EtherType type);
                    
                

Dynamically allocate an EthernetFrame with given contents and return a pointer to it.

                    
                        void freeFrame(EthernetFrame* frame);
                    
                

Delete the dynamically allocated EthernetFrame.

Task 3 - Queue Operations

                    
                        void queueResizeRing(Queue& queue, unsigned int newCapacity);
                    
                

Resize the internal array of the given queue to a given new capacity.

• Dynamically allocate a new array of given size and copy the pointers in the old array to it. Remember to correctly maintain head, size and capacity.
• If the new capacity is smaller than the current size, truncate the elements towards the back of the queue. Say, you are resizing a queue with capacity 10 and size 8 to a new capacity of 5. Then the three elements at the back of the queue should be freed.

                    
                        void enqueue(Queue& queue, EthernetFrame* frame);
                    
                

Add a frame to the back of the queue. No need to check whether the pointer to frame is null.
Change the capacity of the internal array to (current queue size + 1) * 2 when necessary. Remember the queue is circular.

                    
                        void dequeue(Queue& queue);
                    
                

Remove an frame from the queue. If the queue is empty, do nothing and return. Also free the frame.

                    
                        const EthernetFrame* queueFront(const Queue& queue);

                        const EthernetFrame* queueBack(const Queue& queue);
                    
                

Return a pointer to the front or back of the queue. We guarantee to call these functions only when the queue is non-empty (accessing the front of an empty container in C++ STL is undefined behaviour - details of STL will be discussed in class later). But for the sake of defensive programming, you are advised to add a check for this and return nullptr.

                    
                        bool queueIsEmpty(const Queue& queue);
                    
                

Check whether the given queue is empty. If so, return true. Otherwise, return false.

                    
                        void freeQueue(Queue& queue);
                    
                

The name of the function might be misleading. What you need to do is actually clearing the queue - free all the frames it contains (if any), free the array, and set other attributes of the queue correspondingly. Do not delete the queue itself.

Resources & Sample I/O

• Skeleton code: lab3_skeleton.zip
• Demo program: Windows / MacOS

Sample I/O

Your program should produce the following output. You may wish to compare your output against the expected output using a diff checker.

                    
                        Testing task 1...
ARP, ec:98:57:12:34:56 > ff:ff:ff:ff:ff:ff: Request who-has 10.0.0.1 tell 10.0.2.1
ARP, 12:c4:87:d1:ca:39 > ff:ff:ff:ff:ff:ff: Reply 10.0.0.1 is-at 12:c4:87:d1:ca:39
ARP, 12:c4:87:d1:ca:39 > ff:ff:ff:ff:ff:ff: Reply 10.0.0.1 is-at 12:c4:87:d1:ca:39
ARP, ec:98:57:12:34:56 > ff:ff:ff:ff:ff:ff: Request who-has 10.0.0.1 tell 10.0.2.1
ARP, ec:98:57:12:34:56 > ff:ff:ff:ff:ff:ff: Request who-has 10.0.0.1 tell 10.0.2.1
ARP, 12:c4:87:d1:ca:39 > ff:ff:ff:ff:ff:ff: Reply 10.0.0.1 is-at 12:c4:87:d1:ca:39
ARP, 12:c4:87:d1:ca:39 > ff:ff:ff:ff:ff:ff: Reply 10.0.0.1 is-at 12:c4:87:d1:ca:39
ARP, ec:98:57:12:34:56 > ff:ff:ff:ff:ff:ff: Request who-has 10.0.0.1 tell 10.0.2.1
Task 1 tests complete.
Testing task 2...
IPv4, cc:12:92:34:de:2f > 12:34:56:78:90:ab: Dynamically allocated
Task 2 tests complete.
Testing task 3...
empty
front: IPv6, 88:10:98:20:a8:30 > 86:c:92:18:9e:24: 1
back: IPv6, 88:10:98:20:a8:30 > 86:c:92:18:9e:24: 1
front: ARP, 99:32:cb:64:fd:96 > 93:26:b9:4c:df:72: 2
back: IPv4, aa:54:fe:a8:52:fc > a0:40:e0:80:20:c0: 3
front: IPv4, aa:54:fe:a8:52:fc > a0:40:e0:80:20:c0: 3
back: ARP, cc:98:64:30:fc:c8 > ba:74:2e:e8:a2:5c: 5
front: IPv6, bb:76:31:ec:a7:62 > ad:5a:7:b4:61:e: 4
back: IPv6, ee:dc:ca:b8:a6:94 > d4:a8:7c:50:24:f8: 7
front: ARP, cc:98:64:30:fc:c8 > ba:74:2e:e8:a2:5c: 5
back: IPv4, 10:20:30:40:50:60 > ee:dc:ca:b8:a6:94: 9
front: IPv4, dd:ba:97:74:51:2e > c7:8e:55:1c:e3:aa: 6
back: ARP, 32:64:96:c8:fa:2c > 08:10:18:20:28:30: 11
front: IPv6, ee:dc:ca:b8:a6:94 > d4:a8:7c:50:24:f8: 7
back: IPv6, 54:a8:fc:50:a4:f8 > 22:44:66:88:aa:cc: 13
front: ARP, ff:fe:fd:fc:fb:fa > e1:c2:a3:84:65:46: 8
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: IPv4, 10:20:30:40:50:60 > ee:dc:ca:b8:a6:94: 9
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: IPv6, 21:42:63:84:a5:c6 > fb:f6:f1:ec:e7:e2: 10
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: ARP, 32:64:96:c8:fa:2c > 08:10:18:20:28:30: 11
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: IPv4, 43:86:c9:c:4f:92 > 15:2a:3f:54:69:7e: 12
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: IPv6, 54:a8:fc:50:a4:f8 > 22:44:66:88:aa:cc: 13
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: ARP, 65:ca:2f:94:f9:5e > 2f:5e:8d:bc:eb:1a: 14
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
front: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
back: IPv4, 76:ec:62:d8:4e:c4 > 3c:78:b4:f0:2c:68: 15
empty
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: ARP, 2c:58:84:b0:dc:8 > 9a:34:ce:68:2:9c: 101
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv4, 3d:7a:b7:f4:31:6e > a7:4e:f5:9c:43:ea: 102
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, 4e:9c:ea:38:86:d4 > b4:68:1c:d0:84:38: 103
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: ARP, 5f:be:1d:7c:db:3a > c1:82:43:4:c5:86: 104
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv4, 70:e0:50:c0:30:a0 > ce:9c:6a:38:6:d4: 105
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, 81:2:83:4:85:6 > db:b6:91:6c:47:22: 106
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: ARP, 92:24:b6:48:da:6c > e8:d0:b8:a0:88:70: 107
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv4, a3:46:e9:8c:2f:d2 > f5:ea:df:d4:c9:be: 108
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, b4:68:1c:d0:84:38 > 02:4:6:8:a:c: 109
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: ARP, c5:8a:4f:14:d9:9e > 0f:1e:2d:3c:4b:5a: 110
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv4, d6:ac:82:58:2e:4 > 1c:38:54:70:8c:a8: 111
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, e7:ce:b5:9c:83:6a > 29:52:7b:a4:cd:f6: 112
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: ARP, f8:f0:e8:e0:d8:d0 > 36:6c:a2:d8:e:44: 113
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv4, 09:12:1b:24:2d:36 > 43:86:c9:c:4f:92: 114
front: IPv6, 1b:36:51:6c:87:a2 > 8d:1a:a7:34:c1:4e: 100
back: IPv6, 1a:34:4e:68:82:9c > 50:a0:f0:40:90:e0: 115
front: IPv4, 3d:7a:b7:f4:31:6e > a7:4e:f5:9c:43:ea: 102
back: ARP, bf:7e:3d:fc:bb:7a > a1:42:e3:84:25:c6: 200
front: ARP, 5f:be:1d:7c:db:3a > c1:82:43:4:c5:86: 104
back: IPv4, d0:a0:70:40:10:e0 > ae:5c:a:b8:66:14: 201
front: IPv6, 81:2:83:4:85:6 > db:b6:91:6c:47:22: 106
back: IPv6, e1:c2:a3:84:65:46 > bb:76:31:ec:a7:62: 202
front: IPv4, a3:46:e9:8c:2f:d2 > f5:ea:df:d4:c9:be: 108
back: ARP, f2:e4:d6:c8:ba:ac > c8:90:58:20:e8:b0: 203
front: ARP, c5:8a:4f:14:d9:9e > 0f:1e:2d:3c:4b:5a: 110
back: IPv4, 03:6:9:c:f:12 > d5:aa:7f:54:29:fe: 204
front: IPv6, e7:ce:b5:9c:83:6a > 29:52:7b:a4:cd:f6: 112
back: IPv6, 14:28:3c:50:64:78 > e2:c4:a6:88:6a:4c: 205
front: IPv4, 09:12:1b:24:2d:36 > 43:86:c9:c:4f:92: 114
back: ARP, 25:4a:6f:94:b9:de > ef:de:cd:bc:ab:9a: 206
front: nullptr
back: IPv4, 36:6c:a2:d8:e:44 > fc:f8:f4:f0:ec:e8: 207
front: ARP, bf:7e:3d:fc:bb:7a > a1:42:e3:84:25:c6: 200
back: IPv6, 47:8e:d5:1c:63:aa > 09:12:1b:24:2d:36: 208
front: IPv6, e1:c2:a3:84:65:46 > bb:76:31:ec:a7:62: 202
back: ARP, 58:b0:8:60:b8:10 > 16:2c:42:58:6e:84: 209
front: IPv4, 03:6:9:c:f:12 > d5:aa:7f:54:29:fe: 204
back: IPv4, 69:d2:3b:a4:d:76 > 23:46:69:8c:af:d2: 210
front: ARP, 25:4a:6f:94:b9:de > ef:de:cd:bc:ab:9a: 206
back: IPv6, 7a:f4:6e:e8:62:dc > 30:60:90:c0:f0:20: 211
front: IPv6, 47:8e:d5:1c:63:aa > 09:12:1b:24:2d:36: 208
back: ARP, 8b:16:a1:2c:b7:42 > 3d:7a:b7:f4:31:6e: 212
front: IPv4, 69:d2:3b:a4:d:76 > 23:46:69:8c:af:d2: 210
back: IPv4, 9c:38:d4:70:c:a8 > 4a:94:de:28:72:bc: 213
front: ARP, 8b:16:a1:2c:b7:42 > 3d:7a:b7:f4:31:6e: 212
back: IPv6, ad:5a:7:b4:61:e > 57:ae:5:5c:b3:a: 214
front: IPv6, ad:5a:7:b4:61:e > 57:ae:5:5c:b3:a: 214
back: ARP, be:7c:3a:f8:b6:74 > 64:c8:2c:90:f4:58: 215
front: ARP, be:7c:3a:f8:b6:74 > 64:c8:2c:90:f4:58: 215
back: ARP, be:7c:3a:f8:b6:74 > 64:c8:2c:90:f4:58: 215
empty
Task 3 tests complete.


                    
                

Submission & Grading

• Deadline: Friday, 8^th October 2021 23:59.
• You may earn 1 point for each lab via Automated Grading on the ZINC Online Submission System.
• Please check here for a usage overview of ZINC.
• Rename your folder as lab3 containg two source files, Queue.cpp and EthernetFrame.cpp, and then zip lab3 as lab3.zip for submission to ZINC.
  • You need to name your folder as lab3 otherwise ZINC cannot find the file.
  • How to create a zip file in Windows 10.
  • How to create a zip file in macOS.
  • Just zip lab3, a folder containing only Queue.cpp and EthernetFrame.cpp .