Interactive console application to edit a sorted list

Question

I am reading a book that has some difficult vocabulary and I, in order to understand the book thoroughly, decided to collect and lookup those words am not acquainted with, spend sometime learning them, and re-read the book.

I have created an interactive console application specifically for this purpose. The program's main objectives are:

• Open a file for reading and writing
• Load data from file into linked list, if any, and sort them alphabetically.
• Accept input from user, and search through the list for matches to display on screen.
• If right key, is pressed, discard input. If Return key is pressed, save input to file, and if Escape key is pressed, cleanup and terminate program.

The key of interactivity is to show the user whether he added a word to the list or not, to avoid duplicates.

However, I have noticed that my implementation is hefty on the CPU, because when I run it, after short time, the fans become noisy, which make it hard for me to read and concentrate. Please advise on how can I optimize it and what improvements can be made.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <Windows.h>

struct G_list {
    char word[100];
    struct G_list *ptr;
};

typedef struct G_list G_list;

void add_and_sort(const char *str, G_list **head);
void free_list(G_list *head);

int cmp_at_begn(char *str, const char *substr);
void traverse_list(char *str, G_list *head);
void ClearScreen(void *hConsole);

int main(void)
{
    /* open file for reading and writing */
    const char filename[] = "Book.txt";
    FILE *fp = fopen(filename, "a+");
    if (!fp) {
        perror(filename);
        return 1;
    }

    /* ... */
    char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
    const size_t len = strlen(alphabet);

    /* allocate memory */
    G_list **wlist = (G_list **)malloc(sizeof(G_list *) * len);
    for (size_t i = 0; i < len; i++) {
        wlist[i] = (G_list *)malloc(sizeof(G_list));
        wlist[i]->ptr = NULL;
        wlist[i]->word[0] = 0;
    }

    /* load data from file */
    int c;
    char load[100];
    while (fgets(load, sizeof(load), fp)) {
        load[strcspn(load, "\n")] = 0;
        c = *load - 'a';
        if (c < 0 || c >= len) {
            continue;
        }
        add_and_sort(load, wlist + c);
    }

    /* recieve input and display data */
    int index = 0;
    char buf[100] = { 0 };
    HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);

    while (1) {
        // if backspace, delete character and traverse list
        if (GetAsyncKeyState(VK_BACK) == -32767) {
            if (index) {
                buf[--index] = '\0';
                ClearScreen(hStdout);
                printf("%s\n............\n", buf);
                if (index) {
                    traverse_list(buf, wlist[*buf - 'a']);
                }
            }
        }
        // if right-arrow key, discard input
        else if (GetAsyncKeyState(VK_RIGHT) == -32767) {
            index = 0;
            *buf = '\0';
            ClearScreen(hStdout);
            continue;
        }
        // if Enter, save to file
        else if (GetAsyncKeyState(VK_RETURN) == -32767) {
            if ((*buf - 'a') < 0 || (*buf - 'a') >= len) {
                continue;
            }
            add_and_sort(buf, &wlist[*buf - 'a']);
            fprintf(fp, "%s\n", buf);
            index = 0;
            *buf = '\0';
            ClearScreen(hStdout);
            continue;
        }
        // if escape, terminate the program
        else if (GetAsyncKeyState(VK_ESCAPE) == -32767) {
            break;
        }
        // accept alphabet-input and display matches if any
        for (short i = 'A'; i <= 'Z'; i++) {
            if (GetAsyncKeyState(i) == -32767) {
                buf[index++] = (char)(i + 32);
                buf[index] = '\0';
                ClearScreen(hStdout);
                printf("%s\n............\n", buf);
                traverse_list(buf, wlist[*buf - 'a']);
            }
        }
    }

    /* release memory */
    fclose(fp);
    for (size_t i = 0; i < len; i++) {
        free_list(wlist[i]);
    }
    free(wlist);
}

void add_and_sort(const char *str, G_list **head)
{
    /* create node */
    G_list *node = (G_list *)malloc(sizeof(G_list));

    /* initialize node members */
    strcpy(node->word, str);
    node->ptr = NULL;

    /* ... */
    if ((*head)->word[0] == '\0') {
        *head = node;
        return;
    }
    else {
        while (1) {
            if (strcmp(str, (*head)->word) < 0) {
                G_list *tmp = *head;
                *head = node;
                node->ptr = tmp;
                break;
            }
            else {
                head = &((*head)->ptr);
                if (!*head) {
                    *head = node;
                    (*head)->ptr = NULL;
                    break;
                }
            }
        }
    }
}

void free_list(G_list *head)
{
    G_list *tmp;
    while (head) {
        tmp = head;
        head = head->ptr;
        free(tmp);
    }
}

// compare at beginning of line
int cmp_at_begn(char *str,
    const char *substr)
{
    if (!*str || !*substr) {
        return (*str == *substr);
    }
    else {
        while (*str && *substr) {
            if (*str++ != *substr++) {
                return 0;
            }
        }
    }
    return !(*substr);
}

void ClearScreen(void *hConsole)
{
    COORD coordScreen = { 0, 0 };    // home for the cursor 
    DWORD cCharsWritten;
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    DWORD dwConSize;
    // Get the number of character cells in the current buffer. 
    if (!GetConsoleScreenBufferInfo(hConsole, &csbi))
    {
        return;
    }
    dwConSize = csbi.dwSize.X * csbi.dwSize.Y;
    // Fill the entire screen with blanks.
    if (!FillConsoleOutputCharacter(hConsole,        // Handle to console screen buffer 
        (TCHAR) ' ',     // Character to write to the buffer
        dwConSize,       // Number of cells to write 
        coordScreen,     // Coordinates of first cell 
        &cCharsWritten))// Receive number of characters written
    {
        return;
    }
    // Get the current text attribute.
    if (!GetConsoleScreenBufferInfo(hConsole, &csbi))
    {
        return;
    }
    // Set the buffer's attributes accordingly.
    if (!FillConsoleOutputAttribute(hConsole,         // Handle to console screen buffer 
        csbi.wAttributes, // Character attributes to use
        dwConSize,        // Number of cells to set attribute 
        coordScreen,      // Coordinates of first cell 
        &cCharsWritten)) // Receive number of characters written
    {
        return;
    }
    // Put the cursor at its home coordinates.
    SetConsoleCursorPosition(hConsole, coordScreen);
}

void traverse_list(char *str, G_list *head)
{
    int v = 0;
    while (head) {
        if (cmp_at_begn(head->word, str)) {
            puts(head->word);
            v = 1;
        }
        else {
            if (v) break;
        }
        head = head->ptr;
    }
}

Answer 1

Well, the most important part is that you currently use asynchronous input and polling, meaning your program does an expensive busy-wait. Maybe you can change to using the windows message-pump, allowing it to block when waiting for input?

Aside from that, using a linked list for your entries is extremely inefficient due to allocation-overhead (aggravated because every entry reserves 100 bytes for the payload), cache-misses (iterating involves following the pointers) and inefficient retrieval (linear search). Consider switching to a trie, or at least a sorted array and binary search.

Now about your implementations:

1. Good names are important. cmp_at_begn() is awkward. is_prefix() reads much better.

2. Const-correctness helps avoid errors. Mark things const where you may to get the compiler to help you.

3. Anyway, rewriting that function to avoid special cases yields good results:

   int is_prefix(const char* s, const char* prefix) {
       while(*prefix && *prefix == *s)
           ++prefix, ++s;
       return !*prefix;
   }
   

4. Restrict variables to the smallest possible scope, thus making things easier to comprehend.

5. traverse_list() is another badly named function. Yes, the function traverses a list, but in order to output entries beginning with a certain prefix, not for the fun of it. So, consider naming it print_with_prefix().

6. Consider whether you couldn't statically link most of your functions. That would make inlining more likely.

7. Don't cast the result of malloc, and avoid sizeof(TYPE). Read "Do I cast the result of malloc?".

Answer 2

Your main while(1) loop where you read keys doesn't have any sleep() call in it.

I didn't check your code for other problems, but currently it's baking the cpu to check for keypresses every couple of nanoseconds.

~100 msec resolution is more like what you would want.

Answer 3

Every time you add a new element to the list you sort the whole list ?!?

Add all items and then do a single sorting.