2015/strings

From CS61
Jump to: navigation, search

Building a String Library

C strings are really just simple arrays, even though in C, we treat a NUL-terminated sequence of characters as a string. Today's exercise is to build a different string representation -- one that stores an explicit size as meta-data before the actual character array. Note that these strings are not NUL-terminated, so using them in places that expect regular C strings will prove problematic as will using regular C strings in places that expect these somewhat safe strings (I say somewhat, because you can corrupt these strings almost as easily as you can corrupt normal C strings).

This exercise is best done in groups of two or, at most, three.

We expect that the practice you gain doing this will be of great value to you as you work on assignment 1.

Learning Objectives

  • Comfortably manipulate hidden meta-data structures.
  • Comfortably build simple functions to a specification.
  • Read a program like the test driver and use it and GDB to efficiently debug your code.

Getting Started

We've helped you get started by building a simple test driver that will let you experiment with your strings. We've also provided a .h file containing prototypes for the core functions that your library will need. If you finish all those, we encourage you to examine the family of string functions that C provides and implement any that amuse you. The GNU strfry() function amuses us greatly.

In any case, pull the cs61-exercises repo and find the directory l04 waiting for you.

You'll find that you can run the test program although the results will look odd since the implementation of the library functions is empty and each function silently returns something less than helpful.

Spend a few minutes examining the driver so you know how to use it and also examining the .h file, so you know what functions you have to write.

Designing your Representation

We've already told you that you're going to store a size before the characters, but you should decide how large to make that size. You might also want to design some helper functions or macros that you'll use in your library to manipulate these strings.

Implement the Library

Once you've become familiar with the library and have a representation, start writing some code. We suggest starting with string_new, string_print and string_free. Use the test driver and debugger to verify that your library is working as you expect it to. After you've written string_new we expect that you'll find string_dup relatively easy.

Next, try string_cat.

Finally, add string_cmp.

If you run out of time, that's fine -- as long as you are confident you could write the functions, what you've learned will translate directly into Assignment 1, so focus on that, not finishing this. On the other hand, if you finish all the functions and still have time (!), type man string and pick out some of those functions to replicate in your string representation.

Hint

You may use any C library functions that you'd like, but remember that the string functions are designed to work with C strings and you might get some surprising behavior (we did!). You might find the memcpy, memmove, bcopy functions more useful.

Before you leave

Please take a minute and complete this survey.