I wrote a small word processing program the other day and found that when the memory allocation for the bianry search tree is kept, where I store every single word I tried to parse using malloc() , my 4G memory will be consumed quickly.
My program has no memory focus, because I only allocate memory for this binary search tree. But still, I can highlight less than 6,000 binary search trees in my program. The structure of this binary search tree is:
typedef struct BSTnode{ char data[20]; struct BSTnode* leftchild; struct BSTnode* rightchild; int num; }BSTnode;
So this is pretty small. According to what I found out, each of these structures costs 80 bytes of memory ( data costs 20 bytes, as well as the rest due to memory alignment) (right?)
So, 6000 that the structure in memory will cost 480 MB.
However, my program failed when I tried to allocate memory for this 6000 structrue (it is normal when I allocate memory for 5000 of them). And my computer has a total memory of 4 GB !! (about 1000MB cached , 2100MB available and 1100MB free (according to the task manager on Windows).
Why is this?
My main concerns:
Why is this?
How to correctly manage memory allocation in my program.
Could you provide additional information? (quote and example, books, etc.)
(By the way, if you want to see my code, please leave a comment below. Too many lines, it takes some time to make it more readable. Sorry)
####################################################### ################### 3
code:
#include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<string.h> typedef struct Node { struct Node* leftChild; struct Node* rightChild; char data[20]; int num; } Node; int inputWord(FILE*, Node*); int main(int argc, char** argv) { printf("Enter the name of file you wanna open here:"); char name[20] = { '\0' }; scanf("%s", name); FILE* fs = fopen(name, "r"); if (!fs) { perror("Failed to open file!"); exit(EXIT_FAILURE); } Node* firstNode = malloc(sizeof(Node)); if (firstNode == NULL ) { perror("ALLOCATION FAILED!"); exit(1); } firstNode->leftChild = firstNode->rightChild = NULL; firstNode->num = 1; strcpy(firstNode->data, "a"); inputWord(fs, firstNode); fclose(fs); printf("Done!!"); return 0; } int inputWord(FILE* fs, Node* firstNode) { rewind(fs); /*first figure out a single word, and then put it into to BST*/ int flag_1 = 0; char buf = '\0'; char word[20] = { '\0' }; Node* ptrOfNode = firstNode; int numOfWord = 0; while (1) { if (numOfWord < 2000) { //amend this number to determine how many word to be input if (1 != fread(&buf, 1, 1, fs)) { perror("failed to read file or eof\n"); } if (!isalpha(buf)) continue; /*this while loop is used to picked out a single word in the text*/ while (flag_1 == 0) { strncat(word, &buf, 1); if (1 != fread(&buf, 1, 1, fs)) { perror("Failed to read char from the file"); exit(2); } if (isalpha(buf)) flag_1 = 0; else flag_1 = 1; //now buf is not alpha } flag_1 = 0; while (1) { if (stricmp(word, ptrOfNode->data) > 0&& ptrOfNode->rightChild!=NULL) ptrOfNode = ptrOfNode->rightChild; else if (stricmp(word, ptrOfNode->data) < 0 && ptrOfNode->leftChild!=NULL) ptrOfNode = ptrOfNode->leftChild; else break; } /*the while loop above break for only two reason: *1.there have been an identical word in the tree; *2.the child where I want to insert the word have not been allocated memory */ if (stricmp(word, ptrOfNode->data) == 0) { ++(ptrOfNode->num); memset(word, '\0', 20); ptrOfNode = firstNode; //move the pointer of Node to the very first numOfWord+=1; continue; } else { if (stricmp(word, ptrOfNode->data) > 0) { //mean that there is no more right child ptrOfNode->rightChild = malloc(sizeof(Node)); if (ptrOfNode->rightChild == NULL ) { perror("FAILED TO ALLOCATED MEMORY!!"); exit(1); } ptrOfNode = ptrOfNode->rightChild; ptrOfNode->leftChild = ptrOfNode->rightChild = NULL; ptrOfNode->num = 1; strcpy(ptrOfNode->data, word); memset(word, '\0', 20); ptrOfNode = firstNode; numOfWord += 1; continue; } else { ptrOfNode->leftChild = malloc(sizeof(Node)); if (ptrOfNode->leftChild == NULL ) { perror("FAILED TO ALLOCATE MEMORY!"); exit(1); } ptrOfNode = ptrOfNode->leftChild; ptrOfNode->leftChild = ptrOfNode->rightChild = NULL; ptrOfNode->num = 1; strcpy(ptrOfNode->data, word); memset(word, '\0', 20); ptrOfNode = firstNode; numOfWord += 1; continue; } } } else break; } return 0; }
And there is another program that I wrote that can fully explain my question. But it’s too long that I can’t make it available to everyone and publish it here. [1] https://github.com/walkerlala/searchText
If you do not think that this is a suitable program for this question (the only one in my link will be absolutely), please consider my problems above .