doubly linked list with double pointer problems

[zxcv]

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

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;
}

[robwhit]

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

[zxcv]

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

[robwhit]

Do you have the struct declaration handy? I can't compile it.

[zxcv]

yup, sorry about that

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

[robwhit]

I just realized I've been working with a known buggy copy. What is the latest code?

[arpsmack]

I believe you're wiping out the head without replacing it when you call remove_node(&head), thus causing all your grief.

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?

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)