Using a link list over an array.

[pereges]

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 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;
}

 

[Ben Bacarisse]

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 */
}

You may not need to store them at all. In once version I saw, the
data in raylist 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 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.

 

[Bartc]

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?

 

[Richard]

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 */
}

You may not need to store them at all. In once version I saw, the
data in raylist 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 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.

 

[pereges]

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.

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.

 

[Ben Bacarisse]

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 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.

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

 

[Herbert Rosenau]

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!

 

[pereges]

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.

 

[CBFalconer]

.... 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 */

 

[pereges]

pereges wrote:

... snip ...


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; /* 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);

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.

 

[CBFalconer]

.... 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.

 

[pereges]

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.

 

[Ben Bacarisse]

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.

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.

 

[pereges]

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;
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].

 

[CBFalconer]

.... snip ...

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.

 

[CBFalconer]

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

 

[Ben Bacarisse]

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.

 

[Ben Bacarisse]

pete wrote:
pereges wrote:

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 Bacarisse]

/* 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.

 

[CBFalconer]

CBFalconer wrote:
.... snip ...


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.