New set of eyes.

[tmfletcher]

I apologize for this ahead of time, but have been staring at this for hours trying to find the problem.

When I run release_memory and send the job number, it should delete the ALLOCPTR node, and then create a FREEPTR node and insert in the FREEPTR linked list.

It works on a single basis, but if you do more than one, it breaks.

All attempts I have made to fix it end in Segmentation faults or endless loops.

This is a homework assignment, and I am NOT asking anyone to do the work for me, just a pointer in the right direction would be insanely helpful.

This is a pass/fail for the class for me.

Thanks in advance for your help.

#include <iostream>

using namespace std;

// GLOBAL DATA STRUCTURES
typedef struct FREE_NODE * FREEPTR;
typedef struct ALLOCNODE * ALLOCPTR;

struct FREE_NODE 
{
  int start_byte;
  int end_byte;
  int size;
  
  FREEPTR next;
};
struct ALLOCNODE
{
  int start_byte;
  int end_byte;
  int size;
  int id;
  
  ALLOCPTR next;
};
// ======   GLOBAL DATA ======
FREEPTR  freelist = NULL;  
ALLOCPTR alloclist = NULL; 
int total_memory_managed = 0; 

//======   PROTOTYPES =======
void dump_freelist(void);
void dump_alloclist(void);
void init_memory_manager(const int amount);
int allocate_memory(const int job, const int amount);
void release_memory(const int job);
int total_free(void);
int total_allocated(void);
int largest_free(void);

//======= TESTING ONLY FUNCTIONS =========
void dump_freelist(void)
{ FREEPTR tmp = freelist; 
  cout << "==================" << endl;
  cout << "  FREE LIST DUMP  " << endl;
  cout << "==================" << endl;
  while (tmp !=NULL)
  {
    cout << tmp->start_byte << " : ";
	cout << tmp->end_byte << " : ";
	cout << tmp->size << endl;
	tmp = tmp->next; 
  }
}
//----------------------
void dump_alloclist(void)
{ ALLOCPTR tmp = alloclist; 
  cout << "=======================" << endl;
  cout << "  ALLOCATED LIST DUMP  " << endl;
  cout << "=======================" << endl;
  while (tmp !=NULL)
  {
    cout << tmp->start_byte << " : ";
	cout << tmp->end_byte << " : ";
	cout << tmp->size << " : ";
	cout << tmp->id << endl;
	tmp = tmp->next; )
  }
}


void init_memory_manager(const int amount)
{
  total_memory_managed = amount;
  // set up the freelist linked list
  freelist = new FREE_NODE;
  freelist -> size = amount;
  freelist -> start_byte = 0;
  freelist -> end_byte = amount - 1;
  freelist -> next = NULL;
  // set up the alloclist linked list
  alloclist = NULL;
}
//----------
int allocate_memory(const int job, const int amount)
{
	FREEPTR tmpF = freelist;
	ALLOCPTR tmpA = alloclist;
	ALLOCPTR tmpAPP = alloclist;
	
	if (amount <= 0 || amount > total_memory_managed || amount > largest_free())  
	{
		return 0;												
	}
	else
	{
		while (tmpF != NULL)
		{
			if (tmpF -> size >= amount)
			{
				tmpF -> size = tmpF -> size - amount;			// Resize the freelist single node.
				tmpF -> end_byte = tmpF -> end_byte - amount;	
				
				tmpA = new ALLOCNODE;							// Create new node for insertion to alloclist.
				tmpA -> size = amount;
				tmpA -> start_byte = tmpF -> end_byte + 1;
				tmpA -> end_byte = (tmpA -> start_byte + amount) - 1;
				tmpA -> id = job;
				
				if (alloclist == NULL)                                 	// If empty list, 
				{
					alloclist = tmpA;									// Set alloclist to point at new node. 
					alloclist -> next = NULL;							// Terminate next for alloclist.
				}
				else
				{	
					if (tmpA -> end_byte < alloclist -> start_byte)		// Put the node in the right place.
					{
						tmpA -> next = alloclist;						// Put tmpA in front of 
						alloclist = tmpA;								// Move alloclist back to the head.
					}
					else												// Handle if tmpA -> end_byte is greater than alloclist -> start_byte.
					{
						tmpAPP = alloclist;
						while (tmpA -> end_byte > tmpAPP -> next -> start_byte) // Find where this needs to be inserted starting after alloclist.
						{		
							tmpAPP = tmpAPP -> next;
						}
						tmpA -> next = tmpAPP -> next;					// When place is found, set NN -> next to next of tmp pointer.
						tmpAPP -> next = tmpA;							// Relink the list.
					}
				}
				break;
			}
			else 
			{
				tmpF = tmpF -> next;									// If not in the right place in linked list, move forward.
			}
		}
				
	}

	return amount;
}
//----------------------
void release_memory(const int job)
{
   ALLOCPTR tmpA = alloclist;
   ALLOCPTR tmpAM = alloclist; 		
   FREEPTR tmpF = freelist;
   FREEPTR tmpFM = freelist;	 	
   
   FREEPTR tmpFNN = new FREE_NODE;  				
   tmpFNN -> next = NULL;

		while (tmpA != NULL) 												// Verify alloclist is not empty or not at end.
		{
			if (tmpA -> id != job) 											// If job is not the one sent, move to next node.
			{
				tmpAM = tmpA;												// Move tmpAM to tmp A after know tmpA != job.
				tmpA = tmpA -> next;    									// Move tmpA ahead one.
			}
			else
			{
				cout << endl << endl << "I'm here" << endl << endl;
				
				tmpFNN -> start_byte = tmpA -> start_byte;					// 
				tmpFNN -> end_byte = tmpA -> end_byte;						//  >Copy information from alloc node, to new free node for insertion to free list.
				tmpFNN -> size = tmpA -> size;								// 
				tmpFNN -> next = NULL;
				
				tmpAM -> next = tmpA ->next;    							// Move the previous next pointer to tmpA's next pointer.
				
				if (tmpA == alloclist)
				{	
					alloclist = tmpA -> next;
					delete tmpA;											// Delete the allocnode.
					tmpA = alloclist;
				}
				else 
				{

					delete tmpA;
					tmpA = alloclist;
				}
				
				
				if (tmpFNN -> start_byte == 0 || freelist == NULL)			// If there is nothing in the freelist OR the startbyte of the insert is 0, make freelist next pointer.
				{	
					tmpFNN -> next = freelist;								// Set tmpFNN -> to whatever freelist is (NULL or first node)
					freelist = tmpFNN;										// Set freelist to tmpFNN as it is now first in the list.
				}
				else
				{
					while (tmpF != NULL)
					{
						if (tmpFNN -> end_byte > tmpF -> start_byte)
						{
							tmpFM = tmpF; 									// Move tmpFM to tmpF
							tmpF = tmpF -> next;							// Advance tmpF for next check.
							
							if (tmpF == NULL)
							{
									tmpFNN -> next = tmpF;
									tmpFM -> next = tmpFNN;
									break;
							}
						}
						else
						{
							tmpFNN -> next = tmpF;
							tmpFM -> next = tmpFNN;
							break;
						}
					};
				}													
			}
		};															
	return;
}
//----------------------
int total_free(void)
{
	FREEPTR tmpF = freelist;

	int total_size = 0;
	
	while (tmpF != NULL)
	{
		if (tmpF -> size == 0)             // if nothing stored in total size (first pass) set total size to size of first node.
		{	
			total_size = tmpF -> size;
			tmpF = tmpF -> next;
		}
		else
		{
			total_size = total_size + tmpF -> size;
			tmpF = tmpF -> next;
		}
	};
  
  return total_size; // return amount of free memory
}
//-----------------------
int total_allocated(void)
{
	ALLOCPTR tmpA = alloclist;
	
	int total_size = 0;
	
	while (tmpA != NULL)
	{
		if (tmpA -> size == 0)             // if nothing stored in total size (first pass) set total size to size of first node.
		{	
			total_size = tmpA -> size;
			tmpA = tmpA -> next;
		}
		else
		{
			total_size = total_size + tmpA -> size;
			tmpA = tmpA -> next;
		}
	};
  
  return total_size; // return amount of free memory
};
//----------------------
int largest_free(void)
{
  FREEPTR tmplf = freelist;
  
  int l_f = 0;
  
  while (tmplf != NULL)
  {
	l_f = tmplf -> size;
	tmplf = tmplf -> next;
  }
    
  return l_f;
}


int main(void)
{
	char ch ;  // used to pause between tests
	int r;     // results of allocate_memory

	cout << "ENTER A CHARACTER ";
	cin >>ch;
	cout << endl;
    
	init_memory_manager(200);
	  
	r = allocate_memory(1,10);  
	cout << "allocate_memory returns : " << r << endl << endl;  
	r = allocate_memory(1,40);  
	cout << "allocate_memory returns : " << r << endl << endl;   
	r = allocate_memory(1,30);   cout << "allocate_memory returns : " << r << endl << endl; 

	dump_freelist();
	cout << endl << endl;
	dump_alloclist();
	cout << endl << endl;
	release_memory(1);
}

[Duthomhas]

I'm continuing on the assumption that you are trying to write a heap manager?

Are you supposed to be just pretending to get the memory with your linked lists?

The best way to continue is to get out a piece of paper and a pencil with a good eraser and start drawing what is going on. Especially when you add and delete and split nodes in your lists.

Use of ALL CAPS for your structure types is jarring, also.

[edit] Oh, almost forgot: you have an extra ) in dump_alloclist().

Hope this helps.

[tmfletcher]

Unfortunately, that is what I have been doing all day is drawing it out, and rewriting it.

The problem lies on the reinsert back into the freelist (the tmpFNN), the freelist is only holding the last removed item, not the previous two.

Anyone have any other suggestions?

PS. Thank you Duoas. And yes, that is ultimately what the program is.

The problem has to be here:

if (tmpFNN -> start_byte == 0 || freelist == NULL)
{	
	tmpFNN -> next = freelist;
	freelist = tmpFNN;
}
else
{
	while (tmpF != NULL)
	{
		if (tmpFNN -> end_byte > tmpF -> start_byte)
		{
			tmpFM = tmpF;
			tmpF = tmpF -> next;
			
			if (tmpF == NULL)
			{
					tmpFNN -> next = tmpF;
					tmpFM -> next = tmpFNN;
					break;
			}
		}
		else
		{
			tmpFNN -> next = tmpF;
			tmpFM -> next = tmpFNN;
			break;
		}
	};
}