Circular double linked list issue ..need help

This is a discussion on Circular double linked list issue ..need help within the C Programming forums, part of the General Programming Boards category; Hi , I am implementing a circular linkedlist. I have got all the basic functions working but facing some issue ...

  1. #1
    Registered User
    Join Date
    Jun 2012
    Posts
    6

    Circular double linked list issue ..need help

    Hi , I am implementing a circular linkedlist. I have got all the basic functions working but facing some issue in the ringMove function. Eventhough it is working fine ,I am getting valgrind error.Please see if there is some error.


    Code:
    #ifndef TKK_AS_C_RINGLIST_H
    #define TKK_AS_C_RINGLIST_H
    
    
    #include <stddef.h>
    
    
    // TODO: RingNode definition
    // Required variables:
    // - data: array of 101 characters (max. 100 + terminating NUL)
    // - prev and next: pointers to previous/next nodes
    typedef struct RingNode_s {
        char data[101];
        struct RingNode_s *next;
        struct RingNode_s *prev;
    }RingNode;
    
    
    /** Construct a new node.
    * @param pos if NULL, a new ring is created, otherwise the new node is inserted after node pos.
    * @param data a C string used to initialize the data (undefined behavior for strings longer than 100 characters).
    * @return the new node (connected to the old ring if pos was provided).
    **/
    
    
    RingNode* ringAdd(RingNode* pos, char const* data);
    
    
    /** Move a set of nodes to another position. O(1).
    * Takes a range of nodes [first, last] and moves them to a new position. The new
    * position may be within another ring or in the same ring as the range, but the
    * behavior is undefined if the destination is within the range to be moved.
    * @param first the first node to move.
    * @param last the last node to move.
    * @param pos the destination: the moved nodes are inserted after node pos.
    * @return first
    **/
    
    
    RingNode* ringMove(RingNode* first, RingNode* last, RingNode* pos);
    
    
    #endif

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include "ringlist.h"
    
    
    RingNode* ringAdd(RingNode* pos, char const* data) {
        RingNode *newring = malloc(sizeof (RingNode));
        strcpy(newring->data, data);
        if (pos) {
            newring->prev = pos;
            newring->next = pos->next;
            pos->next = newring;
            (newring->next)->prev = newring;
        } else {
            newring->next = newring;
            newring->prev = newring;
        }
        return newring;
    }
    
    
    RingNode* ringMove(RingNode* first, RingNode* last, RingNode* pos) {
    
    
        RingNode *item = first;
        RingNode *final = last;
        while (item->next != final) // valgrind error Invalid read of                                        size 8 
        {
            item = item->next;
            if (item == pos)
                return first;
        }
        (first->prev)->next = last->next;
        (last->next)->prev = first->prev;
        last->next = pos->next;
        (pos->next)->prev = last;
        pos->next = first;
        first->prev = pos;
        return first;
    }

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include "ringlist.h"
    
    
    int main() {
    
    
    
    
        RingNode* ringitem1 = ringAdd(NULL, "ringitem1");
        RingNode* ringitem2 = ringAdd(ringitem1, "ringitem2");
        RingNode* ringitem3 = ringAdd(ringitem2, "ringitem3");
        RingNode* ringitem4 = ringAdd(ringitem3, "ringitem4");
        RingNode* ringitem5 = ringAdd(ringitem4, "ringitem5");
        RingNode* ringitem6 = ringAdd(ringitem5, "ringitem6");
        RingNode* ringitem7 = ringAdd(ringitem6, "ringitem7");
        RingNode* ringitem8 = ringAdd(ringitem7, "ringitem8");
        RingNode* ringitem9 = ringAdd(ringitem8, "ringitem9");
    
    
        ringMove(ringitem5, ringitem8, ringitem9);
    
    
        return 0;
    }

    Please sujjest what might be the issue. For clarity and simplicity i have not added the other functions here.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    From the valgrind manual page
    --db-attach=<yes|no> [default: no]
    When enabled, Valgrind will pause after every error shown and print the line:

    ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ----

    Pressing Ret, or N Ret or n Ret, causes Valgrind not to start a debugger for this error.

    Pressing Y Ret or y Ret causes Valgrind to start a debugger for the program at this point. When you have finished with the debugger, quit from
    it, and the program will continue. Trying to continue from inside the debugger doesn't work.

    C Ret or c Ret causes Valgrind not to start a debugger, and not to ask again.
    So, having detected a problem, you can launch the debugger at that spot to have a good look around to see what went wrong.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2012
    Posts
    6
    Quote Originally Posted by Salem View Post
    From the valgrind manual page

    So, having detected a problem, you can launch the debugger at that spot to have a good look around to see what went wrong.
    But is the implementation of ringMove function is fine ? for me it is working

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,854
    > But is the implementation of ringMove function is fine ? for me it is working
    You're confusing "working" with "bug-free".

    If your only test of "working" is that it produces the right answer and doesn't crash, then why are you bothering to run valgrind?

    You run valgrind to find bugs which are not apparent through inspection or testing, yet when it finds one you're all "That's impossible, my code works".

    Draw on paper the ring you think you've created, and then use the debugger to verify all the next/prev pointers of the ring you actually created.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how do i reverse a circular double linked list
    By kobra_swe in forum C Programming
    Replies: 13
    Last Post: 04-08-2008, 05:20 PM
  2. Circular Double Linked List - Logic in Operator=
    By INFERNO2K in forum C++ Programming
    Replies: 5
    Last Post: 09-30-2006, 01:45 PM
  3. circular linked->list help
    By The Brain in forum C++ Programming
    Replies: 8
    Last Post: 10-21-2004, 12:12 PM
  4. Circular linked list
    By campermama in forum C++ Programming
    Replies: 7
    Last Post: 06-15-2004, 12:53 PM
  5. Again, Circular Linked list ???
    By yescha in forum C Programming
    Replies: 2
    Last Post: 11-16-2001, 08:35 PM

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