I'm currently working on solving the Distinct Powers Question (29) on Project Euler. The problem involves finding the number of distinct products for (a^b) where (2 < a < 100) and (2 < b < 100). I initially created an algorithm that successfully handles factorization and checks for duplications. However, as I attempted to enhance the program's performance using linked lists and binary search, I encountered issues leading to a core dump. Despite efforts to identify logical flaws, I couldn't resolve the problem.
Here's the code snippet I'm working with:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_MIN 2
#define A_MAX 100
#define B_MIN 2
#define B_MAX 100
struct Node {
int *data;
struct Node *next;
struct Node *previous;
};
void primeFactor(int *arr, int num) {
for (int k = 2; k <= num; ++k) {
while (num % k == 0) {
num /= k;
arr[k] += 1;
}
}
}
int compareArrays(const int *arr1, const int *arr2, int size) {
for (int k = 0; k < size; ++k) {
if (arr2[k] < arr1[k]) {
return -1; // arr2 is left of arr1
} else if (arr1[k] < arr2[k]) {
return 1; // arr2 is right of arr1
}
}
return 0; // arr2 is arr1
}
void insertSorted(struct Node **head, const int *arr, int size, int *listLength) {
struct Node *current = *head;
int pos = 0;
int left = 0;
int right = *listLength;
int comparison = -3;
while (current != NULL && left < right) {
int mid = (left + right) / 2;
while (pos < mid) {
current = current->next;
pos++;
}
while (pos > mid) {
current = current->previous;
pos--;
}
comparison = compareArrays(current->data, arr, size);
if (comparison == 1) { // arr2 is right of arr1
left = mid + 1;
} else if (comparison == -1) { // arr2 is left of arr1
right = mid;
} else {
break;
}
}
struct Node *prev = (current != NULL) ? current->previous : NULL;
struct Node *nxt = (current != NULL) ? current->next : NULL;
if (comparison != 0) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
if (newNode == NULL) {
perror("Memory allocation error");
exit(EXIT_FAILURE);
}
newNode->data = (int *)malloc(size * sizeof(int));
if (newNode->data == NULL) {
perror("Memory allocation error");
exit(EXIT_FAILURE);
}
memcpy(newNode->data, arr, size * sizeof(int));
if (comparison == -1) { // perform insert left
newNode->next = current;
if (current != NULL) {
current->previous = newNode;
}
if (prev == NULL) {
*head = newNode;
} else {
prev->next = newNode;
newNode->previous = prev;
}
} else if (comparison == 1) { // perform insert right
newNode->next = nxt;
if (current != NULL) {
current->next = newNode;
}
if (nxt != NULL) {
nxt->previous = newNode;
}
} else { // no node exist yet. make node the head.
printf("lol");
*head = newNode;
}
(*listLength)++;
}
}
void freeLinkedList(struct Node *head) {
while (head != NULL) {
struct Node *temp = head;
head = head->next;
free(temp->data);
free(temp);
}
}
int main() {
struct Node *link_list = NULL;
int size = A_MAX;
int listLength = 0;
for (int i = A_MIN; i <= A_MAX; ++i) {
int arr[A_MAX] = {0};
primeFactor(arr, i);
for (int j = B_MIN; j <= B_MAX; ++j) {
int *arr2 = (int *)malloc(size * sizeof(int));
if (arr2 == NULL) {
perror("Memory allocation error");
exit(EXIT_FAILURE);
}
for (int k = 0; k < size; ++k) {
arr2[k] = arr[k] * j;
}
insertSorted(&link_list, arr2, size, &listLength);
}
}
printf("%d\n", listLength);
freeLinkedList(link_list);
return 0;
}```
One logical flaw, which can definitely cause issues such as a core dump occurring, is with the following section of code in your insertSorted function:
memcpy(newNode->data, arr, size * sizeof(int));
if (comparison == -1) { // perform insert left
newNode->next = current;
if (current != NULL) {
current->previous = newNode;
}
if (prev == NULL) {
*head = newNode;
} else {
prev->next = newNode;
newNode->previous = prev;
}
} else if (comparison == 1) { // perform insert right
newNode->next = nxt;
if (current != NULL) {
current->next = newNode;
}
if (nxt != NULL) {
nxt->previous = newNode;
}
} else { // no node exist yet. make node the head.
printf("lol");
*head = newNode;
}
The code uses malloc to allocate memory for newNode but, as indicated in the malloc man page,
The memory is not initialized.
Since comparison can only be 0, -1 or 1, and this code is within the conditional if (comparison != 0) {, then the final else should never be executed. As such, the value of newNode->next is always set to a valid value. However, this is not always the case for newNode->previous. For example, if comparison == -1, then newNode->previous is only set if prev != NULL.
This means that newNode->previous may be uninitialized, thus using it such as with the current = current->previous; line earlier in insertSorted, can cause invalid memory to be accessed.
This issue can easily be fixed. Note that replacing your malloc call with calloc which "... initializes all bytes in the allocated storage to zero" is an option, but as Neil's comment states
Even
callocis not guaranteed to initialize null pointers; it works on most computers because null is very probably 0, (5.13).
Thus, to be more robust, it's better to instead add the line newNode->previous = NULL; just after the memcpy(newNode->data, arr, size * sizeof(int)); line in my specified section of your code.
Also, to make it more clear when casually reading the code that newNode->next is always initialized, and to help ensure later code changes don't break your code, I suggest adding the line newNode->next = NULL; initially as well.