Dict Lab: A Serious Introduction to C

You will start by giving a definition for your main structure struct dict. (You cannot change the name of this type, it is however aliased (typedef’d) in dict.h as dict_t to avoid having to type struct each time.)

For instance, you may want to have a dictionary implemented as a linked list; in that case, you can store the head of that list and its length in your structure:

struct dict {
    struct dict_list* head;
    size_t size;
};

The first field is a pointer (*) to the head of the list, that is, its memory address. The struct dict_list itself contains the key, the value, and the address of the next element in the list:

struct dict_list {
    char* key;
    char* val;
    struct dict_list* next;
};

The end of the list is signaled by having next be NULL.

// Forward declaration.
void execute_command (const char* cmd);

int main (int argc, char** argv) {
  ...
}

void execute_command (const char* cmd) {
  // Actual code
}

Equipped with these structures, start by implementing:

dict_t* dict_create ();

This function should allocate a new structure of type dict_t (aka struct dict), initialize its members, and return the newly allocated structure. To do so, you will call malloc to allocate a sufficient amount of memory:

dict_t* ret = malloc (sizeof (dict_t));

Then, you should initialize the fields of ret. Since ret is a pointer, to access the object it points to, you should use *ret; hence the size field is accessed using (*ret).size. C has a shorthand notation for this very common construct:

ret->size = 0;

Now make sure to initialize head (since its value is garbage as it was just allocated) and you are done and can return ret.

You will be implementing dict_destroy in Part 2; this is the function that will be in charge of freeing the memory that was just allocated: in C, memory that is malloc’d is never automatically freed. Memory allocation is the topic of Ch. 9.

Next, you will implement:

char* dict_get (const dict_t* dict, const char* key);

This function goes through the list given by dict. If you use the above structure, this means starting at el = dict->head and checking each time whether the key at el is key; if it is not, we set el = el->next, until either key is found, or we reach el == NULL.

To compare key with el->key, we need to compare one by one each character in key with those in el->key. Remember that strings in C are just pointers (memory addresses) to the first character in the string, so comparing el->key == key will not do what you want. So how do you even get the length of a string s? You would start at memory location s and advance as long as the byte at s (i.e. *s) is not the end-of-string marker (\0, the NULL character). This can get a bit messy, so luckily, you are allowed to use the string comparison function strcmp(3) provided by the standard library:

• strcmp (s1, s2): returns 0 iff s1 and s2 are the same strings. Hence in if (strcmp (s1, s2))..., the condition holds if the strings are different—be careful.

If key is found, return the corresponding value; otherwise, return NULL.

It is now time for:

void    dict_put (dict_t* dict, const char* key, const char* val);

This function stores the pair key / val in the dictionary dict, possibly erasing the previous value associated with key.

It should make private copies of key and val as required. This means that the function cannot use, for instance, my_element->val = val. To make a copy of a string s, one could:

1. allocate strlen(s) + 1 bytes using malloc(3) (strlen(3) returns the length of a string, not counting the end-of-string marker)
2. go through the strlen(s) + 1 bytes of s and copy each byte, using either a loop or the function memcpy(3)

Again, the standard library provides a function for this: strdup(3)—remember that since its return value was malloc’d, it needs to be free’d.

The function works as follows:

• If key is found in dict, then the associated value should be freed and replaced by a copy of val.
• If key is not found in dict, then a new element is added to the list; that element’s key is a copy of key and its value is a copy of val.

Finally, you should implement:

void    dict_del (dict_t* dict, const char* key);

This function goes through dict searching for key, if it finds it, it should delete the corresponding key/value pair. The memory allocated for the element and its key/value pair should be free’d. If the key does not exist, this function does nothing.

The three commands to be implemented in this part are:

• get KEY: print the value associated with KEY followed by a newline \n. If no such value exists, a blank line is printed.
• put KEY:VALUE: store the pair KEY / VALUE. Note that both KEY and VALUE can be arbitrary strings, with the only guarantee being that KEY does not contain a colon. Additionally, these strings don’t contain a newline \n. Nothing is printed in return.
• del KEY: delete the pair associated with KEY, if it exists. Nothing is printed in return, even if the key does not exist in the dictionary.

You will implement the function:

void dict_clear (dict_t* dict);

This function clears the dictionary dict, destroying each pair key/value, but does not destroy dict itself (remember that dict was allocated using dict_create, so it will need to be freed at some point, but this is not this function’s job.)

In practice, if you use a linked-list implementation, you will start at dict->head and free each key and val, then free the dict_list object itself, before going to the next element. It is strongly recommended that you do not implement this recursively. By saving the next pointer before freeing the element, you will make sure that you are not trying to access a field in a destroyed variable.

This is now the function that frees (destroys) a dictionary:

void dict_destroy (dict_t* dict);

This operates just as dict_clear, but in addition should free the memory that was allocated during dict_create. After a call to this function, if any other library function receives the pointer dict, the behavior is undefined (most likely, it will crash).

This simple function returns the current size of the dictionary:

size_t dict_size (const dict_t* dict);

This function has the (nontrivial) type:

void dict_apply (const dict_t* dict, const dict_apply_fun_t fun, void* arg);

For each pair key / value in dict, it will call the function fun with arguments (key, value, arg). This is a type of “for each” loop (or map), showing that C is well capable of using advanced programming concepts, albeit with a somewhat contrived syntax. The type dict_apply_fun_t is the interesting part here:

typedef void (*dict_apply_fun_t) (const char* key, const char* val, void* arg);

This defines a type dict_apply_fun_t as “pointer to a function that returns void and takes two arguments of type const char* and one of type void* (untyped pointer)”. Indeed, functions have addresses (more on that in Ch. 7), so one can talk about pointers to functions. To call the function pointed at by fun, one can use a normal function-call syntax (fun (key, value, arg)) or dereference the pointer first ((*fun) (key, value, arg))—this is a matter of taste.

In the following example (print.c), we create a dictionary, put a few things in it, then call dict_apply to print all the values in the dictionary. We use the extra argument arg to count the number of elements. We need to retype arg since dict_apply demoted its type to a generic pointer void*.

#include <stdio.h>
#include "dict.h"

void print_pair (const char* key, const char* val, void* arg) {
  // Retype arg
  int* pi = arg;
  printf ("%d. key: %s, val: %s\n", *pi, key, val);
  (*pi)++;
}

int main () {
  dict_t* dict = dict_create ();
  dict_put (dict, "abc", "def");
  dict_put (dict, "123", "456");

  int i = 0;
  dict_apply (dict, &print_pair, &i);
}

Next we compile this with our dictionary library and run it:

$ gcc -c -Wall print.c
$ gcc -c -Wall dict.c
$ gcc print.o dict.o -o print
$ ./print
0. key: abc, val: def
1. key: 123, val: 456

This command does not manipulate files; it simply dumps the dictionary to the standard output. It should start by printing BEGIN_DUMP, then all the pairs key:value separated by newlines, then END_DUMP:

> put abc:def
> put 123:456
> dmp
BEGIN_DUMP
abc:def
123:456
END_DUMP
>

To implement this, refer to the example file print.c in Section dict_apply. The order in which the elements are printed is not important (it depends on how you implemented your dictionary).

The command svf FILE dumps the content of the dictionary in a file, then prints the message SAVED when done:

> put abc:def
> put 123:456
> svf /tmp/test.txt
SAVED
> CTRL-d
goodbye.
$ cat /tmp/test.txt
abc:def
123:456
$

In the following example, we open a file for writing (w), write using fprintf(f, ...) (i.e., printf to file f), and close the file:

FILE* f = fopen (filename, "w");
if (!f)
  error ("could not open %s for writing\n", filename);
fprintf (f, "File object is a pointer with value %p\n", f);
fclose (f);

You will also be using dict_apply for this; this time however, the extra argument arg will prove useful: this will be used to store the FILE* variable.

The command ldf FILE adds the key/value pairs in the file FILE to the dictionary and prints LOADED when done. As with put, if the key already exists, its value is overwritten:

$ cat /tmp/test.txt
abc:def
123:456
$ src/dict
> put 123:numbers
> put xyz:letters
> ldf /tmp/test.txt
LOADED
> dmp
BEGIN_DUMP
123:456
xyz:letters
abc:def
END_DUMP
>

To open a file for reading, use "r" as the second argument of fopen(3); in the following example, we open filename for reading and check if we can read one character:

FILE* f = fopen (filename, "r");
if (!f)
  error ("could not open %s for reading\n", filename);
char c = fgetc (f);
if (c == EOF)
  printf ("%s is empty\n", filename);
else
  printf ("%s is nonempty\n", filename);
fclose (f);

In your implementation, rather than just reading one character, you will repeatedly read each line of f, split that line at the colon, and call dict_put to populate the current dictionary.

In addition, your program should now be able to take arguments that are files that should be loaded silently at the beginning of the execution:

$ cat /tmp/test.txt
abc:def
123:456
$ src/dict /tmp/test.txt
> dmp
BEGIN_DUMP
abc:def
123:456
END_DUMP

The number of such files passed in argument is not limited.

int main (int argc, char* argv[])