sorting input in lexicographical order with dynamic array

Question

I try to write a program which reads in single signs from a keyboard. If they are not already present they should be stored in a array.

After that, all signs get sorted and all already occurring signs are printed.

edit: if the entered sign already exists it is not added. The array should only contain unique elements.

The array starts with a size of 0 and should double its capacity every time it is full when a new character arrives.

Unfortunately it doesn't seem to work correctly. If I look via the debugger it looks like the values get stored one after another, but as soon as the second sign arrives the program crashes in print / qsort.

Am I doing something wrong in the allocation?

Also if you have other recommendations for improve this code please let me know.

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

void reserve_space(char **c, int *capacity);
void print_signs(char **signs, const int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    char *new_c;

    if (*capacity == 0) {       // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        new_c = realloc(*c, sizeof(char) * (*capacity));
        *c = new_c;
    }
    return;
}

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", *signs[i], *signs[i]);            // crash in read after array has 2 signs???
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    char left = *((char *)lhs);
    char right = *((char *)rhs);

    if (left < right) return -1;
    if (left > right) return  1;

    return 0;  /* left == right */
}

int main() {
    int capacity = 0;       // allocated space 
    int sz = 0;             // space currently "filled" with signs
    char *signs = 0;

    char ch = 0;
    int pos = 0;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                continue;   /* indicating element exists already */
        }

        if (pos == capacity - 1)    // -1 because last sign must be terminating '\0'
            reserve_space(&signs, &capacity);

        signs[pos] = ch;    //adding new sign at pos of "old" \0
        ++sz;
        ++pos;
        signs[pos] = '\0';  //adding new terminating \0

        qsort(&signs, sz - 1, sizeof(char), cmp);

        print_signs(&signs, sz);
    }
    getchar();
}

Answer 1

There is a bug in print_sign: the order of precedence between * and [] is such that *signs[i] is parsed as *(signs[i]) instead of (*signs)[i] as you assume.

Here is a corrected version:

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", (*signs)[i], (*signs)[i]);
    }
    printf("\n");
}

There is actually no reason to pass the address of the pointer to this function. It can be simplified into:

void print_signs(char *signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

And called as print_signs(signs, sz);

There are many other issues in your code:

• ch should be defined as int.

• the continue statement in the lookup loop is moot, you should instead write the loop as

  for (pos = 0; pos < sz; ++pos) {
      if (signs[pos] != ch)
          break;   /* indicating element exists already */
  }
  if (pos < sz)
      continue;
  

• there are off by 1 errors in the rest if the main function

• the comparison function is broken too.

Here is a corrected version:

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

void reserve_space(char **c, int *capacity);
void print_signs(const char *signs, int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    if (*capacity == 0) {   // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        *c = realloc(*c, sizeof(char) * (*capacity));
    }
}

void print_signs(const char *signs, int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    unsigned char left = *(const unsigned char *)lhs;
    unsigned char right = *(const unsigned char *)rhs;

    if (left < right) return -1;
    if (left > right) return  1;
    return 0;  /* left == right */
}

int main() {
    int sz = 0;             // space currently "filled" with signs
    int capacity = 0;       // allocated space 
    char *signs = NULL;
    int ch;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                break;
        }
        if (pos < sz)
            continue;  // character is already in the array

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        signs[sz] = ch;    // append the sign in the array
        sz++;
        // '\0' terminator is not needed as array is not used as a string
    }
    qsort(signs, sz, sizeof(char), cmp);
    print_signs(signs, sz);
    free(signs);

    getchar();
    return 0;
}