468,737 Members | 1,790 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,737 developers. It's quick & easy.

Using a link list over an array.

Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.

the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;

I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.

with an array eg. raylist[some_size] when i trace the rays, i do the
following :

for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}

I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.

I was thinking that using a link list may help my situation a little
bit here.

ray *p;
ray *q;
p = ray_list_head_ptr; /* ray_list_head_ptr points to the first node
in link list */

while( p != NULL)
{
/* trace the ray pointed by p */
q = p;
p = p->next;
/* Now the ray pointed by q is of no use so free that memory and
make the node pointed by p as the first node of the ray list */
free(q);
ray_list_head_ptr = p;
}
Jun 27 '08 #1
36 2533
pereges <Br*****@gmail.comwrites:
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.

the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;

I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.

with an array eg. raylist[some_size] when i trace the rays, i do the
following :

for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}
You may not need to store them at all. In once version I saw, the
data in raylist[i] seemed to be determined by i (in effect the
position of the ray in a fixed grid). If this is the case, just make
the ray at the point of use.

You only need to store them if the computation uses them all at once
(or in nearly at once). For example, if computing raylist[i] is
easier knowing ralylist[0] ... raylist[i-1].
I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.

I was thinking that using a link list may help my situation a little
bit here.
It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.

--
Ben.
Jun 27 '08 #2

"pereges" <Br*****@gmail.comwrote in message
news:f5**********************************@z16g2000 prn.googlegroups.com...
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.
I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.
Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?

--
bartc
Jun 27 '08 #3
Ben Bacarisse <be********@bsb.me.ukwrites:
pereges <Br*****@gmail.comwrites:
>Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.

the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;

I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.

with an array eg. raylist[some_size] when i trace the rays, i do the
following :

for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}

You may not need to store them at all. In once version I saw, the
data in raylist[i] seemed to be determined by i (in effect the
position of the ray in a fixed grid). If this is the case, just make
the ray at the point of use.

You only need to store them if the computation uses them all at once
(or in nearly at once). For example, if computing raylist[i] is
easier knowing ralylist[0] ... raylist[i-1].
>I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.

I was thinking that using a link list may help my situation a little
bit here.

It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.
Even the pattern of access is slower the linked list is likely to be
slower as well. Dont forget things like virtual memory coming into play
as he traverses his list on top of the overhead of reading new points
and moving to the next ray.

Jun 27 '08 #4
On Jun 19, 5:00 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.
On Jun 19, 5:00 pm, "Bartc" <b...@freeuk.comwrote:
Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?

Good idea. I think I will create them on the fly, trace them and free
them as soon as their purpose is over.
Jun 27 '08 #5
pereges <Br*****@gmail.comwrites:
On Jun 19, 5:00 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.
I also wrote (in the same message):

| You may not need to store them at all. In once version I saw, the
| data in raylist[i] seemed to be determined by i (in effect the
| position of the ray in a fixed grid). If this is the case, just make
| the ray at the point of use.
On Jun 19, 5:00 pm, "Bartc" <b...@freeuk.comwrote:
>Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?

Good idea. I think I will create them on the fly, trace them and free
them as soon as their purpose is over.
I would have been nice if you had quoted the fact that I made the same
suggestion that you considered to be a good idea rather than the part
that is probably not of any use :-)

--
Ben.
Jun 27 '08 #6
On Thu, 19 Jun 2008 11:36:57 UTC, pereges <Br*****@gmail.comwrote:
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
Arrays are fine when
- the nuber of elements needed is constant
- all memers are in use while the array exists
- no or at least rare resorting of the array is needed
- the number of elements is low
because sorting off array costs many moves of many members
as sorting by moving array member around is reall time exensive

lists are fine when
- you've no idea how many members the list may contain
its easy to shrink or increase the number of elements
- a unknown number of elements will go out of usage
while other lives in usage
- the number of elements in use changes heavely
during the time the list exists
- resorting is needed more ofen
moving pointers around is quick, at lest more quickly
as complete array members. Sorted insert/delete of a
a single member costs only changing a handful pointers
instead of moving up to O(n) array mebers up or down
- its more easy to split and join lists than whole arrays

At least there is no "what is better"? Sometimes arrays and sometimes
lists are better, strictly bounded on the usaga of the usage of the
data.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!
Jun 27 '08 #7
On Jun 20, 11:37 pm, "Herbert Rosenau" <os2...@pc-rosenau.dewrote:
On Thu, 19 Jun 2008 11:36:57 UTC, pereges <Brol...@gmail.comwrote:
Hi, I am wondering which of the two data structures (linklistor
array) would be better in my situation. I have to create alistof
rays for my ray tracing program.

Arrays are fine when
- the nuber of elements needed is constant
- all memers are in use while the array exists
- no or at least rare resorting of the array is needed
- the number of elements is low
becausesortingoff array costs many moves of many members
assortingby moving array member around is reall time exensive

lists are fine when
- you've no idea how many members thelistmay contain
its easy to shrink or increase the number of elements
- a unknown number of elements will go out of usage
while other lives in usage
- the number of elements in use changes heavely
during the time thelistexists
- resorting is needed more ofen
moving pointers around is quick, at lest more quickly
as complete array members. Sorted insert/delete of a
a single member costs only changing a handful pointers
instead of moving up to O(n) array mebers up or down
- its more easy to split and join lists than whole arrays

At least there is no "what is better"? Sometimes arrays and sometimes
lists are better, strictly bounded on the usaga of the usage of the
data.
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.
Jun 30 '08 #8
pereges wrote:
>
Is it easier to sort link lists as opposed to arrays ??
This isn't a C question, but it's easy to sort either
data structure.
In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.
That's nice. I've seen stupid things, too.

(If you want to learn about sorting and data structures and
other such language-independent topics, comp.programming would be
a better forum than a language-specific newsgroup. There's also
the revolutionary notion of consulting a book ...)

--
Er*********@sun.com
Jun 30 '08 #9
pereges wrote:
>
.... snip ...
>
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that
even accessing a single Nth node required n-1 passes.
Sorting lists is easy, and O(NlogN). See the following code:

/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */
/* end listops.c */

and the header file:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h/* NULL */
#include <iso646.h/* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */

#endif
/* end listops.h */

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 1 '08 #10
On Jul 1, 8:03 am, CBFalconer <cbfalco...@yahoo.comwrote:
pereges wrote:

... snip ...
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that
even accessing a single Nth node required n-1 passes.

Sorting lists is easy, and O(NlogN). See the following code:

/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;

} /* revlist */

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;

} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;

} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;} /* mergesort */

/* end listops.c */

and the header file:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h/* NULL */
#include <iso646.h/* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */

#endif
/* end listops.h */

Hello, I tried to use your program to sort a list a vectors based on
their x coordinate but it seems only a part of the list was sorted.

This is vector data structure:

typedef struct
{
double coord[3]; /* 0 - x 1 - y 2 -z */

}vector;

Then I try to create the link list of nvert vertices stored in
array vert[0..nvert-1] using the node structure defined in listops.h:

node *p, *head = NULL;
node *prev;
int i;
for(i = 0; i < nvert; i++)
{
p = malloc(sizeof(node));
p->next = NULL;
p->data = &vert[i]; /* Store the address of the vector in p-
>data */
if(head == NULL)
{
head = p;
prev = head;
}
else
{
prev->next = p;
prev = p;
}
}

Now, each node contains a data pointer which points to a vector in
vert[]. Here's the comp function I used to sort
on basis of x coordinate i.e. coord[0] member :

int comp(void *vpa, void *vpb)
{
node *a = (node *) vpa;
node *b = (node *)vpb;

vector *va = (vector *) (a->data);
vector *vb = (vector *) (b->data);

return (va->coord[0] < vb->coord[0] ? -1 : va->coord[0] vb-
>coord[0]);
}

then I applied the mergesort:

mergesort(head, comp);

I check the result using:

p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-
>coord[2]);
p = p->next;
}

and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.
Jul 1 '08 #11
pereges wrote:
>
.... snip ...
>
then I applied the mergesort:

mergesort(head, comp);

I check the result using:

p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-
coord[2]);++
p = p->next;
}

and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.
I didn't read your code in detail, but simply noted the above.
mergesort is a function, and it returns a pointer to the head of
the sorted list. You discarded the result.

The simplest way to build the list is by adding items at the head

nodeptr listhead = NULL;
nodeptr temp;
...
while (another item to store) {
temp = malloc(sizeof *temp);
temp->next = listhead;
temp->datum = newitem;
listhead = temp;
}

after which listhead points to the unsorted list. After:

listhead = mergesort(listhead, cmpfunction());

that list is sorted. You have to supply the proper cmpfunction for
your data.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 1 '08 #12
On Jul 1, 4:49 pm, CBFalconer <cbfalco...@yahoo.comwrote:
pereges wrote:

... snip ...
then I applied the mergesort:
mergesort(head, comp);
I check the result using:
p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-
>coord[2]);++
p = p->next;
}
and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.

I didn't read your code in detail, but simply noted the above.
mergesort is a function, and it returns a pointer to the head of
the sorted list. You discarded the result.

The simplest way to build the list is by adding items at the head

nodeptr listhead = NULL;
nodeptr temp;
...
while (another item to store) {
temp = malloc(sizeof *temp);
temp->next = listhead;
temp->datum = newitem;
listhead = temp;
}

after which listhead points to the unsorted list. After:

listhead = mergesort(listhead, cmpfunction());

that list is sorted. You have to supply the proper cmpfunction for
your data.
Sorry I missed that bit of information. I checked again and it works
perfectly. Btw, I'm a little confused between qsort on array and merge
sort on link list. Which in your opinion is better ? From my project's
point of view, there seems to be some very obvious advantages.

Jul 1 '08 #13
pereges <Br*****@gmail.comwrites:
On Jul 1, 8:03 am, CBFalconer <cbfalco...@yahoo.comwrote:
>pereges wrote:
<snip>
Is it easier to sort link lists as opposed to arrays ??
<snip>
>Sorting lists is easy, and O(NlogN). See the following code:
<snip>
>/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;
<snip>
Hello, I tried to use your program to sort a list a vectors based on
their x coordinate but it seems only a part of the list was sorted.
<snip>
then I applied the mergesort:

mergesort(head, comp);

I check the result using:

p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-
>>coord[2]);
p = p->next;
}
With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key code.
Maybe the problem is in that part not shown.
and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.
--
Ben.
Jul 1 '08 #14
On Jul 1, 6:35 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>
With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key code.
Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes

/* creating the link list */

node *p, *head = NULL;
int i = 0;

while (i < m->nvert)
{
p = malloc(sizeof *p);
p->next = head;
p->data = &m->vert[i];
head = p;
i++;
}

/* Sorting link list */

head = mergesort(head, cmp);
p = head;

/* Printing the vectors using soreted link list */
while (p != NULL)
{
vector_print(p->data);
p = p->next;
}

/* cmp function */

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}

The above cmp function sorts w.r.t the coord[1] member. Similarly, I
will write functions for coord[0] or coord[2].
Jul 1 '08 #15
pereges wrote:
On Jul 1, 6:35 pm, Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key code.
Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);
int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:

int cmp(const node *vpa, const node *vpb)
{
const vector *const a = vpa -data;
const vector *const b = vpb -data;

return b->coord[1] a->coord[1] ? -1
: b->coord[1] != a->coord[1];
}

The comparison function for a list
is not interchangable with that used for qsort,
so there's no reason why it should take the same type of arguments.

The arguments passed to the comparison function for a list
will always be pointers to list nodes,
so the comparison function for a list
should take pointers to list nodes as arguments.

--
pete
Jul 1 '08 #16
pereges wrote:
CBFalconer <cbfalco...@yahoo.comwrote:
.... snip ...
>>
I didn't read your code in detail, but simply noted the above.
mergesort is a function, and it returns a pointer to the head of
the sorted list. You discarded the result.

The simplest way to build the list is by adding items at the head

nodeptr listhead = NULL;
nodeptr temp;
...
while (another item to store) {
temp = malloc(sizeof *temp);
temp->next = listhead;
temp->datum = newitem;
listhead = temp;
}

after which listhead points to the unsorted list. After:

listhead = mergesort(listhead, cmpfunction());

that list is sorted. You have to supply the proper cmpfunction for
your data.

Sorry I missed that bit of information. I checked again and it works
perfectly. Btw, I'm a little confused between qsort on array and merge
sort on link list. Which in your opinion is better ? From my project's
point of view, there seems to be some very obvious advantages.
That depends on the natural form to hold your data. If you have no
idea how much of it is coming in, a list is obviously an easier
input mechanism. Since the O() number is the same for both
quiksort, heapsort, and mergesort (and others) there is a minor
difference in speed.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 1 '08 #17
pete wrote:
pereges wrote:
>Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>>With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key
code. Maybe the problem is in that part not shown.

Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}

It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data. It just needs to know how to decide which is
larger. Also the mergesort function itself is very general, and
doesn't require unnecessary rework of the list. See the code I
published for listops.c

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 1 '08 #18
CBFalconer <cb********@yahoo.comwrites:
pete wrote:
>pereges wrote:
>>Ben Bacarisse <ben.use...@bsb.me.ukwrote:

With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key
code. Maybe the problem is in that part not shown.

Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}

It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:

I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort.
Only if the data is indirect -- can be pointed to by a void *.
It doesn't need to know anything
about the data.
You can't use it (portably) to sort a list of ints where the int is
inside the node or indeed any node that contains the actual data. I
suspect this sort of thing matters to pete.
It just needs to know how to decide which is
larger. Also the mergesort function itself is very general, and
doesn't require unnecessary rework of the list. See the code I
published for listops.c
--
Ben.
Jul 1 '08 #19
CBFalconer wrote:
pete wrote:
>pereges wrote:
>>Ben Bacarisse <ben.use...@bsb.me.ukwrote:

With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key
code. Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:

I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data.
What kind of data do you think that
int (*cmp)(node *, node *);
is special for?

--
pete
Jul 2 '08 #20
Ben Bacarisse wrote:
CBFalconer <cb********@yahoo.comwrites:
>pete wrote:
>>pereges wrote:
Ben Bacarisse <ben.use...@bsb.me.ukwrote:

With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key
code. Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort.

Only if the data is indirect -- can be pointed to by a void *.
> It doesn't need to know anything
about the data.

You can't use it (portably) to sort a list of ints where the int is
inside the node or indeed any node that contains the actual data. I
suspect this sort of thing matters to pete.
Other way.
You can use it to sort a list of pointers to any type.
/*
** sort a list of pointers to vector
*/
int cmp(const node *vpa, const node *vpb)
{
const vector *const a = vpa -data;
const vector *const b = vpb -data;

return b->coord[1] a->coord[1] ? -1
: b->coord[1] != a->coord[1];
}

/*
** sort a list of pointers to long double
*/
int cmp(const node *vpa, const node *vpb)
{
const long double *const a_Lf_ptr = vpa -data;
const long double *const b_Lf_ptr = vpb -data;

return *b_Lf_ptr *a_Lf_ptr ? -1 : *b_Lf_ptr != *a_Lf_ptr;
}

/*
** sort a list of pointers to string representations of long unsigned
*/
int cmp(const node *vpa, const node *vpb)
{
const long unsigned a_num = strtoul(vpa -data, NULL, 10);
const long unsigned b_num = strtoul(vpb -data, NULL, 10);

return b_num a_num ? -1 : b_num != a_num;
}

--
pete
Jul 2 '08 #21
pete wrote:
Ben Bacarisse wrote:
>CBFalconer <cb********@yahoo.comwrites:
>>pete wrote:
pereges wrote:
Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>
>With CBFalconer's definition of a node, the code above will not
>compile (p->data is a void *) so you have not shown us some key
>code. Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);
>
int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;
>
vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);
>
if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort.

Only if the data is indirect -- can be pointed to by a void *.
>> It doesn't need to know anything
about the data.

You can't use it (portably) to sort a list of ints where the int is
inside the node or indeed any node that contains the actual data. I
suspect this sort of thing matters to pete.

Other way.
You can use it to sort a list of pointers to any type.
/*
** sort a list of pointers to string representations of long unsigned
*/
/* BEGIN file_sort_2.c */
/*
From news:comp.lang.c
program that reads 3 list of numbers,
which are stored in three seperate files,
and creates one sorted list.
Each file should contain not more than 15 numbers.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define NFILES 3
#define MAX_LINES_PER_FILE 15
#define LU_RAND_SEED 0LU
#define LU_RAND(S) ((S) * 69069LU + 362437 & 0XFFFFFFFF)
#define NMEMB(A) (sizeof (A) / sizeof *(A))

struct list_node {
struct list_node *next;
void *data;
};

typedef struct list_node list_type;

int numcomp(const list_type *a, const list_type *b);
int get_line(char **lineptr, size_t *n, FILE *stream);
int list_fputs(const list_type *node, FILE *stream);
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size);
void list_free(list_type *node, void (*free_data)(void *));
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_list (list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
static list_type *split_list(list_type *head);

int main(void)
{
int rc;
char fn[L_tmpnam];
FILE *fp;
long unsigned index, line;
long unsigned lu_seed = LU_RAND_SEED;
char *buff = NULL;
size_t size = 0;
list_type *head = NULL;
list_type *tail = NULL;

puts("/* BEGIN file_sort_2.c output */");
/*
** Open temporary input text files for writing.
** Write long unsigned values to standard output
** as well as to temporary input text files.
** Close each file after filling with long unsigned values.
** Open input text files for reading.
** Represent each line of each input text file
** as a string in a node of a linked list.
** Close each temp input file after reading.
*/
tmpnam(fn);
for (index = 0; index != NFILES; ++index) {
fp = fopen(fn, "w");
if (fp == NULL) {
fputs("fopen(fn, \"w\") == NULL\n", stderr);
break;
}
printf("\nInput file #%lu\n", index + 1);
line = lu_seed % MAX_LINES_PER_FILE + 1;
while (line-- != 0) {
lu_seed = LU_RAND(lu_seed);
fprintf( fp, "%lu\n", lu_seed);
fprintf(stdout, "%lu\n", lu_seed);
}
fclose(fp);
fp = fopen(fn, "r");
if (fp == NULL) {
fputs("fopen(fn, \"r\") == NULL\n", stderr);
break;
}
while ((rc = get_line(&buff, &size, fp)) 0) {
tail = list_append(&head, tail, buff, rc);
if (tail == NULL) {
fputs("tail == NULL\n", stderr);
break;
}
}
fclose(fp);
if (rc != EOF) {
fprintf(stderr, "rc == %d\n", rc);
break;
}
}
/*
** Free allocated buffer used by get_line function.
** Remove temp input file.
*/
free(buff);
remove(fn);
/*
** Sort list.
** Display list.
** Free list.
*/
head = list_sort(head, numcomp);
puts("\nSorted Output List");
list_fputs(head, stdout);
list_free(head, free);
puts("\n/* END file_sort_2.c output */");
return 0;
}

int numcomp(const list_type *a, const list_type *b)
{
const long unsigned a_num = strtoul(a -data, NULL, 10);
const long unsigned b_num = strtoul(b -data, NULL, 10);

return b_num a_num ? -1 : b_num != a_num;
}

int get_line(char **lineptr, size_t *n, FILE *stream)
{
int rc;
void *p;
size_t count;
/*
** The (char) casts in this function are not required
** by the rules of the C programming language.
*/
count = 0;
while ((rc = getc(stream)) != EOF
|| !feof(stream) && !ferror(stream))
{
++count;
if (count == (size_t)-2) {
if (rc != '\n') {
(*lineptr)[count] = '\0';
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
}
break;
}
if (count + 2 *n) {
p = realloc(*lineptr, count + 2);
if (p == NULL) {
if (*n count) {
if (rc != '\n') {
(*lineptr)[count] = '\0';
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
}
} else {
if (*n != 0) {
**lineptr = '\0';
}
ungetc(rc, stream);
}
count = 0;
break;
}
*lineptr = p;
*n = count + 2;
}
if (rc != '\n') {
(*lineptr)[count - 1] = (char)rc;
} else {
(*lineptr)[count - 1] = '\0';
break;
}
}
if (rc != EOF || !feof(stream) && !ferror(stream)) {
rc = INT_MAX count ? count : INT_MAX;
} else {
if (*n count) {
(*lineptr)[count] = '\0';
}
}
return rc;
}

int list_fputs(const list_type *node, FILE *stream)
{
int rc = 0;

while (node != NULL
&& (rc = fputs(node -data, stream)) != EOF
&& (rc = putc('\n', stream)) != EOF)
{
node = node -next;
}
return rc;
}

list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size)
{
list_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -next = NULL;
node -data = malloc(size);
if (node -data != NULL) {
memcpy(node -data, data, size);
if (*head != NULL) {
tail -next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}

void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_list(head, compar) : head;
}

static list_type *sort_list(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
list_type *tail;

if (head -next != NULL) {
tail = split_list(head);
tail = sort_list(tail, compar);
head = sort_list(head, compar);
head = merge_lists(head, tail, compar);
}
return head;
}

static list_type *split_list(list_type *head)
{
list_type *tail;

tail = head -next;
while ((tail = tail -next) != NULL
&& (tail = tail -next) != NULL)
{
head = head -next;
}
tail = head -next;
head -next = NULL;
return tail;
}

static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) 0 ? &tail : &head;
list = sorted = *node;
*node = sorted -next;
while (*node != NULL) {
node = compar(head, tail) 0 ? &tail : &head;
sorted -next = *node;
sorted = *node;
*node = sorted -next;
}
sorted -next = tail != NULL ? tail : head;
return list;
}

/* END file_sort_2.c */
--
pete
Jul 2 '08 #22
pete <pf*****@mindspring.comwrites:
Ben Bacarisse wrote:
>CBFalconer <cb********@yahoo.comwrites:
>>pete wrote:
pereges wrote:
Ben Bacarisse <ben.use...@bsb.me.ukwrote:
>
>With CBFalconer's definition of a node, the code above will not
>compile (p->data is a void *) so you have not shown us some key
>code. Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);
>
int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;
>
vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);
>
if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort.

Only if the data is indirect -- can be pointed to by a void *.
>> It doesn't need to know anything
about the data.

You can't use it (portably) to sort a list of ints where the int is
inside the node or indeed any node that contains the actual data. I
suspect this sort of thing matters to pete.

Other way.
You can use it to sort a list of pointers to any type.
OK, I need some help now... At first glance that is possible with
CBFalconer's compare function prototype.
/*
** sort a list of pointers to vector
*/
int cmp(const node *vpa, const node *vpb)
{
const vector *const a = vpa -data;
const vector *const b = vpb -data;

return b->coord[1] a->coord[1] ? -1
: b->coord[1] != a->coord[1];
}

/*
** sort a list of pointers to long double
*/
int cmp(const node *vpa, const node *vpb)
{
const long double *const a_Lf_ptr = vpa -data;
const long double *const b_Lf_ptr = vpb -data;

return *b_Lf_ptr *a_Lf_ptr ? -1 : *b_Lf_ptr != *a_Lf_ptr;
}

/*
** sort a list of pointers to string representations of long unsigned
*/
int cmp(const node *vpa, const node *vpb)
{
const long unsigned a_num = strtoul(vpa -data, NULL, 10);
const long unsigned b_num = strtoul(vpb -data, NULL, 10);

return b_num a_num ? -1 : b_num != a_num;
}
All of these are possible with CBFalconer's cmp function prototype are
they not? Have I missed a flaw with it?

If nodes that contain the data (my example) are not the reason to
prefer a node *, what is?

--
Ben.
Jul 2 '08 #23
pete <pf*****@mindspring.comwrites:
/* BEGIN file_sort_2.c */
What is the point of posting yards of code (three large messages now)?
I am entirely in agreement that passing a pair of node *s to the
comparison function is an excellent way to proceed. More code will
not make me more sure of that. If you think I have misunderstood
something, please say (in words) what you think that is.

--
Ben.
Jul 2 '08 #24
Ben Bacarisse wrote:
pete <pf*****@mindspring.comwrites:
>/* BEGIN file_sort_2.c */

What is the point of posting yards of code (three large messages now)?
I may have been riled a little, by someone not you,
who I knew wouldn't make any attempt
to understand what I was saying.
I am entirely in agreement that passing a pair of node *s to the
comparison function is an excellent way to proceed.
I know.
Thank you.

--
pete
Jul 2 '08 #25
pete wrote:
CBFalconer wrote:
.... snip ...
>
>I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data.

What kind of data do you think that
int (*cmp)(node *, node *);
is special for?
A node*, which gives the compare function access to the next field,
and also means the compare function needs to know the definition of
a node. It doesn't need any of this, it just needs a pointer to
the const data. Mergesort doesn't need to know the form of the
data, and thus uses const void* pointers. That way errors in
writing the compare won't foul things up.

Think about it. The compare function should compare two
thingummies. It doesn't need to be a special function for the
sort. It doesn't need to know about nodes. It certainly doesn't
care where the next node is. For all you know the data may be
encoded names, needing decoding, translation, etc.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 2 '08 #26
CBFalconer <cb********@yahoo.comwrites:
pete wrote:
>CBFalconer wrote:
... snip ...
>>
>>I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data.

What kind of data do you think that
int (*cmp)(node *, node *);
is special for?

A node*, which gives the compare function access to the next field,
and also means the compare function needs to know the definition of
a node. It doesn't need any of this, it just needs a pointer to
the const data. Mergesort doesn't need to know the form of the
data, and thus uses const void* pointers. That way errors in
writing the compare won't foul things up.

Think about it. The compare function should compare two
thingummies. It doesn't need to be a special function for the
sort. It doesn't need to know about nodes. It certainly doesn't
care where the next node is. For all you know the data may be
encoded names, needing decoding, translation, etc.
It is never quite that simple. Your interface restricts mergesort to
those lists that use indirect data. It is possible to remove this
restriction -- the simplest way is (in part) to pass node pointers to
the compare function. Passing a void * (stored in the node) is not
100% general.

--
Ben.
Jul 2 '08 #27
CBFalconer wrote:
pete wrote:
>CBFalconer wrote:
... snip ...
>>I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data.
What kind of data do you think that
int (*cmp)(node *, node *);
is special for?

A node*, which gives the compare function access to the next field,
and also means the compare function needs to know the definition of
a node. It doesn't need any of this, it just needs a pointer to
the const data. Mergesort doesn't need to know the form of the
data, and thus uses const void* pointers. That way errors in
writing the compare won't foul things up.

Think about it. The compare function should compare two
thingummies. It doesn't need to be a special function for the
sort. It doesn't need to know about nodes. It certainly doesn't
care where the next node is. For all you know the data may be
encoded names, needing decoding, translation, etc.
Your mergesort can only call cmp with arguments of type nodeptr,
never with any other type of argument.
That's why it should be
int (*cmp)(nodeptr , nodeptr )

nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
I wrote
int (*cmp)(node *, node *);
before, because pereges' code
is referring to his node pointers as (node *).

--
pete
Jul 2 '08 #28
Ben Bacarisse wrote:
CBFalconer <cb********@yahoo.comwrites:
>pete wrote:
>>CBFalconer wrote:
... snip ...
>>>
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort. It doesn't need to know anything
about the data.

What kind of data do you think that
int (*cmp)(node *, node *);
is special for?

A node*, which gives the compare function access to the next field,
and also means the compare function needs to know the definition of
a node. It doesn't need any of this, it just needs a pointer to
the const data. Mergesort doesn't need to know the form of the
data, and thus uses const void* pointers. That way errors in
writing the compare won't foul things up.

Think about it. The compare function should compare two
thingummies. It doesn't need to be a special function for the
sort. It doesn't need to know about nodes. It certainly doesn't
care where the next node is. For all you know the data may be
encoded names, needing decoding, translation, etc.

It is never quite that simple. Your interface restricts mergesort to
those lists that use indirect data. It is possible to remove this
restriction -- the simplest way is (in part) to pass node pointers to
the compare function. Passing a void * (stored in the node) is not
100% general.
It's not really worth arguing over. To me, the fact that the
construction of a node allows any list and data to be expressed,
and that the system doesn't pass about unneeded data or access, is
more than sufficient. I can concede that others have different
objectives.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 2 '08 #29
btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?
Jul 2 '08 #30
btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?
Jul 2 '08 #31
btw since i saw it pete's code, isn't the static declaration of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?
Jul 2 '08 #32
pereges wrote:
btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?
It's because I grabbed it out a small library
where only six of the list functions are public.

I prefer my public list functions to treat NULL
as a pointer to a list of zero length.
My static list functions don't do that.
They are written only to be called
from the public functions
which don't generate calls with NULL arguments.

merge_lists, which is one of the static functions
that you've seen posted as one of the helper functions
for list_sort, isn't made to handle a zero length list.
This is its public interface:

list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
if (tail != NULL) {
if (head != NULL) {
head = merge_lists(head, tail, compar);
} else {
head = tail;
}
}
return head;
}
http://www.mindspring.com/~pfilandr/...les/list_lib.h

http://www.mindspring.com/~pfilandr/...les/list_lib.c

--
pete
Jul 2 '08 #33
pereges wrote:
>
btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of
using it ? Will it restrict the amount of code that is included
in other files ?
That 'static' applies to the function, not the returned type. It
hides the function from any other source file, although it can be
passed out as a function pointer.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Jul 2 '08 #34
In article <48***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of
using it ? Will it restrict the amount of code that is included
in other files ?
>That 'static' applies to the function, not the returned type.
More precisely, it refers to the *name* of the function. That's
why:
... it can be passed out as a function pointer.
-- Richard
--
Please remember to mention me / in tapes you leave behind.
Jul 2 '08 #35
On Mon, 30 Jun 2008 19:35:11 UTC, pereges <Br*****@gmail.comwrote:
>
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.
When you have to sort an array you have to move complete array members
around. This is time intensive at all.

Sorting lists - whenever this can not done easy while sort while
inserting - is nothing than moving pointers to elements around. Lots
of less work.

Exchanging 2 array members needs
- copy one array member out of its place
- copy the other member on its new place
- copy the other member on the place the other was

Exchanging 2 list elements is is easy done by moving pointers to them
around. Not a single list member has to be moved at all.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!
Jul 3 '08 #36
On Thu, 3 Jul 2008 05:57:16 +0000 (UTC), "Herbert Rosenau"
<os****@pc-rosenau.dewrote:
>On Mon, 30 Jun 2008 19:35:11 UTC, pereges <Br*****@gmail.comwrote:
>>
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.

When you have to sort an array you have to move complete array members
around. This is time intensive at all.

Sorting lists - whenever this can not done easy while sort while
inserting - is nothing than moving pointers to elements around. Lots
of less work.

Exchanging 2 array members needs
- copy one array member out of its place
- copy the other member on its new place
- copy the other member on the place the other was

Exchanging 2 list elements is is easy done by moving pointers to them
around. Not a single list member has to be moved at all.
Let node a point to node b point to node c point to node d. Let's
swap b and c. Let's make it easy and assume we know it is a that
points to b (otherwise we have to spend time finding it).
Copy a.next to a temp.
Copy b.next to a.next
Copy c.next to b.next
Copy the temp to c.next

Unless the array elements are aggregates, arrays look faster.

Remove del for email
Jul 4 '08 #37

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Yang Lee | last post: by
3 posts views Thread by Tom Timmermann | last post: by
2 posts views Thread by siliconwafer | last post: by
4 posts views Thread by plmanikandan | last post: by
10 posts views Thread by free2cric | last post: by
103 posts views Thread by saraSS | last post: by
1 post views Thread by ahoway | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
xarzu
2 posts views Thread by xarzu | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.