7
\$\begingroup\$

i'm self learning programming and following CS50 course on Youtube. Below is my attempt to solve the PSET 3 Tideman. The program "seems" to work, as it doesn't produce any errors or warnings, and it seems to produce the result correctly for a few test cases(3 to 5 candidates with 8 or more voters).

What I would like to learn more about are as follows:

  1. whether or not my code contains any obvious logical errors that won't work for cases where there is a lot of tied pairs between candidates, or if there are multiple candidates who have not lost in any preference pairs, i.e., multiple candidates have not been on the losing side. How would I need to change my program to determine the result then?

  2. Since I'm new to programming, I'm using a lot of loops and nested loops, I'm not sure if this(using a whole bunch of loops in a program) is a common/good/normal practice or if there are any more "elegant" way of doing things in programming in the professional coding world?

  3. Any other critiques in any areas are greatly appraciated!

thank you!

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

/*max number of candidates*/
#define MAX 9

/*preferences[i][j] is the number of voters who prefer i over j, i and j being candidate index*/
int preferences[MAX][MAX];

/*bool type 2-d array, if true, locked[i][j] means i is locked in over j*/
bool locked[MAX][MAX];

/*each pair has a winner and a loser index, win_margin is the number of votes won*/
struct pair
{
    int winner;
    int loser;
    int win_margin;
};

/*used for merge-sorting the pairs, based on win_margin*/
struct left
{
    int winner;
    int loser;
    int win_margin;
};

struct right
{
    int winner;
    int loser;
    int win_margin;
};

char* candidate[MAX];
struct pair pairs[MAX * (MAX - 1) / 2];
int pair_count;
int candidate_count;

/*prototype functions*/
bool vote(int rank, char name[], int ranks[]);
void record_preferrences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void merge_sort(struct pair* pairs, int beg_index, int end_index);
void merge(struct pair* pairs, int beg_index, int end_index, int mid);
void lock_pairs(void);
void print_winner(void);

int main(int argc, char* argv[])
{
    char buffer[100];
    int voter_count;
    pair_count = 0;


    /*check the commanline input validty*/
    if (argc < 2 || argc > MAX)
        printf("Need to put in candidates' names, and max number of candidates is 9.\n");

    /*populate the candidate array from command line arguments*/
    candidate_count = argc - 1;

    /*memory allocation*/   
    for (int i = 0; i < MAX; i++)
    {
        if ((candidate[i] = malloc(50)) == NULL)
            printf("Error. memory allocation unseccessful.\n");
    }

    /*populate the candidate array with candidates' names*/
    for (int j = 0; j < candidate_count; j++)
    {
        strcpy(candidate[j], argv[j + 1]);
        printf("Candidate %d is: %s\n", j + 1, candidate[j]);
    }

    /*clear out the graph of locked in pairs*/
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    /*get number of voters*/
    do
    {
        int flag = 0;
        printf("Number of voters: ");
        fgets(buffer, sizeof(buffer), stdin);
        sscanf(buffer, "%d", &voter_count);
        if (voter_count < 2)
        {
            printf("Enter a number that's larger than 2.\n");
            continue;
        }
        
        for (int i = 0; i < strlen(buffer) - 1; i++)
        {
            if (isdigit(buffer[i]) == 0)    /*found non-numeric character with in user input*/      
            {
                if (buffer[i] == '-' || buffer[i] == '+')
                    continue;
                else
                {
                    printf("Enter only whole numbers that's larger than 2.\n");
                    flag = 1;
                    break;
                }
            }
        }

        if (flag == 1)
            continue;
        else
            break;
    } while (true);

    /*gather rank info for each vote; check each vote's validty; record preferences*/
    for (int i = 0; i < voter_count; i++)
    {
        /*ranks[i] represent voter's i th preference*/
        int* ranks;
        if((ranks = malloc(sizeof(int) * candidate_count) == NULL)
            printf("memory allocation for voter[%d]'s ranks failed.\n", i + 1);
        char name[50];
        
        for (int j = 0; j < candidate_count; j++)
        {
            do
            {
                int flag = 0;
                printf("Ballot %d, rank %d: ", i + 1, j + 1);
                fgets(name, sizeof(name), stdin);
                name[strlen(name) - 1] = '\0';
                if (!vote(j, name, ranks))
                {
                    printf("Invalid name entered. Please Re-enter.\n");
                    continue;
                }
                if (j >= 1)
                {
                    for (int k = 0; k < j; k++)
                    {
                        if (strcmp(candidate[ranks[k]], candidate[ranks[j]]) == 0)
                        {
                            flag = 1;
                            printf("Duplicate name entered. Please Reenter.\n");
                            break;
                        }
                    }
                    
                    if (flag == 1)
                        continue;
                    else
                        break;
                }
                else
                    break;
            } while (true);
            free(ranks);
        }
        
        /*after each vote info has been collected, record perferences in preferences[i][j]*/
        record_preferrences(ranks);
        printf("\n");   
    }

    /*for each pair of candidates, record winner and loser.*/
    add_pairs();

    /*sort the pairs, by the winning margin of each pair*/
    sort_pairs();

    /*lock pairs with the largest win margin first, keep locking down the list until a cycle is created*/
    lock_pairs();

    print_winner();
}

/*check each vote's validty; update the ranks[], ranks[0] is the first rank of a vote*/
bool vote(int rank, char name[], int ranks[])
{
    int flag = 0;
    for (int k = 0; k < candidate_count; k++)
    {
        if (strcmp(name, candidate[k]) == 0)
        {
            flag = 1;
            ranks[rank] = k;
            break;
        }   
    }
    if (flag == 0)
        return false;
    else
        return true;
}

/*record preferences*/
void record_preferrences(int ranks[])
{
    /*loop through each rank in ranks[], */
    for (int i = 0; i < candidate_count; i++)
    {
        /*rank[0] is preferred over all other ranks; rank[1] preferred over all ranks after it */
        int winner = ranks[i];
        for (int j = i + 1; j < candidate_count; j++)
        {
            int loser = ranks[j];
            preferences[winner][loser] += 1;
        }
    }
}

/*record the preferences in struct pair pairs*/
void add_pairs(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pairs[pair_count].win_margin = preferences[i][j];
                printf("pair[%d], in pair[%d][%d] winner is: %s; loser is : %s, by %d votes.\n", pair_count, i + 1, j + 1, candidate[i], candidate[j], preferences[i][j]);
            }
            if (preferences[j][i] > preferences[i][j])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pairs[pair_count].win_margin = preferences[j][i];
                printf("pair[%d], in pair[%d][%d] winner is: %s; loser is : %s, by %d votes.\n", pair_count, i + 1, j + 1, candidate[j], candidate[i], preferences[j][i]);
            }
            if(preferences[i][j] == preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pairs[pair_count].win_margin = 0;
                printf("pair[%d], in pair[%d][%d], there is a tie between %s and %s.\n", pair_count, i + 1, j + 1, candidate[i], candidate[j]);
            }
            pair_count++;
        }
    }
    printf("There are %d pairs.", pair_count);
    printf("\n");
}

/*sort pairs based on the amount of winning margin in each pair*/
void sort_pairs(void)
{
    printf("unsorted array is:");
    for (int i = 0; i < pair_count; i++)
    {
        printf("%d ", pairs[i].win_margin);
    }

    /*use merge sort to sort the array*/
    int beg_index = 0;
    int end_index = pair_count - 1;
    merge_sort(pairs, beg_index, pair_count - 1);
    printf("\n");
    
    printf("sorted array is:");
    for (int i = 0; i < pair_count; i++)
    {
        printf("%d ", pairs[i].win_margin);
    }
    printf("\n");
}

/*produce the sorted array*/
void merge_sort(struct pair *pairs, int beg_index, int end_index)
{   
    if (beg_index < end_index)
    {
        int mid = (beg_index + end_index) / 2;
        merge_sort(pairs, beg_index, mid);
        merge_sort(pairs, mid + 1, end_index);
        merge(pairs, beg_index, end_index, mid);
    }   
}

/*merge the sorted 2 half arrays*/
void merge(struct pair* pairs, int beg_index, int end_index, int mid)
{
    int n1 = mid - beg_index + 1;
    int n2 = end_index - (mid + 1) + 1;
    
    struct left* left;
    if((left = malloc(sizeof(struct left) * (n1 + 1))) == NULL)
        printf("memory allocation failed for struct left array.\n");    
    struct right *right;
    if((right = malloc(sizeof(struct right) * (n2 + 1))) == NULL)
        printf("memory allocation failed for struct right array.\n");

    for (int i = 0; i < n1; i++)
    {
        left[i].win_margin = pairs[beg_index + i].win_margin;
        left[i].winner = pairs[beg_index + i].winner;
        left[i].loser = pairs[beg_index + i].loser;
    }
    for (int j = 0; j < n2; j++)
    {
        right[j].win_margin = pairs[mid + 1 + j].win_margin;
        right[j].winner = pairs[mid + 1 + j].winner;
        right[j].loser = pairs[mid + 1 + j].loser;
    }
        

    int i = 0;
    int j = 0;
    int k = beg_index;

    while (i < n1 && j < n2)
    {
        if (left[i].win_margin <= right[j].win_margin)
        {
            pairs[k].win_margin = left[i].win_margin;
            pairs[k].winner = left[i].winner;
            pairs[k].loser = left[i].loser;
            i++;
        }
        else
        {
            pairs[k].win_margin = right[j].win_margin;
            pairs[k].winner = right[j].winner;
            pairs[k].loser = right[j].loser;
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        pairs[k].win_margin = left[i].win_margin;
        pairs[k].winner = left[i].winner;
        pairs[k].loser = left[i].loser;
        i++;
        k++;
    }

    while (j < n2)
    {
        pairs[k].win_margin = right[j].win_margin;
        pairs[k].winner = right[j].winner;
        pairs[k].loser = right[j].loser;
        j++;
        k++;
    }
    free(left);
    free(right);
}

void lock_pairs(void)
{
    /*the pair with the largest win_margin always got locked first*/
    locked[pairs[pair_count - 1].winner][pairs[pair_count - 1].loser] = true;

    /*unique_ounter counts the number of unique candidate index on the loser side; if less than
candidate_count, keep locking since locking won't create a cycle*/
    int unique_counter = 1;
    int flag;

    for (int i = pair_count - 2; i >= 0; i--)
    {   
        for (int j = pair_count - 1; j >= i; j--)
        {
            flag = 0;
            /*check duplicate loser index for locked pairs so far*/
            if (pairs[i].loser == pairs[j].loser)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
            unique_counter += 1;
        if (unique_counter < candidate_count && pairs[i].win_margin != 0)
            locked[pairs[i].winner][pairs[i].loser] = true;
        if(unique_counter == candidate_count)
            break;
    }

    for (int i = pair_count - 1; i >= 0; i--)
    {
        if (locked[pairs[i].winner][pairs[i].loser])
        {
            printf("pair[%d] locked.\n", i);
        }
        else
        {
            printf("pair[%d] remains unlocked.\n", i);
        }
    }
}

void print_winner(void)
{
    int* lost_pool;
    if((lost_pool = malloc(sizeof(int) * candidate_count)) == NULL)
        printf("memory allocation failed for lost_pool array.\n");
    int* win_pool;
    if((win_pool = malloc(sizeof(int) * candidate_count)) == NULL)
        printf("memory allocation failed for win_pool array.\n");
    int flag;
    lost_pool[0] = pairs[pair_count - 1].loser;
    int k = 1;
    int l = 0;

    /*for all the locked pairs, find the candidates on the losing side and add to lost_pool array; 
for duplicates, only add once.*/
    for (int i = pair_count - 2; i >= 0; i--)
    {
        flag = 0;
        for (int j = pair_count - 1; j > i; j--)
        {
            if (pairs[i].loser == pairs[j].loser)
            {
                flag = 1;
                break;
            }
        }

        if (locked[pairs[i].winner][pairs[i].loser] && flag == 0)
        {
            lost_pool[k] = pairs[i].loser;
            k++;
        }
    }

    printf("Candidats who lost in locked pairs: ");
    for (int i = 0; i < k; i++)
    {
        printf("%s ", candidate[lost_pool[i]]);
    }
    printf("\n");
    
    /*the candidate(s) that is not in the lost_pool within the locked pairs, will be the winner*/
    
    for (int i = 0; i < candidate_count; i++)
    {
        int flag = 0;
        for (int j = 0; j < k; j++)
        {
            if (i == lost_pool[j])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            win_pool[l] = i;
            l++;
        }
    }

    if (l == 1)
        printf("The Winner is: %s!\n", candidate[win_pool[0]]);
    if (l > 1)
    {
        printf("The following are in the win_pool: ");
        for (int i = 0; i < l; i++)
            printf("%s ", candidate[win_pool[i]]);
    }
    free(lost_pool);
    free(win_pool);
}

New contributor
Jack Zha is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! You probably want to edit some links to external results for those who aren't familiar with CS50 or Tideman. That way reviewers know what you implement and your background a little bit better and thus can focus on the code. Also, if you're a beginner, consider adding the beginner tag, as reviewers try to create more beginner friendly reviews that way. I hope you get some nice reviews :). \$\endgroup\$ – Zeta Oct 17 at 9:01
  • 1
    \$\begingroup\$ Thanks for the tip! I will edit my post accordingly. \$\endgroup\$ – Jack Zha Oct 17 at 10:09
9
\$\begingroup\$

Avoid global variables

The larger the project, the higher the chance that if you use global variables, that you have conflicting global variable names. Try to avoid them when possible. Here are some generic rules you can follow:

  • Declare variables in the function that first uses them.
  • Pass variables as arguments to other functions that need to access them. This can be either by pointer or by value; if the variables are large structs or if they need to be written to, pass them by pointer, otherwise by value.
  • If you need to pass more than few variables, consider grouping them in a struct instead.

Avoid forward declarations

You had to add some forward declarations above main(). You can avoid this by reversing the order in which the functions appear in the source file. Doing so avoids you having to repeat yourself, and there is less chance of mistakes. Only if there are cyclic dependencies between functions should you need forward declarations.

Print errors to stderr, and handle them in some way

First, always print errors to stderr. This is especially useful if you are redirecting the output of your program to a file for example; this way the errors don't get lost, and the output doesn't contain unexpected data.

However I also see that while you check for invalid conditions and print an error message, you don't do anything about it, and just let the program continue running. In the best scenario, this leads to a crash, but in the worst scenario it looks like it is running fine but the final output will be incorrect. Whenever you have an error condition, do something about it. If you don't know how to recover from the error, the immediately exit from the program in some way, for example by calling exit(1) or abort().

Avoid assignments in if-statements

Prefer to do the assignment before the if-statement. The reason is that it is quite easy to make mistakes when combining the assignment with the condition being tested (for example, writing = instead of == or the other way around). So for example, prefer to write:

for (int i = 0; i < MAX; i++)
{
    candidate[i] = malloc(50);

    if (!candidate[i]) {
        fprintf(stderr, "Error. Memory allocation unsuccessful.\n");
        abort();
    }
}

You often do this for memory allocations. I would just write a wrapper function that does the error handling, like so:

void *checked_malloc(size_t size) {
    void *ptr = malloc(size);

    if (!ptr) {
        fprintf(stderr, "Error. Memory allocation unsuccessful.\n");
        exit(1);
    }

    return ptr;
}

And then use it like so:

for (int i = 0; i < MAX; i++)
{
    candidate[i] = checked_malloc(50);
}

Avoid magic numbers

Avoid writing magic numbers in your code, and instead declare them as a constant variable or a macro. For example:

#define MAX_NAME_LENGTH 50
...
candidate[i] = checked_malloc(MAX_NAME_LENGTH);

Guard against buffer overflows

There are a few cases where you still allow buffer overflows. For example, when reading the candidate names from the command line, you use a bare strcpy() which doesn't check if the candidate's name fits in the allocated buffer. So for example, write:

strncpy(candidate[j], argv[j + 1], MAX_NAME_LENGTH);
candidate[j][MAX_NAME_LENGTH - 1] = 0; // Necessary!

But you could have avoided this by allocating buffers of the right size. You can do this by doing a strlen() before allocating candidate[j], but if possible use the function strdup():

candidate[j] = strdup(argv[j + 1]);

But why do you need to make a copy of the name anyway? You can just have candidate[j] point directly to the right command line argument:

candidate[j] = argv[j + 1];

Nested loops

Nesting loops and/or conditional statements is perfectly normal, and often it's just the natural way to write things. However, if you nest too much the code might "fall off" the right hand of the screen and become unreadable. Sometimes it makes sense to wrap an inner loop into a function; this way you reduce the apparent nesting of loops, and make the code simpler to reason about.

Proper input validation

Your check for a valid number of voters is both quite complex and still wrong. For example, I can give the input 2-3+4, and this will be accepted. There will also be a potential crash if the input reaches EOF before any character (not even a newline) is read, because then strlen(buffer) will be zero.

There are multiple ways to solve this. To keep the code short, I would do the following:

while (true)
{
    char dummy;

    printf("Number of voters: ");
    fgets(buffer, sizeof buffer, stdin);

    if (sscanf(buffer, "%d %c", &voter_count, &dummy) == 1 && voter_count > 2) {
        break;
    }

    fprintf(stderr, "Enter a single number larger than 2!\n");
}

I used the fact that sscanf() returns the number of successful conversions, that a space in the format string matches any amount of consecutive whitespace (including the newline), and that after the newline there should not be any other character in the buffer. Thus, if it succesfully read the number and there was nothing after it except for whitespace, the return value will be 1, otherwise it will be 0 or 2.

I also noted that your error message says the number should be larger than two, but you actually check whether the number is not smaller than two, which means it passes it if it is equal to or larger than two.

Make flags bool, give them a proper name

If you want to store a true/false value in a variable, make it a bool. You already do that in some places, but for some reason you use int for flag.

Also, flag tells me what kind of variable it is, but not what is used for. Try to give a more descriptive name. For example, when checking for duplicates, name it duplicate_found. This way, you can write:

if (pairs[i].loser == pairs[j].loser)
{
    duplicate_found = true;
    break;
}

...

if (!duplicate_found)
    unique_counter++;
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi G. Sliepen, I cannot thank you enough for the time and efforts you put into this response. You have no idea how much that meant to a self-learner like myself. Thank you again!! \$\endgroup\$ – Jack Zha 2 days ago
  • \$\begingroup\$ No problem, I'm glad you find the answer useful. By the way, consider marking the answer that was most useful to you as the accepted answer. \$\endgroup\$ – G. Sliepen 2 days ago
6
\$\begingroup\$

Congrats on starting to program in C. I started on my own as well, so I know how overwhelming it can be at first. I'm going to be hitting you with a lot in a couple of seconds, so I want you to know that it's not possible to internalize all of this information in one day, and this is an awesome start.

I agree with both of the previous answers, so I'm not going to be referencing the same points, but please do take their advice.

To start with, I recommend not writing programs in the "Enter number of voters" style. Console applications are usually run like old-school batch processes, where the program arguments are passed in with the initial invocation. If your program requires a number of voters as an argument, check argv for it. When programs need a ton of input, such as might not be feasible to pass in via the command-line, a filename argument is usually the way to go.

Formatting

Make sure to leave whitespace between tokens. The following code is syntactically correct, but makes reading unnecessarily more tedious.

if(ranks = malloc...)
    printf("memory allocation...");
char name[50];

I also can't stress enough how much I recommend never leaving out braces after an if block. I'm not particularly dogmatic about code style usually, but Apple's goto fail is only one example of how this can come back to bite you.

Compiler Errors

There is an error on line 131. You forgot to remove the extra open parenthesis at the beginning of the expression.

src/main.c:131:67: error: expected ‘)’ before ‘printf’
  131 |         if((ranks = malloc(sizeof(int) * candidate_count) == NULL)
      |           ~                                                       ^
      |                                                                   )
  132 |             printf("memory allocation for voter[%d]'s ranks failed.\n", i + 1);

Semantic Errors

On line 131, you meant to check whether the result from the call to malloc(3) was valid, but the precedence of the = vs == operators means you're doing something completely different.

if(ranks = malloc(sizeof(int) * candidate_count) == NULL)

What you are saying here is the following:

  1. Heap-allocate sizeof(int) * candidate bytes of memory.
  2. Check whether the result is equal to NULL.
  3. Assign the result of the previous check to ranks.

Your ranks variable will therefore be equal to either 0 or 1, but it will not be a pointer to heap-allocated memory. Not only are you leaking a ton of memory, your program is also not going to work as intended.

The correct assign-and-check syntax uses parentheses to circumvent the lower precedence of the assignment operator, like this.

if ((ranks = malloc(sizeof (int) * candidate_count)) == NULL) {

On line 105, you are using a loop counter of type int and comparing it against the length of the buffer width. Signed vs. unsigned comparisons like this can create really hard to track bugs. You can circumvent this problem by simply declaring your loop counter as the same type as that returned by strlen(3).

for (size_t i = 0; i < strlen(buffer); ++i) {
    ...
}

You also aren't using the end_index variable you declared on line 269, in the sort_pairs function.

/*sort pairs based on the amount of winning margin in each pair*/
void sort_pairs(void)
{
    printf("unsorted array is:");
    for (int i = 0; i < pair_count; i++)
    {
        printf("%d ", pairs[i].win_margin);
    }

    /*use merge sort to sort the array*/
    int beg_index = 0;
    int end_index = pair_count - 1;
    merge_sort(pairs, beg_index, pair_count - 1);
    printf("\n");
    
    printf("sorted array is:");
    for (int i = 0; i < pair_count; i++)
    {
        printf("%d ", pairs[i].win_margin);
    }
    printf("\n");
}

It looks like you were going to use the beg_index and end_index variables as the start and stop configuration for the for loop, but you eventually went in another direction, using the pair_count variable.

This is fine (although I don't necessarily agree with the specific method of relying on the global pair_count variable), but when you do that, just take out the unnecessary variables. Keeping them in makes the system harder to understand, due to the added noise from useless variables.

The following patch contains the necessary modifications to make your code compile cleanly.

--- src/main.c.original 2020-10-17 13:31:23.904117706 -0400
+++ src/main.c  2020-10-17 14:07:09.290771020 -0400
@@ -102,7 +102,7 @@
             continue;
         }
         
-        for (int i = 0; i < strlen(buffer) - 1; i++)
+        for (size_t i = 0; i < strlen(buffer) - 1; i++)
         {
             if (isdigit(buffer[i]) == 0)    /*found non-numeric character with in user input*/      
             {
@@ -128,7 +128,7 @@
     {
         /*ranks[i] represent voter's i th preference*/
         int* ranks;
-        if((ranks = malloc(sizeof(int) * candidate_count) == NULL)
+        if((ranks = malloc(sizeof(int) * candidate_count)) == NULL)
             printf("memory allocation for voter[%d]'s ranks failed.\n", i + 1);
         char name[50];
         
@@ -266,7 +266,6 @@
 
     /*use merge sort to sort the array*/
     int beg_index = 0;
-    int end_index = pair_count - 1;
     merge_sort(pairs, beg_index, pair_count - 1);
     printf("\n");

I recommend you use stricter compilation settings for your programs. Here is what I used to compile your program, yielding the recommendations I've covered.

gcc -std=c17 -Wall -Wextra -Wpedantic -O0 -ggdb3 -fanalyzer -fsanitize=address,leak,undefined -D_GNU_SOURCE -o review main.c

This disables all optimizations to prevent variables being optimized away when you're debugging, although I've heard that using the -Og can lead to a better debugging experience. I have not gotten around to checking this for myself, but it's something you might explore.

The address sanitizer library checks I've included are important, because even though your program is now compiling with no warnings or errors on my machine, this is the output I get when I run it.

Need to put in candidates' names, and max number of candidates is 9.
Number of voters: 3



There are 0 pairs.
unsorted array is:
sorted array is:
src/main.c:366:17: runtime error: index -1 out of bounds for type 'pair [36]'
=================================================================
==3448==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5631c33a00d4 at pc 0x5631c3389d47 bp 0x7ffce7e9c040 sp 0x7ffce7e9c030
READ of size 4 at 0x5631c33a00d4 thread T0
    #0 0x5631c3389d46 in lock_pairs src/main.c:366
    #1 0x5631c338488b in main src/main.c:183
    #2 0x7f1392783151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
    #3 0x5631c338324d in _start (/home/jflopezfernandez/projects/code-reviews/c/250779-c-implementation-of-tideman-algorithm/review+0xf24d)

0x5631c33a00d4 is located 44 bytes to the right of global variable 'candidate' defined in 'src/main.c:40:7' (0x5631c33a0060) of size 72
0x5631c33a00d4 is located 12 bytes to the left of global variable 'pairs' defined in 'src/main.c:41:13' (0x5631c33a00e0) of size 432
SUMMARY: AddressSanitizer: global-buffer-overflow src/main.c:366 in lock_pairs
Shadow bytes around the buggy address:
  0x0ac6b866bfc0: f9 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ac6b866bfd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac6b866bfe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac6b866bff0: 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0ac6b866c000: 00 00 00 00 00 00 01 f9 f9 f9 f9 f9 00 00 00 00
=>0x0ac6b866c010: 00 00 00 00 00 f9 f9 f9 f9 f9[f9]f9 00 00 00 00
  0x0ac6b866c020: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac6b866c030: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac6b866c040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac6b866c050: 00 00 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0ac6b866c060: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==3448==ABORTING

Disabling the sanitizer library so I could run valgrind, I got this output from the GCC static analyzer.

src/main.c: In function ‘print_winner’:
src/main.c:415:18: warning: dereference of NULL ‘lost_pool’ [CWE-690] [-Wanalyzer-null-dereference]
  415 |     lost_pool[0] = pairs[pair_count - 1].loser;
      |     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  ‘print_winner’: events 1-7
    |
    |  409 |     if((lost_pool = malloc(sizeof(int) * candidate_count)) == NULL)
    |      |       ~             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |       |             |
    |      |       |             (1) allocated here
    |      |       (2) assuming ‘lost_pool’ is NULL
    |      |       (3) following ‘true’ branch (when ‘lost_pool’ is NULL)...
    |  410 |         printf("memory allocation failed for lost_pool array.\n");
    |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |         |
    |      |         (4) ...to here
    |  411 |     int* win_pool;
    |  412 |     if((win_pool = malloc(sizeof(int) * candidate_count)) == NULL)
    |      |       ~              
    |      |       |
    |      |       (5) following ‘false’ branch (when ‘win_pool’ is non-NULL)...
    |......
    |  415 |     lost_pool[0] = pairs[pair_count - 1].loser;
    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |                  |                  |
    |      |                  |                  (6) ...to here
    |      |                  (7) dereference of NULL ‘lost_pool’
    |
src/main.c:468:58: warning: dereference of NULL ‘win_pool’ [CWE-690] [-Wanalyzer-null-dereference]
  468 |         printf("The Winner is: %s!\n", candidate[win_pool[0]]);
      |                                                  ~~~~~~~~^~~
  ‘print_winner’: events 1-25
    |
    |  409 |     if((lost_pool = malloc(sizeof(int) * candidate_count)) == NULL)
    |      |       ^
    |      |       |
    |      |       (1) following ‘false’ branch (when ‘lost_pool’ is non-NULL)...
    |......
    |  412 |     if((win_pool = malloc(sizeof(int) * candidate_count)) == NULL)
    |      |       ~            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |       |            |
    |      |       |            (2) ...to here
    |      |       |            (3) allocated here
    |      |       (4) assuming ‘win_pool’ is NULL
    |      |       (5) following ‘true’ branch (when ‘win_pool’ is NULL)...
    |  413 |         printf("memory allocation failed for win_pool array.\n");
    |      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |         |
    |      |         (6) ...to here
    |......
    |  421 |     for (int i = pair_count - 2; i >= 0; i--)
    |      |     ~~~
    |      |     |
    |      |     (7) following ‘false’ branch (when ‘i < 0’)...
    |......
    |  440 |     printf("Candidats who lost in locked pairs: ");
    |      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    |      |     |
    |      |     (8) ...to here
    |  441 |     for (int i = 0; i < k; i++)
    |      |     ~~~
    |      |     |
    |      |     (9) following ‘true’ branch (when ‘i < k’)...
    |      |     (11) following ‘false’ branch (when ‘i >= k’)...
    |  442 |     {
    |  443 |         printf("%s ", candidate[lost_pool[i]]);
    |      |                                          ~
    |      |                                          |
    |      |                                          (10) ...to here
    |  444 |     }
    |  445 |     printf("\n");
    |      |     ~~~~~~~~~~~~
    |      |     |
    |      |     (12) ...to here
    |......
    |  449 |     for (int i = 0; i < candidate_count; i++)
    |      |     ~~~                                  ~~~
    |      |     |                                     |
    |      |     |                                     (20) ...to here
    |      |     (13) following ‘true’ branch...
    |      |     (21) following ‘false’ branch...
    |  450 |     {
    |  451 |         int flag = 0;
    |      |             ~~~~
    |      |             |
    |      |             (14) ...to here
    |  452 |         for (int j = 0; j < k; j++)
    |      |         ~~~
    |      |         |
    |      |         (15) following ‘true’ branch (when ‘j < k’)...
    |  453 |         {
    |  454 |             if (i == lost_pool[j])
    |      |                ~              ~
    |      |                |              |
    |      |                |              (16) ...to here
    |      |                (17) following ‘true’ branch...
    |  455 |             {
    |  456 |                 flag = 1;
    |      |                 ~~~~~~~~
    |      |                      |
    |      |                      (18) ...to here
    |......
    |  460 |         if (flag == 0)
    |      |            ~
    |      |            |
    |      |            (19) following ‘false’ branch (when ‘flag != 0’)...
    |......
    |  467 |     if (l == 1)
    |      |        ~
    |      |        |
    |      |        (22) ...to here
    |      |        (23) following ‘true’ branch (when ‘l == 1’)...
    |  468 |         printf("The Winner is: %s!\n", candidate[win_pool[0]]);
    |      |                                                  ~~~~~~~~~~~
    |      |                                                          |
    |      |                                                          (24) ...to here
    |      |                                                          (25) dereference of NULL ‘win_pool’
    |

And here is the valgrind output from running your program after rebuilding without the -fsanitize=address,leak,undefined option.

[jflopezfernandez@www 250779-c-implementation-of-tideman-algorithm]$ valgrind --leak-check=full --show-leak-kinds=all ./review
==3688== Memcheck, a memory error detector
==3688== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3688== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==3688== Command: ./review
==3688== 
Need to put in candidates' names, and max number of candidates is 9.
Number of voters: 3



There are 0 pairs.
unsorted array is:
sorted array is:
==3688== Invalid write of size 4
==3688==    at 0x10A81A: print_winner (main.c:415)
==3688==    by 0x10972C: main (main.c:185)
==3688==  Address 0x4a3ce00 is 0 bytes after a block of size 0 alloc'd
==3688==    at 0x483A77F: malloc (vg_replace_malloc.c:307)
==3688==    by 0x10A7AD: print_winner (main.c:409)
==3688==    by 0x10972C: main (main.c:185)
==3688== 
==3688== Invalid read of size 4
==3688==    at 0x10A98B: print_winner (main.c:443)
==3688==    by 0x10972C: main (main.c:185)
==3688==  Address 0x4a3ce00 is 0 bytes after a block of size 0 alloc'd
==3688==    at 0x483A77F: malloc (vg_replace_malloc.c:307)
==3688==    by 0x10A7AD: print_winner (main.c:409)
==3688==    by 0x10972C: main (main.c:185)
==3688== 
==3688== Conditional jump or move depends on uninitialised value(s)
==3688==    at 0x483DC75: strlen (vg_replace_strmem.c:459)
==3688==    by 0x48DDAB7: __vfprintf_internal (in /usr/lib/libc-2.32.so)
==3688==    by 0x48C8BBE: printf (in /usr/lib/libc-2.32.so)
==3688==    by 0x10A9B5: print_winner (main.c:443)
==3688==    by 0x10972C: main (main.c:185)
==3688== 
Candidats who lost in locked pairs:  
==3688== 
==3688== HEAP SUMMARY:
==3688==     in use at exit: 450 bytes in 12 blocks
==3688==   total heap usage: 16 allocs, 4 frees, 2,498 bytes allocated
==3688== 
==3688== 0 bytes in 3 blocks are definitely lost in loss record 1 of 2
==3688==    at 0x483A77F: malloc (vg_replace_malloc.c:307)
==3688==    by 0x109516: main (main.c:131)
==3688== 
==3688== 450 bytes in 9 blocks are still reachable in loss record 2 of 2
==3688==    at 0x483A77F: malloc (vg_replace_malloc.c:307)
==3688==    by 0x10925C: main (main.c:72)
==3688== 
==3688== LEAK SUMMARY:
==3688==    definitely lost: 0 bytes in 3 blocks
==3688==    indirectly lost: 0 bytes in 0 blocks
==3688==      possibly lost: 0 bytes in 0 blocks
==3688==    still reachable: 450 bytes in 9 blocks
==3688==         suppressed: 0 bytes in 0 blocks
==3688== 
==3688== Use --track-origins=yes to see where uninitialised values come from
==3688== For lists of detected and suppressed errors, rerun with: -s
==3688== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)

As the static analyzer and valgrind both show, there are errors in the code.

I ran the program by itself to see what would happen, and this was the output.

Need to put in candidates' names, and max number of candidates is 9.
Number of voters: 3



There are 0 pairs.
unsorted array is:
sorted array is:
Candidats who lost in locked pairs: 

Whatever the error is (I honestly skimmed the output, it's almost time for dinner c:), it's not causing the program to crash. This is bad, because you always want to fail as early as possible, allowing you to detect errors as early in the development process as you can. It's always easier to fix errors sooner rather than later.

All in all, this is a solid start, and I commend you for taking the first step. If I can make a suggestion, your next steps should be the following:

  1. Learn how to use a debugger, whether it's GDB or LLDB (or whatever)
  2. Read the GCC, Clang, or whatever compiler you use's manual to figure out how to best configure your program for compilation for diagnostics, debuggin, profiling, static analysis, etc.
  3. Learn how to use valgrind

Programming in C is awesome, and I love it, but I wasted hours of my life using printf statements to debug programs when following the advice to learn how to actually debug would have saved me hours of frustration. And remember, you can't printf if your program doesn't have an open file descriptor to write to, so if you write a daemon or a shared library, the printf method gets even harder to hack (i.e., you could use syslog for a daemon, etc.).

By the way, if you don't have a copy or just haven't read "The C Programming Language" by Brian Kernighan and Dennis Ritchie, don't wait. I didn't buy the book for years because I was outraged that a 200-something page book was so expensive (especially when I already had "The C++ Programming Language" by Bjarne Stroustroup, which I bought for nearly the same price). Trust me, the book is worth every penny. If you can swing it, "The Unix Programming Environment" (also by Brian Kernighan, this time with Rob Pike) is also an awesome read. It will contextualize all of the perceived idiosyncracies of programming in C.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you and i will definitely try out the debugger! I have been trying to use debug tool in Visual Studio 2019, but it just refused to work...and the resulting mountain of printf() statments, lol. And yes, i think some point down the road, i will definitely grab that book! It has come up on my searches multiple times now... \$\endgroup\$ – Jack Zha 2 days ago
5
\$\begingroup\$

@G.Sliepen covered most of what I would have. A few spare things:

  • Particularly since this is a one-translation-unit (one-file) program, mark every function except main to be static.
  • Consider not declaring left and right structures at all, reusing pair; or at least typedef aliases to pair rather than re-declaring all of the members
  • Use a separate structure tag and typedef name so that you don't have to precede all of your variables with struct
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If no self-referential pointers are needed then struct tags are a waste: struct { ... } typedef Foo is all that's needed, right? \$\endgroup\$ – Unslander Monica Oct 18 at 5:48
  • \$\begingroup\$ Yep 😊 I'm in the habit of making a tag to be able to predeclare structures in header files, but here that isn't needed. \$\endgroup\$ – Reinderien Oct 18 at 13:26
  • \$\begingroup\$ Thank you sir for the clarification! \$\endgroup\$ – Jack Zha 2 days ago

Your Answer

Jack Zha is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.