A doubly linked-list in C

Discussion in 'C Programming' started by arnuld, Apr 18, 2009.

  1. arnuld

    arnuld Guest

    This program compiles fine but has semantic error, I am unable to find it.
    I am trying to learn Linked-List implementation in C:

    WANTED: Values to be added to the First element.
    PROBLEM: it always says first element has values, even when the first element has NULL values


    /* A doubly linked list implementation in C. I add some values and then remove some. Each element is a struct and
    * we use key to identify the element.
    *
    * VERISON 1.0
    *
    */


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>



    enum {
    SIZE_KEY = 10,
    SIZE_VALUE = 20
    };


    struct KV_pair
    {
    char key[SIZE_KEY];
    char value[SIZE_VALUE];
    struct KV_pair* next;
    struct KV_pair* prev;
    };


    void add_pair(struct KV_pair *const base, char* k, char* v );
    struct KV_pair* add_element_to_list(struct KV_pair *const base, struct KV_pair* ps);
    struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair* f );

    void print_pair(struct KV_pair *const );

    int main(void)
    {
    struct KV_pair* baseElement = malloc( 1 * (sizeof *baseElement));

    if( NULL == baseElement )
    {
    fprintf(stderr, "IN: %s, at %d, malloc() failed\n", __FILE__, __LINE__);
    exit( EXIT_FAILURE );
    }

    memset(baseElement, '\0', sizeof(baseElement));

    add_pair(baseElement, "k1", "v1");

    print_pair(baseElement);


    return 0;
    }



    void add_pair(struct KV_pair *const base, char* k, char* v )
    {
    struct KV_pair* s = malloc( 1 * sizeof(*s));

    if( NULL == s )
    {
    fprintf(stderr, "IN: %s, at %d: malloc() failed\n", __FILE__, __LINE__);
    }
    else if( NULL == base->key )
    {
    struct KV_pair* temp = base;
    printf("List is empty first element to add\n");
    strcpy(temp->key, k);
    strcpy(temp->value, v);
    free(s);
    s = NULL;
    }
    else
    {
    printf("List already has some elements\n");
    strcpy(s->key, k);
    strcpy(s->value, v);

    if( add_element_to_list(base, s) )
    {
    printf("Element added\n");
    }
    else
    {
    printf("unable to add the element\n");
    }
    }
    }


    struct KV_pair* add_element_to_list(struct KV_pair *const base, struct KV_pair* ps)
    {
    struct KV_pair* b = find_element(base, ps);

    if( b )
    {
    printf("IN: %s, at %d, Element already exists, can not add\n", __FILE__, __LINE__);
    return ps;
    }
    else
    {
    printf("DUMMY addition, will write this part later\n");
    return ps;
    }

    return NULL;
    }


    struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair* f )
    {
    struct KV_pair* b = base;

    if( b )
    {
    for( ; NULL != b; b = b->next )
    {
    if( 0 == strcmp(b->key, f->key) )
    {
    return b;
    }
    }
    }

    return NULL;
    }


    void print_pair(struct KV_pair *const base)
    {
    struct KV_pair* b = base;

    for( ; NULL != b; b = b->next )
    {
    printf("Key = %s\n", b->key);
    printf("Value = %s\n", b->value);
    printf("----------\n");
    }
    }
    ===================== OUTPUT =========================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra doubley-LL.c
    [arnuld@dune programs]$ ./a.out
    List already has some elements
    DUMMY addition, will write this part later
    Element added
    Key =
    Value =
    ----------
    [arnuld@dune programs]$




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
    arnuld, Apr 18, 2009
    #1
    1. Advertising

  2. arnuld

    Kaz Kylheku Guest

    On 2009-04-18, arnuld <> wrote:
    > void add_pair(struct KV_pair *const base, char* k, char* v )
    > {
    > struct KV_pair* s = malloc( 1 * sizeof(*s));
    >
    > if( NULL == s )
    > {
    > fprintf(stderr, "IN: %s, at %d: malloc() failed\n", __FILE__, __LINE__);
    > }
    > else if( NULL == base->key )


    This comparison will never be true because base->key is an array, not
    a pointer.

    > {
    > struct KV_pair* temp = base;
    > printf("List is empty first element to add\n");
    > strcpy(temp->key, k);
    > strcpy(temp->value, v);
    > free(s);
    > s = NULL;


    So this will never happen.

    > }
    > else
    > {
    > printf("List already has some elements\n");
    > strcpy(s->key, k);
    > strcpy(s->value, v);
    >
    > if( add_element_to_list(base, s) )
    > {
    > printf("Element added\n");
    > }
    > else
    > {
    > printf("unable to add the element\n");
    > }


    This block does nothing because add_element_to_list is an incomplete
    stub. The KV_Pair pointed at by s is not added to the list, and is instead
    leaked (the program loses its one and only pointer to that object).

    >===================== OUTPUT =========================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra doubley-LL.c
    > [arnuld@dune programs]$ ./a.out
    > List already has some elements


    So this is the consequence of the silly base->key == NULL comparison that
    is always false, since the pointer to the first element of an array is not
    a null pointer.

    > DUMMY addition, will write this part later
    > Element added


    THe element was not added, since that is not finished.

    > Key =
    > Value =


    And so you end up with a list that contains only the based node. The key and
    value arrays have been overwritten with zeros, so they are empty strings.

    Machine does what you tell it, not what you want.:)
    Kaz Kylheku, Apr 18, 2009
    #2
    1. Advertising

  3. arnuld

    arnuld Guest

    > On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:

    >> On 2009-04-18, arnuld <> wrote:
    >> ....SNIP....
    >> else if( NULL == base->key )


    > This comparison will never be true because base->key is an array, not
    > a pointer.


    :-\

    and I thought when we access the values then arrays and pointers are same.
    I am programming in C from last 6 months, I really don't understand how
    long does it take to understand this pointer business and the
    pointer-array business.



    > So this is the consequence of the silly base->key == NULL comparison
    > that is always false, since the pointer to the first element of an array
    > is not a null pointer.


    I did a memset() on it. memset() fills an array with NULLs. '\0' is the
    NULL


    I am programming in C from last 6 months, I really don't understand how
    long does it take to understand this pointer business and the
    pointer-array business.


    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
    arnuld, Apr 18, 2009
    #3
  4. arnuld

    BartC Guest

    "arnuld" <> wrote in message
    news:p...
    > This program compiles fine but has semantic error, I am unable to find it.
    > I am trying to learn Linked-List implementation in C:
    >
    > WANTED: Values to be added to the First element.
    > PROBLEM: it always says first element has values, even when the first
    > element has NULL values


    > struct KV_pair
    > {
    > char key[SIZE_KEY];
    > char value[SIZE_VALUE];
    > struct KV_pair* next;
    > struct KV_pair* prev;
    > };
    >
    >
    > void add_pair(struct KV_pair *const base, char* k, char* v );
    > struct KV_pair* add_element_to_list(struct KV_pair *const base, struct
    > KV_pair* ps);
    > struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair*
    > f );
    >
    > void print_pair(struct KV_pair *const );
    >
    > int main(void)
    > {
    > struct KV_pair* baseElement = malloc( 1 * (sizeof *baseElement));
    >
    > if( NULL == baseElement )
    > {
    > fprintf(stderr, "IN: %s, at %d, malloc() failed\n", __FILE__,
    > __LINE__);
    > exit( EXIT_FAILURE );
    > }
    >
    > memset(baseElement, '\0', sizeof(baseElement));


    I think you need sizeof(*baseElement) here, otherwise you might only clear 4
    bytes instead of 40 for example. Or just use sizeof(struct KV_pair).

    > else if( NULL == base->key )


    As already pointed out, you need to use base->key[0]==0, or
    strcmp(base->key,"")==0. Or change KV_pair to store key/value strings in
    allocated memory (then you don't have limits on their lengths, although
    deleting is a bit more work).

    Your linked list logic seems a little strange (to me): your empty linked
    list starts with a dummy node containing empty key/value pairs. Normally
    you'd start with a NULL root (baseEelement) which subsequently points to the
    first element which is added.

    (In add_pair(), you allocate space for a new element (s), then immediately
    free it if this is the first element.)

    Your malloc error checking code is comprehensive (and commendable) but it
    does tend to obscure the logic (I wouldn't bother it myself, not until the
    thing works, although the advice here might be different).

    --
    Bartc
    BartC, Apr 18, 2009
    #4
  5. arnuld

    Phil Carmody Guest

    rkiesling <> writes:
    > arnuld <> writes:
    >>> On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:

    >>
    >>>> On 2009-04-18, arnuld <> wrote:
    >>>> ....SNIP....
    >>>> else if( NULL == base->key )

    >>
    >>> This comparison will never be true because base->key is an array, not
    >>> a pointer.

    >
    > Incorrect.


    Good start - 1 error in 1 word.

    > The -> operator has a higher precedence than ==.


    Irrelevant. 1 error and 1 irrelevancy in 1 sentence and 1 word.

    > And base->key is an element of the array, not the complete
    > array.


    Back to errors again. You're doing well. 2 errors and 1
    irrelevancy in 2 sentences and 1 word.

    > And, btw, an implementation-dependent macro like
    > NULL on the left side of an operator is not terribly
    > suitable, either.


    I'll call that an error too, as they can be perfectly
    suitable, so a blanket statement that they're not is
    false. 3 errors and 1 irrelevancy in 3 sentences and 1
    word. Great pace - can you keep it up?

    > Owing to the operator precedence,
    >
    > else if( base->key == NULL )
    >
    > is equivalent.


    Another irrelevancy. Not as good as an error, but still a
    brave attempt. 3 errors and 2 irrelevancies in 4 sentences
    and 1 word.

    > You need to keep the operator precedence rules in mind,
    > unless you want to use a lot of parens.


    It's still irrelevant to the problem at hand. 3 errors and 3
    irrelevancies in 5 sentences and 1 word.

    base->key is an array of characters. Wherever it appears
    in the course, if it cannot logically be interpreted as
    that actual array (such as in a context like sizeof), then
    it will be interpreted as a pointer to the address of the
    first element of the array. If base points to a valid
    object, then base->key can never be NULL. If base does not
    point to a valid object, then base->key is an invalid
    expression. If the OP wanted to check the character _at_
    (the first slot of the array) base->key, he should have
    dereferenced it with either * or [].

    Phil
    --
    Marijuana is indeed a dangerous drug.
    It causes governments to wage war against their own people.
    -- Dave Seaman (sci.math, 19 Mar 2009)
    Phil Carmody, Apr 18, 2009
    #5
  6. arnuld

    Kaz Kylheku Guest

    On 2009-04-18, rkiesling <> wrote:
    > Simply passing the reference does not say anything about the
    > contents of the struct or array. C decouples the semantics
    > of passing on the reference from the actual contents of the
    > struct or array. And so this is intended.


    I missed an announcement here. Is there a competition to post the dumbest
    article that shows a lack of C knowledge, yet manages to use the words
    ``decouple'', ``semantics'' and ``portable''?

    Aha, trolling.

    > I'll try to illustrate these cases


    I recommend watercolor, or /washable/ crayons.
    Kaz Kylheku, Apr 18, 2009
    #6
  7. arnuld

    Flash Gordon Guest

    rkiesling wrote:
    > Richard Heathfield <> writes:
    >
    >> rkiesling said:
    >>
    >>> arnuld <> writes:
    >>>
    >>>>> On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:
    >>>>>> On 2009-04-18, arnuld <> wrote:
    >>>>>> ....SNIP....
    >>>>>> else if( NULL == base->key )
    >>>>
    >>>>> This comparison will never be true because base->key is an
    >>>>> array, not a pointer.
    >>> Incorrect. The -> operator has a higher precedence than ==.

    >> So what?
    >>
    >>> And base->key is an element of the array, not the complete array.

    >> No, base->key is an array of SIZE_KEY chars in the struct type
    >> KV_pair (check the OP if you don't believe me). When used in a
    >> value context, it resolves to the address of the first element, but
    >> it is not itself an element, and neither is the address of its
    >> first element.

    >
    > Simply passing the reference does not say anything about the
    > contents of the struct or array. C decouples the semantics
    > of passing on the reference from the actual contents of the
    > struct or array. And so this is intended.


    C does not have the concept of passing a reference. It has the concept
    of passing a value and, if you want to consider it a separate concept,
    passing a pointer value.

    The struct definition was
    struct KV_pair
    {
    char key[SIZE_KEY];
    char value[SIZE_VALUE];
    struct KV_pair* next;
    struct KV_pair* prev;
    };

    The function declarations were
    void add_pair(struct KV_pair *const base, char* k, char* v );
    struct KV_pair* add_element_to_list(struct KV_pair *const base, struct
    KV_pair* ps);
    struct KV_pair* find_element(struct KV_pair *const base, struct KV_pair*
    f );

    void print_pair(struct KV_pair *const );

    So base is a pointer to a struct KV_pair, and base->key is the array key
    in the struct. So base could be a null pointer, in which case evaluating
    base->key is undefined behaviour, but if base is a valid pointer it is
    impossible for base->key to be a null pointer or compare equal to one.

    > The else clause above only tests whether base->key has a
    > memory area associated with it.


    No, it doesn't. See above.

    > To get the actual beginning character of base->key you would
    > need *base->key, equivalent to base->key[0],


    No, in almost all situations base->key will give you the address of the
    first element, your suggestion will always give you the contents of the
    first element.

    > but those are
    > dependent on the semantics of a * types and more portable to
    > use a subscript and leave the pointer addition to the
    > compiler.


    <snip more stuff based on misconceptions>

    What are you talking about?

    > If in every case the program previously contained the
    > statement,
    >
    > base -> key = NULL;


    <snip>

    If it did then the compiler would be required to issue a diagnostic, and
    I strongly suspect that almost all compilers would abort the compilation
    with an error.

    >>> And, btw, an implementation-dependent macro like
    >>> NULL on the left side of an operator is not terribly
    >>> suitable, either.

    >> Why on earth not?

    >
    >> Owing to the operator precedence,
    >>
    >> else if( base->key == NULL )
    >>
    >> is equivalent.

    >
    >> Yes, it's equivalent. So what?

    >
    > Because as a macro, NULL can expand to 0, 0L, ((void *)0),


    Yes, but irrelevant.

    > ((void *)(*fn)()),


    Not that though.

    > or just about any other construct that
    > refers to a zero memory location,


    It has nothing to do with a zero memory location.

    > depending on the compiler,
    > C dialect, and the machine.


    On ALL implementations it is a constant expression with a value of 0 or
    such an expression cast to void*

    > A compiler should be
    > able to accomplish the type cast to a char * array, but
    > often there are machine dependent factors.


    No, there are no machine dependent factors. It is REQUIRED to work.

    > If, above, base
    > were not a single scalar address, the construct would almost
    > certainly not be valid without some serious type casting.


    What are you talking about? We know exactly what type it is, the only
    other considerations are whether it contains a null pointer and whether
    it contains a valid pointer.

    > Since NULL, as a simple scalar, is less dependent on
    > alignment issues,


    Allignment issues are completely irrelevant.

    > it is easier to (or at least more
    > intuitive) to let the base->key, which can potentially have
    > various alignments in memory, dictate the scalar types and
    > alignments that == is going to need for either operand. And
    > the assumption that macro NULL expands correctly in all contexts,
    > while reasonable with most compilers, is not always certain.


    You seem to have severe problems with your understanding of the
    situation. NULL is required to expand correctly, and the rest of what
    you are saying seems to be based on misconceptions as well.

    >> No parentheses are needed for if(NULL == base->key). The right thing
    >> to do with that expression is not to reorder it or parenthesise it
    >> but to remove it (and its following statement) completely, because
    >> it's totally pointless.

    >
    > In this case, certainly. I'd also say that a non-trivial program
    > would need to check for unforseen cases. (Maybe not to the point
    > of unplugging the hard drive in the middle of a run, but nearly.)


    Again, irrelevant to the issues at hand.
    --
    Flash Gordon
    Flash Gordon, Apr 18, 2009
    #7
  8. arnuld <> writes:
    >> On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:

    >
    >>> On 2009-04-18, arnuld <> wrote:
    >>> ....SNIP....
    >>> else if( NULL == base->key )

    >
    >> This comparison will never be true because base->key is an array, not
    >> a pointer.

    >
    > :-\
    >
    > and I thought when we access the values then arrays and pointers are same.
    > I am programming in C from last 6 months, I really don't understand how
    > long does it take to understand this pointer business and the
    > pointer-array business.


    About as long as it takes to read and understand section 6 of the
    comp.lang.c FAQ, <http://www.c-faq.com>.

    The relationship between arrays and pointers in C really isn't all
    that complicated. Arrays and pointers are two very different things.
    The trouble is that certain C constructs almost seem to conspire to
    confuse them, making it *seem* like they're the same thing in certain
    contexts. You just have to learn to understand a piece of code that
    uses arrays and pointers in terms of what's actually going on, rather
    than just looking at the syntax.

    Arrays are not pointers.
    Pointers are not arrays.
    Read section 6 of the FAQ.

    >> So this is the consequence of the silly base->key == NULL comparison
    >> that is always false, since the pointer to the first element of an array
    >> is not a null pointer.

    >
    > I did a memset() on it. memset() fills an array with NULLs. '\0' is the
    > NULL


    Nope. (Others have explained this.)

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Apr 18, 2009
    #8
  9. arnuld

    jameskuyper Guest

    rkiesling wrote:
    > Richard Heathfield <> writes:
    > > rkiesling said:
    > >> arnuld <> writes:
    > >>>> On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:
    > >>>>> On 2009-04-18, arnuld <> wrote:
    > >>>>> ....SNIP....
    > >>>>> else if( NULL == base->key )
    > >>>
    > >>>> This comparison will never be true because base->key is an
    > >>>> array, not a pointer.
    > >>
    > >> Incorrect. The -> operator has a higher precedence than ==.

    > >
    > > So what?
    > >
    > >> And base->key is an element of the array, not the complete array.

    > >
    > > No, base->key is an array of SIZE_KEY chars in the struct type
    > > KV_pair (check the OP if you don't believe me). When used in a
    > > value context, it resolves to the address of the first element, but
    > > it is not itself an element, and neither is the address of its
    > > first element.

    >
    > Simply passing the reference does not say anything about the
    > contents of the struct or array. C decouples the semantics
    > of passing on the reference from the actual contents of the
    > struct or array. And so this is intended.
    >
    > The else clause above only tests whether base->key has a
    > memory area associated with it.


    If base is a dereferencable pointer to a struct KV_pair object, there
    must be a memory area associated with base->key; otherwise, the
    behavior is undefined, rendering the test meaningless.

    > To get the actual beginning character of base->key you would
    > need *base->key, equivalent to base->key[0], but those are
    > dependent on the semantics of a * types and more portable to
    > use a subscript and leave the pointer addition to the
    > compiler.


    The standard defines (6.5.2.1p2) the behavior of base->key[0] as being
    equivalent to *(base->key + 0), and it defines the behavior of pointer
    addition (6.5.6p8) such that base->key+0 is the same as base->key, so
    if base->key[0] does not have the same behavior as *base->key, the
    implementation is non-conforming.

    > ... If base itself is an array of pointer,


    The type of 'base' is "struct KV_pair *"; that's not an array of
    pointers, that's a pointer; possibly to a single struct KV_pair
    object, possibly to a member of an array.

    If base were an array of pointer, then the expression base->key would
    be a constraint violation; you can only apply the -> operator to
    pointers to structures (6.5.2.3p1), not to arrays; not even if those
    arrays contain pointers to structures.

    ....
    > I'll try to illustrate these cases, if you'll please excuse
    > the lecture.
    >
    > If in every case the program previously contained the
    > statement,
    >
    > base -> key = NULL;


    base->key is an array, and is therefore not a modifiable lvalue
    (6.3.2.1p1) so it cannot be set equal to NULL. Such code would be a
    constraint violation (6.5.16p2).

    > then the test above would be valid (The program would also
    > need to free () the memory pointed to by base -> key).


    Since key is an array member of the struct pointed at by "base", the
    only way to free() the memory pointed at by base->key would be to free
    () the memory associated with the object pointed at by "base".

    > However, if the program previously had the statement
    >
    > strcpy (base -> key, "");
    >
    > or
    >
    > base -> key[0] = '\0';
    >
    > Then the test would not always be valid, because base->key still
    > would have a memory area associated with it.


    If base->key did not already have a memory area associated with it,
    both of those constructs would have undefined behavior. If it did have
    a memory area associated with it, writing data into that memory would
    have no affect on whether or not such a memory area was associated
    with data->key.

    ....
    > >> And, btw, an implementation-dependent macro like
    > >> NULL on the left side of an operator is not terribly
    > >> suitable, either.

    > >
    > > Why on earth not?

    >
    > > Owing to the operator precedence,
    > >
    > > else if( base->key == NULL )
    > >
    > > is equivalent.

    >
    > > Yes, it's equivalent. So what?

    >
    > Because as a macro, NULL can expand to 0, 0L, ((void *)0),
    > ((void *)(*fn)()), or just about any other construct that
    > refers to a zero memory location, depending on the compiler,
    > C dialect, and the machine.


    Referring to a zero memory location is not one of the requirements for
    being a null pointer constant. The requirements are "An integer
    constant expression with the value 0, or such an expression cast to
    type void *" (6.3.2.3p3). The expansion of NULL is implementation-
    dependent, but the fact that it must be a null pointer constant is
    specified by the standard, and every legitimate use of NULL depends
    only upon the fact that it is a null pointer constant.

    You don't specify what fn is; if it's a macro, there's a possibility
    that that ((void *)(*fn)()) might qualify as a null pointer constant.
    However, as the identifier of either a function or an object, it runs
    afoul of the requirement that an integer constant expression "shall
    only have operands that are integer constants, enumeration constants,
    character constants, sizeof expressions whose results are integer
    constants, and floating constants that are the immediate operands of
    casts." If 'fn' were any of those things, then *fn would be a
    constraint violation. If it's not one of those things, NULL is not
    allowed to expand into ((void *)(*fn)()).

    Furthermore, 'fn' is not a reserved name. As a result, strictly
    conforming code is allowed to give it a definition, and the
    implemenation is not. It's trivial to give fn a defintion that makes
    ((void *)(*fn)()) unambiguously not a null pointer constant, and
    therefore not a permitted expansion for the NULL macro.

    > ... A compiler should be
    > able to accomplish the type cast to a char * array, but
    > often there are machine dependent factors.


    Regardless of any of the machine-dependent factors you're concerned
    with, NULL is required to be a null pointer constant (7.17p3). When
    occurring in a context such as the one above, a null pointer constant
    is required to be converted the same type as base->key (6.9.5p5),
    which is a pointer type (6.3.2.1p3). A null pointer constant converted
    to a pointer type, becomes a null pointer of that type (6.3.2.3p3). A
    null pointer is required to compare unequal to any pointer which
    points at an actual object (6.5.9p6). If base->key has defined
    behavior, then base->key is an actual object, and the expression base-
    >key == NULL is therefore guaranteed to evaluate to 'false'.


    > ... If, above, base
    > were not a single scalar address, the construct would almost
    > certainly not be valid without some serious type casting.


    If that were true, it would render the implementation non-conforming.

    ....
    > alignment issues, it is easier to (or at least more
    > intuitive) to let the base->key, which can potentially have
    > various alignments in memory, dictate the scalar types and
    > alignments that == is going to need for either operand.


    It does. That's what the standard specifies for null pointer constants
    (6.9p5).

    > ... And
    > the assumption that macro NULL expands correctly in all contexts,
    > while reasonable with most compilers, is not always certain.


    It's certain on conforming compilers.
    jameskuyper, Apr 18, 2009
    #9
  10. arnuld

    CBFalconer Guest

    arnuld wrote:
    >
    > This program compiles fine but has semantic error, I am unable to
    > find it. I am trying to learn Linked-List implementation in C:
    >
    > WANTED: Values to be added to the First element.
    > PROBLEM: it always says first element has values, even when the
    > first element has NULL values


    Write down the structure of the list when empty, with 1 item, with
    2 items. For example, there is always something to mark the
    existence of the list:

    typedef struct marker {datum *next; datum *prev;} marker;
    typedef struct datum {marker mark; foo /* actual data */} datum;

    marker list = {NULL, NULL); /* empty - nothing more */

    Now what does a list with one item look like?

    list: ptr ptr /* both ptrs point to datum */
    datum /* whose marker component points are NULL

    Now try two elements. Remember list is always known to everybody.

    list ptr1 ptr2 /* no longer the same */
    datum #1 /* pointed to by ptr1 */
    /* its marker ptrs are next to datum#2, prev to NULL */
    datum #2 /* pointed to by ptr2 */
    /* marker ptrs are next to NULL, prev to datum#1 */

    Now work out how the list appears with three items in it. Make
    sure you can always tell when you get to the end (or beginning) of
    the list. Check the operations needed to insert an item at the
    beginning, end, middle. Same to delete items.

    You can write lots of code from that. The details of what the list
    holds are controlled by foo. Other things are detailed, and you
    can create code to manipulate, search, insert, delete, whatever.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Apr 19, 2009
    #10
  11. arnuld

    CBFalconer Guest

    Flash Gordon wrote:
    >

    .... snip ...
    >
    > C does not have the concept of passing a reference. It has the
    > concept of passing a value and, if you want to consider it a
    > separate concept, passing a pointer value.


    Disagree. It has the concept, but it isn't named a 'reference'.
    It is implemented by passing a pointer (by value) to the item to be
    'referenced'.

    Note the additional flexibility. That pointer itself can be
    'referenced'. The code using that 2nd level of referencing can
    access the first pointer (with one *) or the original item (with
    two *s). You can't play these games with languages that have
    fundamental references.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Apr 19, 2009
    #11
  12. arnuld

    Kaz Kylheku Guest

    On 2009-04-19, CBFalconer <> wrote:
    > Flash Gordon wrote:
    >>

    > ... snip ...
    >>
    >> C does not have the concept of passing a reference. It has the
    >> concept of passing a value and, if you want to consider it a
    >> separate concept, passing a pointer value.

    >
    > Disagree. It has the concept, but it isn't named a 'reference'.


    From C99:

    A pointer type may be derived from a function type, an object type, or an
    incomplete type, called the referenced type. A pointer type describes an
    object whose value provides a reference to an entity of the referenced type.
    A pointer type derived from the referenced type T is sometimes called
    "pointer to T". The construction of a pointer type from a referenced type is
    called "pointer type derivation"
    Kaz Kylheku, Apr 19, 2009
    #12
  13. arnuld

    Ben Pfaff Guest

    pete <> writes:

    > Here's my favorite null pointer constant
    >
    > ('-'-'-')


    Here's my least favorite null pointer constant:
    x
    given
    enum { x, y, z };
    Always seems like it should give a type mismatch error when I
    accidentally pass it as a function argument of pointer type but,
    of course, it does not.
    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
    Ben Pfaff, Apr 19, 2009
    #13
  14. arnuld

    Phil Carmody Guest

    Phil Carmody <> writes:
    > it will be interpreted as a pointer to the address of the


    Either 'pointer to' or 'address', not both.

    Phil
    --
    Marijuana is indeed a dangerous drug.
    It causes governments to wage war against their own people.
    -- Dave Seaman (sci.math, 19 Mar 2009)
    Phil Carmody, Apr 19, 2009
    #14
  15. arnuld

    Phil Carmody Guest

    Richard Heathfield <> writes:
    > rkiesling said:
    >> Because as a macro, NULL can expand to 0, 0L, ((void *)0),
    >> ((void *)(*fn)()), or just about any other construct that
    >> refers to a zero memory location, depending on the compiler,
    >> C dialect, and the machine.

    >
    > So?


    Oh, I missed that bit. What's this "zero memory location"
    that he's refering to? I can't find it mentioned in the
    usual references.

    Phil
    --
    Marijuana is indeed a dangerous drug.
    It causes governments to wage war against their own people.
    -- Dave Seaman (sci.math, 19 Mar 2009)
    Phil Carmody, Apr 19, 2009
    #15
  16. arnuld

    Phil Carmody Guest

    Flash Gordon <> writes:
    > rkiesling wrote:
    >> Richard Heathfield <> writes:
    >>
    >>> rkiesling said:
    >>>
    >>>> arnuld <> writes:
    >>>>
    >>>>>> On Sat, 18 Apr 2009 06:57:10 +0000, Kaz Kylheku wrote:
    >>>>>>> On 2009-04-18, arnuld <> wrote:
    >>>>>>> ....SNIP....
    >>>>>>> else if( NULL == base->key )
    >>>>>
    >>>>>> This comparison will never be true because base->key is an
    >>>>>> array, not a pointer.
    >>>> Incorrect. The -> operator has a higher precedence than ==.
    >>> So what?
    >>>
    >>>> And base->key is an element of the array, not the complete array.
    >>> No, base->key is an array of SIZE_KEY chars in the struct type
    >>> KV_pair (check the OP if you don't believe me). When used in a
    >>> value context, it resolves to the address of the first element, but
    >>> it is not itself an element, and neither is the address of its
    >>> first element.

    >>
    >> Simply passing the reference does not say anything about the
    >> contents of the struct or array. C decouples the semantics
    >> of passing on the reference from the actual contents of the struct
    >> or array. And so this is intended.

    >
    > C does not have the concept of passing a reference.


    Oh yes it does!

    > It has the concept
    > of passing a value and, if you want to consider it a separate concept,
    > passing a pointer value.


    Such pointer passing is *explicitly* described as passing a reference.
    The concept is passing by reference, the technique used for passing
    by reference is passing a pointer by value.

    Phil
    --
    Marijuana is indeed a dangerous drug.
    It causes governments to wage war against their own people.
    -- Dave Seaman (sci.math, 19 Mar 2009)
    Phil Carmody, Apr 19, 2009
    #16
  17. arnuld

    Ian Collins Guest

    Ben Pfaff wrote:
    > pete <> writes:
    >
    >> Here's my favorite null pointer constant
    >>
    >> ('-'-'-')

    >
    > Here's my least favorite null pointer constant:
    > x
    > given
    > enum { x, y, z };
    > Always seems like it should give a type mismatch error when I
    > accidentally pass it as a function argument of pointer type but,
    > of course, it does not.


    Another area where C++ is a "safer C"!

    --
    Ian Collins
    Ian Collins, Apr 19, 2009
    #17
  18. arnuld

    Phil Carmody Guest

    Ian Collins <> writes:
    > Ben Pfaff wrote:
    >> pete <> writes:
    >>
    >>> Here's my favorite null pointer constant
    >>>
    >>> ('-'-'-')

    >>
    >> Here's my least favorite null pointer constant:
    >> x
    >> given
    >> enum { x, y, z };
    >> Always seems like it should give a type mismatch error when I
    >> accidentally pass it as a function argument of pointer type but,
    >> of course, it does not.

    >
    > Another area where C++ is a "safer C"!


    C++ pushers will say anything to defend their sick religion!

    ;-)

    Phil
    --
    Marijuana is indeed a dangerous drug.
    It causes governments to wage war against their own people.
    -- Dave Seaman (sci.math, 19 Mar 2009)
    Phil Carmody, Apr 19, 2009
    #18
  19. arnuld

    Ian Collins Guest

    Phil Carmody wrote:
    > Ian Collins <> writes:
    >> Ben Pfaff wrote:
    >>> pete <> writes:
    >>>
    >>>> Here's my favorite null pointer constant
    >>>>
    >>>> ('-'-'-')
    >>> Here's my least favorite null pointer constant:
    >>> x
    >>> given
    >>> enum { x, y, z };
    >>> Always seems like it should give a type mismatch error when I
    >>> accidentally pass it as a function argument of pointer type but,
    >>> of course, it does not.

    >> Another area where C++ is a "safer C"!

    >
    > C++ pushers will say anything to defend their sick religion!


    Humbug!

    :)
    --
    Ian Collins
    Ian Collins, Apr 19, 2009
    #19
  20. arnuld

    Flash Gordon Guest

    Kaz Kylheku wrote:
    > On 2009-04-19, CBFalconer <> wrote:
    >> Flash Gordon wrote:
    >> ... snip ...
    >>> C does not have the concept of passing a reference. It has the
    >>> concept of passing a value and, if you want to consider it a
    >>> separate concept, passing a pointer value.

    >> Disagree. It has the concept, but it isn't named a 'reference'.

    >
    > From C99:
    >
    > A pointer type may be derived from a function type, an object type, or an
    > incomplete type, called the referenced type. A pointer type describes an
    > object whose value provides a reference to an entity of the referenced type.
    > A pointer type derived from the referenced type T is sometimes called
    > "pointer to T". The construction of a pointer type from a referenced type is
    > called "pointer type derivation"


    OK, it has a concept of a reference (just as it has the concept of an
    object) but it isn't what a lot of people mean when they talk about
    references, just as a lot of people don't mean object in the C standard
    sense when they talk about objects.
    --
    Flash Gordon
    Flash Gordon, Apr 19, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    921
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    453
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    321
    Terry Reedy
    Sep 5, 2005
  4. Daniel
    Replies:
    5
    Views:
    381
  5. dssuresh6

    need for doubly linked list

    dssuresh6, Nov 18, 2004, in forum: C Programming
    Replies:
    4
    Views:
    621
    J. J. Farrell
    Nov 19, 2004
Loading...

Share This Page