I realize that this particular question has been beaten to death on here, but I am absolutely lost as to why this error is still occurring for me.
Bare in mind that this isn't for an assignment or anything, so whatever logical flaws/errors you may see in my implementation are due to a lack of programming experience; I have none and this is my first attempt at implementing a typical data structure. I'm trying to teach myself programming at the moment so please understand if I'm making any glaring errors anywhere.
That said, here is the source for a binary search tree implementation (with some other junk stuff I threw in; I tried to make cin like C++'s cin):
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdint.h>
#define INIT_BUF_SIZE 1
#define INIT_STACK_SIZE 1
#define ERROR_MSG "The program could not allocate enough memory :[\n"
typedef enum {false, true} bool;
typedef struct Node {
int value;
int quantity;
struct Node *parent;
struct Node *left;
struct Node *right;
} Node;
typedef struct Node_Stack {
unsigned int size;
unsigned int max_size;
Node **s;
} Node_Stack;
typedef struct Count_Stack {
unsigned int size;
unsigned int max_size;
unsigned int *s;
} Count_Stack;
Node *root = NULL;
Node_Stack stack;
Count_Stack c_stack;
/********************* Stack Operations *********************/
bool init_c_stack (void) {
unsigned int *temp = calloc(INIT_STACK_SIZE, sizeof(int));
if (temp == NULL) {return false;}
c_stack.s = temp;
c_stack.size = 0;
c_stack.max_size = INIT_STACK_SIZE;
return true;
}
void delete_c_stack (void) {
c_stack.s = NULL;
c_stack.size = 0;
c_stack.max_size = 0;
free(c_stack.s);
}
bool init_stack (void) {
Node **temp = calloc(INIT_STACK_SIZE, sizeof(Node *));
if (temp == NULL) {return false;}
stack.s = temp;
stack.size = 0;
stack.max_size = INIT_STACK_SIZE;
return true;
}
void delete_stack (void) {
stack.s = NULL;
stack.size = 0;
stack.max_size = 0;
free(stack.s);
}
bool init_stacks (void) {return init_stack() && init_c_stack();}
void delete_stacks (void) {
delete_c_stack();
delete_stack();
}
bool update_c_stack (void) {
if (c_stack.s == NULL) {return false;}
unsigned int *t = realloc(c_stack.s,
sizeof(*c_stack.s)*(c_stack.max_size + 1));
if (t == NULL) {return false;}
c_stack.s = t;
c_stack.max_size++;
return true;
}
bool update_stack (void) {
if (stack.s == NULL) {return false;}
Node **t = realloc(stack.s, sizeof(*stack.s)*(stack.max_size + 1));
if (t == NULL) {return false;}
printf("stack.max_size before = %u\n", stack.max_size);
printf("reallocated to %d bytes\n",
sizeof(Node *)*(stack.max_size + 1));
stack.s = t;
stack.max_size++;
printf("stack.max_size after = %u\n", stack.max_size);
return true;
}
bool push_count (unsigned int i) {
if (c_stack.s == NULL) {return false;}
if (c_stack.size < c_stack.max_size || update_c_stack()) {
c_stack.s[c_stack.size++] = i;
return true;
}
return false;
}
bool push (Node *i) {
if (stack.s == NULL) {return false;}
if (stack.size < stack.max_size || update_stack()) {
stack.s[stack.size++] = i;
return true;
}
return false;
}
/******************* End of Stack Operations *******************/
bool add_node (int x) {
if (get_num_levels(root) == UINT_MAX) {
printf("Failed to add %d to tree\n", x);
return false;
}
Node *f = find(root, x), *t = (Node *)calloc(1, sizeof(Node)), *p;
if (root == NULL) {
t->value = x;
t->quantity = 1;
t->parent = NULL;
t->left = NULL;
t->right = NULL;
root = t;
}
else if (f == NULL) { // x doesn't exist in tree
f = root;
p = f->parent;
while (f != NULL) {
p = f;
if (x < f->value) {f = f->left;}
else if (x > f->value) {f = f->right;}
}
t->value = x;
t->quantity = 1;
t->parent = p;
t->left = NULL;
t->right = NULL;
if (x < p->value) {p->left = t;}
else if (x > p->value) {p->right = t;}
else {f->quantity++;} // x already exists in tree
}
printf("\n" TREE_SEPERATOR "\n");
printf("\nAdded node containing %d\n", x);
print_tree_formatted();
printf("\nNow %d nodes in the tree.\n", get_num_nodes(root));
printf("\nNow %d levels in the tree.\n", get_num_levels(root));
return true;
}
bool remove_node (int x) {
Node *f = find(root, x);
if (f != NULL) {
if (f->quantity > 1) {f->quantity--;}
else {replace_node(f); free(f);}
printf("\n" TREE_SEPERATOR "\n");
printf("\nRemoved node containing %d\n", x);
print_tree_formatted();
printf("\nNow %d nodes in the tree.\n", get_num_nodes(root));
printf("\nNow %d levels in the tree.\n", get_num_levels(root));
return true;
}
return false;
}
/*************************************************************************
* Function Name: *
* str_split *
* Purpose: *
* The function below takes a single string and breaks it up into a *
* set of constituent sub-strings, based on the delimiter that is *
* passed in to break the string by. *
* Parameters: *
* - s The string to be split *
* - len The length of the string *
* - c The size of the returned char * array *
* - delim The delimiter by which the string s is to be broken up by *
* Return Value: *
* char ** A pointer to an array of c number of strings, or NULL on *
* failure to allocate enough space *
*************************************************************************/
char **str_split (char *s, unsigned int len, unsigned int c, const char delim) {
char **result;
unsigned int i, j, k = 0, l;
if (s == NULL || len == 0) {return NULL;}
/* Allocate memory for c number of strings/char pointers */
result = calloc(c + 1, sizeof(char *));
if (result != NULL) {
for (i = 0; i < c + 1; i++) {
/* Allocate space for the actual chars for each string */
result[i] = calloc(len, sizeof(char));
if (result[i] == NULL) {return NULL;}
}
/***************************************************************
* i holds index of advancing pointer *
* j holds index of following pointer *
* k holds index of string in returning array of char pointers *
* l holds index of char in string *
***************************************************************
* Loop over and copy contents of s into the each index of *
* result *
***************************************************************/
for (i = 0, j = 0; i < len; i++) {
l = 0;
if (s[i] == delim) {
for (; j < i; j++) {result[k][l++] = s[j];}
k++;
j = i + 1;
}
}
for (; j < i; j++) {result[k][l++] = s[j];}
}
return result;
}
/*************************************************************************
* Function Name: *
* cin *
* Purpose: *
* The function below allows for "continuous" user input, based on *
* how much the user has already entered, by dynamically allocating *
* more memory whenever the input buffer is maxed out. *
* Parameters: *
* - cur_size The initial allocation size for the input buffer *
* Return Value: *
* char * A string/pointer to an array of characters or NULL *
* if allocation failed *
*************************************************************************/
char *cin (unsigned int cur_size) {
char *input = (char *)malloc(cur_size);
int i = 0, c = EOF;
if (input != NULL) {
// cook keyboard input until NL or EOF
while ((c = getchar()) != '\n' && c != EOF) {
if ((char)c == 8 || (char)c == 127) {
printf("\b \b\b \b\b \b");
fflush(stdout);
i = (i > 0) ? i - 1 : i;
}
else {
input[i++] = (char)c;
if (i == cur_size) {
/* Attempt to double the current size of the buffer */
cur_size *= 2;
input = realloc(input, cur_size);
if (input == NULL) {
printf("Unable to allocate enough memory for input\n");
break;
}
}
}
}
// null-terminate user input
input[i] = '\0';
}
return input;
}
...
int main (void) {
char *input, **s, t, delim = ' ';
unsigned int len, i, count, result;
bool valid;
/* Allocate space for both stacks */
init_stacks(); // DO NOT MOVE OR DUPLICATE CALL
while (true) {
/* Continuously grab null-terminated user input string */
input = cin(INIT_BUF_SIZE);
if (input != NULL) {
len = string_length(input);
/* Get the number of times the char delim appears in input */
count = num_in_string(input, delim);
/***********************************************************
* First word in user input should either be: *
* - "add" *
* - "remove" *
* - "print" *
* - Any of the exit commands ("q", "quit", or "exit"). *
***********************************************************/
t = input[0];
/* Exit loop if first token is an exit command */
if (user_exit(input)) {break;}
/*******************************************************
* Only process user input if there's at least 2 words *
* Eg: add 1 <-- Valid *
* add <-- Invalid *
* remove 1 <-- Valid *
* foobar <-- Invalid *
*******************************************************/
if (count > 0) {
/* Get the user input split up by spaces */
s = str_split(input, len, ++count, delim);
if (s != NULL) {
/*******************************************
* Look at each token entered by the user, *
* except the first one *
*******************************************/
for (i = 1; i < count; i++) {
/***********************************************
* Assuming the token is a number, convert the *
* token to an integer *
***********************************************/
result = string_to_int(s[i], &valid);
if (same_string(s[0], "print")) {
if (same_string(s[1], "stack")) {
printf("size = %u\n", stack.size);
printf("max_size = %u\n", stack.max_size);
}
else {printf("%s\n", s[i]);}
fflush(stdout);
}
else if (valid) {
if (same_string(s[0], "add")) {
add_node(result);
}
else if (same_string(s[0], "remove")) {
remove_node(result);
}
}
}
/* Free up memory allocated for split user input */
for (i = 0; i < count; i++) {free(s[i]);} // DO NOT MOVE
free(s); // DO NOT MOVE
}
else {printf(ERROR_MSG);} // couldn't allocate heap space
}
/* Free up memory allocated for cin */
free(input); // DO NOT MOVE
}
}
/* Free up memory allocated for both stacks */
delete_stacks(); // DO NOT MOVE
return 0;
}
So when I run this, the program runs fine as I'm adding in the following tree (in sequence): 15, 7, 23, 3, 11, 19, 27.
Then, when I add the number 5 to the tree, the program crashes with the titular error. I've tried debugging with both gdb (and lldb), but I don't think that was really effective, even with the -g flag turned on.
It doesn't make sense to me since the call to realloc in both update_stack and update_count_stack doesn't fail prior to adding the number 5.
I do realize too that it isn't typical or good practice to increase the size of a dynamically allocated memory chunk by 1 over and over again, as it is inefficient, but I just want to know why this is occurring here, and how I might be able to fix it - I feel like I'm just missing something obvious and am pulling my hair out over something minuscule!
Edit
Thanks for the feedback, everyone.
I copy-pasted my source file on here a bit indolently yesterday, so please excuse that as I had to run at the moment. I've since tried to minimize the posted code to only show relevant functions, which include those that call malloc, realloc, or free. I've also tried adding some comments into the code to help understand it a bit better.
typedef enum {false, true} bool;and C99 come and makestdbool.hwelcome to 1999.get_num_levels_recursive. The value ofcountis indeterminate if neither if-clause results to true. Likewise, inreplace_node, you're passing an indeterminatepjust about everywhere.MALLOC_CHECK_=2in the environment.malloc().s,x,y,a[],b[]etc are even in the current context, meaningless.