OSU CSE 2421
Multi-dimensional and multi-level arrays
J.E.Jones
OSU CSE 2421
Arrays
One-dimensional
◦ Multi-dimensional (nested) ◦ Multi-level
Structures ◦ Allocation ◦ Access
◦ Alignment
J. E. Jones
OSU CSE 2421
Declaration
T A[R][C];
◦ 2D array of data type T
A[0][0] • • • A[0][C-1]
3D, 4D, etc. beyond scope of this class
•• •• ••
◦ R rows, C columns
◦ Type T element requires K bytes
A[R-1][0]
• • •
A[R-1][C-1]
Array Size
◦ R*C*Kbytes
Arrangement
◦ Row-Major Ordering
int A[R][C];
AAAAAA [0] ••• [0] [1] ••• [1] • • • [R-1] ••• [R-1] [0] [C-1] [0] [C-1] [0] [C-1]
4*R*C Bytes
J. E. Jones
OSU CSE 2421
#define PCOUNT 4 zip_dig pgh[PCOUNT] =
{{1, 5, 2, 0, 6},
{1, 5, 2, 1, {1, 5, 2, 1, {1, 5, 2, 2,
3 }, 7 }, 1 }};
zip_dig pgh[4];
15206152131521715221 76 96 116 136 156
int pgh[4][5];
zip_dig pgh[4] equivalent to int pgh[4][5]
◦ Variable pgh: array of 4 elements, allocated contiguously ◦ Each element is an array of 5 int’s, allocated contiguously
“Row-Major” ordering of all elements in memory
J. E. Jones
OSU CSE 2421
To get access to a specific nested array element
◦ Consider it a two-step process:
1. Compute the address to the desired row
2. Compute the offset within the row to the desired element
3. Add #1 and #2; result is address of designed element
J. E. Jones
OSU CSE 2421
A
A+(i*C*4) A+((R-1)*C*4)
Row Vectors
◦ A[i]isarrayofCelements
◦ Each element of type T requires K bytes ◦ Starting address A+ i * (C * K)
int A[R][C];
A[0] A[i] A[R-1]
A A•••A A•••A A [0] ••• [0] [i] ••• [i] [R-1] ••• [R-1]
[0] [C-1] [0] [C-1] [0] [C-1]
J. E. Jones
OSU CSE 2421
pgh
pgh+20 pgh+40
int *get_pgh_zip(int index) {
15206152131521715221
# %rdi = index
leaq (%rdi,%rdi,4),%rax leaq pgh(,%rax,4),%rax
# 5 * index
# pgh + (20 * index)
Row Vector
◦ pgh[index] is array of 5 int’s
◦ Starting address pgh+20*index
Machine Code
◦ Computes and returns address
◦ Compute as pgh + 4*(index+5*index)
return pgh[index]; }
J. E. Jones
OSU CSE 2421
A
A+(i*C*4) A+((R-1)*C*4)
Array Elements
◦ A[i][j]iselementoftypeT,whichrequiresKbytes
◦ Address A+(i*(C*K))+ j*K=A+((i*C)+ j)*K
[0]
[C-1]
[j] [0]
[C-1]
int A[R][C];
A[0] A[i] A[R-1]
AA•••A•••AA [0] ••• [0] ••• [i] ••• [R-1] ••• [R-1]
1. Address of row start
A+(i*C*4)+(j*4)
2. Offset within row
J. E. Jones
OSU CSE 2421
pgh
pgh+20 pgh+40
int get_pgh_digit(int index, int dig) {
15206152131521715221
leaq (%rdi,%rdi,4), %rax
# 5*index
# %rsi => 2nd parameter
# 5*index+dig
# M[pgh + 4*(5*index+dig)]
addq %rax, %rsi
movl pgh(,%rsi,4), %eax
Array Elements
◦ pgh[index][dig]isint
◦ Address: pgh + 20*index + 4*dig
pgh[2][3]
= pgh + 4*(5*index + dig)
return (pgh[index][dig]); }
J. E. Jones
OSU CSE 2421
zip_dig cmu = { 1, 5, 2, 1, 3 }; zip_dig mit = { 0, 2, 1, 3, 9 }; zip_dig ucb = { 9, 4, 7, 2, 0 };
Variable univ denotes array of 3 elements
#define UCOUNT 3
int *univ[UCOUNT] = {mit, cmu, ucb};
◦ 8 bytes
Each pointer points to
Note int *
cmu
160136 mit02139
univ
16 20 24 28 32 36
176 256 ucb
94720
Each element is a pointer
15213
168 16 136 140 144 148 152 156
256 260 264 268 272 276
array of integers
J. E. Jones
OSU CSE 2421
int get_univ_digit(size_t index, size_t digit) {
return univ[index][digit]; }
salq addq movl ret
$2, %rsi univ(,%rdi,8), %rsi (%rsi), %eax
# 4*digit (2nd parameter) # p = univ[index] + 4*digit # return *p
Computation
◦ Element access Mem[Mem[univ+8*index]+4*digit] ◦ Must do two memory reads
First read gets pointer to row array
Second read accesses element within array
J. E. Jones
OSU CSE 2421
Nested array Multi-level array
int get_pgh_digit(size_t index, size_t digit) int get_univ_digit(size_t index, size_t digit) {{
return pgh[index][digit]; return univ[index][digit]; }}
Accesses looks similar in C, but address computations very different:
Mem[pgh+20*index+4*digit] Mem[Mem[univ+8*index]+4*digit]
J. E. Jones
OSU CSE 2421
Fixed dimensions ◦ Know value of N at
#define N 16
typedef int fix_matrix[N][N];
/* Get element a[i][j] */
int fix_ele(fix_matrix a, size_t i, size_t j) {
compile time
Variable dimensions, explicit indexing
return a[i][j]; }
◦ Traditional way to implement dynamic arrays
#define IDX(n, i, j) ((i)*(n)+(j))
Variable dimensions, implicit indexing
size_t i, size_t j) {
◦ Now supported by gcc (non-ANSI C)
/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n],
/* Get element a[i][j] */ int vec_ele(size_t n, int *a,
return a[IDX(n,i,j)]; }
}
J. E. Jones
size_t i, size_t j) { return a[i][j];
OSU CSE 2421
Array Elements (int a[16][16])
Address a+i*(C*K)+ j*K
C = 16, K = 4, therefore, each row = 16*4 = 64 bytes Total Size of Array: 16*16*4 = 1024 bytes
/* Get element a[i][j] */
int fix_ele(fix_matrix a, size_t i, size_t j) {
return a[i][j]; }
# a in %rdi, i in %rsi, j in %rdx salq $6, %rsi
# 64*i
# a + 64*i
# M[a + 64*i + 4*j]
#calculate address of needed row addq %rsi, %rdi
#now get to specific row element movl (%rdi,%rdx,4), %eax
ret
J. E. Jones
OSU CSE 2421
Array Elements
Address A+i*(C*K)+ j*K
C = n, K = 4
Must perform integer multiplication
/* Get element a[i][j] */
int var_ele(size_t n, int a[n][n], size_t i, size_t j) {
return a[i][j]; }
# n in %rdi, a in %rsi, i in %rdx, j in %rcx
imulq
%rdx, %rdi (%rsi,%rdi,4), %rax
# n*i
# a + 4*n*i
# a + 4*n*i + 4*j
leaq movl ret
(%rax,%rcx,4), %eax
J. E. Jones