«

Tor Rustad wrote, On 02/12/07 01:47:
> CBFalconer wrote:
>> Tor Rustad wrote:
>> .... snip ...
>>> Yes, assuming argv[0] represent the program name, I have yet to
>>> see an environment where this isn't the case. Anybody knows of one?
>>
>> Virtually any embedded program.
>
> For some reason, I was talking about "hosted environment".

Any Unix like system if the process execing your program decides to lie
about the name of the program it is invoking. Look up the Posix exec*
functions to see what I mean.
--
Flash Gordon

On Sat, 01 Dec 2007 17:43:55 -0500, pete wrote:
> =?UTF-8?q?Harald_van_D=C4=B3k?= wrote:
>> On Sat, 01 Dec 2007 07:32:04 -0500, pete wrote:
>> > =?UTF-8?q?Harald_van_D=C4=B3k?= wrote:
>> >> On Sat, 01 Dec 2007 07:06:31 -0500, pete wrote:
>> >> > wrote:
>> >> >>
>> >> >> On Dec 1, 4:30 am, pateld...@yahoo.com wrote:
>> >> >> > How do I sort an string array using pointers
>> >> >>
>> >> >> #include <stdio.h>
>> >> >> #include <stdlib.h>
>> >> >> #include <string.h>
>> >> >>
>> >> >> static int
>> >> >> cmpstringp(const void *p1, const void *p2) {
>> >> >> /* The actual arguments to this function are "pointers to
>> >> >> pointers to char",
>> >> >> but strcmp() arguments are "pointers to char", hence the
>> >> >> following cast plus dereference */
>> >> >> return strcmp(* (char * const *) p1, * (char * const *) p2);
>> >> >
>> >> > The type of your strcmp arguments is (char *const). The strcmp
>> >> > parameter type is (const char *).
>> >>
>> >> char * can be implicitly converted to const char *.
>> >>
>> >> > This way would be more better:
>> >> >
>> >> > return strcmp(* (const char **) p1, * (const char **) p2);
>> >>
>> >> argv is declared as char *[].
>> >> argv[n] (which is what p1 and p2 point to) is a char *. You
>> >> shouldn't
>> >> access a char * as if it were a const char *.
>> >>
>> >> I'm not saying it's not allowed,
>> >> because I'm not sure about that, but I consider it poor style at
>> >> least.
>> >
>> > However,
>> > strcmp *will* access its arguments as type (const char *).
>>
>> No, it won't.
>> It will access its parameters as type (const char *), and its
>> parameters *are* type const char *, as the result of the implicit
>> conversion from the arguments (of type char *) to const char *.
>
> I can't parse out which effect you say occurs:
> "... as the result of the implicit conversion from the arguments
> (of type char *) to const char *."

char *x = "a";
char *y = "b";
strcmp(x, y);

The arguments are x and y. x and y are of type char *. The arguments are
implicitly converted to the type of the parameters as declared in
strcmp's function prototype.

>> You can
>> compare it to this:
>>
>> Good:
>>
>> char a = 'x';
>> int b = a;
>> const int *c = &b;
>>
>> Bad:
>>
>> char a = 'x';
>> const int *c = (int *) &a;
>
> At least in the bad example, your code acknowledges that the purpose of
> the cast is to convert the value to the type of the object receiving the
> value.
>
> The whole point of casting a pointer initializer, is to convert the
> value
> to the type of the object receiving the value.
>
> Recording the type history of the value, is not the purpose of the cast.

But you weren't casting the pointer value argv[n], you were
reinterpreting its bit pattern, by casting a pointer to argv[n]. That's
what the second example does (except for the actual dereference). That's
what you shouldn't do.

static int
cmpstringp(const void *p1, const void *p2) {
return strcmp(* (char * const *) p1, * (char * const *) p2);
}

cmpstringp will be called by qsort as, for example,
cmpstringp(&argv[1], &argv[2]);

argv[n] is of type char *. So p1 and p2 are pointers to a char *. So they
should be dereferenced as pointers to char *. If you want to get a
const char *, you can convert the value _after_ dereferencing.

CBFalconer wrote:
>
> pete wrote:
> > CBFalconer wrote:
> >
> ... snip ...
> >
> >> /* ================================ */
> >> /* Merge two ordered lists into one */
> >> nodeptr mergelists(nodeptr p1, nodeptr p2,
> >> int (*cmp)(void *, void*)); /* compare */
> >
> > I think that
> >
> > nodeptr mergelists(nodeptr p1, nodeptr p2,
> > int (*cmp)(nodeptr, nodeptr)); /* compare */
> >
> > would make more sense.
>
> No, because nodeptr->data can point to any collection of data, and
> you may want to sort based on some particular facet of that data.
> The void* allows the user to customize as needed.

No, because the arguments to your mergelists compar function
will always be pointers to nodes,
so it doesn't make sense to pretend
that the arguments to the compar function can be anything else.

The void* doesn't do anything to enhance the ability
of the user to customize as needed.

To rewrite any of these below shown compar functions
with (void *) parameters instead of nodeptr parameters,
would require an extra cast to the structure type pointer,
to make (a -> data) out to be a pointer to a structure type.

int lu_comp(nodeptr a, nodeptr b)
{
const long unsigned a_num = *(long unsigned *)(a -> data);
const long unsigned b_num = *(long unsigned *)(b -> data);

return b_num > a_num ? -1 : b_num != a_num;
}
int lu_comp_v(void *a, void *b)
{
const long unsigned a_num = *(long unsigned *)(((nodeptr)a)->data);
const long unsigned b_num = *(long unsigned *)(((nodeptr)b)->data);

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


int numcomp(nodeptr a, nodeptr 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 numcomp_v(void *a, void *b)
{
const long unsigned a_num = strtoul(((nodeptr)a)->data, NULL, 10);
const long unsigned b_num = strtoul(((nodeptr)b)->data, NULL, 10);

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


int lencomp(nodeptr a, nodeptr b)
{
const size_t a_len = strlen(a -> data);
const size_t b_len = strlen(b -> data);

return b_len > a_len ? -1 : b_len != a_len;
}
int lencomp_v(void *a, void *b)
{
const size_t a_len = strlen(((nodeptr)a) -> data);
const size_t b_len = strlen(((nodeptr)b) -> data);

return b_len > a_len ? -1 : b_len != a_len;
}



--
pete

=?UTF-8?q?Harald_van_D=C4=B3k?= wrote:
>
> On Sat, 01 Dec 2007 17:43:55 -0500, pete wrote:
> > =?UTF-8?q?Harald_van_D=C4=B3k?= wrote:
> >> On Sat, 01 Dec 2007 07:32:04 -0500, pete wrote:
> >> > =?UTF-8?q?Harald_van_D=C4=B3k?= wrote:
> >> >> On Sat, 01 Dec 2007 07:06:31 -0500, pete wrote:
> >> >> > wrote:
> >> >> >>
> >> >> >> On Dec 1, 4:30 am, pateld...@yahoo.com wrote:
> >> >> >> > How do I sort an string array using pointers
> >> >> >>
> >> >> >> #include <stdio.h>
> >> >> >> #include <stdlib.h>
> >> >> >> #include <string.h>
> >> >> >>
> >> >> >> static int
> >> >> >> cmpstringp(const void *p1, const void *p2) {
> >> >> >> /* The actual arguments to this function are "pointers to
> >> >> >> pointers to char",
> >> >> >> but strcmp() arguments are "pointers to char",
> >> >> >> hence the
> >> >> >> following cast plus dereference */
> >> >> >> return strcmp(* (char * const *) p1,
> >> >> >> * (char * const *) p2);
> >> >> >
> >> >> > The type of your strcmp arguments is (char *const). The strcmp
> >> >> > parameter type is (const char *).
> >> >>
> >> >> char * can be implicitly converted to const char *.
> >> >>
> >> >> > This way would be more better:
> >> >> >
> >> >> > return strcmp(* (const char **) p1, * (const char **) p2);
> >> >>
> >> >> argv is declared as char *[].
> >> >> argv[n] (which is what p1 and p2 point to) is a char *. You
> >> >> shouldn't
> >> >> access a char * as if it were a const char *.
> >> >>
> >> >> I'm not saying it's not allowed,
> >> >> because I'm not sure about that, but I consider it poor style at
> >> >> least.
> >> >
> >> > However,
> >> > strcmp *will* access its arguments as type (const char *).
> >>
> >> No, it won't.
> >> It will access its parameters as type (const char *), and its
> >> parameters *are* type const char *, as the result of the implicit
> >> conversion from the arguments (of type char *) to const char *.
> >
> > I can't parse out which effect you say occurs:
> > "... as the result of the implicit conversion from the arguments
> > (of type char *) to const char *."
>
> char *x = "a";
> char *y = "b";
> strcmp(x, y);
>
> The arguments are x and y. x and y are of type char *.
> The arguments are
> implicitly converted to the type of the parameters as declared in
> strcmp's function prototype.
>
> >> You can
> >> compare it to this:
> >>
> >> Good:
> >>
> >> char a = 'x';
> >> int b = a;
> >> const int *c = &b;
> >>
> >> Bad:
> >>
> >> char a = 'x';
> >> const int *c = (int *) &a;
> >
> > At least in the bad example,
> > your code acknowledges that the purpose of
> > the cast is to convert the value to the type
> > of the object receiving the value.
> >
> > The whole point of casting a pointer initializer, is to convert the
> > value
> > to the type of the object receiving the value.
> >
> > Recording the type history of the value,
> > is not the purpose of the cast.
>
> But you weren't casting the pointer value argv[n], you were
> reinterpreting its bit pattern, by casting a pointer to argv[n].
> That's
> what the second example does
> (except for the actual dereference). That's
> what you shouldn't do.
>
> static int
> cmpstringp(const void *p1, const void *p2) {
> return strcmp(* (char * const *) p1, * (char * const *) p2);
> }
>
> cmpstringp will be called by qsort as, for example,
> cmpstringp(&argv[1], &argv[2]);
>
> argv[n] is of type char *.
> So p1 and p2 are pointers to a char *. So they
> should be dereferenced as pointers to char *. If you want to get a
> const char *, you can convert the value _after_ dereferencing.

OK.
I'm thinking about it now.
Thank you.

--
pete

pete wrote:
> CBFalconer wrote:
>> pete wrote:
>>> CBFalconer wrote:
>>>
>> ... snip ...
>>>
>>>> /* ================================ */
>>>> /* Merge two ordered lists into one */
>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>>> int (*cmp)(void *, void*)); /* compare */
>>>
>>> I think that
>>>
>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>> int (*cmp)(nodeptr, nodeptr)); /* compare */
>>>
>>> would make more sense.
>>
>> No, because nodeptr->data can point to any collection of data, and
>> you may want to sort based on some particular facet of that data.
>> The void* allows the user to customize as needed.
>
> No, because the arguments to your mergelists compar function
> will always be pointers to nodes, so it doesn't make sense to pretend
> that the arguments to the compar function can be anything else.

Not the arguments, but what is passed to, for example, strcmp. For
example, data may point to a structure containing two pointers to
strings. The cmp function can select which of those strings get
compared. By simply passing a different cmp function we can sort
the same list in different ways.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

"CBFalconer" <> wrote in message
news:...
> pete wrote:
>> CBFalconer wrote:
>>> pete wrote:
>>>> CBFalconer wrote:
>>>>
>>> ... snip ...
>>>>
>>>>> /* ================================ */
>>>>> /* Merge two ordered lists into one */
>>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>>>> int (*cmp)(void *, void*)); /* compare */
>>>>
>>>> I think that
>>>>
>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>>> int (*cmp)(nodeptr, nodeptr)); /* compare */
>>>>
>>>> would make more sense.
>>>
>>> No, because nodeptr->data can point to any collection of data, and
>>> you may want to sort based on some particular facet of that data.
>>> The void* allows the user to customize as needed.
>>
>> No, because the arguments to your mergelists compar function
>> will always be pointers to nodes, so it doesn't make sense to pretend
>> that the arguments to the compar function can be anything else.
>
> Not the arguments, but what is passed to, for example, strcmp. For
> example, data may point to a structure containing two pointers to
> strings. The cmp function can select which of those strings get
> compared. By simply passing a different cmp function we can sort
> the same list in different ways.

The various cmp functions are simpler to write
when they have nodeptr parameters,
than they are when they have (void *) parameters.

To sort a list of long unsigned with (void *) cmp parameters,
takes a function like this:

int lu_comp_vp(const void * a, const void * b)
{
const long unsigned a_lu = *(long unsigned *)(((nodeptr)a) -> data);
const long unsigned b_lu = *(long unsigned *)(((nodeptr)b) -> data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}

To sort a list of long unsigned with nodeptr cmp parameters,
takes a function like this:

int lu_comp_np(const nodeptr a, const nodeptr b)
{
const long unsigned a_lu = *(long unsigned *)(a -> data);
const long unsigned b_lu = *(long unsigned *)(b -> data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}

It's just simpler code with the nodeptr parameters.

I wrote two programs: NPlist_sort and VPlist_sort.
NP and VP stand for NodePointer and VoidPointer.
The programs both do exactly the same thing.
They each sort a list of strings and
also sort a list of long unsigneds using
the same sorting function with different cmp functions.
The only difference in the two programs is the cmp parameters.
The cmp function for comparing strings is simpler
in the program with nodeptr parameters
and the cmp function for comparing long unsigneds
is simpler in the program with nodeptr parameters.

It's just

int lencomp_vp(const void * a, const void * b)
{
const size_t a_len = strlen(((nodeptr)a) -> data);
const size_t b_len = strlen(((nodeptr)b) -> data);

return b_len > a_len ? -1 : b_len != a_len;
}
int lu_comp_vp(const void * a, const void * b)
{
const long unsigned a_lu = *(long unsigned *)(((nodeptr)a) ->data);
const long unsigned b_lu = *(long unsigned *)(((nodeptr)b) ->data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}
nodeptr mergelists_vp(nodeptr p1, nodeptr p2,
int (*cmp)(const void *, const void *));
nodeptr mergesort_vp(nodeptr root,
int (*cmp)(const void *, const void *));

versus

int lencomp_np(const nodeptr a, const nodeptr b)
{
const size_t a_len = strlen(a -> data);
const size_t b_len = strlen(b -> data);

return b_len > a_len ? -1 : b_len != a_len;
}
int lu_comp_np(const nodeptr a, const nodeptr b)
{
const long unsigned a_lu = *(long unsigned *)(a -> data);
const long unsigned b_lu = *(long unsigned *)(b -> data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}
nodeptr mergelists_np(nodeptr p1, nodeptr p2,
int (*cmp)(const nodeptr, const nodeptr));
nodeptr mergesort_np(nodeptr root,
int (*cmp)(const nodeptr, const nodeptr));

There is no other difference in the programs.

This is the output:

/* BEGIN VPlist_sort.c output */

Original order of list of pointers to strings:
one
two
three
four
five
six
seven
eight
nine
ten

List after stable mergesort_vp by string length:
one
two
six
ten
four
five
nine
three
seven
eight

Original order of list of pointers to long unsigned:
15
14
13
7
20
9
8
12
11
6

List after mergesort_vp:
6
7
8
9
11
12
13
14
15
20

/* END VPlist_sort.c output */

/* BEGIN VPlist_sort.c */

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

#define NMEMB(A) (sizeof (A) / sizeof *(A))

typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

int lencomp_vp(const void * a, const void * b);
int lu_comp_vp(const void * a, const void * b);
nodeptr mergelists_vp(nodeptr p1, nodeptr p2,
int (*cmp)(const void *, const void *));
nodeptr mergesort_vp(nodeptr root,
int (*cmp)(const void *, const void *));

nodeptr revlist(nodeptr root);
nodeptr splitlist(nodeptr p);
void list_free(nodeptr knowed, void (*free_data)(void *));
nodeptr list_push(nodeptr head, void *data, size_t size);
int list_fputs(nodeptr knowed, FILE *stream);
int list_fprintf_lu(nodeptr knowed, FILE *stream);

int main(void)
{
nodeptr head;
nodeptr temp;
char *string[] = {
"one","two","three","four","five",
"six","seven","eight","nine","ten"
};
char **const after = string + NMEMB(string);
char **ptr;
long unsigned lu_numbers[] = {
15,14,13,7,20,9,8,12,11,6
};
long unsigned *const lu_after = lu_numbers + NMEMB(lu_numbers);
long unsigned *lu_ptr;

head = NULL;
for (ptr = string; ptr != after; ++ptr) {
temp = list_push(head, *ptr, strlen(*ptr) + 1);
if (temp == NULL) {
list_free(head, free);
head = NULL;
puts("malloc trouble!");
break;
}
head = temp;
}
head = revlist(head);
puts("/* BEGIN VPlist_sort.c output */");
puts("\nOriginal order of list of pointers to strings:");
list_fputs(head, stdout);
puts("\nList after stable mergesort_vp by string length:");
head = mergesort_vp(head, lencomp_vp);
list_fputs(head, stdout);
list_free(head, free);
puts("\nOriginal order of list of pointers to long unsigned:");
head = NULL;
for (lu_ptr = lu_numbers; lu_ptr != lu_after; ++lu_ptr) {
temp = list_push(head, lu_ptr, sizeof *lu_ptr);
if (temp == NULL) {
list_free(head, free);
head = NULL;
puts("malloc trouble!");
break;
}
head = temp;
}
head = revlist(head);
list_fprintf_lu(head, stdout);
puts("\nList after mergesort_vp:");
head = mergesort_vp(head, lu_comp_vp);
list_fprintf_lu(head, stdout);
list_free(head, free);
puts("\n/* END VPlist_sort.c output */");
return 0;
}

int lencomp_vp(const void * a, const void * b)
{
const size_t a_len = strlen(((nodeptr)a) -> data);
const size_t b_len = strlen(((nodeptr)b) -> data);

return b_len > a_len ? -1 : b_len != a_len;
}

int lu_comp_vp(const void * a, const void * b)
{
const long unsigned a_lu = *(long unsigned *)(((nodeptr)a) -> data);
const long unsigned b_lu = *(long unsigned *)(((nodeptr)b) -> data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}

int list_fprintf_lu(nodeptr knowed, FILE *stream)
{
int rc;

while (knowed != NULL) {
rc = fprintf(stream, "%lu\n",
*(long unsigned *)(knowed -> data));
if (0 > rc) {
break;
}
knowed = knowed -> next;
}
return rc;
}

void list_free(nodeptr knowed, void (*free_data)(void *))
{
nodeptr next_node;

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

int list_fputs(nodeptr knowed, FILE *stream)
{
while (knowed != NULL) {
if (fputs(knowed -> data, stream) == EOF) {
return EOF;
}
if (putc('\n', stream) == EOF) {
return EOF;
}
knowed = knowed -> next;
}
return '\n';
}

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

nodeptr list_push(nodeptr head, void *data, size_t size)
{
nodeptr knowed;

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

nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (! 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 */

nodeptr mergelists_vp(nodeptr p1, nodeptr p2,
int (*cmp)(const void *, const void *))
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 && 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_vp */

nodeptr mergesort_vp(nodeptr root,
int (*cmp)(const void *, const void *))
{
nodeptr p;

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

return root;
} /* mergesort_vp */

/* END VPlist_sort.c */



/* BEGIN NPlist_sort.c */

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

#define NMEMB(A) (sizeof (A) / sizeof *(A))

typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

int lencomp_np(const nodeptr a, const nodeptr b);
int lu_comp_np(const nodeptr a, const nodeptr b);
nodeptr mergelists_np(nodeptr p1, nodeptr p2,
int (*cmp)(const nodeptr, const nodeptr));
nodeptr mergesort_np(nodeptr root,
int (*cmp)(const nodeptr, const nodeptr));
nodeptr revlist(nodeptr root);
nodeptr splitlist(nodeptr p);
void list_free(nodeptr knowed, void (*free_data)(void *));
nodeptr list_push(nodeptr head, void *data, size_t size);
int list_fputs(nodeptr knowed, FILE *stream);
int list_fprintf_lu(nodeptr node, FILE *stream);

int main(void)
{
nodeptr head;
nodeptr temp;
char *string[] = {
"one","two","three","four","five",
"six","seven","eight","nine","ten"
};
char **const after = string + NMEMB(string);
char **ptr;
long unsigned lu_numbers[] = {
15,14,13,7,20,9,8,12,11,6
};
long unsigned *const lu_after = lu_numbers + NMEMB(lu_numbers);
long unsigned *lu_ptr;

head = NULL;
for (ptr = string; ptr != after; ++ptr) {
temp = list_push(head, *ptr, strlen(*ptr) + 1);
if (temp == NULL) {
list_free(head, free);
head = NULL;
puts("malloc trouble!");
break;
}
head = temp;
}
head = revlist(head);
puts("/* BEGIN NPlist_sort.c output */");
puts("\nOriginal order of list of pointers to strings:");
list_fputs(head, stdout);
puts("\nList after stable mergesort_np by string length:");
head = mergesort_np(head, lencomp_np);
list_fputs(head, stdout);
list_free(head, free);
puts("\nOriginal order of list of pointers to long unsigned:");
head = NULL;
for (lu_ptr = lu_numbers; lu_ptr != lu_after; ++lu_ptr) {
temp = list_push(head, lu_ptr, sizeof *lu_ptr);
if (temp == NULL) {
list_free(head, free);
head = NULL;
puts("malloc trouble!");
break;
}
head = temp;
}
head = revlist(head);
list_fprintf_lu(head, stdout);
puts("\nList after mergesort_np:");
head = mergesort_np(head, lu_comp_np);
list_fprintf_lu(head, stdout);
list_free(head, free);
puts("\n/* END NPlist_sort.c output */");
return 0;
}

int lencomp_np(const nodeptr a, const nodeptr b)
{
const size_t a_len = strlen(a -> data);
const size_t b_len = strlen(b -> data);

return b_len > a_len ? -1 : b_len != a_len;
}

int lu_comp_np(const nodeptr a, const nodeptr b)
{
const long unsigned a_lu = *(long unsigned *)(a -> data);
const long unsigned b_lu = *(long unsigned *)(b -> data);

return b_lu > a_lu ? -1 : b_lu != a_lu;
}

int list_fprintf_lu(nodeptr knowed, FILE *stream)
{
int rc;

while (knowed != NULL) {
rc = fprintf(stream, "%lu\n",
*(long unsigned *)(knowed -> data));
if (0 > rc) {
break;
}
knowed = knowed -> next;
}
return rc;
}

void list_free(nodeptr knowed, void (*free_data)(void *))
{
nodeptr next_node;

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

int list_fputs(nodeptr knowed, FILE *stream)
{
while (knowed != NULL) {
if (fputs(knowed -> data, stream) == EOF) {
return EOF;
}
if (putc('\n', stream) == EOF) {
return EOF;
}
knowed = knowed -> next;
}
return '\n';
}

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

nodeptr list_push(nodeptr head, void *data, size_t size)
{
nodeptr knowed;

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

nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (! 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 */

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

p = &n;
n.next = p;

while (p1 && 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_np */

nodeptr mergesort_np(nodeptr root,
int (*cmp)(const nodeptr, const nodeptr))
{
nodeptr p;

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

return root;
} /* mergesort_np */

/* END NPlist_sort.c */

pete wrote:
> "CBFalconer" <> wrote in message
>> pete wrote:
>>> CBFalconer wrote:
>>>> pete wrote:
>>>>> CBFalconer wrote:
>>>>>
>>>> ... snip ...
>>>>>
>>>>>> /* ================================ */
>>>>>> /* Merge two ordered lists into one */
>>>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>>>>> int (*cmp)(void *, void*)); /* compare */
>>>>>
>>>>> I think that
>>>>>
>>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
>>>>> int (*cmp)(nodeptr, nodeptr)); /* compare */
>>>>>
>>>>> would make more sense.
>>>>
>>>> No, because nodeptr->data can point to any collection of data, and
>>>> you may want to sort based on some particular facet of that data.
>>>> The void* allows the user to customize as needed.
>>>
>>> No, because the arguments to your mergelists compar function
>>> will always be pointers to nodes, so it doesn't make sense to pretend
>>> that the arguments to the compar function can be anything else.
>>
>> Not the arguments, but what is passed to, for example, strcmp. For
>> example, data may point to a structure containing two pointers to
>> strings. The cmp function can select which of those strings get
>> compared. By simply passing a different cmp function we can sort
>> the same list in different ways.
>
> The various cmp functions are simpler to write when they have
> nodeptr parameters, than they are when they have (void *) parameters.

The only thing affected is the cmp function, and now the void*
parameters make the central block (that manipulates the list,
including sorting) much simpler and a constant library entry. The
only thing needed in the actual cmp function is something like:

int acmp(const void *litem, const void* ritem) {
const whatever ldptr = litem, rdptr = ritem;

... code using ldptr and rdptr ...
}

Remember that the actual cmp code is in the users code area. The
list processing, sorting, etc. code couldn't care less what is in
the data fields. Note how I have eliminated great gobs of
inter-related code.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

CBFalconer wrote:
>
> pete wrote:
> > "CBFalconer" <> wrote in message
> >> pete wrote:
> >>> CBFalconer wrote:
> >>>> pete wrote:
> >>>>> CBFalconer wrote:
> >>>>>
> >>>> ... snip ...
> >>>>>
> >>>>>> /* ================================ */
> >>>>>> /* Merge two ordered lists into one */
> >>>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
> >>>>>> int (*cmp)(void *, void*)); /* compare */
> >>>>>
> >>>>> I think that
> >>>>>
> >>>>> nodeptr mergelists(nodeptr p1, nodeptr p2,
> >>>>> int (*cmp)(nodeptr, nodeptr)); /* compare */
> >>>>>
> >>>>> would make more sense.
> >>>>
> >>>> No, because nodeptr->data can point to any collection of data, and
> >>>> you may want to sort based on some particular facet of that data.
> >>>> The void* allows the user to customize as needed.
> >>>
> >>> No, because the arguments to your mergelists compar function
> >>> will always be pointers to nodes, so it doesn't make sense to pretend
> >>> that the arguments to the compar function can be anything else.
> >>
> >> Not the arguments, but what is passed to, for example, strcmp. For
> >> example, data may point to a structure containing two pointers to
> >> strings. The cmp function can select which of those strings get
> >> compared. By simply passing a different cmp function we can sort
> >> the same list in different ways.
> >
> > The various cmp functions are simpler to write when they have
> > nodeptr parameters, than they are when they have (void *) parameters.
>
> The only thing affected is the cmp function, and now the void*
> parameters make the central block (that manipulates the list,
> including sorting) much simpler and a constant library entry. The
> only thing needed in the actual cmp function is something like:
>
> int acmp(const void *litem, const void* ritem) {
> const whatever ldptr = litem, rdptr = ritem;
>
> ... code using ldptr and rdptr ...
> }

That's the point.
With nodeptr parameters instead of void * parameters,
the equivalent cmp function becomes:

int acmp(const nodeptr litem, const nodeptr ritem) {
... code using litem and ritem ...
}

.... which is a simpler way to write it.

--
pete

pete wrote:
>
> CBFalconer wrote:

> > The only thing affected is the cmp function, and now the void*
> > parameters make the central block (that manipulates the list,
> > including sorting) much simpler and a constant library entry. The
> > only thing needed in the actual cmp function is something like:
> >
> > int acmp(const void *litem, const void* ritem) {
> > const whatever ldptr = litem, rdptr = ritem;

It's not "const whatever",
it's always going to be "const nodeptr".

The way that your mergesort and mergelist functions
call the cmp function,
the argument is always going to be a nodeptr value,
and the only way that the cmp function can use that value
is as a nodeptr value.

> > ... code using ldptr and rdptr ...
> > }
>
> That's the point.
> With nodeptr parameters instead of void * parameters,
> the equivalent cmp function becomes:
>
> int acmp(const nodeptr litem, const nodeptr ritem) {
> ... code using litem and ritem ...
> }
>
> ... which is a simpler way to write it.

--
pete

pete wrote:
>
> pete wrote:
> >
> > CBFalconer wrote:
>
> > > The only thing affected is the cmp function, and now the void*
> > > parameters make the central block (that manipulates the list,
> > > including sorting) much simpler and a constant library entry. The
> > > only thing needed in the actual cmp function is something like:
> > >
> > > int acmp(const void *litem, const void* ritem) {
> > > const whatever ldptr = litem, rdptr = ritem;
>
> It's not "const whatever",
> it's always going to be "const nodeptr".

> > > ... code using ldptr and rdptr ...
> > > }

Because the code using ldptr and rdptr ...,
is always going to be (ldptr -> data) and (rdptr -> data).

--
pete