[SOLVED] data structure Project #9 data structures

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;
};
/* students ID number (key) */ /* students 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 students 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
blmemmove
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