« Back to the main CS 300 website

Project 1: Strings + Vectors

Strings part (excl. mbslen) due Feb 5, 2021 at 6:00pm AoE
Everything else due Feb 12, 2021 at 6:00pm AoE

Introduction

In the first portion of this project, you will implement a subset of C’s string manipulation library. In the second portion of this project, you will create your own implementation of a vector datastructure (a structure similar to std::vector in the C++ Standard Library or to an ArrayList in Java). Through both portions of the project, you will gain a better understanding of pointers as well as the general layout of data in memory.

You’re unlikely to ever find yourself implementing your own string or vector library outside this course. However, this assignment is designed to teach you about data representation concepts in memory that software engineers in industry use every day. Plus, it doesn’t hurt to understand how the standard libraries does their magic!

Learning Objectives

• Learn how to work with pointers.
• Understand how data is laid out in memory.
• Become familiar with popular string library functions.
• Become familiar with memory allocation and deallocation functions (malloc, realloc, free).
• Appreciate the more advanced data structures available in the C++ standard library.

Conceptual Questions

• Write your answers to the following questions in your README.
• You should be able to answer the General Questions without any additional project context. You should be able to answer the project-specific questions after you’ve read through the handout.

#include <stdio.h>

void func(const char* s) {
    s++;
}

int main() {
    char* hello = "hello"; 
    func(hello);
    printf("%s", hello); 
}

#include <string.h>
#include "vector300.h"

size_t vector_type = 4;

int main() {
    int val = 5;
    char fun_adjective[8];
    vector_t int_vector;
    strncpy(fun_adjective, "awesome", 8);
    initialize_vector(&int_vector, vector_type);
    vector_add_back(&int_vector, &val);
    destroy_vector(&int_vector);
}

Installation

If you have completed Lab 0, you will already have created a private GitHub repository for your project work under the csci0300 organization.

Recall, to clone your repository for the projects, you run this command (inside the course VM, or on the computer you’re working on):

$ git clone git@github.com:csci0300-s21-projects-YOURUSERNAME.git

(You’ll hopefully have done this as part of Lab 0 already.)

Now, ensure that your repository has a handout remote. Type:

$ git remote show handout

If this reports an error, run:

$ git remote add handout https://github.com/csci0300/cs300-s21-projects.git

Then run:

$ git pull
$ git pull handout master

This will merge our Project 1 stencil code with your repository.

Once you have a local working copy of the repository that is up to date with our stencils, you are good to proceed. You’ll be doing all your work for this project inside the strvec directory in the working copy of your projects repository.

Infrastructure help

Part 1: Strings

String manipulation is an important concept in computer science, and it is something that comes up very often in systems programming. Most programming languages have a string library that relieves programmers from writing their own string operations for every program. The C Standard Library has some excellent string manipulation facilities, but we want to assemble one ourselves!

For this part of the project, you will implement a subset of C’s standard library string functions for ASCII text. You will also explore a different character representation, the UTF-8 encoding (a Unicode character set).

Stencil

Your String Library

Note: Here are the details about the functions you are implementing (click to expand on each function). We’ve also included a link to the relevant man page for each function — Linux man pages provide great documentation on C library functions and are a helpful resource for understanding the behavior of edge cases.

size_t strlen(const char* s);

size_t len = strlen("ALGOT / SKADIS");  // len = 14

int strncmp(const char* s1, const char* s2, size t n);

int result = strncmp("ABCXYZ", "ABCXYZAAO", 6); // result = 0
result = strncmp("abcde", "abdde", 3); // result = some negative number
result = strncmp("abcde", "abdde", 2); // result = 0
result = strncmp("1234567", "123", 100); // some positive number

char *strncpy(char* dest, const char* src, size_t n);

char dest[] = "MACKAPAR";
strncpy(dest, "TJUSIG", 3); // dest now becomes "TJUKAPAR"

char* strchr(const char* str, int chr);

char c = 'N';
char* str = "---HOLJES---NYMANE---NYMANE---";
char* location = strchr(str, (int)c);
// location = "NYMANE---NYMANE---"

char* strtok(char* str, const char* delim);

char* delim = " ";
char str[20] = "hello everyone!";
char* first = strtok(str, delim);
// first = "hello"
char* second = strtok(NULL, delim);
// second = "everyone!"

char str2[20] = "hello all!"
char* delim_2 = "yl";
first = strtok(str2, delim_2);
// first = "he"
second = strtok(NULL, delim_2);
// second = "o a"
char* third = strtok(NULL, delim_2);
// third = "!"

Supporting Extended Character Sets

You may recall from lecture, that ASCII, which can be represented in 1 bytes characters, is the American Standard Code for Information Interchange. However, ASCII is only meant for English and it does not support accents or characters from non-Latin alphabets. Programmers often need to support extended character sets (most commonly UTF-8) to support extended character sets for more inclusive applications.

When programming for extended character sets, some of the standard library support functions for single character (ASCII) strings will not work as intended. C provides support for multibyte characters through their wchar_t struct, which represents a character in 4 bytes. However, since many extended character sets have variable length characters (for example, UTF-8 encodes characters in 1-4 bytes), using wchar_t leads to wasted space in memory. Moreover, programs often receive UTF-8 text as input that isn’t nicely laid out in 4-byte chunks, and must still be able to process it. (As an example, consider a website that processes input from a form: users may put strings like “γνωρίζω” or “❤️😺” into the form!)

In this part of the assignment, you will practice implementing string functions that are compatible with the UTF-8 character set without relying on multi-byte character data types.

UTF-8 characters follow a set byte format based on their length. 1 byte UTF-8 characters are meant to be compatible with ASCII, which means that they always begin with a 0 bit. For 2-4 byte UTF-8 characters, the number of leading 1s indicates the lengh of the character (in bytes). Each subsequent byte begins with the bits 01. You can find an overview of the format below:

size_t mbslen(const char *bytes);

char *emojis = "🥳😊😄";
size_t len = mbslen(emojis);  
// len = 3

Compile, Run, and Test

The Makefile

• Run make inside the stencil directory to compile your work into a test executable. (This will create two executables, run_tests and run_builtin_tests)
• Look at lab 1 for more details on how makefiles work.
• Note: You may see compiler errors from strings.c. Don’t panic. Just look at each error one by one, and look them up online if you get confused.

Test your work (run_tests)

• ./run_tests will run the unit tests in strings_tests.c on the string library you implemented.
• Run ./run_tests all to test against the entire test suite.
  • All of the tests can also be run using the make check command provided in the Makefile
• Run ./run_tests <test name(s)> to test against a specific test or list of tests.

Test against the C Standard Library (run_builtin_tests)

• ./run_builtin_tests will run the unit tests in strings_tests.c on the builtin C Standard Library.
• This is useful for understanding the expected behavior of the string functions and writing your own tests. (If the tests in strings_tests.c are valid tests, these should always pass)
• Run ./run_builtin_tests <all | test names(s)> to test against all tests, a specific test, or list of tests

Write your own tests in strings_tests.c

• test_runner.h describes some helper functions that are useful for writing unit tests.
• Write your tests instrings_test.c, and look at the provided tests for inspiration.

# Make the executables
make  

# Runs tests from `test_strlen` and `test_strstr`in `strings_tests.c`
# on your strings library
./run_tests strlen strstr

# Runs all unit tests in `strings_tests.c` on your strings library
./run_tests all

# Runs all unit tests in `strings_tests.c` on the builtin library
./run_builtin_tests all 

Tips for Getting Started

• Try implementing one function at a time and testing it before you move on.
• Before implementing a function, make sure you understand how it works.
  • Read the function comments and details above for examples.
  • Look at the man pages for a more detailed description of the function and its edge cases.
  • Look at the unit tests in strings_tests.
  • Try writing your own unit tests, and testing them against the builtin standard library
• Remember that in C, even though we’re requiring you to use pointer operations, you can think of the type char * as any of three things: a pointer to a single character, a string, or an array of characters. These are all the same!

Tips for Debugging

• See if your code works on simpler test cases, and then work your way up to the more complicated ones.
• Use the GDB (GNU Debugger) to understand where your code is breaking.
  • Take a look at Lab 1 to refresh your memory on how to debug using GDB.
  • Use this GDB Cheatsheet.
  • break, continue, next, print, x (examine), and backtrace are particularly helpful commands for this assignment.

$ make
$ gdb run_tests
(gdb) b test_strlen
(gdb) b strlen
# Run the executable with strlen as the argument
(gdb) r strlen

Part 2: Vectors

One common data structure which you may be familiar with is an array. Internally, arrays are just adjacent elements of the same type in memory. This allows for fast traversal of the data since iterating though the array elements is as simple as the CPU incrementing a pointer. However, standard arrays are a fixed length and cannot be grown after they have been declared. One alternative to an array is a linked list, which has no fixed size. However, linked lists are what are known as “pointer chasing” data structures. Each element in a linked list includes a pointer to the next, but none of the elements are necessarily near each other in memory.

In this part of the project you will implement a vector, sometimes refered to as an “arraylist”, which is a compromise between the two data structures. Vectors, like arrays, hold their contents in a contiguous region of memory. However, like linked lists, they can dynamically grow in size by reallocating space for their data. To avoid reallocating data everytime a new element is added, they’ll often allocate more space than the user requested.

Assignment Specification

In this part of the project, you will create your own implementation of a vector in C. Following this project, you will use vectors, as well as many other data structures defined in the C++ standard template library, for future assignments.

You have been provided with the basic structure for a vector in vector300.h. The defintion of this struct is below:

typedef struct vector300
{
    void *array; //pointer to a region of memory containing vector's data
    size_t ele_size; //size of the elements type
    size_t capacity; //number of elements the vector can fit
    size_t length; //number of elements in the vector
} vector_t;

Notes and Resources:

• What is the size_t data type in C?
• size_t ele_size: This field allows your vector implementation to be generic!
  • Example:
    • For a vector of ints, the ele_size field will be 4.
    • For a vector of chars, the ele_size will be 1.
• size_t capacity: To avoid reallocating data every time a new element is added, your vectors will often allocate more space than the user requested. We use the capacity field to distinguish between the number of elements the vector dynamically allocated space for and the the number of elements the user requested (the length field).
  • To balance allocating a huge chunk of unused memory and having to repeatedly reallocate data, vectors will often define an initial capacity, and each time the user meets this capacity, it will double the capacity. This is how the C++ vector implmentation and Java’s ArrayList implementation work.

All of the functions you are responsible for implementing is contained within vector.c.

void initialize_vector(vector_t* v, size_t type)

void destroy_vector(vector_t* v)

size_t vector_size(vector_t* v);

void* vector_get(vector_t* v, int index)

void vector_add_back(vector_t* v, void* ele)

void vector_delete_back(vector_t* v)

void vector_add(vector_t *v, void *ele, int index)

void vector_delete(vector_t *v, int index)

A Note on Pointer Arithmetic:

Recall from lecture that when you perform operations on pointers, the pointer is incremented/decremented in units of sizeof(type) bytes.

In this project, the pointers you are working with are void (meaning they have no specified type) so that your vector implementation can be generic. However, performing pointer arithmetic on void pointers will result in compiler errors since the compiler will not know by how many bytes the pointer should actually be indexed. One way to solve this is to first cast your pointer to a char* before doing any operations on it. Once you have casted your pointer to a char*, you can then access the elements at various offsets from the pointer by adding the exact number of bytes between the pointer and the desired element.

Relevant Library Functions

void *malloc(size_t size)

void *realloc(void *ptr, size_t size)

void free(void *ptr)

void *memcpy(void *dest, void *src, size_t n)

void *memmove(void *dest, void *src, size_t n)

Compile, Run, Test

The Makefile

• run the make command. This will create the testsuite executable to be used to run tests.
• To run, you can either use ./testsuite or make check

Testing

This test suite compares your vector implementation to the C++ standard library vector (std::vector). When your implementation is fully functional, the testsuite executable should print nothing out besides your point total.

Upon test failure, the testsuite prints out the expected state of the vector versus your vector. This output, in addition to the use of gdb, should help you track down and fix your errors. Additionally, the Makefile compiles the vector code with an address sanitizer. As such, you will get warnings if your implementation has any memory leaks or errors. A fully functional implementation should show no error output from the address sanitizer while it’s running.

Extra Credit: Encoding Detector

Often you or your programs may need to know the character set used in a file in order to interpret it. Linux actually provides a utility to do this that you may be familiar with, the file program:

$ cat some_text_file.txt
asdf
$ file some_text_file.txt
some_text_file.txt: ASCII text
$ cat some_utf8_file.txt
asdf❤️
$ file some_utf8_file.txt
UTF-8 Unicode text

As an extra credit assignment, you will have the opportunity to implement your own file encoding detector!

Extra Credit Stencil

All of the code for the extra credit can be found in the directory extra-credit. This directory contains the following files:

Assignment Specification

For this part of the project you will be implementing your own file utility (in file.c). Given a file as input, your file implementation should print out whether the given file is encoded using ASCII, UTF-8, or neither (undefined). Feel free to research other character sets to detect in your implementation; however, only ASCII and UTF-8 are required.

Relevant Library Functions

For this part of the assignment, you will have to be able to read input from files. You may find the below functions useful in doing so.

int open(const char *filename, int flags)

int close(int fd)

char *read(int fd, void *buf, size_t n)

Compile, Run, Test

The Makefile

• Run the make command. This will create the file executable
• To run your program against our provided test files, run make check

Testing

The command make check runs your file utility against all our test files. Feel free to create more files to test your encoding detector as needed.

Stretch Goal (hard!)

If you feel adventurous, try to make your file utility produce the same output as the Linux utility, which prints additional information about files (e.g., whether they contain C source code, or what kind of executable they are).

You can go very deep down the rabbit hole here (e.g., to quite literally look into magic 🪄), but a reasonable attempt would match the output for simple text files and source code.

make check-stretch will compare your file tool to the Linux one.

Handing In Your Code

You will hand in your code using Git. In the strvec/ subdirectory, you MUST fill in the text file called README.md. The README.md file will include the following:

1. Any design decisions you made and comments for graders, under “Design Overview”. If there’s nothing interesting to say, just list “None”.
2. Any collaborators and citations for help that you received, under “Collaborators”. CS 300 encourages collaboration, but we expect you to acknowledge help you received, as is standard academic practice.
3. Your answers to the conceptual questions at the start of this handout under “Conceptual Questions”.
4. Notes on approximately how long it took you to complete the project. We won’t use this for grading, but we collect the data to calibrate for future years.

Grading breakdown:

• 45% (45 points) tested string and wchar_t functionality (the test programs we hand out, plus others). If running ./run_tests reports that 100% of tests pass, you’ve probably got all these points.
• 30% (30 points) tested vector functionality. If running make check reports Total score: 20 out of 20, you’ve probably got all these points.
• 20% (20 points) answers to conceptual questions.
• 5% (5 points) completed README.md.
• The Extra Credit will be worth up to 6 additional points

Your submission will not be graded until you configure grading server. You should have used the grading server for Lab 0 already.

Step 1: Log into the grading server with the password you received. Once you’re logged in, enter your GitHub username (at the top).

Step 2: Add the repository URL under the “Strings and Vectors” category. Click “Strings and Vectors” to initiate a fetch of your repository from GitHub.

Note: If your GitHub account is not linked to your Brown email address, the grading server will give you a command to run to verify your project repository.

Step 3: You should see your commit listed on the Labs page, as shown above. You can use the buttons below the commit list to test your code in our grading environment. Make sure it still passes all the tests!

Congratulations, you’ve completed the first project!

Acknowledgements: We are grateful to Brown’s CS 33 course for providing the basis for the strings portiton of this project. The vectors and mbslen portions were developed for CS 300.