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.
The following is my attempt.
file1.c
#include <stdio.h>
extern int read_palindrome();
int main()
{
if (read_palindrome()) printf("input is a palindrome");
else printf("input is not a palindrome");
return 0;
}
file2.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int check_palindrome2(char *, int);
int read_palindrome() {
unsigned int len_max = 128;
unsigned int current_size = 0;
char *pStr = malloc(len_max);
current_size = len_max;
int i = 0;
char c;
if (pStr != NULL) {
while (( c = getchar() ) != 'n') {
pStr[i] = (char)c;
i++;
if(i == current_size) {
current_size += len_max;
char *tmp = realloc(pStr, current_size);
if (tmp == NULL) {
free(pStr);
return 2;
}
pStr = tmp;
}
}
pStr[i] = '';
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;
}
After copying the file onto both machines, running the appropriate compilation commands on both my MacOS and Ubuntu, and feeding a known palindrome of 121.
gcc -c file1.c gcc -c file2.c gcc -o output file1.c file2.c ./output
The code prints input is a palindrome on MacOS but input is not a palindrome on Ubuntu.Can anyone tell me if there’s anything wrong with my code, or there should be something I should be doing differently across the different OS.
Advertisement
Answer
You have inconsistent error handling. In one case you return 2, in another you indirectly return 1. This should be changed:
I will use negative values for errors:
int read_palindrome()
{
unsigned int len_max = 128;
unsigned int current_size = 0;
char *pStr = malloc(len_max);
current_size = len_max;
int i = 0;
char c;
if (pStr == NULL)
return -1;
while (( c = getchar() ) != 'n') {
pStr[i] = (char)c;
i++;
if(i == current_size) {
current_size += len_max;
char *tmp = realloc(pStr, current_size);
if (tmp == NULL) {
free(pStr);
return -1;
}
pStr = tmp;
}
}
pStr[i] = '';
free(pStr);
return check_palindrome2(pStr,i); // If pStr==NULL we do not reach this line.
}
Now you have -1 returned in any error case and you do not use pStr if it is NULL.
Let’s address the “use after free” problem:
free(pStr);
return check_palindrome2(pStr,i);
Accessing pStr after freeing it is illegal. Rearrange the function calls.
int retval = check_palindrome2(pStr,i);
free(pStr);
return retval;
In addition to these changes you need to handle the return value of this function properly:
int main()
{
int pali = read_palindrome();
if (pali < 0)
printf("An error occured.n");
else if (pali)
printf("Input is a palindromen");
else
printf("Input is no palindromen");
return 0;
}
Finally lets speed up your palindrome detection a bit:
int check_palindrome2(char *s, int length)
{
for (int i = 0; i < length / 2; i++) // only walk up to the middle.
{
if (s[i] != s[length-i-1])
return 0;
}
return 1;
}
If s[1] == s[9] is true then s[9] == s[1] will also be true. No need to check twice.