Thread: Linked Lists programming help required, output is being blocked by some code :(

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    10

    Linked Lists programming help required, output is being blocked by some code :(

    Basically, im creating a linked list, i am trying to include a traverse function to allow me to add nodes to after a certain point
    ("void insertIn(PCB_Ptr current): insert a new PCB (current) node before the first node whose CPU burst time is greater or equal to the CPU burst time of current")


    I feel that i am so close to getting this achieved, however i have just encountered an issue,
    Basically all the code compiles, However since adding my code of:
    "
    Code:
    void insertIn (PCB_Ptr CPU_Burst) {
     
      PCB_NodePtr newNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
      
      /* case 1 empty list */
      if (head == NULL)
      {
        head = newNode;
        
      }
      else
      {
        PCB_NodePtr currNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
         PCB_NodePtr trailNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
      
        currNode = head;
        trailNode = NULL;
        
            /*traversal list to find insert location */
        while(currNode !=NULL)
        {
            if(currNode->PCB_Data->CPU_Burst >= newNode->PCB_Data->CPU_Burst)
            {
              
              break;
             
            }
          else
          {
           trailNode = currNode;
           currNode = currNode->next;
          }
          
          
          
        }
        
              /*Case 2  insert at head (not empty) */
       
      if(currNode == head)
      {
        newNode->next = head;
        head = newNode;
      }
        else
        {
          
           
              /* case 3 insert after head ( not empty */
      
          newNode->next = currNode;
          trailNode->next = newNode;
        
        }
          
      }
     
    }
    "

    The output has started being blocked. e.g. it wont print all the output it want it display.
    I was wondering if anyone could point out why?

    My whole code is
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    
    typedef struct PCB* PCB_Ptr;
    typedef struct PCB_Node* PCB_NodePtr;
    
    
    void insertLast(PCB_Ptr );
    void insertFirst(PCB_Ptr );
    void insertIn(PCB_Ptr);
    
    
    void removeFirst();
    void removeLast();
    void kill(int );
    
    
    void printList( PCB_NodePtr);
    
    
    
    
    struct PCB
    {
     int  PCB_ID;
     int  ArrivalTime;
     int  CPU_Burst;
    };
    
    
    struct PCB_Node
    {
    struct PCB* PCB_Data;
    struct PCB_Node* next;
    };
    
    
    
    
    PCB_NodePtr head,tail;
    
    
    
    
    int main()
    {
    
    
    PCB_Ptr job1,job2,job3,job4,job5,job6,job7;
    
    
    
    
    job1=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job1==NULL)
        {
        printf("\n not enough Memory to create job1....");    
        exit(0);
        };
    
    
    
    
    job2=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job2==NULL)
        {
        printf("\n not enough Memory to create job2....");    
        exit(0);
        };
    
    
    job3=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job3==NULL)
        {
        printf("\n not enough Memory to create job3....");    
        exit(0);
        };
    
    
    
    
    job4=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job4==NULL)
        {
        printf("\n not enough Memory to create job4....");    
        exit(0);
        };
    
    
    
    
    job5=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job5==NULL)
        {
        printf("\n not enough Memory to create job5....");    
        exit(0);
        };
      
    job6=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job6==NULL)
        {
        printf("\n not enough Memory to create job6....");    
        exit(0);
        };
    
    
      job7=(PCB_Ptr)malloc(sizeof(struct PCB));
    if(job7==NULL)
        {
        printf("\n not enough Memory to create job7....");    
        exit(0);
        };
    
    
    /* create 5 PCB structs */
    job1->PCB_ID=1111;job1->ArrivalTime=0;job1->CPU_Burst=0;
    job2->PCB_ID=2222;job2->ArrivalTime=2;job2->CPU_Burst=1;
    job3->PCB_ID=3333;job3->ArrivalTime=3;job3->CPU_Burst=2;
    job4->PCB_ID=4444;job4->ArrivalTime=8;job4->CPU_Burst=3;
    job5->PCB_ID=5555;job5->ArrivalTime=12;job5->CPU_Burst=7;
    job6->PCB_ID=6666;job6->ArrivalTime=15;job6->CPU_Burst=10;
    job7->PCB_ID=7777;job7->ArrivalTime=17;job7->CPU_Burst=4;
    
    
    insertLast(job1);
    insertLast(job2);
    insertLast(job3);
    insertLast(job4);
    insertLast(job5);
    insertLast(job6);
    insertLast(job7);
      
    printf("\t \n the list after 4 structs insertion...");
    printList(head );
    
    
    
    
    
    
    printf("\t  Removing the last node of the list generates :\n");
    removeLast();
    printList(head );
    
    
    
    
    printf("\t  inserting a new head of the list generates :\n");
    insertFirst(job6);
    printList(head );
      
    
    
    printf("\t  Removing the head of the list generates :\n");
    removeFirst();
    printList(head );
    
    
    
    
    
    
    printf("\t \n insert Job 7  :\n");
    insertIn(job7);
    printList(head );
    
    
    
    
    /*
    printf("\t \n kill a process  :\n");
    kill(3);
    printList(head );
    */
    
    
    
    
    return 0;
    }
    
    
    
    
    
    
    /*1-    void insertFirst(PCB_Ptr current):
    insert a new PCB (current) node at the front of the queue*/
    
    
    void insertFirst (PCB_Ptr curr){
      
      
    PCB_NodePtr currNode=(PCB_NodePtr)malloc(sizeof(struct PCB_Node));
        currNode->PCB_Data=curr;
        currNode->next=NULL;
    
    
    
    
    if(head==NULL)
    {
      head=currNode;
      tail=currNode;
    }
    
    
    else
    {
      currNode->next = head;
      head=currNode;
    }
    }
    
    
    
    
    
    
    
    
    /* void removeFirst(): remove the first PCB in the queue*/
    void removeFirst() {
    if (head == NULL)
      return;
      
    
    
      else {
        
       free(head);  /* Deallocates memory from the current head */ 
        
        if (head == tail)  /*checks if the node being removed is the only node*/
        {
        head = NULL;
        tail = NULL;
        }
        else {
       head = head->next; /*turn the new head into the node that was next to the head*/
        }
      }
    }
    
    
    /* insert a node at the end of the queue...*/
    
    
    void insertLast(PCB_Ptr curr) {
    
    
    PCB_NodePtr currNode=(PCB_NodePtr)malloc(sizeof(struct PCB));
        currNode->PCB_Data=curr;
        currNode->next=NULL;
    
    
    if(head==NULL)
      {
       head=currNode;
       tail=currNode;
      } 
    else
      {
       tail->next=currNode;
       tail=currNode;    
       }  
    }
    
    
    
    
    
    
    
    
    void insertIn (PCB_Ptr CPU_Burst) {
     
      PCB_NodePtr newNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
      
      /* case 1 empty list */
      if (head == NULL)
      {
        head = newNode;
        
      }
      else
      {
        PCB_NodePtr currNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
         PCB_NodePtr trailNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(struct PCB));
      
        currNode = head;
        trailNode = NULL;
        
            /*traversal list to find insert location */
        while(currNode !=NULL)
        {
            if(currNode->PCB_Data->CPU_Burst >= newNode->PCB_Data->CPU_Burst)
            {
              
              break;
             
            }
          else
          {
           trailNode = currNode;
           currNode = currNode->next;
          }
          
          
          
        }
        
              /*Case 2  insert at head (not empty) */
       
      if(currNode == head)
      {
        newNode->next = head;
        head = newNode;
      }
        else
        {
          
           
              /* case 3 insert after head ( not empty */
      
          newNode->next = currNode;
          trailNode->next = newNode;
        
        }
          
      }
     
    }
    
    
    /* remove the last node in the queue...*/
    void removeLast() {
    
    
          if (tail == NULL)
    
    
                return;
    
    
          else {
    
    
                free(tail);
    
    
                if (head == tail) {
    
    
                      head = NULL;
    
    
                      tail = NULL;
    
    
                } else {
    
    
                      PCB_NodePtr previousToTail; 
                      previousToTail = head;
    
    
                      while (previousToTail->next != tail)
                            previousToTail = previousToTail->next;
    
    
                      tail = previousToTail;
    
    
                      tail->next = NULL;
                }
          }
      
    }
    
    
    
    
    /* print the queue nodes */
    
    
    void printList( PCB_NodePtr head )  {
         PCB_NodePtr temp = head;
         printf ("Current node list:\n");
         
         if (temp==NULL)
             {
              printf ("\t The List is Empty :(\n");
              return;
             } 
         while (temp != NULL) {
              printf ("\t PCB_ID: %d", temp->PCB_Data->PCB_ID);
              printf ("\t Arrival Time: %d", temp->PCB_Data->ArrivalTime);
              printf ("\t CPU_Burst: %d\n", temp->PCB_Data->CPU_Burst);                
              temp = temp->next;
         }
           printf ("<<<<<<<<<<<<<<<< The End >>>>>>>>>>>>>>>>>>\n\n");      
    }
    I would really appreciate any help,

    from what i know, the only part that is blocking the output being displayed is the part i first posted, "Void insertIn"
    I want to make it clear that I dont want a more efficient or better way to do it, or a revamp on the code i've done, I'm happy with it, it took me a long time to do, and its part of my uni coursework.

    I would jsut appreciate if someone could point and help me understand why the output has stopped being displayed by the first quoted piece of code!
    Much appreciated!
    Fahkinsupah

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > typedef struct PCB* PCB_Ptr;
    > typedef struct PCB_Node* PCB_NodePtr;
    The first thing I would suggest you do is get out of the habit of typedef'ing pointers to things.
    It doesn't save anything, but it does make the code harder to understand from the outset, and it really comes unstuck when you start adding the const/volatile qualifiers to pointers.
    You can typedef the struct if you want, just not the pointer.

    > PCB_NodePtr newNode=(PCB_NodePtr)(PCB_NodePtr)malloc(sizeof(st ruct PCB));
    You shouldn't even be casting the result of malloc once, nevermind casting it TWICE.

    Here is the foolproof way.
    PCB_Node *newNode=malloc(sizeof(*newNode));
    So long as you get the initial type right, the rest follows automatically.

    Both your remove functions are seriously flawed.
    Code:
       free(head);  /* Deallocates memory from the current head */
         
        if (head == tail)  /*checks if the node being removed is the only node*/
        {
        head = NULL;
        tail = NULL;
        }
        else {
       //!! OOPS - too late!
       //!! you already freed head, so doing head->next now is suicidal.
       head = head->next; /*turn the new head into the node that was next to the head*/
    You need to assign the node you want to delete to a temporary pointer, and make sure the list is re-linked properly before deleting the node.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Hmm i will take all this into account and has been very helpful information,
    However it works even with these fault for the purpose of what i need the code to do,
    Deadline is coming up very soon (hours) so the only issue i really need to focus on fixing is the problem of with the insertIn function the output being someone stopped and not displayed half way through the code ( i dont know the correct term for it)
    So in terms of urgency, i very much appreciate the advice, but do you know how i can solve this issue of it not displaying? Do you see anything that is blocking the display from being shown?
    Im not a very experienced programmer at all, so its a little bit difficult for me to see these things

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Here's an example debug session.
    Code:
    $ gdb ./a.out 
    GNU gdb (Ubuntu/Linaro 7.3-0ubuntu2) 7.3-2011.08
    Copyright (C) 2011 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "x86_64-linux-gnu".
    For bug reporting instructions, please see:
    <http://bugs.launchpad.net/gdb-linaro/>...
    Reading symbols from /home/sc/Documents/a.out...done.
    (gdb) run
    Starting program: /home/sc/Documents/a.out 
    	 
     the list after 4 structs insertion...Current node list:
    	 PCB_ID: 1111	 Arrival Time: 0	 CPU_Burst: 0
    	 PCB_ID: 2222	 Arrival Time: 2	 CPU_Burst: 1
    	 PCB_ID: 3333	 Arrival Time: 3	 CPU_Burst: 2
    	 PCB_ID: 4444	 Arrival Time: 8	 CPU_Burst: 3
    	 PCB_ID: 5555	 Arrival Time: 12	 CPU_Burst: 7
    	 PCB_ID: 6666	 Arrival Time: 15	 CPU_Burst: 10
    	 PCB_ID: 7777	 Arrival Time: 17	 CPU_Burst: 4
    <<<<<<<<<<<<<<<< The End >>>>>>>>>>>>>>>>>>
    
    	  Removing the last node of the list generates :
    Current node list:
    	 PCB_ID: 1111	 Arrival Time: 0	 CPU_Burst: 0
    	 PCB_ID: 2222	 Arrival Time: 2	 CPU_Burst: 1
    	 PCB_ID: 3333	 Arrival Time: 3	 CPU_Burst: 2
    	 PCB_ID: 4444	 Arrival Time: 8	 CPU_Burst: 3
    	 PCB_ID: 5555	 Arrival Time: 12	 CPU_Burst: 7
    	 PCB_ID: 6666	 Arrival Time: 15	 CPU_Burst: 10
    <<<<<<<<<<<<<<<< The End >>>>>>>>>>>>>>>>>>
    
    	  inserting a new head of the list generates :
    Current node list:
    	 PCB_ID: 6666	 Arrival Time: 15	 CPU_Burst: 10
    	 PCB_ID: 1111	 Arrival Time: 0	 CPU_Burst: 0
    	 PCB_ID: 2222	 Arrival Time: 2	 CPU_Burst: 1
    	 PCB_ID: 3333	 Arrival Time: 3	 CPU_Burst: 2
    	 PCB_ID: 4444	 Arrival Time: 8	 CPU_Burst: 3
    	 PCB_ID: 5555	 Arrival Time: 12	 CPU_Burst: 7
    	 PCB_ID: 6666	 Arrival Time: 15	 CPU_Burst: 10
    <<<<<<<<<<<<<<<< The End >>>>>>>>>>>>>>>>>>
    
    	  Removing the head of the list generates :
    Current node list:
    	 PCB_ID: 1111	 Arrival Time: 0	 CPU_Burst: 0
    	 PCB_ID: 2222	 Arrival Time: 2	 CPU_Burst: 1
    	 PCB_ID: 3333	 Arrival Time: 3	 CPU_Burst: 2
    	 PCB_ID: 4444	 Arrival Time: 8	 CPU_Burst: 3
    	 PCB_ID: 5555	 Arrival Time: 12	 CPU_Burst: 7
    	 PCB_ID: 6666	 Arrival Time: 15	 CPU_Burst: 10
    <<<<<<<<<<<<<<<< The End >>>>>>>>>>>>>>>>>>
    
    	 
     insert Job 7  :
    
    Program received signal SIGSEGV, Segmentation fault.
    0x0000000000400b1a in insertIn (CPU_Burst=0x6030d0) at bar.c:297
    297	        if(currNode->PCB_Data->CPU_Burst >= newNode->PCB_Data->CPU_Burst)
    (gdb) bt
    #0  0x0000000000400b1a in insertIn (CPU_Burst=0x6030d0) at bar.c:297
    #1  0x0000000000400949 in main () at bar.c:165
    (gdb) list
    292	    trailNode = NULL;
    293	
    294	        /*traversal list to find insert location */
    295	    while(currNode !=NULL)
    296	    {
    297	        if(currNode->PCB_Data->CPU_Burst >= newNode->PCB_Data->CPU_Burst)
    298	        {
    299	
    300	          break;
    301	
    (gdb) info locals
    currNode = 0x6030f0
    trailNode = 0x0
    newNode = 0x6031b0
    (gdb) print currNode->PCB_Data
    $1 = (struct PCB *) 0x603010
    (gdb) print *currNode->PCB_Data
    $2 = {PCB_ID = 1111, ArrivalTime = 0, CPU_Burst = 0}
    (gdb) print *newNode->PCB_Data
    Cannot access memory at address 0x0
    But....
    Code:
    printf("\t  inserting a new head of the list generates :\n");
    insertFirst(job6);
    printList(head );
    You've already inserted job6 (and not removed it), so this is seems likely to screw the whole thing up.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Ahhhh that is very helpful,
    But as i said, I am a very basic programmer, i just about understand the functions haha,
    So could you confirm that the issue is due to trailNode?
    If so, any idea on how i can fix this?

  6. #6
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Good that you posted your whole code (unlike many others who don't...).

    I only had a quick look so I don't know if it fixes all the issues. The problem is in removeFirst():
    Code:
    void removeFirst()
    {
        if (head == NULL)
            return;
        else
        {
            /* Memory pointed to by "head" is freed. */
            free(head);  /* Deallocates memory from the current head */
    
            if (head == tail)  /*checks if the node being removed is the only node*/
            {
                head = NULL;
                tail = NULL;
            }
            else
            {
                /* And here invalid pointer "head" is accessed. */
                head = head->next; /*turn the new head into the node that was next to the head*/
            }
        }
    }
    I ugily commented out the "free()" function and it seemed to work.
    Remember that once you free memory pointed to by a pointer, the only thing you can do with that pointer is to either assign NULL to it or destroy it. You may not do anything else - this includes comparing to another pointer, which you also do in your code.
    Last edited by kmdv; 04-05-2013 at 01:11 PM.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Ahh thanks again for the help! is the remove first anything to do with the reason why the Void insertIn isn't working?

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    I would love if someone could tell me how to correct the code its getting to the end of the deadline and im really struggling to make sense of all this!"

  9. #9
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    you need to post your amended code based on the previous - high quality help - you have received - you have not done that yet, in any other posts, so how can we help further - I dont mean to be too cynical but...
    Last edited by rogster001; 04-05-2013 at 01:56 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    I understand this, but i havent amended any code due to doing other things at the same time to meet the criteria, I dont really want to mess around with my code too much just incase it isnt going to actually help the issue of the of last task being printed, the code previous to this has all be submitted and wrote up about, as it does the job i need it to do its not an issue, unless its directly effecting the result of this last task (traverse inserting node part) Sorry if i havent been clear enough but i do really appreciate the help

  11. #11
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    I dont really want to mess around with my code too much just incase it isnt going to actually help the issue of the of last task
    Have you heard of backups? version control? - Or perhaps, since the deadline is approaching : DR

    i havent amended any code due to doing other things at the same time to meet the criteria
    That is your problem - Your course is structured over a period of time that should suffice for study and completion of the task(s) required

    And your last code if already submitted is more likely to drop you some marks, than if you had spent time implementing some of the advice here.
    Last edited by rogster001; 04-05-2013 at 02:19 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  12. #12
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by Fahkinsupah View Post
    I dont really want to mess around with my code too much just incase it isnt going to actually help the issue of the of last task being printed
    o_O

    So, you didn't even try to fix the part I pointed out? Actually, it does fix the display issue. You can try by putting exactly 4 characters - /* <free()> */, but be careful since it will SERIOUSLY mess up the code.

    You ignore all the help you get, wasting our time...

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    No no, I did try it, Dont get the wrong impression that i havent tried the code because i did, Commenting out the frees didnt change the outcome of the result.
    I just didnt save the changed code after trying your methods of advice, I have been getting the same outcome everytime,
    Don't get the impression i don't care, or i havent tried the changes because i did, But the documentation for the changes in the above comments has already been done and submited and it works,
    So if it isn't changing the final result of the me seeing the display for insertIn, i dont overly need it, Sorry for not being clear enough,
    The documentation for that part is done and submited, i cannot change it,
    I do really appreciate your help and i am still learning things from this i dont want you to feel like you are wasting your time.
    I really do thank you for your help,
    I just want to be clear i just need the InsertIn results to be displayed But thanks for the help on other matters.

  14. #14
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Also, as i stated, I dont actually overly want the code directly given to me, I just want someone to point out why it isn't being displayed :/
    Its for coursework so i dont want to cheat and be penalized for plagiarism, i only really want to know Why infact it isn't displaying the code :/
    This is another reason why i dont overly want to change any of the code, I asked for someone to simply explain why :/
    I've been trying to figure it out for hours now, i want to do it on my own, I just want someone to point the issue out as i can't see it due to not being a very experienced programmer.
    I really appreciate the efforts of people though, I can't express this enough!

  15. #15
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    you really need to read this. But anyway - if you are happy to submit what you have, and need to fix the last bug - explain exactly what are the problems you are having? - so far i understand that 'the insertion results are not displaying' - that is not very useful.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 11-22-2012, 12:01 AM
  2. Replies: 1
    Last Post: 07-17-2012, 12:56 AM
  3. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  4. Sorting Linked Lists (code not concept)
    By Newbie Magic in forum C++ Programming
    Replies: 2
    Last Post: 05-11-2004, 08:57 AM

Tags for this Thread