CS 3330: Lab and Homework 2 and 3 - Basic C Routines

This page does not represent the most current semester of this course; it is present merely as an archive.

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.

The practice an actual coding sites are

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 Coding without help

During your scheduled lab time, 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.

The testing site will log

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.

1.2 Stand-alone pure C

You will write stand-alone ANSI C, as defined in ANSI X3.159-1989 Programming Language C in 1989. Most notably, the ANSI C standard requires all variable declarations precede any non-declaration statements in a function. We won’t strictly enforce that in this lab, but the editor will flag these as errors so be aware of that.

You will also write stand-alone C; the only library methods your code will be linked against are malloc, printf, and free. The #include statement will be disabled, so if you want to use those methods you’ll need to declare them yourself. Other aspects of common #includes, such as #define NULL 0, will also need to be done manually. A reasonable set of declarations are

#define NULL 0
#define size_t (unsigned int)
int printf(const char *format, ...);
void free(void *ptr);
void *malloc(size_t size);

1.3 Submissions and Testing

To prevent hammering the server, excessive submissions result in point penalties.

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 me for grading.

2 The Coding Tasks

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

2.1 Code Lab 1

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

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 Code Lab 2

In evaluation you will be randomly assigned one of a set of functions that each accept a list in one format and return a list in a different format. These functions will generally require the use of malloc, and the test cases will verify that you mallocd efficiently.

DO NOT modify the contents or structure of the input list in your solution.

The list types are

2.2.1 Example solution 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; you are welcome to change the default type 
 * (long) and sentinel (-0x3330) if you wish.  For example, using char
 * and '\0' will let you use string literals to initialize arrays...
 * Your code will need to work for any integer type and sentinel. */
#ifndef TYPE
#define TYPE long
TYPE sentinel = -0x3330;
#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; each time you load the testing page one of these will be randomly selected

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 */

In general, you need to know

  1. 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. How 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. How to allocate a list with just one malloc

        /* range */
        range ans; 
        ans.length = /* number of elements */
        ans.ptr = malloc(sizeof(TYPE) * ans.length);
    
        /* array */
        TYPE *ans;
        int length = /* number of elements  */
        ans = malloc(sizeof(TYPE) * (length + 1));
        ans[length] = sentinel;
    
        /* linked list */
        node *head;
        int length = /* number of elements */
        head = malloc(sizeof(node) * length);
  4. How to set up a linked list made with a single malloc. Because only one malloc was used, the nodes can be placed anywhere in the block of memory you want. One approach is to set them up like a stack, putting the last element in the list first:

        for(i = length-1; i >= 0; i -= 1) {
            if (i == length-1) (*head).next = NULL;
            else (*head).next = head - 1; /* address of previously allocated node */
            (*head).payload = GET_ELEMENT(i); /* varies by input format */
            head += 1;
        }
        return head;

    You can also place things in the other order if you prefer:

        for(i = 0; i < length; i += 1) {
            head[i].payload = GET_ELEMENT(i); /* varies by input format */
            head[i].next = (i+1 < length) ? (head + i + 1) : NULL;
        }
        return head;

    You may also scatter the nodes about if you prefer, though the code is uglier and there is no obvious benefit to doing so.

Copyright © 2016 by Luther Tychonievich and Charles Reiss. All rights reserved.
Last updated 2016-09-05 10:26:24