Reservation app in C with linked list, BST, and CSV

Question

This is a reservations app with linked lists for insertion and BST for search. It uses CSV files for storage, recursion for printing and handles memory allocation for variable growth.

I'm looking for tips to simplify, speed up, and make code clearer.

//===== Imports =====
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>

//===== Data Structures =====
typedef struct {
    int y, m, d;
} Date;

typedef struct {
    Date date;
    char *name;
} Reservation;

typedef struct Node {
    Reservation r;
    struct Node* next;
} Node;

typedef struct TreeNode {
    Reservation r;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

//===== Utilities =====
static char* strdupMallocChecked(const char* s) {
    if (!s) s = "";
    char* p = malloc(strlen(s) + 1);
    if (!p) { perror("malloc"); exit(EXIT_FAILURE); }
    strcpy(p, s);
    return p;
}

static bool validateDate(int y, int m, int d) {
    if (m < 1 || m > 12) return false;
    int dm[] = {31,28,31,30,31,30,31,31,30,31,30,31};
    if (m == 2 && ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0))) dm[1] = 29;
    return d >= 1 && d <= dm[m-1];
}

static Date getCurrentDate(void) {
    time_t t = time(NULL);
    struct tm *tm_info = localtime(&t);
    return (Date){ tm_info->tm_year + 1900, tm_info->tm_mon + 1, tm_info->tm_mday };
}

static int dateCompareDate(const Date *a, const Date *b) {
    if (a->y != b->y) return a->y - b->y;
    if (a->m != b->m) return a->m - b->m;
    return a->d - b->d;
}

static int reservationCompare(const Reservation *A, const Reservation *B) {
    int d = dateCompareDate(&A->date, &B->date);
    if (d != 0) return d;
    return strcmp(A->name ? A->name : "", B->name ? B->name : "");
}

//===== Insert =====
static void insertListSorted(Node** head, const Reservation* r) {
    Node* n = malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(EXIT_FAILURE); }
    n->r.date = r->date;
    n->r.name = strdupMallocChecked(r->name);
    n->next = NULL;

    if (!*head || reservationCompare(&n->r, &(*head)->r) < 0) {
        n->next = *head;
        *head = n;
        return;
    }

    Node* cur = *head;
    while (cur->next && reservationCompare(&cur->next->r, &n->r) <= 0) cur = cur->next;
    n->next = cur->next;
    cur->next = n;
}

static void insertTreeByDate(TreeNode** root, const Reservation* r) {
    TreeNode** cur = root;
    while (*cur) {
        int cmp = dateCompareDate(&r->date, &(*cur)->r.date);
        if (cmp < 0) cur = &(*cur)->left;
        else if (cmp > 0) cur = &(*cur)->right;
        else cur = (strcmp(r->name, (*cur)->r.name) < 0) ? &(*cur)->left : &(*cur)->right;
    }

    *cur = malloc(sizeof(TreeNode));
    if (!*cur) { perror("malloc"); exit(EXIT_FAILURE); }
    (*cur)->r.date = r->date;
    (*cur)->r.name = strdupMallocChecked(r->name);
    (*cur)->left = NULL;
    (*cur)->right = NULL;
}

//===== Checks =====
static bool isDateAvailable(Node* head, const Date *d) {
    for (Node* n = head; n; n = n->next)
        if (dateCompareDate(&n->r.date, d) == 0) return false;
    return true;
}

//===== Input =====
static void readLineTrim(char **buf) {
    size_t len = 0;
    ssize_t n = getline(buf, &len, stdin);
    if (n > 0 && (*buf)[n-1] == '\n') (*buf)[n-1] = '\0';
}

static Reservation inputReservation(void) {
    Reservation r = {.date={0,0,0}, .name=NULL};
    Date cur = getCurrentDate();
    char *buf = NULL;

    printf("Enter company name: ");
    readLineTrim(&buf);
    if (!buf || buf[0]=='\0') { free(buf); buf = strdupMallocChecked("unnamed"); }
    r.name = strdupMallocChecked(buf);
    free(buf);

    for (;;) {
        printf("Enter reservation date (YYYY MM DD): ");
        buf = NULL;
        readLineTrim(&buf);
        int y,m,d;
        if (sscanf(buf,"%d %d %d",&y,&m,&d)!=3) { printf("Invalid format. Try again.\n"); free(buf); continue; }
        free(buf);
        if (!validateDate(y,m,d)) { printf("Invalid date.\n"); continue; }
        Date tmp={y,m,d};
        if (dateCompareDate(&tmp,&cur)<0) { printf("Cannot choose past date.\n"); continue; }
        r.date=tmp; break;
    }
    return r;
}

//===== CSV I/O =====
static void saveCSV(Node* head) {
    FILE* f = fopen("res.csv","w");
    if (!f) { perror("saveCSV"); return; }
    for (Node* n=head;n;n=n->next)
        fprintf(f,"%04d,%02d,%02d,%s\n",n->r.date.y,n->r.date.m,n->r.date.d,n->r.name);
    fclose(f);
}

static void loadCSV(Node** head, TreeNode** root) {
    FILE* f = fopen("res.csv","r");
    if (!f) { perror("loadCSV"); return; }
    char* lineBuf=NULL; size_t len=0;
    while (getline(&lineBuf,&len,f)!=-1) {
        lineBuf[strcspn(lineBuf,"\r\n")] = 0;
        char* token = strtok(lineBuf,","); if(!token) continue; int y=atoi(token);
        token=strtok(NULL,","); if(!token) continue; int m=atoi(token);
        token=strtok(NULL,","); if(!token) continue; int d=atoi(token);
        token=strtok(NULL,","); if(!token) continue; char* name=strdupMallocChecked(token);
        Reservation r={{y,m,d},name};
        insertListSorted(head,&r);
        insertTreeByDate(root,&r);
        free(name);
    }
    free(lineBuf);
    fclose(f);
}

//===== Print =====
static void printListRecursive(const Node* n) {
    if(!n) return;
    printf("%04d-%02d-%02d : %s\n",n->r.date.y,n->r.date.m,n->r.date.d,n->r.name);
    printListRecursive(n->next);
}

//===== Search =====
static TreeNode* searchTreeByName(const TreeNode* t,const char* key) {
    if(!t) return NULL;
    int cmp=strcmp(key,t->r.name);
    if(cmp==0) return (TreeNode*)t;
    else if(cmp<0) return searchTreeByName(t->left,key);
    else return searchTreeByName(t->right,key);
}

static Node* searchListByName(const Node* n,const char* key) {
    if(!n) return NULL;
    if(strcmp(n->r.name,key)==0) return (Node*)n;
    return searchListByName(n->next,key);
}

//===== Free =====
static void freeList(Node* n) {
    while(n) {
        Node* nx = n->next;
        free(n->r.name);
        free(n);
        n = nx;
    }
}

static void freeTree(TreeNode* t) {
    if(!t) return;
    freeTree(t->left);
    freeTree(t->right);
    free(t->r.name);
    free(t);
}

static void cleanup(Node** head, TreeNode** root) {
    freeList(*head);
    *head=NULL;
    freeTree(*root);
    *root=NULL;
}

//===== High-level API =====
static void addReservationFlow(Node** head, TreeNode** root) {
    Reservation r = inputReservation();
    if(!isDateAvailable(*head,&r.date)) {
        printf("Room booked.\n");
        free(r.name);
        return;
    }
    insertListSorted(head,&r);
    insertTreeByDate(root,&r);
    printf("Reservation successful.\n");
    free(r.name);
}

//===== Menu =====
static void menuLoop(void) {
    Node* head=NULL;
    TreeNode* root=NULL;
    loadCSV(&head,&root);

    for(;;) {
        puts("\n1.Add  2.Show reservations  3.Search  4.Save+Exit");
        printf("Choice: ");
        char* choice=NULL;
        readLineTrim(&choice);
        int o=atoi(choice);
        free(choice);

        if(o==1) {
            addReservationFlow(&head,&root);
        } else if(o==2) {
            printListRecursive(head);
        } else if(o==3) {
            char* key=NULL;
            printf("Enter company name to search: ");
            readLineTrim(&key);
            Node* resList = searchListByName(head,key);
            TreeNode* resTree = searchTreeByName(root,key);
            if(resList) printf("Found (list): %04d-%02d-%02d %s\n",resList->r.date.y,resList->r.date.m,resList->r.date.d,resList->r.name);
            if(resTree) printf("Found (tree): %04d-%02d-%02d %s\n",resTree->r.date.y,resTree->r.date.m,resTree->r.date.d,resTree->r.name);
            if(!resList && !resTree) printf("Not found.\n");
            free(key);
        } else {
            saveCSV(head);
            break;
        }
    }

    cleanup(&head,&root);
}

//===== Main =====
int main(void) {
    menuLoop();
    return EXIT_SUCCESS;
}

Answer 1

General linked list suggestions

• You are treating Node ** as (the head of) a list. This means that insertion at the end must traverse the entire list every single time. If you have a struct to represent a list which contains the head and the tail node, insertion at the end goes from O(n) to O(1) while retaining O(1) insertion at the front.

• If you do this, you could also store the length of the list and not require it to be recalculated (if needed) on each call.

• If you want to enforce these things, you may wish to implement your list in separate header and source files and make your list type an opaque type.

• One might invoke Bjarne Stroustrop and suggest you shouldn't be using a linked list at all, but rather a dynamic array. With the linked list your insertListSorted function is cleaner and has less work to do in terms of moving data, but that may not be worth it in terms of additional memory overhead and indirection for the nodes.

• If you're sticking with linked lists, you may wish to make the extra effort to design a linked list which can work with different data types. This then becomes something that can be reused in other projects rather than having to be reimplemented each time.

Binary search tree

Your binary search tree preserves the ordering invariant, but it's not a balanced binary search tree. Consider if we had a simple binary search tree that doesn't maintain balance, and we insert 1, 2, 3, 4, and 5.

  1   1    1     1      1
       \    \     \      \
        2    2     2      2
              \     \      \
               3     3      3
                      \      \
                       4      4
                               \
                                5

Unfortunately this looks an awful lot like a linked list, and gains us no efficiency. What we really wanted was:

  1    1       2        2        2        2
        \     / \      / \      / \      / \
         2   1   3    1   3    1   3    1   4
                                    \      / \
                                     4    3   5

Consider reading up on AVL trees.

Ternary operator

toolic has already suggested cleaning up your conditional assigning to cur, but we might not want to mix the ternary operator and regular conditionals. If we don't we get either:

if (cmp < 0)
    cur = &(*cur)->left;
else if (cmp > 0) 
    cur = &(*cur)->right;
else if (strcmp(r->name, (*cur)->r.name) < 0)
    cur = &(*cur)->left;
else
    cur = &(*cur)->right;

Or we could express this using only the ternary operator.

cur = 
    cmp < 0 ? &(*cur)->left :
    cmp > 0 ? &(*cur)->right :
    strcmp(r->name, (*cur)->r.name) < 0 ? &(*cur)->left : &(*cur)->right;

Streamlining searchListByName redundancy

static Node* searchListByName(const Node* n,const char* key) {
    if(!n) return NULL;
    if(strcmp(n->r.name,key)==0) return (Node*)n;
    return searchListByName(n->next,key);
}

If !n then n is NULL and we could simply write:

    if (!n) return n;

But then we'd notice that both conditions return the same value and we can just or the conditions together, taking advantage of the short-circuiting behavior of ||.

static Node* searchListByName(const Node* n, const char* key) {
    if (!n || strcmp(n->r.name, key) == 0) 
        return n;

    return searchListByName(n->next, key);
}

Code organization

As I previously alluded to, all of your linked list and binary search tree logic should de documented in headers, implemented in source files, and then included/linked with the program containing your actual useful app.

By doing this you:

1. Give us a lot less to sort through at one time.
2. Give yourself the opportunity to thoroughly test these data structures independent of the rest of your program.

Answer 2

This is an interactive, menu-driven program. I would expect that runtime failures would result in a return to the menu. But instead, we unceremoniously dump the user back to their shell without opportunity to save their work so far:

    if (!n) { perror("malloc"); exit(EXIT_FAILURE); }

perror() is inappropriate here, since malloc() is not specified to set errno on failure (POSIX systems are required to, but in the absence of other indicators, I'm assuming this is intended to be a portable program).

---

When allocating memory, it's easier to match the requested type if we use the assigned-to variable to compute. In other words, rather than

    *cur = malloc(sizeof(TreeNode));

we would write

    *cur = malloc(sizeof **cur);

---

validateDate() allows dates to be specified billions of years past and future - is that really reasonable?

---

insertTreeByDate() needlessly repeats the logic of reservationCompare(); why not just call it?

    while (*cur) {
        cur = reservationCompare(r, &(*cur)->r) < 0 ?
            &(*cur)->left : &(*cur)->right;
    }

---

readLineTrim() uses undeclared type ssize_t and function getline(). Perhaps this isn't a portable C program as advertised? It should also have a comment explaining how errors are reported when reading standard input fails - it's not at all clear what to test.

---

Similarly, inputReservation() should be clearer that a reservation with {0, 0, 0} as its date is a sentinel value rather than a real return value (this one I did manage to deduce from the code).

---

Instead of repeatedly allocating in the inputReservation() loop, it would be better to re-use the storage when possible, and only free() it after the loop. This loop appears to busy-lockup when we run out of input - that certainly needs to be fixed.

---

saveCSV() is rather rude, overwriting any existing file without warning.

---

loadCSV() doesn't deal with malformed input very well, since atoi() just returns 0 for unparseable strings - perhaps sscanf() would be more appropriate, and more obviously match how we read user input?

This function also treats read errors as EOF, so could result in reading just part of the file.

---

printListRecursive is almost the same as the writing loop in saveCSV(). It should be simple to make them share code (perhaps even consider changing the file format so they can use the same format string).

---

The main menu treats unrecognised input as "save" - probably better instead to emit an error message instead. I recommend switch instead of the if/else if chain.

---

What's most unclear to me is why we duplicate the bookings as a list, when we already have a tree which gives much more efficient access in sorted order.

Answer 3

UX

When I run the code, I see this message:

loadCSV: No such file or directory

The code expects me to have a file named "res.csv", but I do not. The error message could be enhanced to tell me that I need that file. It should also inform me why it needs that file.

Perhaps the code could support prompting the user for a different file when that one is not found.

Naming

It's nice that you created a struct for the date. However, lines like this are hard to understand:

return a->d - b->d;

Consider using words instead of single letter variable names in the struct:

typedef struct {
    int year, month, day;
} Date;

This is easier to understand:

return a->day - b->day;

Consider allowing the validateDate function to take a Date struct as input.

In the validateDate function, dm is a bit cryptic. days_in_month is more descriptive.

Layout

Cramming multiple statement onto a single line can make for really long lines of code, such as:

if (sscanf(buf,"%d %d %d",&y,&m,&d)!=3) { printf("Invalid format. Try again.\n"); free(buf); continue; }

That can detract from readability. This is easier to read and understand:

if (sscanf(buf,"%d %d %d",&y,&m,&d)!=3) {
    printf("Invalid format. Try again.\n");
    free(buf);
    continue;
}

There are many instances of this.

Similarly, these lines:

if (cmp < 0) cur = &(*cur)->left;
else if (cmp > 0) cur = &(*cur)->right;
else cur = (strcmp(r->name, (*cur)->r.name) < 0) ? &(*cur)->left : &(*cur)->right;

are easier to read as:

if (cmp < 0)
    cur = &(*cur)->left;
else if (cmp > 0) 
    cur = &(*cur)->right;
else
    cur = (strcmp(r->name, (*cur)->r.name) < 0) ? &(*cur)->left : &(*cur)->right;

The 3 assignments to cur are aligned vertically.

Answer 4

The recursive call in printListRecursive() is not needed, and could be a simple while loop:

static void printList(const Node* n) {
    while(n) 
    {
        printf("%04d-%02d-%02d : %s\n",n->r.date.y,n->r.date.m,n->r.date.d,n->r.name);
        n=n->next;
    }
}