Read a palindrome of unknown length

Question

I have a task to write the function: int read_palindrome(); // input comes from stdin

which will read one line from standard input and returns 1 if the line is a palindrome and 0 otherwise. A line is terminated by the newline character (’\n’) and the does not include the newline.

There are requirements to be met:

There is no assumption about the length of the input. You are also not allowed to read the input twice, e.g. read the input, forget you read the input but remember the length, read the input again. which results in the input being read twice.

You are also not allowed to create a very large buffer to store the input reasoning that the input line might be expected to be smaller than a very large buffer. The reason for this restriction is that we will consider the memory usage of the program.

The task is to come out with a correct program with the best CPU time and memory usage.

I have attempted my code below. May I know if there is anything I could improve on here to optimise for correctness, CPU and memory?

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

int read_palindrome();
int check_palindrome2(char *, int);

int main() 
{
    if (read_palindrome()) printf("input is a palindrome");
    else printf("input is not a palindrome");
    return 0;
}



int read_palindrome() {
    unsigned int len_max = 128;
    unsigned int current_size = 0;
    char *pStr = malloc(len_max); 
    current_size = len_max;
    int i;
    char c;
    if (pStr != NULL) {
        while (( c = getchar() ) != '\n') { 
            pStr[i] = (char)c;
            i++;
            if(i == current_size) {
                current_size = i+len_max;
                pStr = realloc(pStr, current_size);
            }
        }

        pStr[i] = '\0';
        free(pStr);
    }
    return check_palindrome2(pStr,i);
}   


int check_palindrome2(char *s, int length) {
    for (int i = 0; i < length; i++) {
        if (s[i]!= s[length-i-1]) {
            return 0;
        }
    }
    return 1;
}

Answer 1

• free(pStr) is misplaced. Once it is freed, you may not touch it anymore. Calling check_palindrome2(pStr) after freeing causes an undefined behavior.

  Consider

      int rc = check_palindrome2(pStr, i);
      free(pStr);
      return rc;
  

• check_palindrome2 could be called with a null pointer, but doesn't test it.

• current_size += len_max is more clear than current_size = i+len_max.

• read_palindrome is a misnomer. It doesn't read a palindrome. It reads a string of an unknown length. Now, SRP mandates splitting it into independent read_line and is_palindrome functions.

• You test malloc for a failure. Keep in mind that realloc may fail as well.

      char * tmp = realloc(....);
      if (tmp == NULL) {
          free(pStr);
          return error;
      }
      pStr = tmp;
  

  NB: a simple pStr = realloc(....) is not good. If realloc fails, you'd have a memory leak.

Answer 2

A first point concern palindrome checking. In check_palindrome2(), you only need to perform the comparison until length/2.
From a performance point of view, this part is unlikely to be critical compared to the other ones. However, if it is a homework, useless to stress your Professor.

A critical point concerns the number of reallocation, which clearly decreases the time efficiency of your programme. You cannot avoid it as memory usage is an important criteria according to the requirements. Effectively, allocating a buffer of some Mbytes to read a few bytes is wasting memory. However, increasing memory size by step of 128 bytes to read 1 Gbytes is really not efficient. It is such a situation when one has to find the best trade-off between time efficiency and memory efficiency. One possibility is to make this trade-off adaptive. You start with a small increment (128 in your program), as you did, but then, if you detect that too many reallocations occur, you increase the increment, for example by doubling it. You can do it several times. Maybe pay attention to set a maximum value of this increment.

Another critical point is the efficiency of reading the input. You do it character per character. It may be more efficient to read n characters in a raw, for example with fgets(). Pay attention in this case that in the last reading, it is likely that you will read less than n characters. You will have to test it carefully.

Last but not least, pay attention to avoid memory leakage or premature free. This point was clearly stated in the previous answer.

Answer 3

"There is no assumption about the length of the input." is not reasonable - there is alwasy some reasonable limiting factor - perhaps more than UINT_MAX.

This code assumes current_size <= UINT_MAX by using unsigned.

Using size_t would make more sense as that is the type used by *alloc() and the right-size type for array indexing/pointer math.

// unsigned int len_max = 128;
// unsigned int current_size = 0;
size_t len_max = 128;
size_t current_size = 0;

---

Use _Bool for boolean functions

// int check_palindrome2(char *s, int length) {
_Bool check_palindrome2(char *s, int length) {
// or with <stdbool.h>
bool check_palindrome2(char *s, int length) {

---

Use const

For referenced data that does not change, use const for potential optimizations , wider code application and function clarity.

// int check_palindrome2(char *s, int length) {
int check_palindrome2(const char *s, int length) {

---

Double loop check speed

Perform length/2 checks, not length checks as in for (int i = 0; i < length; i++)

With above improvements:

#include <stdbool.h>

bool check_palindrome2(const char *s, size_t length) {
  const char *end = s + length;
  while (end > s) {
    end--;
    if (*end != *s) {
      return false;
    }
    s++;
  }
  return true;
}

Answer 4

You are storing characters in a string, and then checking them for being a palindrome. This is CPU efficient, but memory inefficient.

To store a palindrome really only requires at most n/2 + 2 characters, maximum (for odd length palindromes, n/2 + 1 for evens). If you check each character input against (*note) str[-1] (even) and str[-2] (odd), you could track how many duplicate characters you had seen, and only lengthen the string on a mismatch.

(*note: using Perl/Python notation that str[-1] is last character in str, etc.)

This would take more CPU, but would save memory in the case of very long palindromes.

For example, with the odd palindrome abcba you only need to store the abc string. The rest could be comparisons going backwards until you reach start-of-string and '\n' at the same time.