3. Memory Representation and Resource Management

Introduction and Context

A data structure is not merely an abstract arrangement of values. In a C program, every array, linked list, tree, graph, and stack ultimately exists as a pattern of bytes in memory. The efficiency and correctness of an algorithm therefore depend not only on its logical design but also on how memory is allocated, addressed, accessed, and released.

C is particularly important for studying memory because it exposes the relationship between program variables and machine memory. Unlike managed languages, C does not automatically determine the lifetime of every object or prevent all invalid accesses. The programmer must understand storage duration, addresses, pointer arithmetic, alignment, allocation interfaces, ownership, and deallocation. These responsibilities provide considerable control and performance, but they also create risks such as dangling pointers, buffer overflows, double frees, memory leaks, and undefined behavior.

This chapter examines memory representation and resource management as foundations for implementing data structures through algorithms. It connects abstract data structures with their physical representation and develops a disciplined approach to safe and efficient memory use.

Learning Objectives

After studying this chapter, a student should be able to:

1. distinguish stack, heap, static, and automatic storage in C;

2. explain object representation, addresses, alignment, and padding;

3. perform pointer arithmetic correctly and identify invalid pointer operations;

4. use `malloc`, `calloc`, `realloc`, and `free` safely;

5. reason about ownership, lifetime, aliasing, and memory safety;

6. analyze cache locality and fragmentation in data-structure implementations;

7. identify and diagnose leaks, use-after-free errors, and buffer violations;

8. select memory-management strategies appropriate to professional software systems.

From Abstract Data Structures to Physical Memory

An abstract data type specifies behavior. For example, a stack supports operations such as push, pop, and top, without requiring a particular representation. An implementation chooses a physical organization: a contiguous array, a linked list, or a dynamically resized block. That choice determines memory overhead, locality, resizing cost, and failure modes.

A C object occupies a region of storage with a size, an address, an alignment requirement, and a lifetime. The value of an object is represented by one or more bytes. The `sizeof` operator reports the number of bytes required for an object or type, while the address-of operator, `&`, produces the address of an object. A pointer stores an address-like value that can be used to refer to an object of a compatible type.

For example:

```c

int count = 42;

int *p = &count;

printf("%d\n", *p);

```

Here, `count` is an `int` object, `p` contains its address, and `p` accesses the object referred to by `p`. The pointer itself occupies storage separate from the object it designates. Changing `p` does not change `count`; changing `p` does.

Memory is byte-addressable on conventional systems, but a byte is not necessarily the same as an integer or pointer. The C language defines sizes and representation rules in terms of implementation-dependent characteristics. Consequently, portable programs use `sizeof`, correct type conversions, and standard library facilities rather than assuming that an `int` always occupies a particular number of bytes.

Storage Duration and the Main Memory Regions

C objects have storage duration, which describes how long their storage exists. The four important categories are automatic, static, allocated, and thread storage duration. In ordinary data-structure programming, the first three are especially significant.

Automatic storage and the call stack

Local variables declared inside a function or block normally have automatic storage duration. Their storage is created when execution enters the relevant block and ceases to exist when execution leaves it. Implementations commonly place such objects in a region called the stack.

```c

void process(void) {

int values[100];

/ values exists only during this invocation /

}

```

The stack is efficient because allocation and release generally follow a last-in, first-out discipline. Function parameters, return information, and local variables are often managed through stack frames. However, the C language does not require a particular stack implementation, and a large local array may exhaust available stack space.

Returning the address of an automatic object is invalid:

```c

int *incorrect(void) {

int value = 10;

return &value; / invalid after the function returns /

}

```

After return, `value` no longer exists. The resulting pointer is dangling, even if its numerical address appears unchanged.

Static storage

Objects with static storage duration exist for the entire execution of the program. This includes file-scope variables and variables declared with the `static` keyword inside a function. They are initialized before program startup; if no explicit initializer is supplied, they are initialized to zero.

```c

static unsigned long comparisons;

void record_comparison(void) {

comparisons++;

}

```

Static storage is useful for persistent state, lookup tables, and objects whose lifetime must span multiple function calls. It can also reduce reentrancy and thread-safety because shared state is accessible across calls. File-scope `static` additionally restricts visibility to the current translation unit, supporting encapsulation.

Allocated storage and the heap

Allocated storage is obtained dynamically during program execution. The standard library functions `malloc`, `calloc`, and `realloc` request storage, while `free` releases it. Implementations commonly obtain such storage from an area called the heap, although the C standard specifies behavior rather than a single physical memory region.

Dynamic storage is essential when the required size is unknown at compile time or when an object must outlive the function that created it. A linked-list node is a typical example:

```c

struct Node {

int value;

struct Node *next;

};

struct Node node = malloc(sizeof node);

if (node != NULL) {

node->value = 7;

node->next = NULL;

}

```

The allocated object remains alive until `free(node)` is called. This flexibility creates an explicit resource-management obligation: every successful allocation must have a clear eventual owner and release path.

Representation, Alignment, and Padding

A type has an alignment requirement: an address boundary at which objects of that type may be efficiently or validly stored. For example, a processor may prefer an `int` to begin at an address divisible by four. The implementation may insert padding between structure members or at the end of a structure to satisfy alignment.

```c

struct Record {

char flag;

int value;

char code;

};

```

The size of this structure may exceed the sum of the sizes of its members because padding can occur before `value` and after `code`. The expression `sizeof(struct Record)` is therefore the correct way to determine its size. Member order can affect size:

```c

struct CompactRecord {

int value;

char flag;

char code;

};

```

Reordering members may reduce internal padding, although layout decisions must not compromise clarity or an external binary interface. Excessive use of packed layouts can cause misaligned accesses and slower execution; it may also be nonportable.

Alignment matters when allocating raw storage, embedding objects, interpreting serialized data, or using custom allocators. Standard allocation functions return storage suitably aligned for any object type whose size is requested through the normal interfaces. Problems arise when programmers manually manipulate addresses or cast arbitrary byte buffers without respecting alignment and effective type rules.

The representation of multi-byte values can also depend on byte order, commonly called endianness. Algorithms that store values in memory and later transmit or persist their bytes should define an explicit serialization format rather than copying internal representations blindly.

Pointer Arithmetic and Address Computation

Pointer arithmetic is defined in terms of elements, not raw bytes. If `p` points to element zero of an array, then `p + 1` points to the next element, at an address increased by `sizeof(*p)` bytes. Subtraction of two pointers is meaningful only when both point into the same array object, or one position past its final element.

```c

int a[4] = {10, 20, 30, 40};

int *p = a;

int second = (p + 1); / 20 */

size_t distance = &a[3] - &a[0]; / 3 /

```

The expression `a[i]` is defined in terms of pointer arithmetic: it is equivalent to `*(a + i)`. A pointer may point one position past an array, which is useful as an endpoint in loops, but that pointer must not be dereferenced.

Pointer arithmetic outside the bounds of a single array object is undefined, even if the resulting numerical address appears reasonable. In particular, treating a pointer to a standalone scalar as if it referred to an array of several scalars is invalid. Casts do not make an invalid access valid.

The type of a pointer determines how arithmetic and dereferencing operate. Incrementing an `int ` advances by one `int`, whereas incrementing a `char ` advances by one byte. A `void *` can hold an object address, but it must generally be converted to an appropriate object-pointer type before dereferencing. C permits conversion between object pointer types subject to alignment and access rules; it does not guarantee that every cast preserves a meaningful interpretation.

Dynamic Allocation as a Managed Process

Dynamic allocation should be treated as a lifecycle rather than as an isolated function call. A reliable process includes determining the required size, checking for overflow, allocating, initializing, using, transferring ownership if necessary, and releasing exactly once.

Allocation functions

`malloc(n)` allocates `n` bytes with indeterminate contents. `calloc(count, size)` allocates space for an array of `count` objects and initializes all bits to zero; zero bits are not universally equivalent to a null pointer or floating-point zero, so semantic initialization may still be required. `realloc(ptr, new_size)` attempts to resize a previously allocated block. It may move the block, in which case the old pointer becomes invalid after successful reallocation.

A safe resizing pattern is:

```c

int temporary = realloc(array, new_capacity sizeof *array);

if (temporary != NULL) {

array = temporary;

capacity = new_capacity;

}

```

If `realloc` fails, the original block remains allocated and must still be freed later. Assigning directly to `array` would lose that address and create a leak. In production code, multiplication used to calculate allocation size should also be checked for integer overflow before it is passed to an allocator.

Ownership and lifetime

Ownership answers a practical question: which component is responsible for releasing an object? A pointer may be borrowed temporarily, transferred to another component, or retained as a shared reference under an explicit convention. C does not enforce ownership, so interfaces and documentation must do so.

For a linked list, a list object may own all nodes reachable from its head. A traversal function may borrow a node pointer but must not free it. If a function removes a node, ownership may transfer to the caller, who then decides whether to inspect or release it. Ambiguous ownership is a major source of leaks and double frees.

A useful discipline is to document, for each pointer parameter and return value, whether the pointer is owned, borrowed, nullable, or required to remain valid for a specified period. Naming conventions and opaque types can reinforce these contracts.

Memory Safety and Undefined Behavior

Memory safety concerns whether every access refers to a valid object, within its lifetime and bounds, with an appropriate type and alignment. Common violations include:

• accessing an array outside its bounds;
• dereferencing a null or uninitialized pointer;
• using a pointer after its object has been freed;
• freeing the same allocation twice;
• freeing memory not obtained from an allocation function;
• reading uninitialized bytes;
• returning or storing the address of an expired automatic object;
• modifying a string literal through a non-constant pointer.

These errors produce undefined behavior. Undefined behavior does not mean merely that an operation returns an unpredictable value; the compiler may assume that such behavior never occurs and optimize accordingly. A program that appears correct in a debug build may fail under optimization or on another machine.

Consider:

```c

int p = malloc(sizeof p);

if (p != NULL) {

*p = 5;

free(p);

p = NULL;

}

```

Setting `p` to `NULL` after freeing prevents this particular pointer from being accidentally reused, but it does not invalidate other aliases to the same allocation. Therefore, nulling one pointer is not a complete solution to ownership problems.

Locality, Performance, and Fragmentation

Memory management affects algorithmic performance beyond asymptotic complexity. Modern processors move data between main memory and caches in blocks called cache lines. Accesses with spatial locality use nearby addresses and often perform well; accesses with temporal locality reuse recently accessed data.

A contiguous array usually provides strong spatial locality. Iterating through an array of structures can be efficient when each operation uses most fields. An array of structures (AoS) may be less suitable when an algorithm repeatedly accesses only one field; a structure of arrays (SoA) can place the frequently used field contiguously and improve cache utilization.

Linked lists provide flexible insertion and deletion, but nodes allocated independently may be scattered across the heap. Traversal then follows pointers to unrelated cache lines, causing more cache misses and reducing prefetching opportunities. Thus, the same theoretical `O(n)` traversal can have substantially different practical performance depending on layout.

Fragmentation is another concern. External fragmentation occurs when free memory is divided into separated blocks, preventing a large request even though the total free memory is sufficient. Internal fragmentation occurs when an allocated block is larger than requested because of alignment or allocator size classes. Frequent allocation and release of many differently sized objects can increase both overhead and fragmentation.

Strategies such as pools, arenas, object caches, and slab-like allocators address predictable allocation patterns. A pool allocates a large region and divides it into fixed-size objects. An arena releases many related objects together, reducing per-object deallocation costs. These strategies improve locality and simplify ownership, but they require careful lifetime design and may retain memory longer than individual deallocation would.

Detecting Leaks and Diagnosing Failures

A memory leak occurs when allocated storage remains reachable neither through a valid program reference nor through a planned ownership structure. Leaks gradually increase memory consumption and may cause service degradation or termination. A leak is different from fragmentation: a leaked block is still considered allocated, whereas fragmentation concerns the arrangement of allocated and free regions.

Diagnosis should combine code review, tests, instrumentation, and runtime tools. Compiler warnings and sanitizers can detect many invalid accesses. AddressSanitizer commonly identifies out-of-bounds access, use-after-free, and double-free errors. Leak detectors report allocations that remain unreleased at program termination. A debugger can inspect pointer values and allocation paths, while profiling tools can reveal growth over time.

Testing should exercise failure paths, not only successful operations. For a dynamic array, tests should include zero capacity, repeated growth, allocation failure, removal from an empty structure, and destruction of partially initialized objects. Cleanup code should be safe when called after an incomplete operation.

A practical review procedure is:

1. identify every allocation site;

2. record the owner immediately after successful allocation;

3. trace all return, error, and exception-like paths;

4. verify that ownership is transferred or released exactly once;

5. test boundary conditions and allocation failures;

6. run sanitizers and leak analysis on representative workloads.

An Illustrative Case: A Resizable Work Queue

Background

A server component maintains a queue of integer job identifiers. The first implementation uses a dynamically resized array. The queue begins with a capacity of eight elements and doubles its capacity whenever it becomes full.

Situation and Problem

After several hours, the process consumes increasing amounts of memory. Under a stress test, some jobs also appear corrupted. Investigation finds code similar to:

```c

q->items = realloc(q->items,

q->capacity 2 sizeof(int));

q->capacity *= 2;

```

The code has two defects. First, a failed `realloc` overwrites the only pointer to the original block. Second, arithmetic may overflow for very large capacities. A separate dequeue operation stores a pointer to an element, then triggers a resize elsewhere; the stored pointer becomes invalid if reallocation moves the array.

Analysis

The queue owns its `items` block, so the block must remain associated with the queue unless resizing succeeds. Any pointer into the block is a borrowed address whose validity ends if `realloc` moves the block. The queue should expose indices or copied values rather than long-lived internal element pointers.

Approach and Solution

A safer growth operation calculates the new capacity only after checking that multiplication is representable, uses a temporary pointer, and updates queue metadata only after success:

```c

bool grow(struct Queue *q) {

if (q->capacity > SIZE_MAX / 2)

return false;

size_t new_capacity = q->capacity * 2;

if (new_capacity > SIZE_MAX / sizeof *q->items)

return false;

int *new_items = realloc(q->items,

new_capacity sizeof q->items);

if (new_items == NULL)

return false;

q->items = new_items;

q->capacity = new_capacity;

return true;

}

```

The queue destructor releases the array once and sets the pointer to `NULL`. Dequeue returns an integer by value, not an internal pointer. Tests simulate allocation failure and verify that the original queue remains usable when growth fails.

Outcome

The revised design prevents loss of the original allocation, avoids stale element pointers, and gives callers a clear failure result. Runtime sanitizers confirm that operations remain within bounds and that destruction releases all queue storage.

Learning Points

The case demonstrates that resource management is part of data-structure design. A theoretically efficient resizing policy is not sufficient unless allocation failure, pointer invalidation, integer overflow, and ownership are addressed. It also illustrates why an abstract interface should hide representation details that could expose unstable addresses.

Professional Practice, Governance, and Emerging Directions

In professional systems, memory management is both a technical and governance concern. Security vulnerabilities frequently arise from buffer overflows, use-after-free, and incorrect length calculations. Code review standards should require explicit ownership conventions, checked sizes, cleanup paths, and tests for malformed input. Sensitive data may also require deliberate clearing before release, although compiler optimization can complicate naïve clearing techniques; approved secure-memory utilities should be used when confidentiality demands it.

Build pipelines should enable strong warnings and suitable sanitizers during testing. Static analysis can identify suspicious pointer flows, unchecked allocation results, and possible leaks. In safety-critical or security-sensitive environments, coding standards may restrict casts, variable-length operations, or unrestricted dynamic allocation. The appropriate policy depends on predictability, latency, certification, and threat requirements.

Contemporary systems increasingly combine manual memory management with safer abstractions. C projects may adopt ownership conventions, opaque handles, arena allocators, or wrapper APIs. Other components may be implemented in memory-safe languages and interact with C through carefully specified foreign-function interfaces. Automated tools, including static analyzers and fuzzing systems, can explore memory-related failures, but they do not replace sound design: tools may miss paths, while ownership and lifetime remain architectural decisions.

Best Practices for C Data Structures

The following practices provide a practical standard for implementation:

• use `sizeof *pointer` rather than repeating a type name in allocation expressions;
• check every allocation before dereferencing the result;
• use temporary pointers for `realloc`;
• check multiplication and addition used in size calculations;
• define one clear owner for every dynamically allocated object;
• document whether interfaces borrow, transfer, or retain pointers;
• keep lifetimes as short and predictable as practical;
• avoid exposing internal pointers when resizing can invalidate them;
• initialize fields before publication to other code or threads;
• release partially constructed objects safely on failure;
• prefer contiguous storage when access patterns benefit from locality;
• use pools or arenas when allocation patterns are stable and lifetimes are related;
• compile with warnings and test with sanitizers and leak detection;
• treat warnings and undefined behavior reports as defects, not cosmetic issues.

Chapter Summary

Memory representation gives physical meaning to data structures implemented in C. Automatic objects commonly live for a block or function invocation, static objects for the entire program, and dynamically allocated objects until explicitly released. Pointers provide access to objects but do not themselves establish ownership or extend lifetime. Correct pointer arithmetic is limited by array boundaries, while alignment and padding affect object size and layout.

Dynamic allocation requires a complete lifecycle: calculate a safe size, allocate, initialize, use, transfer ownership where necessary, and release exactly once. Memory safety depends on respecting bounds, lifetime, type, and alignment. Arrays often provide superior cache locality compared with pointer-heavy linked structures, while pools and arenas can reduce allocation overhead and fragmentation for suitable workloads. Leak detection, sanitizers, static analysis, and disciplined review are essential professional practices. Ultimately, resource management is not an afterthought; it is part of the correctness, performance, security, and maintainability of every C data structure.

Key Terms

Storage duration: The period during which an object’s storage exists.

Automatic storage: Storage normally associated with block-local objects whose lifetime ends when execution leaves the block.

Static storage: Storage that exists for the entire execution of a program.

Allocated storage: Storage obtained dynamically through allocation functions and released explicitly.

Stack: A commonly used region supporting function-call frames and automatic storage.

Heap: A commonly used region from which dynamic allocations are obtained.

Pointer: An object that stores a value used to refer to another object or function according to language rules.

Pointer arithmetic: Address calculation defined in units of the pointed-to type within an array object.

Alignment: A requirement or preference that an object begin at a suitable address boundary.

Padding: Unused bytes inserted into a structure to satisfy alignment or layout requirements.

Object lifetime: The interval during which an object exists and may validly be accessed.

Ownership: Responsibility for managing an allocated object and eventually releasing it.

Dangling pointer: A pointer whose referenced object no longer exists or is no longer valid.

Memory leak: Allocated storage that is no longer usefully reachable and has not been released.

Fragmentation: Inefficient division of memory into allocated and free regions or oversized blocks.

Cache locality: The tendency of a program to access memory near recently accessed or repeatedly used data.

Undefined behavior: Program behavior for which the C standard imposes no requirements.

Sanitizer: A compiler-supported runtime instrumentation facility for detecting classes of programming errors.

Arena allocator: An allocator that groups allocations and releases them collectively.

Effective resource management: Coordinated allocation, use, ownership, validation, and release of program resources.

Review Questions

Short Answer Questions

1. What is the difference between automatic storage duration and static storage duration?

2. Why can a pointer to a local variable become dangling after a function returns?

3. What does `sizeof *p` express in a dynamic allocation statement?

4. Why must pointer subtraction generally involve elements of the same array?

5. Distinguish a memory leak from external fragmentation.

Long Answer Questions

1. Explain the relationship among object representation, alignment, padding, and structure size in C.

2. Describe a complete and safe lifecycle for dynamically allocated memory, including ownership and error handling.

3. Compare contiguous arrays and linked lists with respect to locality, allocation overhead, resizing, and invalidation risks.

4. Explain how `realloc` works and discuss the dangers of assigning its result directly to the original pointer.

5. Discuss common forms of undefined behavior involving pointers and the role of sanitizers and static analysis in detecting them.

Analytical / Application Questions

1. Design an ownership policy for a linked list library that supports insertion, removal, traversal, and destruction. Specify which functions borrow pointers and which transfer ownership.

2. A program repeatedly creates and destroys one million small tree nodes. Analyze why it may perform poorly and propose an allocator or layout strategy, including its risks.

3. A dynamic array stores structures and frequently processes only one numeric field from every element. Compare an array-of-structures representation with a structure-of-arrays representation and justify a choice based on cache locality and interface requirements.

22. Multiple Choice Questions with Answers

Question 1

Which statement correctly describes a pointer to an object with automatic storage duration?

A. It remains valid indefinitely after the function returns.

B. It becomes invalid when the object’s lifetime ends.

C. It automatically transfers the object to the heap.

D. It can be safely dereferenced if its numerical address is unchanged.

Correct Answer: B. It becomes invalid when the object’s lifetime ends.

Question 2

Why is a temporary pointer recommended when using realloc?

A. It guarantees that the block will not move.

B. It initializes all bytes in the resized block.

C. It preserves the original pointer if reallocation fails.

D. It converts the allocation into static storage.

Correct Answer: C. It preserves the original pointer if reallocation fails.

Question 3

For an int pointer p pointing to the first element of an int array, what does p + 1 represent?

A. The next byte in memory.

B. The next int element in the same array.

C. The address of the array’s final element.

D. An invalid pointer in all circumstances.

Correct Answer: B. The next int element in the same array.

Question 4

Which situation is an example of a dangling pointer?

A. A pointer initialized to NULL.

B. A pointer to a currently allocated object.

C. A pointer used after the object it referenced was freed.

D. A pointer passed as a borrowed parameter while the object remains alive.

Correct Answer: C. A pointer used after the object it referenced was freed.

Question 5

What is the principal reason that structure size may exceed the sum of its member sizes?

A. The compiler duplicates every member.

B. Padding may be inserted for alignment.

C. Pointers always occupy zero bytes.

D. Static members are added to every instance.

Correct Answer: B. Padding may be inserted for alignment.

Question 6

Which access is defined for a pointer one position past the end of an array?

A. Dereferencing it to read a value.

B. Dereferencing it to write a value.

C. Using it as an endpoint without dereferencing it.

D. Subtracting it from a pointer to an unrelated object.

Correct Answer: C. Using it as an endpoint without dereferencing it.

Question 7

Which design generally offers better spatial locality for sequential traversal?

A. A linked list whose nodes are separately allocated.

B. A contiguous array of elements.

C. A set of unrelated pointers to heap blocks.

D. A structure containing only dangling pointers.

Correct Answer: B. A contiguous array of elements.

Question 8

What is the main ownership error when two components both release the same allocation?

A. Internal fragmentation.

B. Double free.

C. Cache thrashing only.

D. Static initialization.

Correct Answer: B. Double free.

Question 9

Which practice best handles a failed realloc call?

A. Overwrite the original pointer immediately and continue.

B. Free the original pointer before calling realloc.

C. Store the result temporarily and retain the original block on failure.

D. Assume realloc always succeeds for small programs.

Correct Answer: C. Store the result temporarily and retain the original block on failure.

Question 10

Which tool-supported technique is most directly suited to finding use-after-free and out-of-bounds accesses during testing?

A. AddressSanitizer instrumentation.

B. Changing all pointers to integers.

C. Removing allocation checks.

D. Reordering structure members without testing.

Correct Answer: A. AddressSanitizer instrumentation.