Linked List

What are Linked list? Please somebody show some ready made programs of
linked list

re: Linked List

On Fri, 28 Dec 2007 05:00:36 -0600, dmp wrote
(in article
<227a3f38-d6c6-46b9-b51c-b033e5736b6d@i29g2000prf.googlegroups.com>):
Time to change your major.


--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

re: Linked List

dmp said:
A data structure in which each item (except the last) contains data
indicating where the next item in the list can be found. Optionally, each
item except the first can also contain data indicating where the previous
item in the list can be found (in which it becomes a double-linked list).
#include <stdio.h>
struct foo
{
int data;
int next;
};

int main(void)
{
struct foo linkedlist[2] = { { 6, 1 }, { 42, -1 } };
int link = 0;
while(link != -1)
{
printf("%d\n", linkedlist[link].data);
link = linkedlist[link].next;
}
return 0;
}

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

re: Linked List

On Dec 28, 3:00 am, dmp <pateld...@yahoo.comwrote:Every heard of a search engine? ;)

http://en.wikipedia.org/wiki/Linked_list

Regards,
Ivan Novick
http://www.0x4849.net

re: Linked List

dmp wrote:Here are two:
http://www.mindspring.com/~pfilandr/...iles/Lf_sort.c
http://www.mindspring.com/~pfilandr/.../string_sort.c

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

--
pete

re: Linked List

On Jan 3, 10:27*am, pete <pfil...@mindspring.comwrote:

re: Linked List

pete wrote:After that, file_sort_2.c, and file_parse_2.c
are both homework problems posted to clc.
file_sort_2.c introduces the get_line function.

/* BEGIN file_sort_2.c */
/*
From news:comp.lang.c
*/
#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) * 69069 + 362437 & 0XFFFFFFFFLU)
#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);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 *));
int list_fputs(const list_type *node, FILE *stream);
static list_type *sort_node (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)
{
long unsigned index, lu_seed, line;
int rc;
char *buff;
size_t size;
list_type *tail, *head;
char fn[L_tmpnam];
FILE *fp;

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.
*/
size = 0;
buff = NULL;
head = tail = NULL;
lu_seed = LU_RAND_SEED;
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, strlen(buff) + 1);
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;

count = 0;
while ((rc = getc(stream)) != EOF) {
++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) {
rc = INT_MAX count ? count : INT_MAX;
} else {
if (*n count) {
(*lineptr)[count] = '\0';
}
}
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_node(head, compar) : head;
}

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

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

if (head -next != NULL) {
tail = split_list(head);
tail = sort_node(tail, compar);
head = sort_node(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

re: Linked List

pete wrote:file_parse_2.c is the only one of the bunch
that doesn't do any sorting.

/* BEGIN file_parse_2.c */
/*
From news:comp.lang.c
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define LINES_PER_FILE 3
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0XFFFFFFFFLU)

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

typedef struct list_node list_type;

void free_ptrs(char ***p, size_t nmemb);
void display_array(char ***p, size_t n_lines, size_t n_fields);
int get_line(char **lineptr, size_t *n, 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 *));
int list_fputs(const list_type *node, FILE *stream);

int main(void)
{
long unsigned lu_seed;
int rc;
char *buff, *ptr;
size_t size, line, n_lines, n_fields, field;
list_type *tail, *head;
char fn[L_tmpnam];
FILE *fp;
char ***f;

puts("/* BEGIN file_parse_2.c output */");
/*
** Create input text file.
** Open temporary input text file for writing.
*/
tmpnam(fn);
fp = fopen(fn, "w");
if (fp == NULL) {
fputs("fopen(fn), \"w\") == NULL\n", stderr);
exit(EXIT_FAILURE);
}
/*
** Write temporary input text file.
*/
lu_seed = LU_RAND_SEED;
for (line = 0; line != LINES_PER_FILE; ++line) {
lu_seed = LU_RAND(lu_seed);
fprintf(fp,
"%.8lu %s %.1lu %.3lu %.3lu %.3lu %.4lu %.3lu\n",
line, "USNIST00Z 00000000_00",
lu_seed % 10, lu_seed % 1000,
lu_seed % 500, lu_seed % 250,
lu_seed % 10000, lu_seed % 125);
}
/*
** Close temporary input text file.
*/
fclose(fp);
/*
** Open temporary input text file for reading.
*/
fp = fopen(fn, "r");
if (fp == NULL) {
remove(fn);
fputs("fopen(fn), \"r\") == NULL\n", stderr);
exit(EXIT_FAILURE);
}
/*
** Represent each line of the temporary input text file
** as a string in a node of a linked list.
*/
n_lines = 0;
head = tail = NULL;
size = 0;
buff = NULL;
while ((rc = get_line(&buff, &size, fp)) 0) {
tail = list_append(&head, tail, buff, strlen(buff) + 1);
if (tail == NULL) {
fputs("tail == NULL\n", stderr);
break;
}
++n_lines;
}
/*
** Close temporary input text file.
** Free allocated buffer used by get_line function.
** Remove temporary input text file.
*/
fclose(fp);
free(buff);
remove(fn);
/*
** End program if there have been any
** file problems or allocation problems.
*/
if (rc != EOF) {
list_free(head, free);
fprintf(stderr, "rc == %d\n", rc);
exit(EXIT_FAILURE);
}
/*
** Display linked list.
*/
puts("\nInput file:");
list_fputs(head, stdout);
/*
** Create array.
*/
f = malloc(n_lines * sizeof *f);
if (f == NULL) {
list_free(head, free);
fputs("f == NULL\n", stderr);
exit(EXIT_FAILURE);
}
n_fields = 1;
for (ptr = head -data; *ptr != '\0'; ++ptr) {
if (*ptr == ' ') {
++n_fields;
}
}
for (line = 0; line != n_lines; ++line) {
f[line] = malloc(n_fields * sizeof *f[line]);
if (f[line] == NULL) {
free_ptrs(f, line);
list_free(head, free);
fputs("f[line] == NULL\n", stderr);
exit(EXIT_FAILURE);
}
f[line][0] = NULL;
}
/*
** Tokenize list data and
** assign strings to pointers in array.
*/
line = 0;
for (tail = head; tail != NULL; tail = tail -next) {
f[line][0] = tail -data;
tail -data = NULL;
for (field = 1; n_fields field; ++field) {
f[line][field] = strchr(f[line][field - 1], ' ');
if (f[line][field] == NULL) {
free_ptrs(f, n_lines);
list_free(head, free);
fputs("f[line][field] == NULL\n", stderr);
exit(EXIT_FAILURE);
}
*f[line][field]++ = '\0';
}
++line;
}
/*
** Free list.
*/
list_free(head, free);
/*
** Display resulting array.
*/
puts("\nResulting array:");
display_array(f, n_lines, n_fields);
/*
** Free array.
*/
free_ptrs(f, n_lines);
puts("/* END file_parse_2.c output */");
return 0;
}

void display_array(char ***p, size_t n_lines, size_t n_fields)
{
size_t line, field;

for (line = 0; line != n_lines; ++line) {
for (field = 0; field != n_fields; ++field) {
printf("array[%lu][%lu] ",
(long unsigned)line, (long unsigned)field);
puts(p[line][field]);
}
putchar('\n');
}
}

void free_ptrs(char ***p, size_t nmemb)
{
while (nmemb-- != 0) {
free(p[nmemb][0]);
free(p[nmemb]);
}
free(p);
}

int get_line(char **lineptr, size_t *n, FILE *stream)
{
int rc;
void *p;
size_t count;

count = 0;
while ((rc = getc(stream)) != EOF) {
++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) {
rc = INT_MAX count ? count : INT_MAX;
} else {
if (*n count) {
(*lineptr)[count] = '\0';
}
}
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;
}
}

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

/* END file_parse_2.c */

--
pete

re: Linked List

pete wrote:file_collate_2.c is interesting because it has a list of lists.

/* BEGIN file_collate_2.c */
/*
** Program reads files of customer names
** and products purchased.
** Some files may have identical customers
** with some same purchases as other files.
** Program makes a list of purchased products
** and who has purchased them.
** Demonstrates use of the list_collate function
** on list of lists.
** Both of the macros, NFILES and MAX_PRODUCTS_PER_FILE
** can be changed to any positive value
** without having to alter any other part of the program.
** Also, the number of strings in the
** NAMES and PRODUCT_NAMES macros, can be changed
** without having to alter any other part of the program.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define NFILES 6
#define MAX_PRODUCTS_PER_FILE 4

#define NAMES \
{"Ms Smith","Mr. Jones","Ms Brown","Mr. Green","Ms Grant"}

#define PRODUCT_NAMES \
{"milk","candy","meat","juice","fruit",\
"eggs","cereal","coffee","tea","gum",\
"bread","ketchup","salt","pepper","sugar"}

#define LFSM ("") /* (List File Start Marker) */
#define LU_RAND_SEED 123456LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0XFFFFFFFFLU)
#define NMEMB(A) (sizeof (A) / sizeof *(A))

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

typedef struct {
char *product_name;
list_type *consumers;
} purchases;

void product_free(void *data);
list_type *product_list(const list_type *head);
void prod_merge(list_type *head);
void cons_merge(list_type *head);
int prod_cmp(const list_type *a, const list_type *b);
int cons_cmp(const list_type *a, const list_type *b);
int product_display(const list_type *head, FILE *stream);
int consumer_display(const list_type *head, FILE *stream);
long unsigned shuffle
(long unsigned *array, long unsigned n, long unsigned seed);
int get_line(char **lineptr, size_t *n, 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 *));
list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
void list_collate(list_type *node,
int (*compar)(const list_type *, const list_type *),
void (*data_merge)(list_type *));
static list_type *sort_node (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)
{
long unsigned index, line;
int rc;
char *buff;
size_t size;
list_type *tail, *head, *product;
char fn[L_tmpnam];
FILE *fp;
long unsigned lu_seed = LU_RAND_SEED;
char *name[] = NAMES;
char *product_name[] = PRODUCT_NAMES;
long unsigned number[NMEMB(product_name)];
const size_t LFSM_size = 1 + strlen(LFSM);
const long unsigned n_files = NFILES;
const long unsigned mppf
= MAX_PRODUCTS_PER_FILE NMEMB(product_name)
? NMEMB(product_name) : MAX_PRODUCTS_PER_FILE;

puts("/* BEGIN file_collate_2.c output */");
puts("\nInput: Customer purchase record files");
/*
** Open temporary input text files for writing.
*/
size = 0;
buff = NULL;
head = tail = NULL;
tmpnam(fn);
for (index = 0; index != n_files; ++index) {
fp = fopen(fn, "w");
if (fp == NULL) {
fputs("fopen(fn, \"w\") == NULL\n", stderr);
break;
}
/*
** Write to standard output,
** as well as to temporary input text files.
*/
fprintf(stdout, "%s\n ", name[lu_seed % NMEMB(name)]);
fprintf( fp, "%s\n" , name[lu_seed % NMEMB(name)]);
lu_seed = shuffle(number, NMEMB(number), lu_seed);
line = lu_seed % mppf + 1;
while (line-- != 0) {
fprintf(stdout, " %s,", product_name[number[line]]);
fprintf( fp, "%s\n", product_name[number[line]]);
}
puts("\b ");
/*
** Close each file after writing.
*/
fclose(fp);
/*
** Mark the start of each file in the list.
** (List File Start Marker)(LFSM)
*/
tail = list_append(&head, tail, LFSM, LFSM_size);
if (tail == NULL) {
fputs("tail == NULL_1\n", stderr);
break;
}
/*
** Open input text files for reading.
*/
fp = fopen(fn, "r");
if (fp == NULL) {
fputs("fopen(fn, \"r\") == NULL\n", stderr);
break;
}
/*
** Represent each line of each input text file
** as a string in a node of a linked list.
*/
while ((rc = get_line(&buff, &size, fp)) 0) {
/*
** Make sure that the List File Start Marker
** isn't showing up where it's not supposed to.
*/
if (strcmp(LFSM, buff) == 0) {
fputs("strcmp(LFSM, buff) == 0\n", stderr);
break;
}
tail = list_append(&head, tail, buff, strlen(buff) + 1);
if (tail == NULL) {
fputs("tail == NULL_2\n", stderr);
break;
}
}
/*
** Close each temp input file after reading.
*/
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);
/*
** Create list of product_names,
** with each product having a list of consumers.
** Free file list.
*/
product = product_list(head);
list_free(head, free);
/*
** Display list.
** Free list.
*/
puts("\n\nOutput: Product consumer list");
product_display(product, stdout);
list_free(product, product_free);
puts("\n/* END file_collate_2.c output */");
return 0;
}

void product_free(void *data)
{
purchases *const ptr = data;

list_free(ptr -consumers, free);
free(ptr -product_name);
free(ptr);
}

list_type *product_list(const list_type *head)
{
purchases temp;
size_t size;
size_t c_size;
char *consumer;
list_type *c_tail = NULL;
list_type *product = NULL;
list_type *p_tail = NULL;
/*
** Make a list of structures.
** Each structure will have a pointer to the name of a product
** from an input text file and also a pointer to a list
** with one node that contains a pointer
** to the customer name from the file.
**
** (head) list format:
** LFSM marks the begining of new file entry in list.
** First line of each file is customer name;
** Arbitrary number of subsequent lines are product names;
** Then, either the list ends or...
** LFSM marks the begining of new file entry in list.
*/
while (head != NULL) {
if (strcmp(head -data, LFSM) == 0) {
head = head -next;
if (head != NULL) {
consumer = head -data;
c_size = strlen(consumer) + 1;
head = head -next;
}
continue;
}
size = strlen(head -data) + 1;
temp.product_name = malloc(size);
if (temp.product_name == NULL) {
fputs("temp.product_name == NULL\n", stderr);
list_free(temp.consumers, free);
list_free(product, product_free);
product = NULL;
break;
}
memcpy(temp.product_name, head -data, size);
temp.consumers = NULL;
c_tail =
list_append(&temp.consumers, c_tail, consumer, c_size);
if (c_tail == NULL) {
fputs("c_tail == NULL\n", stderr);
list_free(temp.consumers, free);
list_free(product, product_free);
product = NULL;
break;
}
p_tail = list_append(&product, p_tail, &temp, sizeof temp);
if (p_tail == NULL) {
fputs("p_tail == NULL\n", stderr);
list_free(temp.consumers, free);
list_free(product, product_free);
product = NULL;
break;
}
head = head -next;
}
/*
** (product) is a pointer to a list of structures,
** with each stucture containing
** a pointer to a product name and
** a pointer to a list of consumer names that only has one node.
** Each structure, at this point,
** represents the purchase of each individual item:
** the product,
** and the person who bought it.
** Sort the list by product name.
*/
product = list_sort(product, prod_cmp);
/*
** The list_collate function operates on a sorted list.
** In this call, list_collate will merge the
** lists of customer names of nodes
** which have the same product names.
** The merged list is assigned to one node
** and the other node is deleted.
** Nodes with duplicate customer names
** in the resulting merged list,
** are deleted by another call to list_collate,
** from within prod_merge.
*/
list_collate(product, prod_cmp, prod_merge);
/*
** Each structure, at this point,
** represents each different purchased product,
** and all of the different people who bought it.
*/
return product;
}

void prod_merge(list_type *head)
{
purchases *data = head -data;
list_type *next = head -next;
purchases *next_data = next -data;

data -consumers = list_merge
(data -consumers, next_data -consumers, cons_cmp);
list_collate(data -consumers, cons_cmp, cons_merge);
free(next_data -product_name);
free(next_data);
}

void cons_merge(list_type *head)
{
free(head -next -data);
}

int prod_cmp(const list_type *a, const list_type *b)
{
purchases *const a_ptr = a -data;
purchases *const b_ptr = b -data;

return strcmp(a_ptr -product_name, b_ptr -product_name);
}

int cons_cmp(const list_type *a, const list_type *b)
{
return strcmp(a -data, b -data);
}

int product_display(const list_type *head, FILE *stream)
{
int rc = 0;

while (head != NULL) {
purchases *const ptr = head -data;

rc = fprintf(stream, "Product: %s\nConsumers:",
ptr -product_name);
if (0 rc) {
break;
}
rc = consumer_display(ptr -consumers, stream);
if (0 rc) {
break;
}
head = head -next;
}
return rc;
}

int consumer_display(const list_type *head, FILE *stream)
{
int rc = 0;

while (head != NULL) {
rc = fprintf(stream," %s," , head -data);
if (0 rc) {
break;
}
head = head -next;
}
if (rc 0) {
rc = fputs("\b \n\n", stream);
}
return rc;
}

long unsigned shuffle
(long unsigned *array, long unsigned n, long unsigned seed)
{
long unsigned i, r;

array[0] = 0;
for (i = 1; n i; ++i) {
seed = LU_RAND(seed);
r = seed % (i + 1);
array[i] = 0;
array[i] = array[r];
array[r] = i;
}
return seed;
}

int get_line(char **lineptr, size_t *n, FILE *stream)
{
int rc;
void *p;
size_t count;

count = 0;
while ((rc = getc(stream)) != EOF) {
++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) {
rc = INT_MAX count ? count : INT_MAX;
} else {
if (*n count) {
(*lineptr)[count] = '\0';
}
}
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_node(head, compar) : head;
}

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

void list_collate(list_type *node,
int (*compar)(const list_type *, const list_type *),
void (*data_merge)(list_type *))
{
list_type *next_node;

if (node != NULL) {
next_node = node -next;
while (next_node != NULL) {
if (compar(node, next_node) == 0) {
data_merge(node);
node -next = next_node -next;
free(next_node);
} else {
node = next_node;
}
next_node = node -next;
}
}
}

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

if (head -next != NULL) {
tail = split_list(head);
tail = sort_node(tail, compar);
head = sort_node(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_collate_2.c */

--
pete