HW3: Palindrome, Strings and Memory

Problem 1 is a set of online questions on the Gradescope assignment HW3_p1: single-choice and multiple-choice questions about functions, pointers to functions, strings, and dynamic memory in C.

Answer the questions directly on Gradescope. Each question is graded all-or-nothing (a multiple-select question is correct only if your selection matches exactly). Your total score is visible immediately after submission, and you may resubmit as many times as you like until the deadline; the latest answers count.

A string s₀s₁⋯s_m−1 is said to be a palindrome if s_i = s_m−1−i holds for every i ∈ {0, 1, ⋯, m−1}.

Read n strings and test whether each of them is a palindrome.

Input format

On the first line, a nonnegative integer n.

Then 2n lines follow. The (2i−1)-th line is a positive integer representing the length of the i-th string. The 2i-th line is the i-th string, which is guaranteed to contain no whitespace characters.

Output format

n lines. For every i ∈ {1, ⋯, n}, print Yes on the i-th line if the i-th string is a palindrome; print No otherwise.

Example

5
1
a
4
(())
2
[[
5
abcba
8
ab0220ba

Yes
No
Yes
Yes
Yes

Notes

There are no guarantees on the maximum possible value of n or the length of the strings. Dynamic memory should be used to store each input string.

It is often a good exercise to implement your own versions of some standard library functions. In this task, you need to implement some standard library functions related to character and string manipulations.

The functions you need to implement are listed below.

int hw3_islower(int ch);
int hw3_isupper(int ch);
int hw3_isalpha(int ch);
int hw3_isdigit(int ch);
int hw3_tolower(int ch);
int hw3_toupper(int ch);

size_t hw3_strlen(const char *str);
char *hw3_strchr(const char *str, int ch);
char *hw3_strcpy(char *dest, const char *src);
char *hw3_strcat(char *dest, const char *src);
int hw3_strcmp(const char *lhs, const char *rhs);

Your implementations should conform to the C standard. The standard documentations and examples on these functions can be found at cppreference. Do not trust materials from any other sources like Wikipedia, Baidu Zhidao, CSDN, Zhihu, etc.

Notes

• All functions' return types, parameter declarations and behaviors should meet the requirements in the cppreference pages. The function names are prefixed hw3_ to avoid name collisions.
• Be careful: cppreference contains both C and C++ documentation. Refer to the C pages; C and C++ are not fully compatible.
• We use ASCII encoding (the most common one), although the C standard allows others (not required in CS100).
• You may ignore the restrict qualifier on the pointer parameters of strlen, strchr, strcpy, strcat and strcmp.
• For backward compatibility, the C standard requires strchr to return char * instead of const char *. To silence the "discarded qualifiers" warning, use an explicit cast like char *pos = (char *)str; or return (char *)str;.
• Some behaviors depend on locale settings. You only need to work under the default locale ("C").
• You may not call any standard library functions — implement everything yourself.
• It is guaranteed that the tests do not lead to undefined behaviors.

Keep it simple

Make your implementation as simple as possible:

• For hw3_islower, hw3_isupper, hw3_isalpha, hw3_isdigit, hw3_tolower and hw3_toupper, the function body should contain only one statement, which is a return.
• For hw3_strlen, hw3_strchr, hw3_strcpy, hw3_strcat and hw3_strcmp, the function should be no more complex than a single pass over the given strings — do not scan the strings over and over, or go back and forth between positions. For example, if your hw3_strlen traverses the whole string to count the characters, you may not call it inside hw3_strcmp just to get the lengths, because you still need to traverse the strings to compare them.
• You may define helper functions, but make sure they are necessary and meaningful.

Background

Making a C program memory-safe is hard: every memory access must be valid, and all dynamically allocated memory must be correctly freed. Tools such as AddressSanitizer, UndefinedBehaviorSanitizer and Valgrind exist to catch these bugs automatically. In this problem you will write a very simple such tool yourself.

Description

Write a tool that detects memory leaks and invalid calls to free. A memory leak happens when a block allocated on the heap (by malloc or calloc) is never freed. A call to free(ptr) is valid if and only if

• ptr is a null pointer, or
• ptr was returned by a previous malloc/calloc call, and this is the first time it is passed to free.

Before starting, read the cppreference pages on malloc, calloc and free (ignore the thread-safety parts). Do not trust materials from other sources. You do not need to handle realloc or aligned_alloc.

Main ideas

• Record every call to malloc and calloc — an array of records is enough.
• When free(ptr) is called, check whether ptr is in the array. If yes, the free is valid: remove the record (we recommend simply setting the recorded pointer to NULL). If not, it is invalid — print an error message.
• At program termination, walk the array: any remaining non-NULL pointer is a leak. Print information about each leaked block.

Recording file and line

It helps to record not only the address but also the source file and line number, so an error message can look like

100 bytes memory not freed (allocated in file hw3_problem1.c, line 32)

or

Invalid free in file hw3_problem1.c, line 49

So each array element should be a struct:

#define MAX_RECORDS 1000

struct Record {
  void *ptr;              // address of the allocated memory
  size_t size;            // size of the allocated memory
  int line_no;            // line number of the malloc/calloc call
  const char *file_name;  // file in which the call happens
};

struct Record records[MAX_RECORDS];

Pay attention to the type of size: on 64-bit machines size_t may be 64-bit, and a block can exceed the range of 32-bit integer types. The file name and line number come from the predefined macros __FILE__ and __LINE__ (see predefined macros).

The magic: intercepting the calls

Use #define to replace calls to malloc, calloc and free so they are captured by your own functions:

void *recorded_malloc(size_t size, int line, const char *file) {
  void *ptr = malloc(size);
  if (ptr != NULL) {
    // record this allocation
  }
  return ptr;
}

void *recorded_calloc(size_t cnt, size_t each_size, int line, const char *file) {
  void *ptr = calloc(cnt, each_size);
  if (ptr != NULL) {
    // record this allocation
  }
  return ptr;
}

void recorded_free(void *ptr, int line, const char *file) {
  // check validity, then free or report
}

#define malloc(SIZE) recorded_malloc(SIZE, __LINE__, __FILE__)
#define calloc(CNT, EACH_SIZE) recorded_calloc(CNT, EACH_SIZE, __LINE__, __FILE__)
#define free(PTR) recorded_free(PTR, __LINE__, __FILE__)

Leak checking at exit

To run a check when the program terminates, declare a function with __attribute__((destructor)):

void check_leak(void) __attribute__((destructor));

void check_leak(void) {
  // walk the array; anything still non-NULL is leaked
}

Even with an empty main, such a program will run check_leak on exit.

Usage

Place your code in p4.c as a header-style file with include guards (the course driver #includes it, like memcheck.h above):

// p4.c
#ifndef CS100_MEMCHECK_H
#define CS100_MEMCHECK_H 1

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

#define MAX_RECORDS 1000

struct Record { /* ... */ };

/* ... your recorded_* functions and check_leak ... */

#define malloc(SIZE) recorded_malloc(SIZE, __LINE__, __FILE__)
#define calloc(CNT, EACH_SIZE) recorded_calloc(CNT, EACH_SIZE, __LINE__, __FILE__)
#define free(PTR) recorded_free(PTR, __LINE__, __FILE__)

#endif // CS100_MEMCHECK_H

Output format

When the program terminates, print a summary. First a line Summary:, then for every leaked block a line

<size> bytes memory not freed (allocated in file <file>, line <line>)

and finally a closing line — either All allocations have been freed. or <k> allocation records not freed (<bytes> bytes in total).. An invalid free prints Invalid free in file <file>, line <line> at the point where it happens.