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:
| C code | What this does |
|---|---|
| Set up the program Include printf and begin main. |
| Store the integer The value occupies four bytes in the course environment. |
| Keep its address xp points to the integer; no copy is made. |
| View one byte at a time The cast preserves the address. cp indexes characters, one byte each. |
| Read in address order Four iterations read cp[0] through cp[3]. Little-endian order prints DCBA. |
| 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
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
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.
| C code | What this does |
|---|---|
| Set up the program Include the library declarations and begin main. |
| Allocate the row table Two int-pointer slots require 16 bytes. Stop if malloc fails. |
| Allocate each row Each row receives its own three-int block: 12 bytes per row. |
| Handle a failed row Release earlier rows, then the table, before returning. The failed row has no block to free. |
| Initialize the integers Two nested loops fill all six values. The table stores addresses; the rows store these integers. |
| Follow both indices array[1] selects the second row; [2] selects its third value: 22. |
| Release three blocks Free each row first, then the table that holds their addresses. |
| 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
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.
| C code | What this does |
|---|---|
| Library declarations stdio.h supplies printf; stdlib.h supplies malloc and free. |
| Check the layout assumption This compile-time check confirms that the pointer table ends at an int-aligned offset. |
| Begin the program The following lines create one allocation. |
| Count both regions Two pointers form the header; six integers form the data region. Here: 16 + 24 bytes. |
| Allocate once One malloc reserves both regions. Stop if it fails. |
| Find the integer region array + 2 skips two pointer slots (16 bytes). The cast changes the access type to int *. |
| Initialize the row addresses Row 0 starts at the data base. Row 1 starts three ints (12 bytes) later. |
| Initialize the integers The same nested indexing works because both row pointers now contain valid addresses. |
| Read an element Follow row 1 to byte offset 28, then two ints to offset 36. The value is 22. |
| Release one block Free the original allocation address. The interior row addresses must not be freed separately. |
| 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
| Question | Separate rows | One block |
|---|---|---|
| Layout | Table and independent rows | Table, then adjacent rows |
| malloc calls for 2 rows | 3 | 1 |
| Requested bytes here | 16 + 12 + 12 = 40 | 16 + 24 = 40 |
| Cleanup | Free each row, then table | Free block once |
| Setup complexity | Allocate each row; handle partial failure | Calculate aligned data start; initialize interior pointers |
| Access | array[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
- On little-endian ARM64, what byte does a char * see first for 0x31323334?
- For three separately allocated rows of two ints, how many allocations and requested bytes are needed?
- After a row table is allocated, why is array[0][0] unsafe before assigning array[0]?
- With three columns, how many bytes does data_start + 3 advance?
- A single-block grid is released by freeing each row and then the table. What is wrong?
Show answers and reasoning
- 0x34, the least significant byte; in ASCII it represents '4'.
- Four allocations: one 24-byte pointer table plus three 8-byte rows = 48 requested bytes.
- The row slot contains an uninitialized value, not a usable row address.
- 12 bytes: three elements times four bytes per int.
- 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.