Arrays and records
Array accessing
An array is an ordered sequence of identical
objects.
The ordering is determined by a scalar data object
(usually integer or enumeration data). This value is
called the subscript or index, and written as A[I]
for array A and subscript I.
Multidimensional arrays have more than one
subscript. A 2-dimensional array can be modeled as
the boxes on a rectangular grid.
The L-value for array element A[I,J]is given by the
accessing formula
2
Array accessing (continued)
Rewriting access equation:
L-value(A[I,J]) = - d1*L1 - d2*L2 +I*d1 + J*d2
Set I = 0; J= 0;
L-value(A[0,0]) = - d1*L1 - d2*L2 +0*d1 + 0*d2
L-value(A[0,0]) = - d1*L1 - d2*L2, which is a
constant.
Call this constant the virtual origin (VO);
It represents the address of the 0th element of the
array.
L-value(A[I,J]) = VO +I*d1 + J*d2
To access an array element, typically use a dope
vector:
Array accessing summary
To create arrays:
1. Allocate total storage beginning at :
(U2-L2+1)*(U1-L1+1)*eltsize
2. d2 = eltsize
3. d1 = (U2-L2+1)*d2
4. VO = - L1*d1 - L2*d2
5. To access A[I,J]: Lvalue(A[I,J]) = VO + I*d1 +
J*d2
This works for 1, 2 or more dimensions.
May not require runtime dope vector if all values are
known at compile time. (e.g., in Pascal, d1, d2, and
VO can be computed by compiler.)
Array example
Given following array:
var A: array [7..12, 14..16] of real;
Give dope vector if array stored beginning at location 500.
d2 = 4 (real data)
d1 = (16-14+1) * 4 = 3 * 4 = 12
VO = 500 (7 * 12) (14 * 4) = 500 - 84 - 56 = 360
L-value(A[I,J]) = 360 + 12* I + 4* J
1. VO can be a positive or
negative value, and can have
an address that is before,
within, or after the actual
storage for the array:
2. In C, VO = since bounds start at 0.
Example: char A[25]
L-value(A[I]) = VO + (I-L1) * d1 = + I
* 1 = + I
8
Slices
Array slices
Given array : A[L1:U1, L2:U2]: Give d1, d2, and VO for
vector:
Dope vector A[I,*] = B[L2:U2]
VO = L-value(A[I,L2]) - d2*L2
M1 = eltsize = d2
Dope vector A[*,J] = B[L1:U1]
VO = L-value(A[L1,J]) - d1*L1
M1 = rowsize = d1
Create new dope vector
that accesses original
data
10
More on slices
Diagonal slices:
VO = L-value(A[L1,L2])
- d1*L1 - d2*L2
M1 = d1 + d2
Other
possibilities:
11
Associative arrays
Access information by name without having a
predefined ordering or enumeration:
Example: Names and grades for students in a class:
NAME[I] = name of Ith student
GRADE[I] = Grade for Ith student
Associative array: Use Name as index:
CLASS[name] will be grade.
Problem: Do not know enumeration before obtaining
data so dope vector method of accessing will not
work.
Implemented in Perl and in SNOBOL4 (as a table)
12
Perl example
%ClassList = (Michelle, `A', Doris, `B', Michael,
`D');
# % operator makes an associative array
$ClassList{Michelle} has the value A
@y = %ClassList
# Converts ClassList to an enumeration
# array with index 0..5
Doris
B
Michael
D
Michelle
A
$I=
$I=
$I=
$I=
$I=
$I=
0
1
2
3
4
5
$y[$I]
$y[$I]
$y[$I]
$y[$I]
$y[$I]
$y[$I]
=
=
=
=
=
=
13
Records / Structs in C
Representation:
A sequence of objects:
record { A: object;
B: object;
C: object }
14
C Structure Example
struct animal_struct {
char dog;
unsigned long cat;
unsigned short pig;
char fox;
};
Size? (assume 32bit compiler)
15
C Structure Example
struct animal_struct {
char dog; /* 1 byte */
unsigned long cat; /* 4 bytes */
unsigned short pig; /* 2 bytes */
char fox; /* 1 byte */
};
Size (assuming 32bit compiler)
= 11 / 12 bits
16
Data Alignment / Packing
Due to access optimization
struct animal_struct {
char dog; /* 1 byte */
u8 __pad0[3]; /* 3 bytes */
unsigned long cat; /* 4 bytes */
unsigned short pig; /* 2 bytes */
char fox; /* 1 byte */
Why?
u8 __pad1; /* 1 byte */
Memory banks
};
17
Another optimization: Ex. 2
18
Data Alignment / Packing
Can we do better?
Rearrange the members
Ex 1:
struct animal_struct {
unsigned long cat; /* 4 bytes */
unsigned short pig; /* 2 bytes */
char dog; /* 1 byte */
char fox; /* 1 byte */
};
For example 2?
19
Union types
typedef union { int X;
float Y;
char Z[4];} B;
B P;
Similar to records, except all have overlapping
(same) L-value.
But problems can occur. What happens below?
P.X = 142;
printf(%O\n, P.Z[3])
All 3 data objects have same L-value and occupy same
storage. No enforcement of type checking.
Poor language design
20
Variant records
type PayType=(Salaried, Hourly);
var Employee:record
ID: integer;
Dept: array[1..3] of char;
Age: integer;
case PayClass: PayType of
Salaried:(MonthlyRate:real;
StartDate:integer);
Hourly:(HourRate:real;
Reg:integer;
Overtime:integer)
end
(Pascal Code)
21
Variant records (continued)
Tagged union type - Pascal variant records
type whichtype = (inttype, realtype, chartype);
type uniontype = record
case V: whichtype of
inttype: (X: integer);
realtype: (Y: real);
chartype: (Z: char4); Assumes string of length 4
end
But can still subvert tagging:
var P: uniontype
P.V = inttype;
P.X = 142;
P.V = chartype;
What is P.V value now?
22
Lists
Ordered sequence of objects
First member = head of List
Specification:
Rarely of fixed length
Rarely homogeneous
Without explicit attributes for the list members
LISP:
(Fn_name Data_1 Data_2 Data_n)
23
Lists (continued)
Implementation
Operations
Join => cons
Head
Tail
24
Lists (continued)
Implementation
Node
Type:
Head:
list / atom
25
Lists (continued)
Creation
Values: a, b, c
26
Lists (continued)
Implementation
27
Lists (continued)
Implementation
28