CS31: Lab 6

This lab should be done with your lab partner.

Lab 6 Goals:

practice with pointers and structs in C
writing and using a library in C, .h and .c files
C generic type (void *), and recasting
operations on bytes of memory: memcpy, malloc, realloc, bcmp
gain expertise in gdb and valgrind for debugging C programs

Lab 6 Introduction

In this assignment you and your partner will implement a C library that provides a Python-like list implementation. Other C code can use the functions provided by your library to create lists of basic C types. Your library will provide an easy-to-use list interface that hides all the low-level details about the underlying memory management of the list implementation.

First, both you and your partner should run update31 to grab some starting point code.

  $ update31
  $ cd cs31/labs/06
  $ pwd
  /home/your_user_name/cs31/labs/06
  $ ls
  Makefile  plist.c plist.h  testlist.c

Starting Point Code:

plist.h: contains the starting point of the header file for your plist library. It contains the function prototype for the init_list function. You should add function prototypes for all functions in your plist interface as you incrementally implement and test them. The type name used for parameters this file should be plist (the external type representation).
plist.c: contains the implementation of your Python-like list library. Library function definitions and internal type definitions should be added to this file. A shell for the init_list function is given to you. You should add static helper functions as needed for good modular design. The type name used for parameters in this file should be struct python_list * (the internal type representation).
testlist.c: a test program for your plist library. Add code here to test the functionality of your library. Make sure to test all library functions for different list bucket types. Again, add helper functions to make this code manageable. The type name used for variable declarations in this file should be plist (the external type representation).

Project Details, Requirements and Hints

You will implement a python-like list library, plist, that can be used by C application programmers who want to uses lists in their code but don't want to have to think about low-level memory allocation, reallocation, deallocation, or element shifting.

Information on building and using C libraries

Read over the "CREATING AND USING YOUR OWN LIBRARY CODE" section of the following (this is also available off my C help pages): Building and Using libraries in C. This gives an introduction to writing .h files, implementing library code .c files, and compiling and linking library code into C application code that uses the library. For this assignment, you will build your library code as a single object file (.o file). The Makefile already does this for you.

Using the plist library (ex. testlist.c)

C's generic type (void *) is used as the type for passing data values to, and for returning data values from, plist library functions. C applications that use the plist library re-cast void * return values to the real C type it stores in the plist, and recast real C type values passed as arguments to plist library functions as void *.

The plist.h file contains the interface to your library. Applications using the plist library should #include it:

#include "plist.h"

plist.h contains a typedef plist. plist is the type name that should be used in application code that uses the plist library. Here are some examples of how a C application may use plist library functions:

int value;
plist my_int_list;
plist my_char_list;

my_int_list = init_list(sizeof(int));    // create a new plist to store ints
my_char_list = init_list(sizeof(char));   // create a new plist to store chars
...
append(my_int_list, (void *)6);  // appends the 4-byte value 6 to end of list
append(my_int_list, (void *)7);
append(my_charList, (void *)6);  // appends the 1 byte value 6 to the list
...
set(my_int_list, 1, (void *)12);  // set's bucket 1's value to 12 
value = (int)get(my_int_list, 1);  // get the (int) value in bucket 1
                                   // re-cast the void * return type to int
free_list(my_int_list);

Implementing the plist library (plist.c, plist.h)

The underlying implementation will use an array of bytes (unsigned char) to store values added to the plist. If the values stored are ints, then 4 contiguous entries in the array of bytes are used to store each list value. If the values stored are chars, then a single array bucket can store each list value. You will use low-level memory access methods and functions in stdlib to access each value.

The following struct definition is defined in plist.c. You can use it, or something similar, to implement the plist data structure.

struct python_list {
  int size;
  int capacity;
  int type_size;
  unsigned char *array;  // it is important that this field starts on a 4-byte 
                         // aligned address (note how this def ensures that)
};

Code within the plist library implementation (plist.c) should use the type name struct python_list.

The implementation should dynamically allocate and reallocate space as needed to store the values added by the user of your library. For this assignment, you should start with an array of 20 bytes, and then each time it fills, increase its size by 20 more bytes (use a constant). With 20 bytes you can store 20 chars, 10 shorts, or 5 ints before having to reallocate space for a larger array. This is ridiculously small, and not the most efficient re-sizing algorithm, but will allow you to easily test your re-sizing functionality on reasonably sized lists.

The plist library implementation must support lists of several different C basic types of different size bytes. To do this, the plist implementation will map 1, 2 or 4 byte data values onto an underlying contiguous sequence of bytes (and array of unsigned char). The plist library implementation only knows the number of bytes in the stored values; it does not anything about the type of value actually stored in these bytes. It therefore should use methods that only manipulate low-level bytes of memory space, and should not have special case code for individual C types (you can't do this with the given plist interface anyway). The stdlib library contains some useful functions (memcpy, malloc, realloc, etc.) for manipulating bytes of memory.

Requirements

You must implement the following plist library functions:
1. init_list: takes a bucket type size (must be one of 1, 2, or 4 bytes) and returns 0 on error or an initialized, empty plist on success.
  Its function prototype must be:
```
plist init_list(int type_size) ;
```
2. free_list: free all space associated with this list the user of a plist will call this function when s/he is done using the plist variable.
  Its function prototype must be:
```
void free_list(plist list) ;
```
3. size: return the number of elements in the list (not the list capacity).
  Its function prototype must be:
```
int size(plist list) ;
```
4. append: add an element to the end of the list
  Its function prototype must be:
```
void append(plist list, void *value) ;
```
5. set: set the index'th element in the list to the given value. This is an overwrite function; the index must be valid, meaning that it is within the current size of the list. The user cannot create a list with holes using set. set can only overwrite an existing value in the list.
  Its function prototype must be:
```
void set(plist list, int index, void *value) ;
```
6. get: returns the element in the index'th bucket of the list.
  Its function prototype must be:
```
void *get(plist list, int index) ;
```
7. insert: inserts the passed value at the specified index in the list. All values currently at that position or higher in the list are shifted over to make room for this value. This function grows the list by one. insert grows the list size by one. The index must be within the current size of the list or one more (equivalent to an append); the user cannot create a list with holes.
  Its function prototype must be:
```
void insert_list(plist list, int index, void *value) ;
```
You may not change any of the function prototypes in the plist library. Your library code must work with our test code that makes calls to these functions as they are defined above.
You library must support creating and using plists that can store any of the follow C types:
```
  char
  unsigned char
  short 
  unsigned short
  int 
  unsigned int
```
A single plist will store all of the same type (i.e. either it is a list of int values or a list of char values but it cannot store both int and char values).
Your testlist.c file should contain example test code that demonstrates the correctness of your solution. If you use my #defines for specifying different bucket types, your testlist.c file will only have a single type test, but should work for any change in those #defines to test all other type possibilities. If you implement a print_list helper function (and I think you should), I recommend printing out both the signed and unsigned interpretation of every list value (for example "%d and %u" for unsigned and signed ints). This will make the code a bit more manageable to write, and it is nice to see both interpretations of the bits to check for correctness.
Error handling inside the plist library: Your implementation should have complete error checking. For example, it should check for bad values passed into your library functions (NULL ptrs, invalid parameter values, ...), it should also check for error return values from system calls and C library function calls. With the exception of the init_list function that returns error values, most of the plist functions do not explicitly return errors to the caller. Instead, you should use assert statements to test for and handle catastrophic errors inside the plist library code.
assert takes a conditional expression and terminates the program if the condition is not true. For example:
```
ptr = malloc( ... );
assert(ptr != NULL);
```
assert statements generally are not be used in production code, but are used during implementation and correctness testing phases of program development. They are also a good way to test for pre and post conditions associated with functions and get immediate feedback when they are violated.
Look at the man page for assert for details on how to call it.
Use good modular design. If you are repeating common functionality all over the place, this should be implemented as a separate function that is called by your code. Any functions that are private to a single .c file, should be declared static:
```
  static int foo(int x, int y);  // foo is only in scope within this .c file
```
Your code should be well-designed, well-commented, contain no wrapped lines and use other good programming style features. See my C Style Guide (link at bottom of class page) for more details and examples.
Your code must be free of memory access errors (no valgrind errors).

Useful C functions and Hints

Implement and test incrementally! Use valgrind as you go to catch memory access errors as you make them.
Use stdlib functions when possible to perform low-level memory accesses. Here are some that may be useful (you may not need to use all of these):
```
  malloc, realloc, bcmp, memcpy, memmove
```
See their man pages for more information and examples of their use.
Some information about C's generic type void *:
- A parameter or return value should only be declared to be void * when the type of the parameter or return value is unknown or could vary.
- A void * is a 32 bit value on a 32-bit architecture and a 64-bit value on a 64-bit architecture (it is a pointer to something, so it has enough space to store an address value). However, it is not always the case that the actual value returned in these 32 or 64 bits is a pointer (an address). It could be a char, short, int, in which case only the first 1, 2, or 4 bytes of the void * value contain valid data (the rest could be garbage).
- Not every void * value is a pointer. You cannot always dereference it. For example, in the example calls to append and set above, the int vaules store in the list are passed in through the void * parameter (these are not the address 6, but the value 6). Think very carefully about type.
- You cannot declare a local or global variable to be of type void *. Only parameters and function return values can be of type void *.
- In code that knows what the type is, you need to re-cast the void * value to the known type before accessing it
```
   int x = (int)get(my_list, i);  // this will cause a gcc warning
                                  // and is the only warning that is 
                                  // okay to have when compiling your code 
```
There are a few different methods for reading and writing multi-byte values from an underlying array of bytes.
1. One way uses memcpy (and related functions). For example, here is how to copy some number of bytes from the array of bytes, starting at the address of bucket i, into a program variable using memcpy:
```
  unsigned long value; // unsigned long is a good for storing different 
                       // type values that are passed via void *
                       // because on a 64-bit machine it is 64 bits
                       // and on 32-bit machine it is 32 bits

  memcpy((void *)&value, (void *)&array[i], num_bytes);
```
2. Another approach is to use pointers, re-casting, and dereferencing to directly access values from the underlying array of bytes. This approach requires that data are well-aligned in the underlying array of bytes (int values must be stored on 4-byte aligned addresses for example), and it is more appropriate when you know the exact type stored in the array. Here is an example:
```
  unsigned char array[100];
  int x;
  char ch;

  // gets 4 byte int value starting at the address of bucket i
  x = *((int *)&array[i]); // interpret the address of bucket i as a 
                           // pointer to an int, then dereference it 
                           // to get the int value stored there
  // gets 1 byte char value starting at bucket i
  ch = *((char *)&array[i]);
```
For all the required parts of this assignment, use the first method (memcpy and related functions) inside your plist.c code to access the byte(s) stored in each plist bucket from the underlying array of bytes.
Think very carefully about type. Sometimes you are using pointer values, sometime you are not. Sometimes a void * value is a pointer, sometimes it is not.
Review pointers in C. Here are some C programming references. In particular, my documentation about pointers in C (and other C pointer documentation) may be helpful for this assignment.

Extra Challenge

Do not try this part until all the required parts of your lab 6 solution are implemented and fully tested; extra credit features with an incomplete or buggy required part will be worth much less than a fully working lab 6 solution with no extra credit features. Here are some ideas for extra, not required, functionality to add to your plist library: extra challenge ideas

Submit

Once you are satisfied with your solution, hand it in by typing handin31 at the unix prompt.

Only one of you or your partner should run handin31 to submit your joint solutions If you accidentally both run it, send me email right away letting me know which of the two solutions I should keep and which I should discard (you don't want the grader to just guess which joint solution to grade).

You may run handin31 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize, after handing in some programs, that you'd like to make a few more changes to them.

CS31 Lab 6: Implementing Python lists in C