doubly linked list with double pointer problems

This is a discussion on doubly linked list with double pointer problems within the C Programming forums, part of the General Programming Boards category; Im trying to come up with a doubly linked list for a mini job system. Right now, I cant seem ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    57

    doubly linked list with double pointer problems

    Im trying to come up with a doubly linked list for a mini job system.

    Right now, I cant seem to remove any nodes and my final empty call gives me a double free error during runtime. Im guessing its in the double pointer magic now but Im pretty confused.

    Anyone mind taking a look?
    Thanks

    Code:
    void init_job_node(struct job_node *job) {
    	/* Data */
    	job->childPid = 0;
    	job->status = 0;
    	job->cmd = NULL;
    	
    	/* Locations */
    	job->next = NULL;
    	job->prev = NULL;
    }
    
    int create_job_node(struct job_node **job) {
    	/* Create */
    	*job = (struct job_node *)malloc(sizeof(struct job_node));
    	if(!*job)
    		return 1;
    	
    	/* Setup */
    	init_job_node(*job);
    	return 0;
    }
    
    void free_job_node(struct job_node **job) {
    	/* Data */
    	free((*job)->cmd);
    	
    	/* Locations */
    	free(*job);
    	*job = NULL;
    }
    
    void empty_job_nodes(struct job_node **job_list) {
    	/* Base/Error Cases */
    	if(*job_list == NULL)
    		return;
    	
    	/* Recurse! */
    	empty_job_nodes(&(*job_list)->next);
    	
    	/* Step */
    	free_job_node(&(*job_list));
    }
    
    void print_job_nodes(struct job_node *job_list) {
    	/* Base/error cases */
    	if(job_list == NULL)
    		return;
    	
    	/* Step */
    	printf("%i\t%s\n", job_list->childPid, job_list->cmd);
    	
    	/* Recurse */
    	print_job_nodes(job_list->next);
    }
    
    void append_node(struct job_node **job_list, struct job_node *job) {
    	/* Base cases */
    	if(*job_list == NULL) {
    		*job_list = job;
    		return;
    	}
    	
    	if((*job_list)->next == NULL) {
    		(*job_list)->next = job;
    		job->next = NULL;
    		job->prev = (*job_list)->prev;
    		return;
    	}
    	
    	/* Recurse */
    	append_node(&((*job_list)->next), job);
    }
    
    void remove_node(struct job_node **job) {
    	if(*job == NULL)
    		return;
    	
    	if((*job)->prev != NULL)
                    (*job)->prev->next = (*job)->next;
            if((*job)->next != NULL)
                    (*job)->next->prev = (*job)->prev;
    	
    	free_job_node(job);
    	*job = NULL;
    }
    
    int main() {
    	int i;
    	struct job_node *head;
    	struct job_node *tmp;
    	
    	create_job_node(&head);
    	for(i = 1; i < 10; ++i) {
    		create_job_node(&tmp);
    		tmp->childPid = i;
    		append_node(&head, tmp);
    	}
    	
    	printf("first:\n");
    	print_job_nodes(head);
    	printf("\n");
    	
    	remove_node(&tmp);
    	printf("after:\n");
    	print_job_nodes(head);
    	printf("\n");
    	
    	empty_job_nodes(&head);
    	printf("empty:\n");
    	print_job_nodes(head);
    	
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Code:
    void append_node(struct job_node **job_list, struct job_node *job) {
            //...
    	if((*job_list)->next == NULL) {
    		(*job_list)->next = job;
    		job->next = NULL;
    		job->prev = (*job_list)->prev;
    		return;
    	}
            //...
    }
    See anything funny?

    You might want to iterate instead of recurse. Recursion uses up stack space, iteration doesn't.

    http://faq.cprogramming.com/cgi-bin/...&id=1043284351

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    57
    Ok, that helped. Totally missed that.

    I still cant remove the head node and still get a double free error.

    Anything else look odd?
    Thanks

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Do you have the struct declaration handy? I can't compile it.

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    57
    yup, sorry about that

    Code:
    struct job_node {
    	/* Data */
    	pid_t childPid;
    	int status;
    	char *cmd;
    	
    	/* Locations */
    	struct job_node *next;
    	struct job_node *prev;
    };
    Thanks for all the quick replies

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    I just realized I've been working with a known buggy copy. What is the latest code?

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    I believe you're wiping out the head without replacing it when you call remove_node(&head), thus causing all your grief.

    Code:
    void remove_node(struct job_node **job) {
    	if(*job == NULL)  // head isn't NULL, ok so far
    		return;
    	
    	if((*job)->prev != NULL)  // head->prev should be NULL, still ok
                    (*job)->prev->next = (*job)->next;
            if((*job)->next != NULL)  // head->next != NULL, so lets do this
                    (*job)->next->prev = (*job)->prev;  // next->prev is set to NULL (since head doesn't have a prev)
    	
    	free_job_node(job);  // head gets freed
    	*job = NULL;  // wuh oh... head never got replaced
    }
    Ok the following code works for me (using his original code and all fixes mentioned earlier) and correctly removes the head from the list. Can anyone confirm?

    Code:
    void remove_node(struct job_node **job) {
      if(*job == NULL)
        return;
    
      if((*job)->next != NULL)
        (*job)->next->prev = (*job)->prev;
      if((*job)->prev != NULL)
        (*job)->prev->next = (*job)->next;
      else { // if this node doesn't have a prev, then it must be the head!
        struct job_node *tmp = (*job)->next;
        free_job_node(job);
        *job = tmp;
        return;
      }
    
      free_job_node(job);
      *job = NULL;
    }
    Oh btw, I also typedef'd pid_t to int (I didn't see it defined anywhere)
    Last edited by arpsmack; 01-31-2008 at 10:46 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Copying 2-d arrays
    By Holtzy in forum C++ Programming
    Replies: 11
    Last Post: 03-14-2008, 03:44 PM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  4. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 08:13 AM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21