In order to discuss how hardware provides optimal performance for your code, its is important to understand what hardware thinks code is. This is really assembly, but C is close enough to assembly for our purposes.

This assignment will consist of an in-lab coding exercise, followed by a homework assignment due a week after the in-lab exercise.

The coding site for the in-lab coding exercise is here. The coding site for the homework is here.

We’ll detect that you are in lab doing the assigned task based on the computer you access the site through and the time at which you access it.

1 Logistics

1.1 Lab: Coding without help

For the initial lab, you will code up one or more C library routines. That coding must be done on your own (no help, no reference texts, etc). However, the tasks you’ll do are listed here, and you are welcome to practice on your own time (clarification added 2017-09-12: and you can use help, reference texts, etc. for this practice).

The testing site will log

• The time, duration, and client computer from which you access it the site
• If you open another window or fail to leave the window you have in full-screen mode
• Common cheating activities, like pasting something you didn’t copy during the same coding session

You’ll only get a good grade if you don’t cheat and work from an Olsson 001 computer during your assigned lab time.

You may use the site as many times as you want to to practice before your lab. (We will ignore everything submitted from non-lab machines or before the lab times.)

1.2 Homework

For the homework, the submission site will accept a file upload and give you the results of testing. You do not need to write this code in a test-like environment, and we expect you to do this work outside of lab.

1.3 Submissions and Testing

To prevent hammering the server during the lab, excessive submissions may result in point penalties. For the homework, unlimited submissions are allowed, but we ask that you avoid excessive submissions.

If you submit a file that contains method int main(int argc, char *argv[]) then that method will be run and you’ll see anything it printfs, along with a summary of how you used malloc and free. If you submit a file without main, a set of automated tests will be run and you’ll see the ratio of tests passed. Either way, the submission is logged on the server and available to us for grading.

2 The Coding Tasks

During the lab, you’ll be asked to code two small programs dealing with strings:

2.1 Code Lab

2.1.1 strlen

Write a function with signature

unsigned int strlen( const char * )

that returns the length of a null-terminated string.

Do not use malloc or free in your solution.

This is the same as the standard library method strlen except it uses built-in C type unsigned int instead of macro-defined type size_t.

One solution is (if parameter is the name of the argument)

int i = 0; while(parameter[i]) i+=1; return i;

2.1.2 strsep

Write a function with signature

char *strsep( char **stringp, char delim )

If *stringp is null, return null and do nothing else. Otherwise, find the first token in the string *stringp, where tokens are delimited by delim. Overwrite the delimiter at the end of the token with a null byte ('\0'); update *stringp to point past the token. In case no delimiter is found, the token is taken to be the entire string *stringp, and *stringp is made 0.

return a pointer to the token; that is, return the original value of *stringp.

Do not use malloc or free in your solution.

This is the similar to the standard library method strsep except it uses char, not const char *, as the delimiter. strsep differs from the more common strtok only in that it can return zero-length tokens if two delimiters are adjacent (strtok merges adjacent tokens).

One solution is

char *ans = *stringp;
if (*stringp == 0) return 0;
while (**stringp != delim && **stringp != '\0') *stringp += 1;
if (**stringp == delim) { **stringp = '\0'; *stringp += 1; }
else { *stringp = 0; }
return ans;

2.2 Homework assignment

For this homework assignment, you will need to write utility functions for two of the following types of lists:

• Singly-linked lists, of form struct node { TYPE payload; struct node *next; }. If you are creating these, you should use a seperate malloc() call for each element of the list.

• Sentinel-terminated array, of form TYPE *list; with a given TYPE sentinel; where list[numberOfElements] == sentinel. If you are creating these, you will be told to use a single call malloc(sizeof(TYPE)*(numberOfElements+1)).

• The size-and-pointer pair made popular in recent languages as the preferred implementation of a dynamic array or range, being a struct range { unsigned int length; TYPE *ptr; } The ptr field should be created with a single malloc call.

Each student will be randomly assigned two of these types of lists, called A and B below. You can retrieve your skeleton code, which will include your random assignment here. This is also where you will complete the assignment.

You will be required to write the following functions:

• A function to convert an A list into a B list.
• A function to append a copy of one B list to another B list. To allow you to modify the destination list, a pointer to it will be passed.
• A function to remove all instances of a specified value from B list. To allow you to modify the destination list, a pointer to it will be passed.

2.3 Skeleton code pieces

Some header info to define the types and values we need:

/* this bit of code lets the grader change the type used in the lists. 
 * It will be provided.
 * Your code should work for any integer type and sentinel. */
#ifndef TYPE
#define TYPE short;
TYPE sentinel = -1234;
#else
extern TYPE sentinel;
#endif

The types we’ll deal with

typedef struct node_t { TYPE payload; struct node_t *next; } node;
typedef struct range_t { unsigned int length; TYPE *ptr; } range;

Potential signatures for the functions you must implement:

node *convert(range list); /* from range to linked list */
TYPE *convert(range list); /* from range to array */
node *convert(TYPE *list); /* from array to linked list */
TYPE *convert(node *list); /* from linked list to array */
range convert(TYPE *list); /* from array to range */
range convert(node *list); /* from linked list to range */

void append(range *dest, range source); /* append range to range */
void append(TYPE **dest, TYPE *source); /* append sentinel array to sentinel array */
void append(node **dest, node *source);  /* append linked list to linked list */

void remove_if_equal(range *dest, TYPE value);
void remove_if_equal(TYPE **dest, TYPE value);
void remove_if_equal(node **dest, TYPE value);

For the append function, if the dest argument is a pointer to the list 1, 2, 3, 4, 5, 6 and the source argument is the list 7, 8, 9, then after append returns, the dest list should be changed to 1, 2, 3, 4, 5, 6, 7, 8, 9. New space should be allocated as necessary with malloc or realloc. Any memory no longer used should be deallocated.

For the remove_if_equal function, if the dest argument is a pointer to the list 1, 2, 3, 1, 2, 3 and the value argument is 2, then after remove_if_equal returns, the dest list shouuld be changed to 1, 3, 1, 3.

Note that malloc (and realloc) may not initialize the memory they return. In particular, the malloc in our testing environment deliberately ensures the memory is not zeroed.

2.4 Submission

You should submit your solution via this web coding form that will be very similar to what you used for the lab. In addition to having the option to code on the web coding form, this form will include the option to upload and download code

2.5 Basic hints

1. To get the the length of the input list (for the malloc call):

   int lengthOf(node *list) {
       int i=0; while(list) { list = (*list).next; i+=1; } return i;
   }
   int lengthOf(TYPE *list) {
       int i=0; while(list[i] != sentinel) i+=1; return i;
   }
   int lengthOf(range list) {
       return list.length;
   }

2. To access the values from a list:

       /* range */
       int i;
       for(i = 0; i < list.length; i += 1)
           doSomethingWith(list.ptr[i]);
   
       /* array */
       int i;
       for(i = 0; list[i] != sentinel; i += 1) 
           doSomethingWith(list[i]);
   
       /* linked-list */
       node *here;
       for(here = list; here; here = (*here).next) 
           doSomethingWith((*here).payload);

3. malloc() might not initialize the memory it returns, so pointers in that memory may not start out as NULL.

4. *foo[1] is the same as *(foo[1]), not (*foo)[1]