reading the source of calling a singly-linked list

Discussion in 'C Programming' started by Phred Phungus, Feb 12, 2010.

  1. I'm looking at pp. 381-392 of _C Unleashed_ and set the goal of this
    thread to read through the source of this text. I'll make a full source
    listing after the sig.

    $ ls -l
    total 480
    ....
    -rw-r--r-- 1 dan dan 8734 2000-06-08 16:13 dllist.c
    -rw-r--r-- 1 dan dan 3935 2000-06-08 16:13 dllisteg.c
    -rw-r--r-- 1 dan dan 3279 2000-06-08 16:13 dllist.h
    -rw-r--r-- 1 dan dan 6614 2000-06-08 16:13 dllistmn.c
    ....
    -rw-r--r-- 1 dan dan 4835 2010-02-04 22:48 sllist.c
    -rw-r--r-- 1 dan dan 4777 2000-06-08 16:13 sllist.c~
    -rw-r--r-- 1 dan dan 2851 2000-06-08 16:13 sllist.h
    -rw-r--r-- 1 dan dan 3307 2000-06-08 16:13 sllistmn.c



    I hardly know how to broach my subject without reading a program as I
    see it. When I see things, I see what I'm looking for and can miss
    obvious facts that lay slightly abreast. Since the source listing is
    long, I thought it would be better to ask a concrete question about the
    first thing that throws me.

    Well, the first thing I see is

    assert(Tag == 0);

    This occurs in the function PrintBook. So caller must have the first
    arg as zero, else execution aborts.

    Why is Tag 0 when main calls?
    --
    fred
    $ cat sl3.c


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

    #include "sllist.h"

    typedef struct BOOK
    {
    char Title[30];
    char Author[30];
    } BOOK;

    typedef struct FIELD_INFO
    {
    int TitleWidth;
    int AuthWidth;
    } FIELD_INFO;

    int PrintBook(int Tag, void *Memory, void *Args)
    {
    BOOK *b = Memory;
    FIELD_INFO *f = Args;

    assert(Tag == 0);

    printf("Read %*s, by %*s\n",
    f->TitleWidth,
    b->Title,
    f->AuthWidth,
    b->Author);

    return 0;
    }


    int main(void)
    {
    BOOK Book[] =
    {
    {"Expert C Programming", "van der Linden"},
    {"C Programming FAQs", "Summit"},
    {"C++ Programming Language", "Stroustrup"},
    {"Algorithms in C", "Sedgewick"},
    {"Teach Yourself BCB", "Reisdorph"},
    {"The Standard C Library", "Plauger"},
    {"C++ Unleashed", "Liberty"},
    {"Data Structures & Algorithms", "Lafore"},
    {"C Programming Language", "Kernighan & Ritchie"},
    {"Linux Unleashed", "Husain and Parker"},
    {"C Unleashed", "Heathfield & Kirby"},
    {"C : A Reference Manual", "Harbison & Steele"},
    {"DOS Programmers Reference", "Dettmann & Johnson"},
    {"C: How to Program", "Deitel & Deitel"},
    {"Builder Unleashed", "Calvert"},
    {"UNIX Unleashed", "Burk and Horvath"}

    };

    SLLIST *List = NULL;
    SLLIST *Removed = NULL;

    BOOK *Data;

    FIELD_INFO FldInfo = { 30, 30};
    size_t NumBooks = sizeof Book / sizeof Book[0];

    size_t i;

    /* Populate the list */
    for(i = 0; i < NumBooks; i++)
    {
    if(SL_SUCCESS !=
    SLFront(&List, 0, Book + i, sizeof(BOOK)))
    {
    puts("Couldn't allocate enough memory.");
    SLDestroy(&List);
    exit(EXIT_FAILURE);
    }
    }

    /* Print the list */
    SLWalk(List, PrintBook, &FldInfo);

    /* Remove one item */
    Removed = List;

    for(i = 0; i < NumBooks / 2; i++)
    {
    Removed = Removed->Next;
    }

    Data = SLGetData(Removed->Next, NULL, NULL);
    printf("\nRemoving title %s\n\n", Data->Title);
    SLDeleteNext(Removed);

    /* Print the list again to confirm deletion */
    SLWalk(List, PrintBook, &FldInfo);

    /* Destroy the list */
    SLDestroy(&List);

    return 0;
    }

    // gcc ll1.o -D_GNU_SOURCE -Wall -Wextra sl3.c -o out
    $ cat sllist.h
    /* sllist.h - header for single linked list lib
    *
    * SLLIST - Single-Linked List Library
    *
    * Copyright (C) 2000 Richard Heathfield
    * Eton Computer Systems Ltd
    * Macmillan Computer Publishing
    *
    * This program is free software; you can redistribute it
    * and/or modify it under the terms of the GNU General
    * Public License as published by the Free Software
    * Foundation; either version 2 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will
    * be useful, but WITHOUT ANY WARRANTY; without even the
    * implied warranty of MERCHANTABILITY or FITNESS FOR A
    * PARTICULAR PURPOSE. See the GNU General Public License
    * for more details.
    *
    * You should have received a copy of the GNU General
    * Public License along with this program; if not, write
    * to the Free Software Foundation, Inc., 675 Mass Ave,
    * Cambridge, MA 02139, USA.
    *
    * Richard Heathfield may be contacted by email at:
    *
    *
    */


    #ifndef SLLIST_H__
    #define SLLIST_H__

    #define SL_SUCCESS 0
    #define SL_NO_MEM 1
    #define SL_ZERO_SIZE 2


    typedef struct SLLIST
    {
    int Tag;
    struct SLLIST *Next;
    void *Object;
    size_t Size;
    } SLLIST;

    /* Add new item immediately after current item */
    int SLAdd(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size);

    /* Add item to front of list. Care: if you pass
    * this function any node other than the first,
    * you will get Y-branches in your list:
    *
    * oldroot-->-
    * \
    * >->-passeditem-->-->--oldnext
    * /
    * newitem-->-
    *
    * This would be a Bad Thing.
    */
    int SLFront(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size);

    /* Add new item right at the end of the list */
    int SLAppend(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size);

    /* Replace existing data */
    int SLUpdate(SLLIST *Item,
    int NewTag,
    void *NewObject,
    size_t NewSize);

    /* Retrieve data from this node */
    void *SLGetData(SLLIST *Item,
    int *Tag,
    size_t *Size);

    /* Delete this item. Returns pointer to
    * next item - caller's responsibility
    * to maintain list integrity.
    */
    SLLIST *SLDeleteThis(SLLIST *Item);

    /* Delete item immediately following
    * the one passed in. List integrity
    * maintained automatically.
    */
    void SLDeleteNext(SLLIST *Item);

    /* Destroy the entire list */
    void SLDestroy(SLLIST **List);

    /* Call func(Tag, ThisItem, Args) for each item */
    int SLWalk(SLLIST *List,
    int(*Func)(int, void *, void *),
    void *Args);
    #endif
    $ cat sllist.c
    /* sllist.c - source for single linked list lib
    *
    * SLLIST - Single-Linked List Library
    *
    * Copyright (C) 2000 Richard Heathfield
    * Eton Computer Systems Ltd
    * Macmillan Computer Publishing
    *
    * This program is free software; you can redistribute it
    * and/or modify it under the terms of the GNU General
    * Public License as published by the Free Software
    * Foundation; either version 2 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will
    * be useful, but WITHOUT ANY WARRANTY; without even the
    * implied warranty of MERCHANTABILITY or FITNESS FOR A
    * PARTICULAR PURPOSE. See the GNU General Public License
    * for more details.
    *
    * You should have received a copy of the GNU General
    * Public License along with this program; if not, write
    * to the Free Software Foundation, Inc., 675 Mass Ave,
    * Cambridge, MA 02139, USA.
    *
    * Richard Heathfield may be contacted by email at:
    *
    *
    */

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

    #include "sllist.h"

    int SLAdd(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    SLLIST *NewItem;
    int Result = SL_SUCCESS;

    assert(Item != NULL);

    if(Size > 0)
    {
    NewItem = malloc(sizeof *NewItem);
    if(NewItem != NULL)
    {
    NewItem->Tag = Tag;
    NewItem->Size = Size;
    NewItem->Object = malloc(Size);

    if(NewItem->Object != NULL)
    {
    memcpy(NewItem->Object, Object, Size);
    /* Handle empty list */
    if(NULL == *Item)
    {
    NewItem->Next = NULL;
    *Item = NewItem;
    }
    else /* Insert just after current item */
    {
    NewItem->Next = (*Item)->Next;
    (*Item)->Next = NewItem;
    }
    }
    else
    {
    free(NewItem);
    Result = SL_NO_MEM;
    }
    }
    else
    {
    Result = SL_NO_MEM;
    }
    }
    else
    {
    Result = SL_ZERO_SIZE;
    }

    return Result;
    }

    int SLFront(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = SL_SUCCESS;

    SLLIST *p = NULL;

    assert(Item != NULL);

    Result = SLAdd(&p, Tag, Object, Size);
    if(SL_SUCCESS == Result)
    {
    p->Next = *Item;
    *Item = p;
    }

    return Result;
    }

    int SLAppend(SLLIST **Item,
    int Tag,
    void *Object,
    size_t Size)
    {
    int Result = SL_SUCCESS;
    SLLIST *EndSeeker;

    assert(Item != NULL);

    if(NULL == *Item)
    {
    Result = SLAdd(Item, Tag, Object, Size);
    }
    else
    {
    EndSeeker = *Item;
    while(EndSeeker->Next != NULL)
    {
    EndSeeker = EndSeeker->Next;
    }
    Result = SLAdd(&EndSeeker, Tag, Object, Size);
    }

    return Result;
    }

    int SLUpdate(SLLIST *Item,
    int NewTag,
    void *NewObject,
    size_t NewSize)
    {
    int Result = SL_SUCCESS;

    void *p;

    if(NewSize > 0)
    {
    p = realloc(Item->Object, NewSize);
    if(NULL != p)
    {
    Item->Object = p;
    memmove(Item->Object, NewObject, NewSize);
    Item->Tag = NewTag;
    Item->Size = NewSize;
    }
    else
    {
    Result = SL_NO_MEM;
    }
    }
    else
    {
    Result = SL_ZERO_SIZE;
    }

    return Result;
    }

    void *SLGetData(SLLIST *Item,
    int *Tag,
    size_t *Size)
    {
    void *p = NULL;

    if(Item != NULL)
    {
    if(Tag != NULL)
    {
    *Tag = Item->Tag;
    }
    if(Size != NULL)
    {
    *Size = Item->Size;
    }
    p = Item->Object;
    }

    return p;
    }

    SLLIST *SLDeleteThis(SLLIST *Item)
    {
    SLLIST *NextNode = NULL;

    if(Item != NULL)
    {
    NextNode = Item->Next;

    if(Item->Object != NULL)
    {
    free(Item->Object);
    }
    free(Item);
    }

    return NextNode;
    }

    void SLDeleteNext(SLLIST *Item)
    {
    if(Item != NULL && Item->Next != NULL)
    {
    Item->Next = SLDeleteThis(Item->Next);
    }
    }

    void SLDestroy(SLLIST **List)
    {
    SLLIST *Next;
    if(*List != NULL)
    {
    Next = *List;
    do
    {
    Next = SLDeleteThis(Next);
    } while(Next != NULL);
    *List = NULL;
    }
    }

    int SLWalk(SLLIST *List,
    int(*Func)(int, void *, void *),
    void *Args)
    {
    SLLIST *ThisItem;
    int Result = 0;

    for(ThisItem = List;
    0 == Result && ThisItem != NULL;
    ThisItem = ThisItem->Next)
    {
    Result = (*Func)(ThisItem->Tag,
    ThisItem->Object,
    Args);
    }

    return Result;
    }

    /* end of sllist.c */

    // gcc -c -D_GNU_SOURCE -Wall -Wextra sllist.c -o ll1.o
    $
     
    Phred Phungus, Feb 12, 2010
    #1
    1. Advertising

  2. Phred Phungus

    Paul N Guest

    On 12 Feb, 10:34, Phred Phungus <> wrote:
    > I'm looking at pp. 381-392 of _C Unleashed_ and set the goal of this
    > thread to read through the source of this text.  I'll make a full source
    > listing after the sig.
    >
    > I hardly know how to broach my subject without reading a program as I
    > see it.  When I see things, I see what I'm looking for and can miss
    > obvious facts that lay slightly abreast.


    It's not entirely clear what you're asking or what your problem is.
    You may just need to sit down and read the code for a bit longer, or
    perhaps read some simpler code first and build up to it. If you're
    still confused, you may then have a better idea of *why* you are
    confused.

    >  Since the source listing is
    > long, I thought it would be better to ask a concrete question about the
    > first thing that throws me.
    >
    > Well, the first thing I see is
    >
    > assert(Tag == 0);
    >
    > This occurs in the function PrintBook.  So caller must have the first
    > arg as zero, else execution aborts.
    >
    > Why is Tag 0 when main calls?


    (big snip of code)

    As far as I can see, SLWalk goes through the linked list doing
    something to each member. The way you are calling it, that "something"
    is PrintBook. That comes from this line:

    > SLWalk(List, PrintBook, &FldInfo);


    SLWalk allows you to set a "Tag" for each member of the list, to
    affect what happens when you walk. But your program does not use this
    feature. Tag is always 0, and PrintBook checks this to make sure
    nothing has gone wrong.

    But how do those zeros get there? Well, the answer seems to be in the
    way you are setting up the list in the first place. You add the items
    to the list using SLFront - see this line in main:

    > SLFront(&List, 0, Book + i, sizeof(BOOK)))


    and SLFront uses SLAdd, see these lines:

    > int SLFront(SLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > int Result = SL_SUCCESS;
    >
    > SLLIST *p = NULL;
    >
    > assert(Item != NULL);
    >
    > Result = SLAdd(&p, Tag, Object, Size);
    > if(SL_SUCCESS == Result)
    > {
    > p->Next = *Item;
    > *Item = p;
    > }


    and SLAdd sets the Tag as requested, see its code:

    > int SLAdd(SLLIST **Item,
    > int Tag,
    > void *Object,
    > size_t Size)
    > {
    > SLLIST *NewItem;
    > int Result = SL_SUCCESS;
    >
    > assert(Item != NULL);
    >
    > if(Size > 0)
    > {
    > NewItem = malloc(sizeof *NewItem);
    > if(NewItem != NULL)
    > {
    > NewItem->Tag = Tag;
    > NewItem->Size = Size;
    > NewItem->Object = malloc(Size);
    > .. (rest snipped)


    So in the line

    > SLFront(&List, 0, Book + i, sizeof(BOOK)))


    in main, the second parameter (the 0) is the value that the Tag will
    get set to. Just follow it through.

    Hope this helps.
    Paul.
     
    Paul N, Feb 12, 2010
    #2
    1. Advertising

  3. Phred Phungus

    spinoza1111 Guest

    On Feb 12, 6:34 pm, Phred Phungus <> wrote:
    > I'm looking at pp. 381-392 of _C Unleashed_ and set the goal of this
    > thread to read through the source of this text.  I'll make a full source
    > listing after the sig.
    >
    > $ ls -l
    > total 480
    > ...
    > -rw-r--r-- 1 dan dan  8734 2000-06-08 16:13 dllist.c
    > -rw-r--r-- 1 dan dan  3935 2000-06-08 16:13 dllisteg.c
    > -rw-r--r-- 1 dan dan  3279 2000-06-08 16:13 dllist.h
    > -rw-r--r-- 1 dan dan  6614 2000-06-08 16:13 dllistmn.c
    > ...
    > -rw-r--r-- 1 dan dan  4835 2010-02-04 22:48 sllist.c
    > -rw-r--r-- 1 dan dan  4777 2000-06-08 16:13 sllist.c~
    > -rw-r--r-- 1 dan dan  2851 2000-06-08 16:13 sllist.h
    > -rw-r--r-- 1 dan dan  3307 2000-06-08 16:13 sllistmn.c
    >
    > I hardly know how to broach my subject without reading a program as I
    > see it.  When I see things, I see what I'm looking for and can miss
    > obvious facts that lay slightly abreast.  Since the source listing is
    > long, I thought it would be better to ask a concrete question about the
    > first thing that throws me.
    >
    > Well, the first thing I see is
    >
    > assert(Tag == 0);
    >
    > This occurs in the function PrintBook.  So caller must have the first
    > arg as zero, else execution aborts.
    >
    > Why is Tag 0 when main calls?
    > --
    > fred
    > $ cat sl3.c
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <assert.h>
    >
    > #include "sllist.h"
    >
    > typedef struct BOOK
    > {
    >    char Title[30];
    >    char Author[30];
    >
    > } BOOK;
    >
    > typedef struct FIELD_INFO
    > {
    >    int TitleWidth;
    >    int AuthWidth;
    >
    > } FIELD_INFO;
    >
    > int PrintBook(int Tag, void *Memory, void *Args)
    > {
    >    BOOK *b = Memory;
    >    FIELD_INFO *f = Args;
    >
    >    assert(Tag == 0);
    >
    >    printf("Read %*s, by %*s\n",
    >           f->TitleWidth,
    >           b->Title,
    >           f->AuthWidth,
    >           b->Author);
    >
    >    return 0;
    >
    > }
    >
    > int main(void)
    > {
    >    BOOK Book[] =
    >    {
    >      {"Expert C Programming", "van der Linden"},
    >      {"C Programming FAQs", "Summit"},
    >      {"C++ Programming Language", "Stroustrup"},
    >      {"Algorithms in C", "Sedgewick"},
    >      {"Teach Yourself BCB", "Reisdorph"},
    >      {"The Standard C Library", "Plauger"},
    >      {"C++ Unleashed", "Liberty"},
    >      {"Data Structures & Algorithms", "Lafore"},
    >      {"C Programming Language", "Kernighan & Ritchie"},
    >      {"Linux Unleashed", "Husain and Parker"},
    >      {"C Unleashed", "Heathfield & Kirby"},
    >      {"C : A Reference Manual", "Harbison & Steele"},
    >      {"DOS Programmers Reference", "Dettmann & Johnson"},
    >      {"C: How to Program", "Deitel & Deitel"},
    >      {"Builder Unleashed", "Calvert"},
    >      {"UNIX Unleashed", "Burk and Horvath"}
    >
    >    };
    >
    >    SLLIST *List = NULL;
    >    SLLIST *Removed = NULL;
    >
    >    BOOK *Data;
    >
    >    FIELD_INFO FldInfo = { 30, 30};
    >    size_t NumBooks = sizeof Book / sizeof Book[0];
    >
    >    size_t i;
    >
    >    /* Populate the list */
    >    for(i = 0; i < NumBooks; i++)
    >    {
    >      if(SL_SUCCESS !=
    >            SLFront(&List, 0, Book + i, sizeof(BOOK)))
    >      {
    >        puts("Couldn't allocate enough memory.");
    >        SLDestroy(&List);
    >        exit(EXIT_FAILURE);
    >      }
    >    }
    >
    >    /* Print the list */
    >    SLWalk(List, PrintBook, &FldInfo);
    >
    >    /* Remove one item */
    >    Removed = List;
    >
    >    for(i = 0; i < NumBooks / 2; i++)
    >    {
    >      Removed = Removed->Next;
    >    }
    >
    >    Data = SLGetData(Removed->Next, NULL, NULL);
    >    printf("\nRemoving title %s\n\n", Data->Title);
    >    SLDeleteNext(Removed);
    >
    >    /* Print the list again to confirm deletion */
    >    SLWalk(List, PrintBook, &FldInfo);
    >
    >    /* Destroy the list */
    >    SLDestroy(&List);
    >
    >    return 0;
    >
    > }
    >
    > // gcc  ll1.o -D_GNU_SOURCE -Wall -Wextra sl3.c -o out
    > $ cat sllist.h
    > /*  sllist.h - header for single linked list lib
    >   *
    >   *  SLLIST - Single-Linked List Library
    >   *
    >   *  Copyright (C) 2000  Richard Heathfield
    >   *                      Eton Computer Systems Ltd
    >   *                      Macmillan Computer Publishing
    >   *
    >   *  This program is free software; you can redistribute it
    >   *  and/or modify it under the terms of the GNU General
    >   *  Public License as published by the Free Software
    >   *  Foundation; either version 2 of the License, or
    >   *  (at your option) any later version.
    >   *
    >   *  This program is distributed in the hope that it will
    >   *  be useful, but WITHOUT ANY WARRANTY; without even the
    >   *  implied warranty of MERCHANTABILITY or FITNESS FOR A
    >   *  PARTICULAR PURPOSE.  See the GNU General Public License
    >   *  for more details.
    >   *
    >   *  You should have received a copy of the GNU General
    >   *  Public License along with this program; if not, write
    >   *  to the Free Software Foundation, Inc., 675 Mass Ave,
    >   *  Cambridge, MA 02139, USA.
    >   *
    >   *  Richard Heathfield may be contacted by email at:
    >   *    
    >   *
    >   */
    >
    > #ifndef SLLIST_H__
    > #define SLLIST_H__
    >
    > #define SL_SUCCESS    0
    > #define SL_NO_MEM     1
    > #define SL_ZERO_SIZE  2
    >
    > typedef struct SLLIST
    > {
    >    int Tag;
    >    struct SLLIST *Next;
    >    void *Object;
    >    size_t Size;
    >
    > } SLLIST;
    >
    > /* Add new item immediately after current item */
    > int SLAdd(SLLIST **Item,
    >            int Tag,
    >            void *Object,
    >            size_t Size);
    >
    > /* Add item to front of list. Care: if you pass
    >   * this function any node other than the first,
    >   * you will get Y-branches in your list:
    >   *
    >   *    oldroot-->-
    >   *               \
    >   *                >->-passeditem-->-->--oldnext
    >   *               /
    >   *    newitem-->-
    >   *
    >   * This would be a Bad Thing.
    >   */
    > int SLFront(SLLIST **Item,
    >              int Tag,
    >              void *Object,
    >              size_t Size);
    >
    > /* Add new item right at the end of the list */
    > int SLAppend(SLLIST **Item,
    >               int Tag,
    >               void *Object,
    >               size_t Size);
    >
    > /* Replace existing data */
    > int SLUpdate(SLLIST *Item,
    >               int NewTag,
    >               void *NewObject,
    >               size_t NewSize);
    >
    > /* Retrieve data from this node */
    > void *SLGetData(SLLIST *Item,
    >                  int *Tag,
    >                  size_t *Size);
    >
    > /* Delete this item. Returns pointer to
    >   * next item - caller's responsibility
    >   * to maintain list integrity.
    >   */
    > SLLIST *SLDeleteThis(SLLIST *Item);
    >
    > /* Delete item immediately following
    >   * the one passed in. List integrity
    >   * maintained automatically.
    >   */
    > void SLDeleteNext(SLLIST *Item);
    >
    > /* Destroy the entire list */
    > void SLDestroy(SLLIST **List);
    >
    > /* Call func(Tag, ThisItem, Args) for each item */
    > int SLWalk(SLLIST *List,
    >             int(*Func)(int, void *, void *),
    >             void *Args);
    > #endif
    > $ cat sllist.c
    > /*  sllist.c - source for single linked list lib
    >   *
    >   *  SLLIST - Single-Linked List Library
    >   *
    >   *  Copyright (C) 2000  Richard Heathfield
    >   *                      Eton Computer Systems Ltd
    >   *                      Macmillan Computer Publishing
    >   *
    >   *  This program is free software; you can redistribute it
    >   *  and/or modify it under the terms of the GNU General
    >   *  Public License as published by the Free Software
    >   *  Foundation; either version 2 of the License, or
    >   *  (at your option) any later version.
    >   *
    >   *  This program is distributed in the hope that it will
    >   *  be useful, but WITHOUT ANY WARRANTY; without even the
    >   *  implied warranty of MERCHANTABILITY or FITNESS FOR A
    >   *  PARTICULAR PURPOSE.  See the GNU General Public License
    >   *  for more details.
    >   *
    >   *  You should have received a copy of the GNU General
    >   *  Public License along with this program; if not, write
    >   *  to the Free Software Foundation, Inc., 675 Mass Ave,
    >   *  Cambridge, MA 02139, USA.
    >   *
    >   *  Richard Heathfield may be contacted by email at:
    >   *    
    >   *
    >   */
    >
    > #include <stdlib.h>
    > #include <string.h>
    > #include <assert.h>
    >
    > #include "sllist.h"
    >
    > int SLAdd(SLLIST **Item,
    >            int Tag,
    >            void *Object,
    >            size_t Size)
    > {
    >    SLLIST *NewItem;
    >    int Result = SL_SUCCESS;
    >
    >    assert(Item != NULL);
    >
    >    if(Size > 0)
    >    {
    >      NewItem = malloc(sizeof *NewItem);
    >      if(NewItem != NULL)
    >      {
    >        NewItem->Tag    = Tag;
    >        NewItem->Size   = Size;
    >        NewItem->Object = malloc(Size);
    >
    >        if(NewItem->Object != NULL)
    >        {
    >          memcpy(NewItem->Object, Object, Size);


    OK, this may be what I'm talking about elsethread: tools doing our
    thinking for us.

    You see, Richard, in my view, memcopying would have absolutely no
    place in a tool for building a list in the most general case.

    In my view, a qualified programmer would never (and I mean, never) try
    to make a list of "things in themselves".

    Following Kant, let us distinguish between

    * The NOUMENAL approach of copying things in themselves that you
    don't really know about

    * The PHENOMENAL approach of representing the things "at arms length"
    where they are what the list "sees"

    Your "general purpose list package" seems to me to be noumenal, and
    this is asking for trouble. It's like a book created sometime ago by a
    satirical rogue, "Lady Godey's Fairy Book", in which fairies were
    impaled upon the pages of a book.

    There's no bound on the size of what you're copying. This means widely
    varying performance, in some cases unacceptable. It's always
    unpleasant to use a "tool" one has been given from On High like a good
    little cargo cultist only to find that The Gods Must Be Crazy.

    It's also dishonest as regards the software contract you enter into
    with the tool user. He may not realize that you're making a copy of
    his data. This presents all sorts of considerations including
    security.

    Your programmer psychology seems to me to be that of the basic
    business programmer, who is, in the tradition of Cobol, forever
    "moving", actually copying, meaningless shreds of data around in a
    profoundly alienated fashion, like the law copyist Ginger Nut in
    Melville's Bartelby the Scrivener.

    Which means you're exceptionally dangerous as a putative C expert.

    Perhaps I'm missing something. But copying a thing known by a void
    pointer?

    Perhaps you didn't want to use a void pointer. But that means you let
    your silly illusions as regards C control. You actually believe that
    the gods of programming smile on rule-followers and that you will be
    saved by faith (in ridiculous standards) and not good works.

    This programming Calvinism is to me nonsense, for I feel that it's all
    about good works.

    Dijkstra died for your sins. But if I were you, I'd shape up.

    >          /* Handle empty list */
    >          if(NULL == *Item)
    >          {
    >            NewItem->Next = NULL;
    >            *Item = NewItem;
    >          }
    >          else /* Insert just after current item */
    >          {
    >            NewItem->Next = (*Item)->Next;
    >            (*Item)->Next = NewItem;
    >          }
    >        }
    >        else
    >        {
    >          free(NewItem);
    >          Result = SL_NO_MEM;
    >        }
    >      }
    >      else
    >      {
    >        Result = SL_NO_MEM;
    >      }
    >    }
    >    else
    >    {
    >      Result = SL_ZERO_SIZE;
    >    }
    >
    >    return Result;
    >
    > }
    >
    > int SLFront(SLLIST **Item,
    >              int Tag,
    >              void *Object,
    >              size_t Size)
    > {
    >    int Result = SL_SUCCESS;
    >
    >    SLLIST *p = NULL;
    >
    >    assert(Item != NULL);
    >
    >    Result = SLAdd(&p, Tag, Object, Size);
    >    if(SL_SUCCESS == Result)
    >    {
    >      p->Next = *Item;
    >      *Item = p;
    >    }
    >
    >    return Result;
    >
    > }
    >
    > int SLAppend(SLLIST **Item,
    >               int Tag,
    >               void *Object,
    >               size_t Size)
    > {
    >    int Result = SL_SUCCESS;
    >    SLLIST *EndSeeker;
    >
    >    assert(Item != NULL);
    >
    >    if(NULL == *Item)
    >    {
    >      Result = SLAdd(Item, Tag, Object, Size);
    >    }
    >    else
    >    {
    >      EndSeeker = *Item;
    >      while(EndSeeker->Next != NULL)
    >      {
    >        EndSeeker = EndSeeker->Next;
    >      }
    >      Result = SLAdd(&EndSeeker, Tag, Object, Size);
    >    }
    >
    >    return Result;
    >
    > }
    >
    > int SLUpdate(SLLIST *Item,
    >               int NewTag,
    >               void *NewObject,
    >               size_t NewSize)
    > {
    >    int Result = SL_SUCCESS;
    >
    >    void *p;
    >
    >    if(NewSize > 0)
    >    {
    >      p = realloc(Item->Object, NewSize);
    >      if(NULL != p)
    >      {
    >        Item->Object = p;
    >        memmove(Item->Object, NewObject, NewSize);
    >        Item->Tag = NewTag;
    >        Item->Size = NewSize;
    >      }
    >      else
    >      {
    >        Result = SL_NO_MEM;
    >      }
    >    }
    >    else
    >    {
    >      Result = SL_ZERO_SIZE;
    >    }
    >
    >    return Result;
    >
    > }
    >
    > void *SLGetData(SLLIST *Item,
    >                  int *Tag,
    >                  size_t *Size)
    > {
    >    void *p = NULL;
    >
    >    if(Item != NULL)
    >    {
    >      if(Tag != NULL)
    >      {
    >        *Tag = Item->Tag;
    >      }
    >      if(Size != NULL)
    >      {
    >        *Size = Item->Size;
    >      }
    >      p = Item->Object;
    >    }
    >
    >    return p;
    >
    > }
    >
    > SLLIST *SLDeleteThis(SLLIST *Item)
    > {...
    >
    > read more »
     
    spinoza1111, Feb 13, 2010
    #3
  4. Paul N wrote:
    > On 12 Feb, 10:34, Phred Phungus <> wrote:
    >> I'm looking at pp. 381-392 of _C Unleashed_ and set the goal of this
    >> thread to read through the source of this text. I'll make a full source
    >> listing after the sig.
    >>
    >> I hardly know how to broach my subject without reading a program as I
    >> see it. When I see things, I see what I'm looking for and can miss
    >> obvious facts that lay slightly abreast.

    >
    > It's not entirely clear what you're asking or what your problem is.
    > You may just need to sit down and read the code for a bit longer, or
    > perhaps read some simpler code first and build up to it. If you're
    > still confused, you may then have a better idea of *why* you are
    > confused.
    >
    >> Since the source listing is
    >> long, I thought it would be better to ask a concrete question about the
    >> first thing that throws me.
    >>
    >> Well, the first thing I see is
    >>
    >> assert(Tag == 0);
    >>
    >> This occurs in the function PrintBook. So caller must have the first
    >> arg as zero, else execution aborts.
    >>
    >> Why is Tag 0 when main calls?

    >
    > (big snip of code)
    >
    > As far as I can see, SLWalk goes through the linked list doing
    > something to each member. The way you are calling it, that "something"
    > is PrintBook. That comes from this line:
    >
    >> SLWalk(List, PrintBook, &FldInfo);

    >
    > SLWalk allows you to set a "Tag" for each member of the list, to
    > affect what happens when you walk. But your program does not use this
    > feature. Tag is always 0, and PrintBook checks this to make sure
    > nothing has gone wrong.
    >
    > But how do those zeros get there? Well, the answer seems to be in the
    > way you are setting up the list in the first place. You add the items
    > to the list using SLFront - see this line in main:
    >
    >> SLFront(&List, 0, Book + i, sizeof(BOOK)))

    >
    > and SLFront uses SLAdd, see these lines:
    >
    >> int SLFront(SLLIST **Item,
    >> int Tag,
    >> void *Object,
    >> size_t Size)
    >> {
    >> int Result = SL_SUCCESS;
    >>
    >> SLLIST *p = NULL;
    >>
    >> assert(Item != NULL);
    >>
    >> Result = SLAdd(&p, Tag, Object, Size);
    >> if(SL_SUCCESS == Result)
    >> {
    >> p->Next = *Item;
    >> *Item = p;
    >> }

    >
    > and SLAdd sets the Tag as requested, see its code:
    >
    >> int SLAdd(SLLIST **Item,
    >> int Tag,
    >> void *Object,
    >> size_t Size)
    >> {
    >> SLLIST *NewItem;
    >> int Result = SL_SUCCESS;
    >>
    >> assert(Item != NULL);
    >>
    >> if(Size > 0)
    >> {
    >> NewItem = malloc(sizeof *NewItem);
    >> if(NewItem != NULL)
    >> {
    >> NewItem->Tag = Tag;
    >> NewItem->Size = Size;
    >> NewItem->Object = malloc(Size);
    >> .. (rest snipped)

    >
    > So in the line
    >
    >> SLFront(&List, 0, Book + i, sizeof(BOOK)))

    >
    > in main, the second parameter (the 0) is the value that the Tag will
    > get set to. Just follow it through.
    >
    > Hope this helps.
    > Paul.


    Indeed it does, Paul. Thanks for your generous comment.

    I have a variety of questions about the above. At this point, I can't
    see what is C and what is Richard's published idiom. I wish it could be
    color-coded.

    With reference to the above, could one define a call tree?
    --
    fred
     
    Phred Phungus, Feb 14, 2010
    #4
  5. spinoza1111 wrote:
    > On Feb 12, 6:34 pm, Phred Phungus <> wrote:
    >> I'm looking at pp. 381-392 of _C Unleashed_ and set the goal of this
    >> thread to read through the source of this text. I'll make a full source
    >> listing after the sig.


    I'll skip the usual usenet insult to address this person. He looks like
    a guy who has gone supernova and tries to ground himself in an
    environment he knows.

    I would commend my blue pills, seroquel and depakote. They're expensive
    but they really impact your neurotransmitters.
    > OK, this may be what I'm talking about elsethread: tools doing our
    > thinking for us.


    I'm trying to develop thinking tools, so this isn't a problem for OP.
    >
    > You see, Richard, in my view, memcopying would have absolutely no
    > place in a tool for building a list in the most general case.
    >
    > In my view, a qualified programmer would never (and I mean, never) try
    > to make a list of "things in themselves".
    >
    > Following Kant, let us distinguish between


    Kant? Really? He's not someone I've read. I find his stuff as
    convincing as his contemporary catholicism.
    >
    > * The NOUMENAL approach of copying things in themselves that you
    > don't really know about
    >
    > * The PHENOMENAL approach of representing the things "at arms length"
    > where they are what the list "sees"
    >
    > Your "general purpose list package" seems to me to be noumenal, and
    > this is asking for trouble. It's like a book created sometime ago by a
    > satirical rogue, "Lady Godey's Fairy Book", in which fairies were
    > impaled upon the pages of a book.
    >
    > There's no bound on the size of what you're copying. This means widely
    > varying performance, in some cases unacceptable. It's always
    > unpleasant to use a "tool" one has been given from On High like a good
    > little cargo cultist only to find that The Gods Must Be Crazy.


    Like that movie. The Gods are crazy.
    >
    > It's also dishonest as regards the software contract you enter into
    > with the tool user. He may not realize that you're making a copy of
    > his data. This presents all sorts of considerations including
    > security.
    >
    > Your programmer psychology seems to me to be that of the basic
    > business programmer, who is, in the tradition of Cobol, forever
    > "moving", actually copying, meaningless shreds of data around in a
    > profoundly alienated fashion, like the law copyist Ginger Nut in
    > Melville's Bartelby the Scrivener.
    >
    > Which means you're exceptionally dangerous as a putative C expert.


    Ptosh.
    >
    > Perhaps I'm missing something. But copying a thing known by a void
    > pointer?
    >
    > Perhaps you didn't want to use a void pointer. But that means you let
    > your silly illusions as regards C control. You actually believe that
    > the gods of programming smile on rule-followers and that you will be
    > saved by faith (in ridiculous standards) and not good works.
    >
    > This programming Calvinism is to me nonsense, for I feel that it's all
    > about good works.


    I'm curious if you've darkened the doors of a calvinist meeting in the
    last 5 years? I have. I sang bass in their choir.

    I didn't see any C analogs other than their view of satan. He was the
    guy around every corner for them, but for me, the thing beyond the next
    corner is discovery, so I had a values difference with them.
    >
    > Dijkstra died for your sins. But if I were you, I'd shape up.


    Well I'm for rights for Djikes now, so I think I'm halfway there.
    --
    fred
     
    Phred Phungus, Feb 14, 2010
    #5
    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. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    931
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    609
    Method Man
    Sep 24, 2004
  3. CR

    AlphaSort for singly linked list

    CR, Dec 15, 2003, in forum: C Programming
    Replies:
    1
    Views:
    514
    CBFalconer
    Dec 15, 2003
  4. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,828
    saadbinsaulat
    Feb 27, 2011
  5. Phred Phungus

    calling a singly-linked list

    Phred Phungus, Feb 8, 2010, in forum: C Programming
    Replies:
    16
    Views:
    654
    Phred Phungus
    Feb 10, 2010
Loading...

Share This Page