CSE 240 Module 6

1. Memory Management & Garbage Collection

Garbage Collection in C/C++

Critical Rules:

C/C++ programmers must correctly decide when to free unused memory created with malloc()/new
Memory leakage happens if programmer forgets to free()/delete unused memory
For each malloc()/new, one must use corresponding free()/delete
Number of free()/delete used should equal number of malloc()/new used

Garbage Collection Comparison

Language	Garbage Collection	Advantages	Disadvantages
Java	Automatic (reference counter)	No manual memory management needed	May not run often enough, bad for real-time systems
C++	Manual (programmer controlled)	Complete control over timing	Memory leaks, dangling references possible

Binary Tree Deletion Example

void dTree(TreeNode *p) {
    if (p == 0) return;
    if (p->left != 0)        // size-m problem
        dTree(p->left);
    if (p->right != 0)       // size-m problem  
        dTree(p->right);
    delete p;                // What traversing order is used?
    return;
}

Answer: This uses postorder traversal - deletes children first, then parent.

Deleting Collection of Objects

Best Practices:

Linked List: Use loop with temporal pointer, delete forwards or backwards
Tree: Use pre-order, in-order, or post-order traversing to delete each node
Array/Array of Arrays: Delete array, then each pointer, then each structure

// Deleting Linked List Step by Step (While-Loop)
temp = head;
while (temp != NULL) {
    temp = temp->next;
    delete head;        // C uses free(head);
    head = temp;
}

2. Constructors & Destructors

Constructor Basics

Constructor Properties:

Function whose name is same as class name
Used to automatically initialize objects
Special kind of member function
Automatically called when object declared
Must have same name as class
Cannot return a value; not even void
Must be in public section
Can be overloaded with different parameters

Constructor Example

class Queue {
private:
    int queue_size;
protected:
    int *buffer;
    int front;
    int rear;
public:
    Queue(void) {           // Default constructor
        front = 0; rear = 0;
        queue_size = 0;
        buffer = NULL;
    }
    
    Queue(int n) {          // Constructor overload
        front = 0; rear = 0;
        queue_size = n;
        buffer = new int[queue_size];
    }
    
    virtual ~Queue(void) {  // Destructor (~ tilde)
        delete buffer;
        buffer = NULL;
    }
};

Destructor Basics

Destructor Properties:

Opposite of constructor
Automatically called when object is out-of-scope
Default version only removes ordinary variables, not dynamic variables
Dynamically-allocated variables don't go away until "deleted"
Destructors help to "deallocate" them when object destroyed
Defined like constructor, just add ~ (tilde)

Responsibilities of Garbage Collection

Class Writer vs Class User:

Class Writer: If heap memory (new()) used in constructor, destructor must delete the memory
Class Users: NOT responsible for garbage collection of memory they didn't explicitly create
Rule: Number of deletes must equal number of new()s

3. Memory Types (Stack, Heap, Static)

Program Memory Partition

OS Memory Allocation

┌─────────────────────┐ ← Starting Address
│ Program Code │ (size known at compilation)
├─────────────────────┤
│ Global & Static │ (size known at compilation)
│ Variables & Objects │
├─────────────────────┤ ← Heap Pointer
│ Heap │ (Variables created with malloc/new)
│ ↓ │
│ ↑ │
│ Stack │ (Local variables & functions)
└─────────────────────┘ ← Stack Pointer

Memory Management Rules

Memory Type	Allocation	Variables	Lifetime
Static Memory	Compilation time	Global variables, static local variables	Entire program execution
Stack	Function calls	Non-static local variables	Function scope
Heap	Dynamic (malloc/new)	Dynamically allocated variables	Until free/delete called

Stack Memory for Function Calls

Stack Frame Components:

sp: stack pointer
fp: frame pointer (access local variables)
Return address: saved for function return
Local variables: stored in frame

Before Call → Save Return Address → Make Frame
┌──────────┐ ┌──────────────┐ ┌─────────────┐
│ occupied │ │ return addr │ │ stack frame │
└──────────┘ │ occupied │ │ return addr │
└──────────────┘ │ occupied │
└─────────────┘

Static Memory Usage

void login() {
    static int counter = 0;     // initialized only once
    if (verified()) counter++;  // count # of users logged in
}

Static Local vs Global Variables:

Readability: Static local puts declaration where variable used
Security: Prevents other functions from accessing the variable
Alternative: Put login/logout in one class with static class variable

4. Object-Oriented Programming Concepts

Core OOP Principles

Information Hiding

Details of how operations work not known to "user" of class

Data Abstraction

Details of how data is manipulated within ADT/class not known to user

Encapsulation: Bring together data and operations, but keep "details" hidden

Object-Oriented Paradigm Features

Abstract data type (class): Encapsulation of state accessible only through defined operations
Inheritance: Extending class by keeping unchanged parts, allowing code reusability
Classes organized in hierarchies
Dynamic memory allocation and de-allocation
Dynamic binding
Polymorphism

Classes vs Objects

Key Concepts:

Class: Defines data type based on data and functions that operate on it
Object: Instance of a class that represents the data and its functions
Analogy: Class is like a blueprint, objects are houses built from blueprint
Focus: Object-oriented programming focuses on objects containing data and operations

Programming Paradigm Comparison

Program = Algorithm + Data

Imperative Paradigm: Process (steps) of data manipulation
Object-Oriented Paradigm: Objects of the manipulation

5. Class Definition & Implementation

Class Definition Structure

class Queue {
private:                    // Data almost always private
    int queue_size;
protected:                  // For family members (inheritance)
    int *buffer;
    int front;
    int rear;
public:                     // Member functions almost always public
    void enqueue(int v) {...}
    int dequeue(void) {...}
    bool compact(void);     // Can be implemented outside
};

Access Specifiers

Access Control Rules:

public Data Members: Almost always private (uphold OOP principles)
public Member Functions: Almost always public (user-accessible)
private Members: Accessible only by member functions and friends
protected Members: Accessible by member functions, friends, and derived classes

Implementation Options

In-class Implementation

class Queue {
public:
    int getRear() { return rear; }      // Getter
    void setRear(int value) {           // Setter
        rear = value; 
    }
};

Advantage: More efficient for short functions

Out-class Implementation

void Queue::enqueue(int v) {
    if (rear < queue_size)
        buffer[rear++] = v;
    else
        cout << "Need to compact queue" << endl;
}

Advantage: Structurally clearer separation

Scope Resolution Operator (::)

class_name::function_name

Used when implementation of member functions are separated from class definition.

void Queue::enqueue(int v) {    // Implementation outside class
    if (rear < queue_size)
        buffer[rear++] = v;
    else
        cout << "Need to compact queue before inserting" << endl;
}

Class as Data Type

Class Usage:

Class is full-fledged type (like int, double, etc.)
Can have variables of class type (called "objects")
Can have parameters of class type (pass-by-value, pass-by-reference)
Can use class type like any other type

// Class Declaration and Usage
Queue MyQueue;                    // Stack allocation
Queue *MyQueuePtr = new Queue();  // Heap allocation

MyQueue.buffer = new int[5];      // Direct access
MyQueue.enqueue(10);

MyQueuePtr->buffer = new int[5];  // Pointer access
MyQueuePtr->enqueue(10);

6. Access Control & Information Hiding

Information Hiding Levels

Access Level	Accessible By	Usage
public	Any functions (even outside class)	Interface functions
protected	Member functions, friends, derived classes	Inheritance support
private	Member functions and friends only	Internal data and helper functions

Best Practices

Design Guidelines:

Data Members: Almost always private to hide data from user
Member Functions: Almost always public (unless helper functions)
Organization: Place public first for easy viewing by programmers
Private Data: "Hidden" so irrelevant to users

7. Practical Examples

Complete Queue Class Implementation

class Queue {
private:
    int queue_size;
protected:
    int *buffer;
    int front;
    int rear;
public:
    // Constructors
    Queue(int n) {
        front = 0; rear = 0;
        queue_size = n;
        buffer = new int[queue_size];
    }
    
    // Destructor
    ~Queue() {
        delete buffer;
    }
    
    // Member functions
    void enqueue(int value);
    int dequeue();
    bool compact(void);
};

Circular (Cyclic) Queue

Empty Queue: front == rear
┌─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 2 │ n-2 │ n-1 │
└─────┴─────┴─────┴─────┴─────┘
↑
front/rear

Full Queue: (rear + 1) % n == front
┌─────┬─────┬─────┬─────┬─────┐
│ ● ● │ ● ● │ ● ● │ ● ● │ ● ● │
└─────┴─────┴─────┴─────┴─────┘
↑ ↑
front rear

Circular Queue Benefits:

Each queue operation may take slightly longer time
No penalty when queue is falsely full
Better memory utilization

Time Class Example

#include 
using namespace std;

class Time {
public:
    Time();                          // default constructor
    void setTime(int, int);          // set hour, minute
    void printMilitary();           // print military time format
    void printStandard();           // print standard time format
private:
    int hour;                       // 0 - 23
    int minute;                     // 0 - 59
};

Memory Leak Detection Exercise

Common Memory Leak Scenarios:

Missing free()/delete: Memory allocated but never freed
Lost pointers: Overwriting pointer before freeing memory
Exception handling: Memory allocated before exception thrown
Circular references: Objects referencing each other

// Example: Memory leak in insertion
void insertion() {
    struct actor *c; char *n;
    c = malloc(sizeof(struct actor));
    if (c == 0) {
        printf("out of memory\n"); return -1;
    }
    n = get_name();           // ← Memory leak if get_name() allocates
    strcpy(c->name, n);       // ← Should free(n) here!
    c->next = head;
    head = c;
    return 1;
}

Table of Contents