CSSE 132 Mini-reading · Lecture 16

Advanced Heap: Understanding 2D Arrays in Memory

A grid needs values and a way to find each row. Follow the addresses to see how two different heap layouts support the same array[i][j] syntax. Allow about 10 minutes.

Worksheet 16 connects byte order, pointer types, and dynamic 2D storage. The core idea: an address tells you where; a pointer type tells you how to access what is there. Our examples assume the course's little-endian ARM64 environment: 4-byte int, 8-byte pointers, and ASCII characters.

1. Quick Refresher

malloc requests a number of bytes and returns the starting address, or NULL if allocation fails. It does not initialize values. A pointer stores that address; declaring a pointer alone does not allocate its target. Heap storage survives a function return until you release it with free.

Count bytes using sizeof, check the returned pointer, initialize values before reading, and match each successful allocation with one free. A pointer variable and the block it points to are different pieces of storage.

2. Viewing the Same Memory Differently

Casting an int * to char * changes how you view the bytes. It neither copies the integer nor reverses its storage. Here is Worksheet 16's byte-view example as a complete program:

Example 1: read the code alongside its explanation
C codeWhat this does
#include <stdio.h>

int main(void) {
Set up the program

Include printf and begin main.

    int x = 0x41424344;
Store the integer

The value occupies four bytes in the course environment.

    int *xp = &x; // integer address
Keep its address

xp points to the integer; no copy is made.

    char *cp = (char *)xp; // same address, byte view
View one byte at a time

The cast preserves the address. cp indexes characters, one byte each.

    for (int i = 0; i < 4; ++i)
        printf("%c", cp[i]);
Read in address order

Four iterations read cp[0] through cp[3]. Little-endian order prints DCBA.

    printf("\n");
    return 0;
}
Finish

Print a newline and exit successfully.

New term: byte offset

A byte offset is the number of bytes from a chosen starting address. Offset 0 is the starting byte; offset 1 is one byte after it. If an integer starts at address 1000, its four bytes are at addresses 1000, 1001, 1002, and 1003: offsets 0, 1, 2, and 3. These example addresses are written in decimal.

An offset is a distance, not a full address and not necessarily an array index. Adding 1 to an int * moves one integer, or four bytes here, so its byte offset increases by 4.

Increasing addresses, one byte per box

Four bytes of a little-endian integerEach box is one byte. A char pointer reads D, C, B, A in increasing address order.Increasing byte addresses →offset 00x44Dcp[0]offset 10x43Ccp[1]offset 20x42Bcp[2]offset 30x41Acp[3]xp[0]: one integer, 0x41424344
Each box is one byte. A char pointer reads D, C, B, A in increasing address order.

Little-endian storage puts the least significant byte, 0x44, at the lowest address. Reading characters in increasing address order therefore prints DCBA. xp + 1 advances four bytes; cp + 1 advances one. The diagram's offsets are byte offsets, not int-pointer arithmetic.

A character pointer can inspect an object's representation. This does not make the bytes a C string: there is no zero terminator here, so do not print cp with %s.

3. What Does int ** Mean?

An int ** points to an int *: dereference once to get a pointer, then again to get an integer. Think of following two arrows.

int value = 7;
int *p = &value;
int **pp = &p; // pp points to p
Pointer to a pointerDereference pp once to reach p; dereference again to reach the integer value 7.ppint **pint *value = 7int
Dereference pp once to reach p; dereference again to reach the integer value 7.

For a grid, array points to a table of row pointers. array[i] selects one pointer; array[i][j] follows it and selects an integer. An int ** is not automatically a grid, and casting an ordinary integer block to int ** does not create row pointers.

4. Separate Allocations: A 2 × 3 Grid

Reserve two pointer slots, then three integers for each row. That means three allocations: 16 bytes for the table and 12 bytes per row, totaling 40 requested bytes. The allocator may place the rows far apart.

Separate allocations for a two by three gridBlue boxes store row pointers. Green boxes store integers. Three separate outlines mean three malloc results.arrayAllocation 1: pointer table · 16 bytesarray[0]Row 0: 12 bytes (malloc 2)101112array[1]Row 1: 12 bytes (malloc 3)202122Free each row, then the pointer table.
Blue boxes store row pointers. Green boxes store integers. Three separate outlines mean three malloc results.
Example 2: read the code alongside its explanation
C codeWhat this does
#include <stdio.h>
#include <stdlib.h>

int main(void) {
Set up the program

Include the library declarations and begin main.

    int **array = malloc(2 * sizeof(int *)); // table
    if (array == NULL) return 1;
Allocate the row table

Two int-pointer slots require 16 bytes. Stop if malloc fails.

    for (int i = 0; i < 2; ++i) {
        array[i] = malloc(3 * sizeof(int)); // one row
Allocate each row

Each row receives its own three-int block: 12 bytes per row.

        if (array[i] == NULL) {
            for (int k = 0; k < i; ++k) free(array[k]);
            free(array);
            return 1;
        }
    }
Handle a failed row

Release earlier rows, then the table, before returning. The failed row has no block to free.

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 3; ++j)
            array[i][j] = 10 * (i + 1) + j;
Initialize the integers

Two nested loops fill all six values. The table stores addresses; the rows store these integers.

    printf("%d\n", array[1][2]);
Follow both indices

array[1] selects the second row; [2] selects its third value: 22.

    for (int i = 0; i < 2; ++i) free(array[i]);
    free(array); // release table last
Release three blocks

Free each row first, then the table that holds their addresses.

    return 0;
}
Finish

Exit after all owned memory has been released.

Each loop assignment writes a value into allocated storage. array[1][2] selects row 1, then column 2, and prints 22. The failure branch frees only rows already allocated. On success, free the rows before the table, while their addresses are still available.

5. One Allocation: Table and Data Together

Worksheet 16, Problem 3 asks for one malloc call. Put the table at the start and the six integers after it. The row pointers still hold addresses, but now they point inside the same block.

In the next diagram, count bytes from the beginning of the entire allocation. The first row starts 16 bytes after that beginning: its byte offset is 16. The second row starts 12 more bytes later, at byte offset 28. The numbers above the boxes show these distances, rather than the actual memory addresses.

One 40-byte block, shown in increasing byte offsets

Row pointers and integers inside one allocationOne outer boundary contains the blue pointer table and green integers. Internal arrows point to each row; offsets are in bytes.One malloc result: 40 bytes0row 08row 116102011241228203221362240Pointer table: 16 bytesInteger data: 24 bytesRow 0 → offset 16 Row 1 → offset 28free(array) releases the entire outer box.
One outer boundary contains the blue pointer table and green integers. Internal arrows point to each row; offsets are in bytes.

Alignment: integer storage must begin at an address suitable for int. malloc supplies an aligned base. In the course ARM64 environment, int requires 4-byte alignment; the 16-byte table preserves it. No gap is needed here. The compile-time check below verifies that the table size is a multiple of int's alignment. On a different platform, a layout might need padding before the data; it must not simply assume alignment.

Example 3: read the code alongside its explanation
C codeWhat this does
#include <stdio.h>
#include <stdlib.h>
Library declarations

stdio.h supplies printf; stdlib.h supplies malloc and free.

/* The pointer table must end on an int-aligned address. */
_Static_assert((2 * sizeof(int *)) % _Alignof(int) == 0,
               "This layout requires an aligned data start");
Check the layout assumption

This compile-time check confirms that the pointer table ends at an int-aligned offset.

int main(void) {
Begin the program

The following lines create one allocation.

    size_t header_bytes = 2 * sizeof(int *);
    size_t data_bytes = 2 * 3 * sizeof(int);
Count both regions

Two pointers form the header; six integers form the data region. Here: 16 + 24 bytes.

    int **array = malloc(header_bytes + data_bytes);
    if (array == NULL) return 1;
Allocate once

One malloc reserves both regions. Stop if it fails.

    int *data_start = (int *)(array + 2); // skip table
Find the integer region

array + 2 skips two pointer slots (16 bytes). The cast changes the access type to int *.

    array[0] = data_start; // first row
    array[1] = data_start + 3; // second row
Initialize the row addresses

Row 0 starts at the data base. Row 1 starts three ints (12 bytes) later.

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 3; ++j)
            array[i][j] = 10 * (i + 1) + j;
Initialize the integers

The same nested indexing works because both row pointers now contain valid addresses.

    printf("%d\n", array[1][2]);
Read an element

Follow row 1 to byte offset 28, then two ints to offset 36. The value is 22.

    free(array); // the only allocation base
Release one block

Free the original allocation address. The interior row addresses must not be freed separately.

    return 0;
}
Finish

Return success after cleanup.

array + 2 moves past two pointer slots, not two bytes. The cast views that location as integer storage. data_start + 3 moves three integers (12 bytes), so it finds row 1. Setting the row pointers is essential: malloc does not fill them in.

array[1][2] follows the pointer stored at offset 8 to offset 28, then advances two integers to offset 36. It prints 22, just as before. Only free(array) is correct: the row addresses are interior addresses, not separate malloc results.

The examples use small fixed dimensions so the sizes fit. For the worksheet, first draw the layout for your row and column counts, then calculate the table and data sizes separately.

6. Compare the Approaches: Quick Reference

QuestionSeparate rowsOne block
LayoutTable and independent rowsTable, then adjacent rows
malloc calls for 2 rows31
Requested bytes here16 + 12 + 12 = 4016 + 24 = 40
CleanupFree each row, then tableFree block once
Setup complexityAllocate each row; handle partial failureCalculate aligned data start; initialize interior pointers
Accessarray[i][j]: select row pointer, then integer

These totals exclude allocator bookkeeping. Identical indexing does not imply identical ownership or cleanup.

7. Common Mistakes

  • Confusing int * and int **: integers and pointer slots store different kinds of values. A cast cannot build missing arrows.
  • Insufficient space: the table stores pointers, so use sizeof(int *); row data uses sizeof(int). One block needs both regions.
  • Uninitialized row pointers: allocating the table does not set its entries. Set them before using array[i][j].
  • Counting bytes twice: pointer addition already scales by the pointed-to type. data_start + 3 skips three ints, not three bytes.
  • Wrong cleanup: freeing only the separate-row table leaks rows; freeing interior rows of the single block is invalid.

8. Check Your Understanding

  1. On little-endian ARM64, what byte does a char * see first for 0x31323334?
  2. For three separately allocated rows of two ints, how many allocations and requested bytes are needed?
  3. After a row table is allocated, why is array[0][0] unsafe before assigning array[0]?
  4. With three columns, how many bytes does data_start + 3 advance?
  5. A single-block grid is released by freeing each row and then the table. What is wrong?
Show answers and reasoning
  1. 0x34, the least significant byte; in ASCII it represents '4'.
  2. Four allocations: one 24-byte pointer table plus three 8-byte rows = 48 requested bytes.
  3. The row slot contains an uninitialized value, not a usable row address.
  4. 12 bytes: three elements times four bytes per int.
  5. Rows point inside the block. Release only the original allocation address once.

9. Key Takeaways

  • A pointer cast changes the access type; the stored bytes stay in place.
  • Draw two arrows for int **: table to row, row to integer.
  • Reserve space for pointers as well as values, and initialize both.
  • Pointer arithmetic follows element sizes; verify byte offsets and alignment.
  • Cleanup follows allocation boundaries, even when indexing looks identical.