CBFalconer said:
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 */
