memory allocation newbie problem

I have a program that searches and outputs prime-numbers. I use linked-list to store these numbers (because I need to learn dynamic memory allocation). It's made of struct defined like this:

Code:

struct Tmylist {
  int value; 
  Tmylist *next;
};

It works great. User enters a number and program searches through interval (0, number> and stores all prime-numbers found within this interval into my linked-list. Problem is, when user enters number greater than 25900 (or something near this). It crashes. Someone told me my problem are segments in memory. He told me I have only one memory segment available for allocating with new. I use new like this:

Code:

Tmylist *beggining = new Tmylist;

and maybe I filled the segment. Could anyone help me?

If you're coding under 16 bit environment, this might be the case. What is your compiler and operating system?

Compiler is VC++ 5.0 and OS is W98. But this is a Win32 Console Application project under VC - it executes in DOS window.

Anybody have a clue? I don't know what to do. I just need to know how much memory am I able to allocate with "new" and how to get over it if it's possible...

Here is complete source. Fully functional until you enter a value I mentioned above.

Code:

#include <stdlib.h>
#include <string>
#include <iostream>
#include <time.h>
#include <math.h>
using namespace std;

struct Tlistitem {
  int i;
  unsigned short index;
  Tlistitem *next;
};

//-----

void prime_number_recursion(int& number, Tlistitem* p, int& count, char mod) {
  bool prime_number = true;
  if (('1' == mod) || ('3' == mod)) for (int i = 2; ('3' == mod) ? i <= (int)sqrt(number) : i < number; i++)
    if ((double)number / i == double(number / i)) {prime_number = false; break;}
  if (prime_number) if (cislo > p->i) {
    p->next = new Tlistitem;
    p->next->index = p->index + 1;
    p = p->next;
    p->i = number;
    p->next = NULL;
  }
  if (number < count) prime_number_recursion(++number, p, count, mod);
}

void view_contents(Tlistitem* p, long elapsed_time) {
  if (NULL != p) do {
    p = p->next;
  } while (NULL != p->next);
  cout << "\nCELKOVY PROCESOROVY CAS: "<< elapsed_time << "\nPOCET NALEZENYCH PRVOCISEL: " << p->index + 1 << endl;
}

Tlistitem* initialization() {
  Tlistitem *ptr = new Tlistitem;
  ptr->i = 0;
  ptr->index = 0;
  ptr->next = NULL;
  return ptr;
}

//------

int main() {
  string command;
  while (1) {
    cout << "how many numbers to search for prime-numbers?:\n> ";
    cin >> command;
    if ((0 != atoi(command.c_str())) && (65535 >= atoi(command.c_str()))) break;
    else cout << "input a integer number from <1, 65536)" << endl;
  }
  int count = atoi(command.c_str());
  while (1) {
    cout << "mode of searching:\n1 - no optimalization\n2 - prime-numbers optimalization\n3 - square-root optimalization\n4 - both optimalizations\n> ";
    cin >> command;
    if ((0 < atoi(command.c_str())) && (4 >= atoi(command.c_str()))) break;
    else cout << "invalid input" << endl;
  }
  Tlistitem *beginning = initialization();
  Tlistitem *p = beginning;
  int number = 0;
  cout << "working.......";
  long start = clock();
  prime_number_recursion(number, p, count, command[0]);
  long elapsed_time = clock() - start;
  vypsatobsah(beginning, elapsed_time);
  return 0;
}

There is no code for freeing allocated memory yet, I know it. And only modes 1 and 3 work. It doesn't matter, important is just the memory question.

I think it's stack space that is your problem due to the number of times you're calling prime_number_recursion recursively.

I'm not sure if the setting is the same for VC++ 5.0, but in version 6.0 the project/settings/link/output allows you to alter the amount of stack space allocated. Alternatively you can specify the amount using a linker switch. I allocated alot and got your program to run -

/stack:0x989680,0x989680

However, you may want to look at an iterative approach rather than a recursive one if your function is being called alot as it will use alot less memory.

Thanx, I hope this would work.

One more thing: how about the memory? How much memory I can allocate with "new" and how much memory I can allocate with "alloc"? I mean from a single application of course. Is it really just one segment?

No. In 32 bit environment you can have somewhere around 2GB (teoretically 4GB) of memory. I don't know if there is limit for a single allocation, but I can assure you, that you won't need that much. I think 100MB allocation works fine.

Will it work better if I always allocate memory for new variables using "alloc" instead of "new"? Somebody told me so. For example in my prime-number program.

No, your problems in your prime number program are not due to the way you're allocating memory on the heap.

Everytime you call a function it gets pushed onto the stack(the parameters and the instruction address) and will not be popped until it has returned. When you call a function recursively none of the functions return until the condition is reached that prevents the function from being called. Therefore if you call a function a few thousand times recursively, you'll have a few thousand functions in the space the linker has allocated for the stack. If there is insufficient space you'll get a runtime error.

Even if you allocated no memory in your function you'd still get the error.

Oh, my English must be very bad. Sorry for it. Zen, I already understood this recursion/memory problem. I even knew about it before posting this thread - but I forgot it when writing my program I was just interesting in the difference between allocating in Console and in Win32. Thanx anyway...

OK, I doubt there will be much difference as I believe they both probably use malloc under the surface. The thing you have to watch out for is that if you are creating instances of classes dynamically then you should use new/delete or your constructors and destructors will not be called.