Binary Search Tree ( How to check if out of memory when inserting)

Question

I have created a binarysearchtree and had a question regarding how one would check to see if there was there is no enough memory to create a new node. I know it has something to do with calling the constructor but I don't really understand how or what that has to do with memory.Any help or direction would be much appreciated.

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber)
{
//code to check if memory is full (what i need help on)
//code to insert
}

Just create the node. If there isn't any memory, then the creation fails, an exception is thrown. It's up to you that you don't mess up or mutate the tree in anticipation that there *is* enough memory. — PaulMcKenzie, Oct 28 '14 at 20:14
Just let the operator new throwing its 'bad_aloc' and let your program die, unless you have a good way to fix it (than, catch std::bad_alloc or use new with nothrow) — , Oct 28 '14 at 20:17
I suspect that this is a homework assignment and there is more context that hasn't been shown to us. — Daniel, Oct 28 '14 at 20:31
So the best way to return false if it is full is to catch the exception and return false correct? Want to make sure I'm understanding this correctly. — robo, Oct 28 '14 at 20:31
@robo - It is much more than just catching an exception. That is the easy part. The part you should be concerned with is that you didn't screw up your tree beforehand, and then at the last moment, discover a node can't be created. See my answer. — PaulMcKenzie, Oct 28 '14 at 20:35

score 2 · Answer 1 · answered Oct 28 '14 at 20:31

To answer your question in a generic way, you would do the allocations and make any calls to functions that may throw prior to any mutation or change in your data structure:

For example:

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber)
{
   TreeNode* newNode = new TreeNode();
   // any other functions that may throw
   //...
   // now do housekeeping to update tree
}

So in other words, make sure that you have all your data already set up before you update your tree. This is perfectly safe, as any exception thrown will not harm the existing tree. You can have a simple try/catch acknowledging that the node couldn't be created if an exception is thrown.

The wrong (or more cumbersome) way is this:

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber)
{
   // code that changes the internals of BinarySearchTree
   // ...
   // now create the node
   TreeNode* newNode = new TreeNode();
}

Unless you have a try/catch that does a rollback of the changes made to the tree, you will end up corrupting the tree using this approach if new or some other function throws an exception.

Awesome, I think I understand what I need to do now. Thank you. — robo, Oct 28 '14 at 20:36
+1 I utterly concur with this answer. the only drawback to the node allocation front-load is there is simply no guarantee you *need* to insert until you detect such a condition. I.e. 1.allocate, 2.search, 3.no-insert-needed, 4.delete unused node. That steps 1 and 4 have to be done even when *not needed* because no node will be inserted is not a desirable attribute. A proper algorithm doesn't hose your tree in the first place until you know you *have* to insert a node *and* have successfully allocated said-same. — WhozCraig, Oct 28 '14 at 21:25
@WhozCraig: Ideally the treeInsert function would be able to use a returned reference from treeFind so it doesn't have to reimplement it. And then after finding the insert reference and checking if it needs to insert it would allocate the new memory and proceed. — Zan Lynx, Oct 28 '14 at 21:37

score 0 · Answer 2 · edited May 23 '17 at 11:57

The assumption here is that you want to write a program that does not result in using more resources than your system has available. Rather than making the necessary system call to check resources every time that you add a nodes to your tree ( which sounds like a lot if you plan on memory being an issue ), consider what other approaches you could take to prevent this situation from occurring.

The exception handling suggested in the comments is a good option. Here is a link describing that:

How can I check if there is enough heap memory available?

If you must, you could use sysconf as shown below, but I would avoid doing this every time, perhaps do it every 1000 times you add and keep the result locally to reference and react when you start getting close.

Here is a start to what your looking for:

#include <unistd>

size_t getTotalSystemMemory()
{
    long pages = sysconf(_SC_PHYS_PAGES);
    long page_size = sysconf(_SC_PAGE_SIZE);
    return pages * page_size;
}

Binary Search Tree ( How to check if out of memory when inserting)

2 Answers2