Learn Linked Data Structures in C and RISC-V

Linked Data Structures (e.g., linked lists) in C and RISC-V CS3432 Spring 2024 Shirley Moore, Instructor svmoore@utep.edu March 18, 2024 1

Schedule for Todays Class Announcements 6-weeks course survey on QuestionPro Thank you to all who completed it. Can still fill it out if you haven t already (see link on General channel in Teams). We have discussed the results and will address them. Please see Robert for adjustments to lab grades. Lecture Quiz 3 assigned on BlackBoard, due Sunday, March 3, 11:59pm Midterm Exam will be in-class, closed-book, on paper, Wed., March 6. Midterm exam review during March 4 class Procedures in C and RISC-V (cont.) (slides 12-19 from Feb. 21 class) Procedures with array arguments Encoding jal and jalr instructions Practice problems -- P&H 2.29, 2.30, 2.31 Indirect function/procedure calls Arrays and Pointers in C and RISC-V K&R Chapter 5 P&H 2.9, 2.14 2

Learning Objectives for this week After this week s lectures and practice problems, you should be able to do the following: Write C code that uses arrays and translate to to RISC-V Including arrays of pointers. Write C code that use structures and translate to RISC-V Write C code that uses malloc() and free() and translate to RISC-V. Write C code that manipulates linked lists and translate to RISC-V Write C code that uses a combination of arrays and structs Array of structs Struct of arrays (In general, an array can be a member of a struct). Nested structs (A struct can be a member of a struct). Give results produced by any of the above. The above includes functions/procedures with array and pointer arguments, including when the pointer is the address of a struct. 3

Pointers in C A pointer is a variable that can contain the address of a variable. A pointer in C is constrained to point to a specific type (with the exception of pointers of type void * (pointer to void i.e., a generic pointer). Pointers is assembly/machine language are not typed; they are byte addresses. In C, there is a strong relationship between pointers and arrays. Any code written using array subscripting has an equivalent version that uses pointers. Pointer version is usually faster A compiler will often generate assembly/machine code analogous to the C pointer version, even if the C code is written using subscripting. 4

Array Example (K&R p. 98) pa = a; is the same as pa = &a[0]; a[i] is equivalent to *(a+i) &a[i] is equivalent to a+i

Array Arguments in C When an array name is passed to a function, what is passed is the address of the zeroth element. The function can believe it has been passed either an array or a pointer. Can pass part of an array to a function. Example on next slide: Use copy() (from Example 7 from Feb. 21 class) to copy right half of array X to array Y, where X is of size 2*n ints and Y is of size n ints. 6

Array copy function (Example 7 from Feb. 21 slides) void copy (int a[], int b[], int n) { Copy right half of array X to array Y, where for (int i = 0; i < n; i++) X is of size 2*n ints and Y is of size n ints. a[i] = b[i]; } copy(Y, X+n, n); Same as void rhcopy (int *a, int *b, int n) { int *end = a + n; while (a < end) { *a = *b; a++; b++; } } 7

Structs in C K&R Chapter 6 8

Example using struct point The init_point() function below allocates memory for a point struct and initializes the fields to x, y, (*ft)(x,y), and (*fp)(x,y). Translate to RISC-V using Compiler Explorer with O1 and explain the resulting assembly code. struct point *init_point(int x, int y, float (*ft)(int, int), float (*fp)(int, int)) { p = (struct point *) malloc(sizeof (struct point)); p.x = x; p.y = y; p.temp = (*ft)(x,y); p.pressure = (*fp)(x,y); return p; } 9