Can a data structure implementation know if it is/isn't on the heap?

Question

Consider a main file, and another file that implements a data structure (say: linked list).

The caller of the linked list can either put objects on the linked list on the stack or on the heap, and I assume that is the responsibility of the caller.

So when implementing the linked list, how does it know whether or not it's on the heap? Consider a typical "method" that removes an node from the list. How does the linked list know whether or not it ought to free that memory? From my understanding, freeing something on the stack causes undefined behavior.

Because this is part of a class project, I'm unable to pass something (isOnHeap) to indicate whether or not the caller has put the memory on the heap (clarification: unable as in our implementation does not allow this), so I'm assuming there may be a common solution to this problem, especially considering how common a case it'd be. Note that the linked list implementation must handle freeing of its own memory (assumed this is given since its implementation is hidden from the caller).

Answer 1

A data structure implementation in C should not free anything unless it was explicitly told to do so. A typical linked-list implementation might have functions like "create node", "insert node into list here", "remove node from list", and "destroy node." None of those require checking for stack vs. heap. Typically the only thing that could be on the stack would be the head & tail pointers for the overall list; even that you may as well allocate and free by API functions you design (and use the heap).

If you really want to be able to build an intrusive linked list where the nodes can be kept on the stack, we could talk about that too, but given the background you've posted I doubt this is the case.

Anyway, there's no portable solution to know if something is on the stack or the heap, but there are some platform-specific tricks you can see here: How to know if a pointer points to the heap or the stack? - note that for a class assignment it is extremely unlikely that you should need any of this.

Answer 2

... I'm unable to pass something (isOnHeap) to indicate whether or not the caller has put the memory on the heap

This crops up on occasion but not really in this context. The problem usually shows it head due to different versions of the runtime library. The issue is a library allocates a block that the caller has to free.

An example of the issue can be seen in Windows Net API functions. For example, suppose you call NetGroupEnum function to enumerate groups. The library would allocate the GROUP_INFO_* structure. After the caller is done with the structure, its the caller's responsibility to call the library's NetApiBufferFree function.

In this case, the project needs to provide the allocator and deleter functions. Then your routines simply allocate with the routines provided by someone else; and then deletes with the routines when the object is no longer needed.

And to address the original question, it usually is possible to tease out where the allocation was made. But stack versus heap usually does not matter.

Answer 3

Normally the linked list nodes are created dynamically and will be allocated in the heap. However, if you choose to put a node already on the stack to the list, you will violate this assumption. I assume you are asking this situation.

Then, depends on the implementation of the library, free may do nothing but just register that memory to be available if it's in the heap. And if the memory happens to be in the stack, it could choose to do anything. Or it could give an error and exit. But it is undefined.

Answer 4

Here is simple is_on_stack(addr) function :

int *stack_start = nullptr;

bool is_on_stack(void* ptr) {
  int stack_probe;  
  if( stack_start < &stack_probe  )
    return stack_start < ptr && ptr < &stack_probe; // stack grows upwards;
  else 
    return &stack_probe < ptr && ptr < stack_start; // stack grows downwards;
}

int main() {
  int stack_probe = 0;
  stack_start = &stack_probe;

  int dummy;

  bool r1 = is_on_stack(&dummy); // shall be true

  int* heap_thing = (int*)malloc(sizeof(int));

  bool r2 = is_on_stack(heap_thing); // shall be false         
}

Key point here is these lines at the beginning of main() function:

  int stack_probe = 0;
  stack_start = &stack_probe;