Project: an address book

Lesson 30 of 30 · Part 6 · Going further · about 20 minutes

Time to put the pieces together. In this lesson you'll build a small address book, one step at a time. Each step is a complete program that you can run, and each one adds a little to the one before. Here's the plan:

Piece	What it does	From lesson
`Contact`	one person: a name and a phone number	23, 25
`Book`	all the contacts, in an array that grows	22, 24
`book_add`	adds a contact, making room when it's full	20, 22
`book_list`	shows everyone	17, 24
`book_find`	finds a contact by name	14
`book_remove`	takes a contact out	11, 23
`book_free`	gives the memory back	20, 21

One contact

Start with what one contact looks like: a name and a phone number, both strings. A phone number is kept as text, not as an int: it can start with 0 and has a - in it.

main.c

1#include <stdio.h>2 3typedef struct {4    char name[20];5    char phone[16];6} Contact;7 8void print_contact(const Contact *c) {9    printf("%s: %s\n", c->name, c->phone);10}11 12int main(void) {13    Contact friends[2] = {14        {"Ana", "555-0101"},15        {"Ben", "555-0102"}16    };17    for (int i = 0; i < 2; i++) {18        print_contact(&friends[i]);19    }20    return 0;21}

Output

Ana: 555-0101
Ben: 555-0102

print_contact takes a pointer, so the struct isn't copied, and const promises that the function only reads it. A name must fit in 19 characters, plus the '\0'.

A book that grows

A fixed array of 2 is too small, and you can't know in advance how many friends someone has. So the book keeps its contacts on the heap, in an array that doubles when it's full, just like the growing list in lesson 22. count is how many contacts there are; capacity is how many fit.

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_free(Book *book) {36    free(book->items);37    book->items = NULL;38    book->count = 0;39    book->capacity = 0;40}41 42int main(void) {43    Book book = {NULL, 0, 0};44    book_add(&book, "Ana", "555-0101");45    book_add(&book, "Ben", "555-0102");46    book_add(&book, "Chloe", "555-0103");47    printf("%d contacts, room for %d\n", book.count, book.capacity);48    book_free(&book);49    return 0;50}

Output

3 contacts, room for 4

The book starts empty: items is NULL and there's no room at all. realloc(NULL, size) works just like malloc(size), so the first book_add gets room for 2. The third one finds the book full and asks realloc for room for 4. If realloc fails, the old block is still there, and book_add gives back 0.

Press Step and watch the heap. A block for 2 contacts appears, then it's replaced by a block for 4, with Ana and Ben copied across, and the arrow from book.items moves to it. At the end, book_free gives that block back too: every block on the heap is gray, "freed", and none is marked "leaked".

Guess first

After 5 contacts, how many fit in the book?

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int main(void) {36    Book book = {NULL, 0, 0};37    book_add(&book, "Ana", "555-0101");38    book_add(&book, "Ben", "555-0102");39    book_add(&book, "Chloe", "555-0103");40    book_add(&book, "Dan", "555-0104");41    book_add(&book, "Eva", "555-0105");42    printf("room for %d\n", book.capacity);43    free(book.items);44    return 0;45}

Output

Listing everyone

To show the book, go through items from 0 to count - 1. Stop at count, not capacity: the places after count have nothing written in them yet.

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    if (book->count == 0) {37        printf("(empty)\n");38    }39    for (int i = 0; i < book->count; i++) {40        printf("%d. %s: %s\n", i + 1, book->items[i].name, book->items[i].phone);41    }42}43 44void book_free(Book *book) {45    free(book->items);46    book->items = NULL;47    book->count = 0;48    book->capacity = 0;49}50 51int main(void) {52    Book book = {NULL, 0, 0};53    book_list(&book);54    book_add(&book, "Ana", "555-0101");55    book_add(&book, "Ben", "555-0102");56    book_add(&book, "Chloe", "555-0103");57    book_list(&book);58    book_free(&book);59    return 0;60}

Output

(empty)
1. Ana: 555-0101
2. Ben: 555-0102
3. Chloe: 555-0103

book_list only reads the book, so it takes a const Book *. book_add and book_free change it, so they take a plain Book *.

Finding by name

book_find compares each name with strcmp (== doesn't work on strings, lesson 14). It gives back the index of the contact, or -1 when there's no one with that name:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int book_find(const Book *book, const char *name) {36    for (int i = 0; i < book->count; i++) {37        if (strcmp(book->items[i].name, name) == 0) {38            return i;39        }40    }41    return -1;42}43 44void book_free(Book *book) {45    free(book->items);46    book->items = NULL;47    book->count = 0;48    book->capacity = 0;49}50 51int main(void) {52    Book book = {NULL, 0, 0};53    book_add(&book, "Ana", "555-0101");54    book_add(&book, "Ben", "555-0102");55    book_add(&book, "Chloe", "555-0103");56    const char *wanted[2] = {"Ben", "Zoe"};57    for (int k = 0; k < 2; k++) {58        int i = book_find(&book, wanted[k]);59        if (i == -1) {60            printf("%s: not found\n", wanted[k]);61        } else {62            printf("%s: %s\n", wanted[k], book.items[i].phone);63        }64    }65    book_free(&book);66    return 0;67}

Output

Ben: 555-0102
Zoe: not found

wanted is an array of two const char * pointers, each pointing at a name to look up. Why give back an index instead of the phone number? Because the other functions can use it too: book_remove needs to know where the contact is.

Removing a contact

To take out the contact at index i, move every contact after it one place to the left, then make count one smaller. Assigning one struct to another copies all of it (lesson 23), name and phone together. The order of the others stays the same.

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    if (book->count == 0) {37        printf("(empty)\n");38    }39    for (int i = 0; i < book->count; i++) {40        printf("%d. %s: %s\n", i + 1, book->items[i].name, book->items[i].phone);41    }42}43 44int book_find(const Book *book, const char *name) {45    for (int i = 0; i < book->count; i++) {46        if (strcmp(book->items[i].name, name) == 0) {47            return i;48        }49    }50    return -1;51}52 53int book_remove(Book *book, const char *name) {54    int i = book_find(book, name);55    if (i == -1) {56        return 0;57    }58    for (int j = i; j < book->count - 1; j++) {59        book->items[j] = book->items[j + 1];60    }61    book->count--;62    return 1;63}64 65void book_free(Book *book) {66    free(book->items);67    book->items = NULL;68    book->count = 0;69    book->capacity = 0;70}71 72int main(void) {73    Book book = {NULL, 0, 0};74    book_add(&book, "Ana", "555-0101");75    book_add(&book, "Ben", "555-0102");76    book_add(&book, "Chloe", "555-0103");77    book_add(&book, "Dan", "555-0104");78    book_remove(&book, "Ben");79    if (!book_remove(&book, "Zoe")) {80        printf("No Zoe to remove\n");81    }82    book_list(&book);83    printf("%d contacts, room for %d\n", book.count, book.capacity);84    book_free(&book);85    return 0;86}

Output

No Zoe to remove
1. Ana: 555-0101
2. Chloe: 555-0103
3. Dan: 555-0104
3 contacts, room for 4

The loop stops at count - 1, because items[j + 1] must still be a real contact. After removing Ben there's room for 4 but only 3 contacts: the book doesn't get smaller, and that's fine. This is the whole address book. Press Step once more and follow Ben's place being filled by Chloe, then Chloe's by Dan.

Freeing everything

Every block from malloc or realloc needs exactly one free. The book has only one block, items, because the contacts sit inside it, so book_free needs only one free. It then sets items to NULL and the counts to 0, so the book is a valid empty book again: you could call book_add on it once more, or call book_free twice without freeing the same block twice.

Forget book_free, and the block stays taken until the program ends. That's the memory leak from lesson 21. In a program that runs for a long time, such as a phone's contacts app, leaks pile up.

Tip: Write the function that frees something at the same time as the one that makes it. Then every book_add has a matching book_free from the start.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it. Each exercise adds a feature to the address book.

Exercise 1

Change a number

Write book_set_phone: find the contact with that name and give it the new phone number. Give back 1 if it worked and 0 if there's no such name. The program should then list Ben with 555-9999.

It should print

No Zoe
1. Ana: 555-0101
2. Ben: 555-9999

exercise1.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    for (int i = 0; i < book->count; i++) {37        printf("%d. %s: %s\n", i + 1, book->items[i].name, book->items[i].phone);38    }39}40 41int book_find(const Book *book, const char *name) {42    for (int i = 0; i < book->count; i++) {43        if (strcmp(book->items[i].name, name) == 0) {44            return i;45        }46    }47    return -1;48}49 50int book_set_phone(Book *book, const char *name, const char *phone) {51 52}53 54int main(void) {55    Book book = {NULL, 0, 0};56    book_add(&book, "Ana", "555-0101");57    book_add(&book, "Ben", "555-0102");58    book_set_phone(&book, "Ben", "555-9999");59    if (!book_set_phone(&book, "Zoe", "555-0000")) {60        printf("No Zoe\n");61    }62    book_list(&book);63    free(book.items);64    return 0;65}

Output

Press Run or Ctrl+Enter

Exercise 2

No doubles

Right now you can add Ana twice. Change book_add so that, when the name is already in the book, it adds nothing and gives back 0. The program should print Ana is already there and list only 2 contacts.

It should print

Ana is already there
1. Ana: 555-0101
2. Ben: 555-0102

exercise2.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_find(const Book *book, const char *name) {17    for (int i = 0; i < book->count; i++) {18        if (strcmp(book->items[i].name, name) == 0) {19            return i;20        }21    }22    return -1;23}24 25int book_add(Book *book, const char *name, const char *phone) {26    if (book->count == book->capacity) {27        int new_capacity = book->capacity * 2;28        if (new_capacity == 0) {29            new_capacity = 2;30        }31        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));32        if (bigger == NULL) {33            return 0;34        }35        book->items = bigger;36        book->capacity = new_capacity;37    }38    strcpy(book->items[book->count].name, name);39    strcpy(book->items[book->count].phone, phone);40    book->count++;41    return 1;42}43 44void book_list(const Book *book) {45    for (int i = 0; i < book->count; i++) {46        printf("%d. %s: %s\n", i + 1, book->items[i].name, book->items[i].phone);47    }48}49 50int main(void) {51    Book book = {NULL, 0, 0};52    book_add(&book, "Ana", "555-0101");53    book_add(&book, "Ben", "555-0102");54    if (!book_add(&book, "Ana", "555-0199")) {55        printf("Ana is already there\n");56    }57    book_list(&book);58    free(book.items);59    return 0;60}

Output

Press Run or Ctrl+Enter

Exercise 3

Save to a file

Write book_save: write each contact to the file as one line, the name, a space, then the phone, like Ana 555-0101. Give back 0 if the file can't be opened, 1 otherwise. main already reads the file back and prints it.

It should print

Ana 555-0101
Ben 555-0102
Chloe 555-0103

exercise3.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int book_save(const Book *book, const char *filename) {36 37}38 39int main(void) {40    Book book = {NULL, 0, 0};41    book_add(&book, "Ana", "555-0101");42    book_add(&book, "Ben", "555-0102");43    book_add(&book, "Chloe", "555-0103");44    book_save(&book, "contacts.txt");45    free(book.items);46 47    char line[100];48    FILE *f = fopen("contacts.txt", "r");49    if (f == NULL) {50        printf("Nothing saved\n");51        return 1;52    }53    while (fgets(line, sizeof line, f) != NULL) {54        printf("%s", line);55    }56    fclose(f);57    return 0;58}

Output

Press Run or Ctrl+Enter

What you learned

A bigger program is built from small functions that each do one job: add, list, find, remove, free.
A struct holds one record; a second struct holds the array, its count and its capacity.
The array lives on the heap and doubles with realloc when it's full; realloc(NULL, size) is like malloc(size).
Functions that only read take a const pointer; functions that change the book take a plain pointer.
Removing from the middle means moving the later items one place to the left.
Every block you get gets one free; after freeing, set the pointer to NULL.