/** * 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 />.