calling a singly-linked list

[Phred Phungus]

In the following program:

dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
7
345
23
0
dan@dan-desktop:~/source/unleashed/ch11$ cat ac1.c
#include <stdio.h>
#include <stdlib.h>

struct list {
struct list *next;
int n;
};

static int *read_numbers(struct list *list)
{
char buf[100];
int val, i, *ret;
struct list node, *p;
if(fgets(buf, sizeof buf, stdin)) {
if(sscanf(buf, "%d", &val)!=1) {
fprintf(stderr, "That's not a number\n");
exit(EXIT_FAILURE);
}
if(val!=0) {
node.n = val;
node.next = list;
return read_numbers(&node);
}
} else {
if(ferror(stdin)) {
perror("standard input");
exit(EXIT_FAILURE);
}
/* Naughty user sent EOF; pretend it was a 0 but with a warning */
fprintf(stderr, "Didn't get 0 terminator. List may be incomplete\n");
}

for(i=0,p=list;p;++i,p=p->next)
/*nothing*/;
ret = malloc(i * sizeof *ret);
if(!ret) {
perror("malloc");
exit(EXIT_FAILURE);
}
for(--i,p=list;p;--i,p=p->next)
ret = p->n;
return ret;
}

int main(void)
{
int *numbers;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
return 0;
}


// gcc -D_GNU_SOURCE -Wall -Wextra ac1.c -o out
dan@dan-desktop:~/source/unleashed/ch11$

, am I correct to think that the list is visible to entire program? My
question is how main would correctly output what I input.

Cheers,

 

[Tom St Denis]

, am I correct to think that the list is visible to entire program?  My
question is how main would correctly output what I input.

There is no variable named "list" in the entire program. There is a
struct named 'list' which is visible to the entire unit.

Tom

 

[bartc]

In the following program:

static int *read_numbers(struct list *list)

int main(void)
{
int *numbers;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
return 0;
}

, am I correct to think that the list is visible to entire program? My
question is how main would correctly output what I input.

read_numbers() returns a pointer to an array of ints, which is stored in
numbers. At this point it's only visible to main().

This example tries to print the results:

int main(void)
{
int *numbers,*p;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
p=numbers;
while (*p) printf("%d\n",*p++);
return 0;
}

But it doesn't quite work; I don't know what read_numbers does exactly: it
seems to read one integer per line, following by 0 on a line by itself (and
does this recursively, into an internal linked-list). Then returns an array
of the numbers, however without a terminator, so main() doesn't know how
many numbers there are.

 

[Alan Curry]

|#include <stdio.h>
|#include <stdlib.h>
|
|struct list {
| struct list *next;
| int n;
|};
|
|static int *read_numbers(struct list *list)
[...]

This code, which I posted in another thread, should not be used. It was a
response to a "challenge" and should be considered mainly as a joke. It does
technically do everything the challenge requested, while being useless for
any practical purpose.

In the very same article in which I posted it, I listed 3 reasons why the
challenge (i.e. make a growable list/array-ish data structure without
realloc) was stupid. And I also explained the particular shortcoming of my
code which I was too lazy to fix: it provides no way for the caller to know
how big the list is.

Yet somehow you missed all of that, and decided to hold on to that code and
treat it as if it was worthy of further study, and start a new thread
dedicated to analyzing it. Woosh!

 

[Phred Phungus]

|#include <stdio.h>
|#include <stdlib.h>
|
|struct list {
| struct list *next;
| int n;
|};
|
|static int *read_numbers(struct list *list)
[...]

This code, which I posted in another thread, should not be used. It was a
response to a "challenge" and should be considered mainly as a joke. It does
technically do everything the challenge requested, while being useless for
any practical purpose.

In the very same article in which I posted it, I listed 3 reasons why the
challenge (i.e. make a growable list/array-ish data structure without
realloc) was stupid. And I also explained the particular shortcoming of my
code which I was too lazy to fix: it provides no way for the caller to know
how big the list is.

You mentioned passing a counter to a recursive function.

I didn't see a better posting than yours, and now it's Feb. 9 east of
Chicago.

Yet somehow you missed all of that, and decided to hold on to that code and
treat it as if it was worthy of further study, and start a new thread
dedicated to analyzing it. Woosh!

I'm having trouble hooking up data structures with a platform and
extensions that are somewhat new to me. So I look for simpler toy
programs that do something similar.

It's not hard to mistake differing forms of lists. I was hoping to do
something with this from Unleashed:

//c11_022.c - naive single linked list, using an array.
#include <stdio.h>

typedef struct ITEM
{
char Title[30];
char Author[30];
int Next;
} ITEM;

int main(void)
{
ITEM List[] =
{
{"UNIX Unleashed", "Burk and Horvath", 2},
{"Algorithms in C", "Sedgewick", 9},
{"Builder Unleashed", "Calvert", 10},
{"C++ Unleashed", "Liberty", 12},
{"Linux Unleashed", "Husain and Parker", 8},
{"Teach Yourself BCB", "Reisdorph", 1},
{"Data Structures & Algorithms", "Lafore", 3},
{"DOS Programmers Reference", "Dettmann & Johnson", 11},
{"C Programming Language", "Kernighan & Ritchie", 6},
{"C++ Programming Language", "Stroustrup", 13},
{"C: How to Program", "Deitel & Deitel", 7},
{"C : A Reference Manual", "Harbison & Steele", 15},
{"The Standard C Library", "Plauger", 5},
{"C Programming FAQs", "Summit", 14},
{"Expert C Programming", "van der Linden", -1},
{"C Unleashed", "Heathfield & Kirby", 4}
};

int Current = 0;

while(Current != -1)
{
printf("Read %s, by %s.\n",
List[Current].Title,
List[Current].Author);
Current = List[Current].Next;
}

return 0;
}

// gcc -D_GNU_SOURCE -Wall -Wextra ll1.c -o out

I think the classification for what is a singly-linked list must be
fairly broad. In this, there aren't new nodes created dynamically.

 

[frank]

, am I correct to think that the list is visible to entire program?
My question is how main would correctly output what I input.

read_numbers() returns a pointer to an array of ints, which is stored in
numbers. At this point it's only visible to main().

This example tries to print the results: [code elided]

But it doesn't quite work; I don't know what read_numbers does exactly:
it seems to read one integer per line, following by 0 on a line by
itself (and does this recursively, into an internal linked-list). Then
returns an array of the numbers, however without a terminator, so main()
doesn't know how many numbers there are.

Thanks bart, it's starting to look like something:

dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac2.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
3
6
18
0
3
6
18
135153
dan@dan-desktop:~/source/unleashed/ch11$ cat ac2.c
#include <stdio.h>
#include <stdlib.h>

struct list {
struct list *next;
int n;
};

static int *read_numbers(struct list *list)
{
char buf[100];
int val, i, *ret;
struct list node, *p;
if(fgets(buf, sizeof buf, stdin)) {
if(sscanf(buf, "%d", &val)!=1) {
fprintf(stderr, "That's not a number\n");
exit(EXIT_FAILURE);
}
if(val!=0) {
node.n = val;
node.next = list;
return read_numbers(&node);
}
} else {
if(ferror(stdin)) {
perror("standard input");
exit(EXIT_FAILURE);
}
/* Naughty user sent EOF; pretend it was a 0 but with a warning */
fprintf(stderr, "Didn't get 0 terminator. List may be incomplete\n");
}

for(i=0,p=list;p;++i,p=p->next)
/*nothing*/;
ret = malloc(i * sizeof *ret);
if(!ret) {
perror("malloc");
exit(EXIT_FAILURE);
}
for(--i,p=list;p;--i,p=p->next)
ret = p->n;
return ret;
}

int main(void)
{
int *numbers,*p;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
p=numbers;
while (*p) printf("%d\n",*p++);
return 0;
}

// gcc -D_GNU_SOURCE -Wall -Wextra ac2.c -o out
dan@dan-desktop:~/source/unleashed/ch11$

Again with input as above, can we cheat in main somehow to determine how
many integers are in this array?

 

[Phred Phungus]

There is no variable named "list" in the entire program. There is a
struct named 'list' which is visible to the entire unit.

Tom

So it doesn't go away until the entire program does, right?

 

[Alan Curry]

|>
|> In the very same article in which I posted it, I listed 3 reasons why the
|> challenge (i.e. make a growable list/array-ish data structure without
|> realloc) was stupid. And I also explained the particular shortcoming of my
|> code which I was too lazy to fix: it provides no way for the caller to know
|> how big the list is.
|
|You mentioned passing a counter to a recursive function.
|
|I didn't see a better posting than yours, and now it's Feb. 9 east of
|Chicago.

What part of everything I just said did you not understand?

Every program posted in that thread was awful, because the thread was
centered around a challenge to write a program around a ridiculous
restriction. The result is: the program comes out ugly.

|>
|> Yet somehow you missed all of that, and decided to hold on to that code and
|> treat it as if it was worthy of further study, and start a new thread
|> dedicated to analyzing it. Woosh!
|>

Double woosh.

|
|I'm having trouble hooking up data structures with a platform and
|extensions that are somewhat new to me. So I look for simpler toy
|programs that do something similar.

This is not a toy. Just a bad program, written in response to a challenge
whose rules guaranteed that only bad programs would be submitted. Keep out of
reach of children. Do not taunt happy fun ball.

|
|It's not hard to mistake differing forms of lists. I was hoping to do
|something with this from Unleashed:

"Do something"?

|
|//c11_022.c - naive single linked list, using an array.
|#include <stdio.h>
|
|typedef struct ITEM
|{
| char Title[30];
| char Author[30];
| int Next;
|} ITEM;
|
|int main(void)
|{
| ITEM List[] =

This demonstrates something more useful: that an array plus an index is a lot
like a pointer, and if the array (base address) is implied (because all of
your structures live in one big array) then you can use integers as if they
were pointers, just by adding the base address when you need to dereference.

This one is the opposite of the "crazy recursion" program. It really is a
toy. You won't see statically-sized linked lists, initialized at compile
time, in grownup programs.

But the use of integers as pointers inside a cluster of objects with a common
base address isn't necessarily "naive". It's serialized! Ready to be
relocated with memcpy, or transferred to another process as a single hunk,
since the contents are not dependent on memory location.

 

[Nick Keighley]

Phred Phungus wrote:

I think the classification for what is a singly-linked list must be
fairly broad.  In this, there aren't new nodes created dynamically.

['this' is an illustration of the linked-list concept that uses an array
as the container]

Right. The concept of "linked list" depends purely on each item having a
link to some other item (or items) in the list so that a logical linear
progression exists. There's nothing in the rules that says the links
have to be pointers, or that the list has to be capable of arbitrary
expansion, or anything else.

I learnt my data structures by "emulating" pointers with indexes into
large arrays. This was because the language used didn't have pointers.
In fact I wasn't even aware that this *was* a pointer emulation as I
didn't know about pointers either. I don't think it did me much harm
as far as learning about data structures and algorithms went.

 

[Nick Keighley]

Note well... "should not be used"

"useless for any practical purpose"

You mentioned passing a counter to a recursive function.

I didn't see a better posting than yours, and now it's Feb. 9 east of
Chicago.

better for what? What are you trying to do? It's Feb 9 east of London
as well.

I'm having trouble hooking up data structures with a platform and
extensions that are somewhat new to me.

data structures are pretty independent of platform extensions (or
should be). Are you learning data structures or platform extensions?
I'd try to learn one at a time.

So I look for simpler toy programs that do something similar.

simpler than what? similar to what?

It's not hard to mistake differing forms of lists.  

mistake for what? Differing in what way?

I was hoping to do
something with this from Unleashed:

what's something?

//c11_022.c - naive single linked list, using an array.
#include <stdio.h>

typedef struct ITEM
{
   char Title[30];
   char Author[30];
   int Next;

} ITEM;

int main(void)
{
   ITEM List[] =
   {
     {"UNIX Unleashed", "Burk and Horvath", 2},

[...]
{"Expert C Programming", "van der Linden", -1},

   };

   int Current = 0;

   while(Current != -1)
   {
     printf("Read %s, by %s.\n",
            List[Current].Title,
            List[Current].Author);
     Current = List[Current].Next;
   }

   return 0;

}

//  gcc  -D_GNU_SOURCE -Wall -Wextra ll1.c -o out

I think the classification for what is a singly-linked list must be
fairly broad.  In this, there aren't new nodes created dynamically.

not a necessisity of link lists. But in practice a major reason for
using linked lists is their easy extensibility.

I think you need a goal (or if you have one, you need to articulate
it!)

 

[Keith Thompson]

In the following program:

dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac1.c -o out

[snip]

dan@dan-desktop:~/source/unleashed/ch11$ gcc -D_GNU_SOURCE -Wall
-Wextra ac2.c -o out

[snip]

Either you're posting here under two different names, "Phred Phungus"
and "frank", or we have a remarkable coincidence.

In the interests of coherent communication, please post under just one
name. It doesn't have to be your real one, just consistent.

Thanks.

 

[bartc]

node.next = list; ++count;

Again with input as above, can we cheat in main somehow to determine how
many integers are in this array?

If you really want to cheat, just declare an int count, at file scope, and
increment it as above.

Then main() becomes:

int main(void)
{
int i;
int *numbers,*p;
count=0;
numbers = read_numbers(0);
/* do stuff with numbers[] I guess */
p=numbers;
for (i=0; i<count; ++i) printf("%d\n",*p++);
return 0;
}

This is bad programming however. Better to add an extra parameter to
read_numbers(), a location to return a count. Or just add an extra zero
value to the end of the array (since zero can't be an input value).

 

[Kaz Kylheku]

So it doesn't go away until the entire program does, right?

Since it is a type, ``struct list'' goes away before the program even
starts,

A common feature of C programming environments is that types may be
retained in the form of debugging information, but that's not required
by the language.

 

[Phred Phungus]

Since it is a type, ``struct list'' goes away before the program even
starts,

A common feature of C programming environments is that types may be
retained in the form of debugging information, but that's not required
by the language.

ok. the object doesn't die till the bitter end, right?

 

[Ian Collins]

ok. the object doesn't die till the bitter end, right?

Don't confuse a type and an instance of a type. "struct list" is a type.

As Kaz says, there may be meta-data describing the type somewhere in the
executable, but that isn't an instance of the type, it is an artefact of
the implementation.

 

[Phred Phungus]

Phred Phungus wrote:

I think the classification for what is a singly-linked list must be
fairly broad. In this, there aren't new nodes created dynamically.

['this' is an illustration of the linked-list concept that uses an array
as the container]

Right. The concept of "linked list" depends purely on each item having a
link to some other item (or items) in the list so that a logical linear
progression exists. There's nothing in the rules that says the links
have to be pointers, or that the list has to be capable of arbitrary
expansion, or anything else. As far as the *concept* is concerned,
that's fluff. Highly important and significant fluff from a practical
point of view, but fluff nonetheless from the perspective of what
actually constitutes a linked list.

You have probably already noted that, in your source text, the author of
your example points out that the array implementation is "naive", and
shortly moves on to present pointer-based lists.

That's what I was thinking as I fell asleep last night, having failed on
most things. The reason I wasn't finding it was that the driver was in
a different place, but that place is covered on p 381.

First of all, I'd like to apologize to Alan for reposting code he didn't
want to see again. Alan is both helpful and knowledgable. I think I
have the C program I was looking for with this thread, which appears on
the source disc for unleashed:

dan@dan-desktop:~/source/unleashed/ch11$ gcc ll1.o -D_GNU_SOURCE -Wall
-Wextra sl2.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ ./out
Read UNIX Unleashed, by Burk and Horvath
Read Builder Unleashed, by Calvert
Read C: How to Program, by Deitel & Deitel
Read DOS Programmers Reference, by Dettmann & Johnson
Read C : A Reference Manual, by Harbison & Steele
Read C Unleashed, by Heathfield & Kirby
Read Linux Unleashed, by Husain and Parker
Read C Programming Language, by Kernighan & Ritchie
Read Data Structures & Algorithms, by Lafore
Read C++ Unleashed, by Liberty
Read The Standard C Library, by Plauger
Read Teach Yourself BCB, by Reisdorph
Read Algorithms in C, by Sedgewick
Read C++ Programming Language, by Stroustrup
Read C Programming FAQs, by Summit
Read Expert C Programming, by van der Linden

Removing title C++ Unleashed

Read UNIX Unleashed, by Burk and Horvath
Read Builder Unleashed, by Calvert
Read C: How to Program, by Deitel & Deitel
Read DOS Programmers Reference, by Dettmann & Johnson
Read C : A Reference Manual, by Harbison & Steele
Read C Unleashed, by Heathfield & Kirby
Read Linux Unleashed, by Husain and Parker
Read C Programming Language, by Kernighan & Ritchie
Read Data Structures & Algorithms, by Lafore
Read The Standard C Library, by Plauger
Read Teach Yourself BCB, by Reisdorph
Read Algorithms in C, by Sedgewick
Read C++ Programming Language, by Stroustrup
Read C Programming FAQs, by Summit
Read Expert C Programming, by van der Linden
dan@dan-desktop:~/source/unleashed/ch11$ cat sl2.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 sl2.c -o out
dan@dan-desktop:~/source/unleashed/ch11$ 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:
* (e-mail address removed)
*
*/


#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
dan@dan-desktop:~/source/unleashed/ch11$

With a listing like this, I think one needs to the the header, so that
you know how the functions are declared, but the definitions are just a
mile of code at this point, given that compile, link, and test.

 

[Phred Phungus]

not a necessisity of link lists. But in practice a major reason for
using linked lists is their easy extensibility.

I think you need a goal (or if you have one, you need to articulate
it!)

My goals for this program are outside the purview of clc. My goal for
this thread is to figure out how to effectively call them. It turns out
you need to design the nodes properly, or you have precisely the problem
that afflicted the possible solutions to Stefan's challenge.

No one wanted to comment on this, but the next thing for me with C is to
see whether this is a base that gets covered by Heathfield's sllist.

I make huge mistakes when I disect what happens with this stuff, and
lots of the whoopsies happen because I'm misinterpreting my platform.

"XML is isomorphic to the subset of Lisp data
where the first item in a list is required to be atomic."
John McCarthy

I just started dinking around with lisp. What does he mean here?