Project #9 data structures
struct table
Assume array of 10 elements
array of
struct student
[0] [1]
[8] [9]
. .
.
1
struct student
{ unsigned long number;
char name[25];
unsigned short exam1;
unsigned short exam2;
unsigned short hw;
unsigned short total;
};unsigned short percent;
struct table
{ unsigned short capacity;
unsigned short count;
unsigned short available;
struct student* memory;
};
/* student’s ID number (key) */ /* student’s name */ /* points on Exam #1 */ /* points on Exam #2 */ /* points on homework */ /* total points (exams + hw) */ /* percent (rounded) */
/* number of elements in table */ /* number of students in table */ /* total points available */
/* pointer array of students */
2
1
Suggestion: write down record mapping table for each of the two kinds of records (“struct table” and “struct student”)
How many bytes for one object of type “struct table”?
How many bytes for one object of type “struct student”?
3
Padding is needed between some fields within a record because of memory alignment requirements. The effective address for load and store instructions must be a multiple of the size of the object being transferred:
LDRB, LDRSB, STRB – 1 byte LDRH, LDRSH, STRH – 2 bytes LDR, STR – 4 bytes
LDRD, STRD – 8 bytes
4
2
Project #9 array
From the specs:
The program will use an ordered table to maintain the data set, where each student’s identification number will serve as a unique key to identify that student.
Function “search” can take advantage of the fact that the table is ordered – stop searching as soon as it is no longer possible for the search key to be found.
5
For example, assume the search key is 20:
Capacity: 10 Count: 7
0
10
1
15
2
20
3
30
4
50
5
55
6
70
7
-1
8
-1
9
-1
Halt, return 1 and address of array[2]
6
3
For example, assume the search key is 35:
Capacity: 10 Count: 7
0
10
1
15
2
20
3
30
4
50
5
55
6
70
7
-1
8
-1
9
-1
Halt, return 0 and address of array[4]
If 35 was in the array, it would be in slot 4. If 35 is to be inserted, it should be put in slot 4.
7
Function “delete” can call function “search” to find the location of the element to be deleted.
If item is not found, it cannot be deleted.
Function “delete” must keep the array elements in order – if an element is removed, the following elements must be “moved up”.
8
4
Assume we wish to delete the item with key 20:
Capacity: 10 Capacity: 10 Count: 7 Count: 6
0
10
1
15
2
20
3
30
4
50
5
55
6
70
7
-1
8
-1
9
-1
0
10
1
15
2
30
3
50
4
55
5
70
6
70
7
-1
8
-1
9
-1
9
Function “insert” can call function “search” to find the location where the item should be inserted.
If item is found, it cannot be inserted.
Function “insert” must keep the array elements in order – if an element is inserted, the following elements must be “moved down” first.
10
5
Assume we wish to insert the item with key 35:
Capacity: 10 Capacity: 10 Count: 7 Count: 8
0
10
1
15
2
20
3
30
4
50
5
55
6
70
7
-1
8
-1
9
-1
0
10
1
15
2
20
3
30
4
35
5
50
6
55
7
70
8
-1
9
-1
11
Functions “delete” and “insert” must move elements around within the array – how?
One approach: use a series of Load and Store instructions to copy data from one array slot to another.
Since each array element is 40 bytes:
• 10 LDR/STR pairs (10*4 bytes)
• 5 LDRD/STRD pairs (5*8 bytes)
12
6
Another approach: use function “memmove”. From an example in the “NOTES” file:
ldr r0, =pointA
ldr r1, =pointB
mov r2, #12
bl memmove
The arguments for function “memmove”:
R0 – destination address
R1 – source address
R2 – number of bytes to copy
13
Project #9 parameters
int search( struct table*, unsigned long,
struct student** );
R0 – pointer (address of table)
R1 – integer (student ID number)
R2 – pointer (address of an address)
Any function which calls “search” is responsible for putting a valid value in each of those three registers. The third argument is an address where “search” can store an address.
14
7
int delete( struct table*, unsigned long );
R0 – pointer (address of table) R1 – integer (student ID number)
int insert( struct table*, unsigned long,
char*, int, int, int );
R0 – pointer (address of table)
R1 – integer (student ID number)
R2 – pointer (address of name)
R3 – integer (points on Exam #1) stack – integer (points on Exam #2) stack – integer (points on homework)
15
The 5th and 6th arguments to function “insert” are passed in the stack. Where?
From the perspective of the caller: the 5th argument is at the top of the stack and the 6th argument is immediately afterwards (4 bytes each). For example:
7ed93a38: 00000055 5th argument 7ed93a3c: 00000066 6th argument
16
8
From the perspective of the callee: the positions of the 5th and 6th argument depend on the number of registers which the callee pushes into the stack. For example:
push {lr}
Contents of stack after push {lr}:
7ed93a34:
7ed93a38:
7ed93a3c:
00010480 contents of LR
00000055
00000066
5th argument 6th argument
If the callee pushes more than just LR, then the positions of the 5th and 6th arguments change.
17
Function “insert” can access the 5th and 6th arguments by loading from memory
@ Get 5th argument from stack
ldr r3, [sp, #4]
@ Get 6th argument from stack
ldr r3, [sp, #8]
The offsets (4 and 8) change if more than one register (LR) is pushed into the stack.
18
9