8 Replies - 578 Views - Last Post: 23 February 2015 - 05:08 AM Rate Topic: -----

#1 Bawnawgwa  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 153
  • Joined: 21-January 13

Freeing allocated memory in doubly linked list in C.

Posted 21 February 2015 - 09:29 PM

I am having issues freeing memory that I allocated when adding a node to a doubly linked list. I have tried adding free() at the end of the remove function from the list with no luck. I have tried using all sorts of temporary nodes and dummy nodes to free without losing node information. Have tried storing current node, moving to next one, then freeing the old current one, without luck. Everytime I try to free a node it destroys the list. It loses important node information and can no longer operate properly and I am met with all sorts of memory crashes. I will post my add and delete nodes functions here:

/**
* Adds a  node to a given list
*
* @param q pointer a a list
* @param node pointer to the node to be added
*/
void list_add(list *q, path *node){
        path *pn;
	if(!(pn = (path*)malloc(sizeof(*pn)))){
		perror("malloc");
		exit(1);
	}
	
	pn->pos[0] = node->pos[0];
	pn->pos[1] = node->pos[1];
	pn->f = node->f;
	pn->g = node->g;
	pn->h = node->h;
	pn->parent = node->parent;
	//pn = node;
	if(q->size == 0){
		q->head = q->tail = pn;
	}
	else{
	        pn->prev = q->tail;
		q->tail->next = pn;
		q->tail = pn;
	}
	q->size++;
}

/**
* removes a node from list
*
* @param q pointer to a list
* @param node pointer to a node in list
*
* @return 0 if successful, else -1
*/
int list_remove(list *q, path *node){
	path *tmp;
	
	if(q->size == 0){
		return -1;
	}
	
	q->size--;
	tmp = q->head;
	
	if(q->head != node && q->tail != node){
		while(tmp != node){
			tmp = tmp->next;
		}
		
		tmp->prev->next = tmp->next;
		tmp->next->prev = tmp->prev;
	}
	else if(q->size == 0){
		q->head = q->tail = NULL;
	}
	else if(node == q->head){
		q->head = q->head->next;
	}
	else if(node == q->tail){
		q->tail = q->tail->prev;
	}

	//free(tmp);
	return 0;
}



And this is the function that uses them:
/**
* Uses A* algorithm to find shortest path from starting point to end point
*
* @param startx starting x-coordinate
* @param starty starting y-coordinate
* @param endx ending x-coordinate
* @param endy ending y-coordinate
*/
void find_path(int startx, int starty, int endx, int endy){
	//initialize lists
	closed_list = list_init(closed_list);
	open_list = list_init(open_list);
	neighbors = list_init(neighbors);
	//allocate memory for neighbor nodes
	init_memory();
	
	int g_score, f_score;
	int best_gscore;
	path *current_node, *neighbor;
	//allocate memory for local nodes
	if(!(current_node = (path*)malloc(sizeof(*current_node)))){
		perror("malloc");
		exit(1);
	}
	if(!(neighbor = (path*)malloc(sizeof(*neighbor)))){
		perror("malloc");
		exit(1);
	}
	//setup starting node
	current_node->pos[0] = startx;
	current_node->pos[1] = starty;
	current_node->g = 0;
	current_node->h = heuristic_cost(startx, starty, endx, endy);
	current_node->f = 0;
	//add starting node to open list
	list_add(open_list, current_node);
	g_score = 0;
	int i = 0;
	f_score = g_score + heuristic_cost(startx, starty, endx, endy);
	//Search for shortest path by checking cells and their neighbors
	while(open_list->size != 0){
		//current node = node with lowest f value (g + heuristic) that is in the open list
		current_node = lowest_f_node(open_list);
		if(current_node->pos[0] == endx && current_node->pos[1] == endy){
			build_path(current_node, startx, starty);
			break;
		}
		//remove current node from open list
		list_remove(open_list, current_node);
		//add current_node to closed_list
		list_add(closed_list, current_node);
		//Add neighbors of current node to neihbor_nodes list (only 4 neighbors maximum per node)
		neighbor_nodes(current_node, endx, endy);
		//Set node neighbor to beginning of neighbor list
		neighbor = neighbors->head;
		//looks at left, right, upper, and lower neighbor to a cell
		for(i = 0; i < neighbors->size; i++){
			//If node is in closed list (already visited), ignore and move to next neighbor
			if(in_closedlist(closed_list, neighbor)){
				neighbor = neighbor->next;
				continue;
			}

			g_score = current_node->g + 10;
			best_gscore = 0;
			//If not in open list, node hasn't been visited
			if(!in_openlist(open_list, neighbor)){
				//Has not been visited, so its gscore is "the best" for now
				best_gscore = 1;
				//calculate heuristic
				neighbor->h = heuristic_cost(neighbor->pos[0], neighbor->pos[1], endx, endy);
				
			}
			//Else, if it has been visited (not in open list) but its gscore is better on the current path than previously,
			//set best_gscore to 1 to update the nodes values
			else if(g_score < neighbor->g){
				best_gscore = 1;
			}
			//Update nodes values if best_gscore = 1
			if(best_gscore){
				neighbor->parent = current_node;
				neighbor->g = g_score;
				neighbor->f = neighbor->g + neighbor->h;
				//After node has been updated, if it was not in open list, add it to the open list, otherwise continue
				if(!in_openlist(open_list, neighbor))
					list_add(open_list, neighbor);
			}
			neighbor = neighbor->next;
		}
		clear_neighbors(neighbors);
	}
	//free_list(open_list);
	//free_list(closed_list);
	free(open_list);
	free(closed_list);
	free(neighbors);
	free(neighbor_l);
	free(neighbor_r);
	free(neighbor_u);
	free(neighbor_d);

}



Those free's at the end are to get rid of nodes I malloced in find_path. This find_path works really well when run once lol. It finds shortest path and prints it no problem, but doing it over and over again will be problematic as it is leaking almost every bit of memory it uses ://>.

So in short, can anyone help me figure out how to free an allocated node when I remove it from a list while still being able to use it? I have tried moving the remove function to different locations like the end of the file and still no luck. I even tried allocating a new current_node each iteration of while loop, using it, then freeing it at the end of the while loop and took out the allocation in the list_add() function. This didn't work either :(/>. I am completely out of ideas on how to stop the leakage. Any help would be greatly appreciated :)/>.

Is This A Good Question/Topic? 0
  • +

Replies To: Freeing allocated memory in doubly linked list in C.

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

Re: Freeing allocated memory in doubly linked list in C.

Posted 21 February 2015 - 09:49 PM

You should simply be calling free_list() to deallocate all the things you allocated within your list. Show us your implementation of free_list().

As an aside, why are you using global variables?
Was This Post Helpful? 0
  • +
  • -

#3 Bawnawgwa  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 153
  • Joined: 21-January 13

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 12:23 AM

Eh, free list works, but doesn't save all the memory that was allocated. All it does is start at head of list, loop through till NULL, at each node, store it in temp node, move to next, free temp, repeat. Here it s:
void free_list(list *q){
	path *pn, *tmp;
	pn = q->head;
	while(pn != NULL){
		tmp = pn;
		pn = pn->next;
		free(tmp);
	}
}



But the issue is when I remove a node without freeing when it is removed, it just floats in space, it is not part of the list because when I remove current_node from open list then add it to current list, the add allocates new memory for a new node, and the one "removed" from open list was just disconnected and never freed and can't be reached and just floats around. But I haven't found a successful way to free the node in this algorithm.

Oh, and globals because I know what they will be used for and it kept the parameter list to functions needing them short. Yeah I know, not ideal...

This post has been edited by Bawnawgwa: 22 February 2015 - 12:31 AM

Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 10:17 AM

Whoever call list_remove() is responsible for the memory of the node that got removed.

One of the sources of your leak is that you are not taking responsibility for it here:
//remove current node from open list
list_remove(open_list, current_node);
//add current_node to closed_list
list_add(closed_list, current_node);



Remember that your list_add() allocates a new node? So where are you freeing current_node within the loop?

Another source of your leak is before you go into the the loop. You allocate current_node and then call list_add(). As noted above, that function goes and does another allocation. Later when you enter the load and do this:
current_node = lowest_f_node(open_list);


You lose track of the first allocation you made.

You have do decide how your list acts. Either it allocates/deallocates its own space, or callers have the responsibility to allocate/deallocate space.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,606
  • Joined: 16-October 07

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 01:09 PM

You're allocating all over the place. Why, in list add, do you allocate a new node for to copy the data just passed?

Perhaps your path data shouldn't be combined with the node implementation? At the very least, you'd have an easier time with a function like create_path and maybe even load_path. Think about your list_add taking data, rather than a node. Basically, don't get hung up on your C collection implementation: get that bit to work and get it out of the way.

The globals will ONLY cause pain and suffering. Gather up your global floating data and put in a struct, if need be.
Was This Post Helpful? 1
  • +
  • -

#6 Bawnawgwa  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 153
  • Joined: 21-January 13

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 01:41 PM

Hmm I think I solved some of the problem by freeing current_node at the end of the loop. The program still seemed to work alright. But I still have some leaks with neighbor_nodes and lowest_f_node because I am currently mallocing a node in lowest_f_node so I can store all the values of the lowest node in a list and return it.

Is there a way I can copy all the elements of a node into another, but not the address of the node (which node1 = node2 does and modifying node1 would change node2), without mallocing new space?

And those mallocs all over the place are because I need to do something with the data in a node, but nothing but seg faults without the malloced space.

This post has been edited by Bawnawgwa: 22 February 2015 - 01:45 PM

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,606
  • Joined: 16-October 07

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 03:30 PM

View PostBawnawgwa, on 22 February 2015 - 04:41 PM, said:

Is there a way I can copy all the elements of a node into another, but not the address of the node (which node1 = node2 does and modifying node1 would change node2), without mallocing new space?


The is fundamentally what I was talking about. If the data of your node is in a separate struct, it's much easier to copy it around.

Here's some sample code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct {
    int x, y;
} Point;

typedef struct Node_s {
    Point point;
    struct Node_s *next;
} Node;

typedef struct {
    Node *head, *tail;
} List;

List *createList();
void addList(List *, Point *);
void addListData(List *, int x, int y);
void showPoint(Point *);
void showList(List *);
void freeList(List *);

int main() {
    List *xs = createList();
    showList(xs);
    addListData(xs, 1,2);
    addListData(xs, 2,3);
    showList(xs);
    addListData(xs, 4,5);
    addListData(xs, 5,6);
    showList(xs);
    freeList(xs);

    return 0;
}

/* helper */
void *mallocOrDie(size_t n) {
    void *p = malloc(n);
    if(!p) { perror("malloc"); exit(1); }
    return p;
}

List *createList() {
    List *p = mallocOrDie(sizeof(List));
    p->head = p->tail = NULL;
    return p;
}

void addList(List *xs, Point *pt) {
    Node *node = mallocOrDie(sizeof(Node));
    node->point = *pt;
    node->next = NULL;
    if(!xs->tail){
        xs->head = xs->tail = node;
    } else {
        xs->tail->next = node;
        xs->tail = xs->tail->next;
    }
}

void addListData(List *xs, int x, int y) {
    Point pt = { x, y };
    addList(xs, &pt);
}

void showPoint(Point *pt) { printf("(%d, %d)", pt->x, pt->y); }

void showList(List *xs) {
    Node *p = xs->head;
    while(p) { showPoint(&(p->point)); p = p->next; }
    printf("\n");
}

void freeList(List *xs) {
    Node *p = xs->head;
    while(p) {
        Node *die = p;
        p = p->next;
        free(die);
    }
    free(xs);
}



See how the payload is Point? How you can pass Point * around and copy it into a node with a single statement?

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#8 Bawnawgwa  Icon User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 153
  • Joined: 21-January 13

Re: Freeing allocated memory in doubly linked list in C.

Posted 22 February 2015 - 06:17 PM

Hmm alright, I set up my data in a separate struct, this has the bonus of making nodes a lot nicer to look at while debugging. However, the big issue I am having right now is setting up a parent.

Where I set neighbor->parent = current_node is the basis of the A* algorithm, however, I remove current_node from open_list each loop, thus it must be freed, but freeing it destroys neighbors parent.

I have done some modifications and completely got rid of all my random mallocs and ONLy have malloc in the list_add function and it works, BUT no node has a parent because the parent gets destroyed each loop by having a free(current_node) at the end of the while loop. Hmm...

I need some way to copy the x and y coordinates of current_node into a "parent-like" reference of the neighbor node that will hold after current_node is freed. Perhaps all I need is a 'from_x' and 'from_y' variable in the struct array holding the data, in which I place the current x and y of current_node!

Strike that, that still leaves me know way of moving back through nodes that were supposed to be connected through parent.

This post has been edited by Bawnawgwa: 22 February 2015 - 06:21 PM

Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6979
  • View blog
  • Posts: 14,606
  • Joined: 16-October 07

Re: Freeing allocated memory in doubly linked list in C.

Posted 23 February 2015 - 05:08 AM

View PostBawnawgwa, on 22 February 2015 - 09:17 PM, said:

Where I set neighbor->parent = current_node is the basis of the A* algorithm, however, I remove current_node from open_list each loop, thus it must be freed, but freeing it destroys neighbors parent.


Don't confuse data with the collection it's stored in. You are free to build lists with copies of data. For instance, moving a node from the open set to the closed set is essentially a copy to the closed set and then a removal from the open set.

C is a PITA for memory management, because it makes you do ALL of it. You MUST abstract how your collection object works or you'll get so bogged down in the details and confuse the hell out of yourself. You linked list stores data; it allows you to add, access, and remove it. That's it. Don't worry any more than that and forget pointers entirely when working with A* graph nodes; they're different beasties.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1