Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
1

I need a simple singly-linked list to help implement some memory management functionality. I just finished writing it up and would really like a code review since I haven't written this particular data structure in a long time.

struct pid_node {

  int PID;
  struct pid_node* next; 

};

 struct pid_node* pid_node_create(int PID) {
   struct pid_node* new;
   new = kmalloc(sizeof(struct pid_node));
   if (new == NULL) return NULL;
   new->PID = PID;
   new->next = NULL;
   return new; 
 }

 void add_pid_node(struct pid_node* head, struct pid_node* new) {
   struct pid_node* temp;
   temp = head;
   while(temp->next != NULL) temp = temp->next; 
   temp->next = new; 
 }

 void remove_pid_node(struct pid_node* head, struct pid_node* dead) {
   struct pid_node* temp, other_part_of_list, delete_node;
   temp = head;
   while(temp->next != NULL) {
     if (temp->next == dead) {
       delete_node = temp->next;
       other_part_of_list = temp->next->next;
       temp->next = other_part_of_list;
       kfree(delete_node); //don't leak memory
       return; 
     }
     temp = temp->next; 
   }
   kprintf("Got to end of PID list, didn't remove 'dead'!\n");
 }

 //returns true or false (1 or 0) if a particular PID is within my list
 int query_pid(int PID, struct pid_node* head) {
   struct pid_node* temp;
   temp = head;
   while(temp->next != NULL) {
     if (temp->PID == PID) return 1;
     temp = temp->next;
   }
   return 0; //didn't find it
  }

EDIT - I want to implement a small addition to the end of "remove", in case what I want to remove is the head of this list. Here's what I'm thinking:

if (head == dead) {
     temp = head;
     *head = &(head->next); 
     kfree(temp);
     return; 
   }

////

It doesn't have to be super fancy or anything, just has to properly carry out the four functions.

Thanks a bunch!

share|improve this question
1  
Since you're using kmalloc, why don't you use klist? – Quentin Pradet Apr 9 '12 at 22:05
1  
It is best to make the code compile before submitting it for review (other_part_of_list, delete_node should be pointers). – William Morris Apr 9 '12 at 22:17
Oh shoot, I meant for them to be pid_node* variables by listing them like that (e.g. int x, y, z). Does that not work for pointers? – YoungMoney Apr 9 '12 at 22:20
EDITED - added another snippet of code I'm pretty is wrong that I want to implement. – YoungMoney Apr 10 '12 at 0:19
@YoungMoney See my edit. – Matt Eckert Apr 10 '12 at 0:49
show 1 more comment

2 Answers

up vote 4 down vote

A couple of conceptual errors:

Pass by value

You can remove the temporary copy of head in your functions. In C, all arguments are passed by value. This means you can operate directly on the head parameter exposed to your function without worrying about the argument in the calling code. Although both point to the same location, each is a different pointer variable with its own address.

Pointer declarations

struct pid_node* temp, other_part_of_list, delete_node;

Remember that the * is not part of the type, but part of the declarator. A clearer way to write declarations involving pointers is to move the * directly in front of the identifier. This follows the C convention that "declaration mimics use." So, the line changes to

struct pid_node *temp, other_part_of_list, delete_node;

Now the error (and fix) is obvious. If there is no * before a variable, its a variable of the type instead of a pointer to the type.

struct pid_node *temp, *other_part_of_list, *delete_node;

Edit: remove head special case

In order to modify the head argument itself, which is a pointer-to-struct, you need to pass a pointer-to-pointer-to-struct or return the new head. For example (pointer-to-pointer-to-struct):

void remove_pid_node(struct pid_node **head, struct pid_node *dead) {
...
    if (*head == dead) {
         temp = *head;
         *head = temp->next; 
         kfree(temp);
         return; 
    }

Then you would call the code like this:

remove_pid_node(&head, head);

Note: don't forget to check for NULL arguments.

share|improve this answer
Thanks for the feedback. About the pass-by-value: I understand what you're saying. but there's nothing wrong with what I'm doing right? – YoungMoney Apr 9 '12 at 23:17
Depends on what you mean by wrong. Technically you can add as many extra variables you want to any function, but it decreases readability. – Matt Eckert Apr 9 '12 at 23:22
Ah, I just mean functionality-wise. It should work, yes? – YoungMoney Apr 9 '12 at 23:44
Yes, of course. – Matt Eckert Apr 9 '12 at 23:46
1  
Regarding operating directly on head, using a temp is quite ok. The compiler will optimise this away anyway. Note that if you use head directly, your code becomes untruthful; variable head will point in sequence to all the members of the list and only at the start truly points to what its name says it points to. This could be considered wrong. Calling it something other than head would cure this. I have worked at places where they would code this function parameter const struct pid_node * const head, (extra const) which prevents such modification, but that is just silly. – William Morris Apr 10 '12 at 0:57
show 6 more comments
up vote 2 down vote

General:

  • Algorithm looks good.

  • Functions normally start with the brace on column 0.

  • Add a typedef so that you can refer to just pid_node *, not struct pid_node *, throughout (except in the struct declaration).

    typedef struct pid_node pid_node;

  • I usually prefer to assign an initial value to variables where they are declared (but that is just a personal preference):

     pid_node* temp = head;
 ...

  • variables are not normally capitalized (PID)

add_pid_node:

  • what if head == NULL ?

remove_pid_node

  • best to put each variable definition on its own line.

  • other_part_of_list and delete_node should be pointers.

  • what if head == NULL ?

  • other_part_of_list is not necessary:

    temp->next = temp->next->next;

query_pid:

  • other functions have head first in parameter list, but here not. Inconsistent.

  • what if head == NULL ?

  • head and temp should be const

share|improve this answer
Wow that was great! I will definitely do some revisions based on your comments. Thanks a bunch. EDIT - I guess in my head I was implicitly thinking that I would only ever call these functions when I know head is not NULL, but that's definitely not reliable/good practice. – YoungMoney Apr 9 '12 at 22:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.