D
dmp
What are Linked list? Please somebody show some ready made programs of
linked list
linked list
R
Randy Howard
Time to change your major.
R
Richard Heathfield
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;
}
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;
}
I
Ivan Novick
Every heard of a search engine?
http://en.wikipedia.org/wiki/Linked_list
Regards,
Ivan Novick
http://www.0x4849.net
M
mekaju2001
P
pete
I think you have a link quoting problem.
Here are five ready made programs of linked list:
string_sort_2.c
Lf_sort_2.c
file_sort_2.c
file_parse_2.c
file_collate_2
I'll post the first one here, and then the rest as replies.
string_sort_2.c sorts strings by length because that's
a simple way to show the stability of the sorting function.
/* BEGIN string_sort_2.c */
/*
** Demonstration of use of generic list functions
** to sort a list of strings.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node {
struct list_node *next;
void *data;
};
typedef struct list_node list_type;
#define NUMBERS \
{"one","two","three","four","five",\
"six","seven","eight","nine","ten"}
#define NMEMB(A) (sizeof (A) / sizeof *(A))
int lencomp(const list_type *a, const list_type *b);
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);
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_node (list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *split_list(list_type *head);
static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
int main(void)
{
list_type *head;
list_type *tail;
char *numbers[] = NUMBERS;
char **const after = numbers + NMEMB(numbers);
char **ptr;
puts("/* BEGIN string_sort_2.c output */");
puts("\nOriginal order of list of pointers to strings:");
tail = head = NULL;
for (ptr = numbers; ptr != after; ++ptr) {
tail = list_append(&head, tail, *ptr, strlen(*ptr) + 1);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
list_fputs(head, stdout);
puts("\nList after stable mergesort by string length:");
head = list_sort(head, lencomp);
list_fputs(head, stdout);
list_free(head, free);
puts("\n/* END string_sort_2.c output */");
return 0;
}
int lencomp(const list_type *a, const list_type *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;
}
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;
}
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}
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 string_sort_2.c */
Here are five ready made programs of linked list:
string_sort_2.c
Lf_sort_2.c
file_sort_2.c
file_parse_2.c
file_collate_2
I'll post the first one here, and then the rest as replies.
string_sort_2.c sorts strings by length because that's
a simple way to show the stability of the sorting function.
/* BEGIN string_sort_2.c */
/*
** Demonstration of use of generic list functions
** to sort a list of strings.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list_node {
struct list_node *next;
void *data;
};
typedef struct list_node list_type;
#define NUMBERS \
{"one","two","three","four","five",\
"six","seven","eight","nine","ten"}
#define NMEMB(A) (sizeof (A) / sizeof *(A))
int lencomp(const list_type *a, const list_type *b);
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);
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_node (list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *split_list(list_type *head);
static list_type *merge_lists(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
int main(void)
{
list_type *head;
list_type *tail;
char *numbers[] = NUMBERS;
char **const after = numbers + NMEMB(numbers);
char **ptr;
puts("/* BEGIN string_sort_2.c output */");
puts("\nOriginal order of list of pointers to strings:");
tail = head = NULL;
for (ptr = numbers; ptr != after; ++ptr) {
tail = list_append(&head, tail, *ptr, strlen(*ptr) + 1);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
list_fputs(head, stdout);
puts("\nList after stable mergesort by string length:");
head = list_sort(head, lencomp);
list_fputs(head, stdout);
list_free(head, free);
puts("\n/* END string_sort_2.c output */");
return 0;
}
int lencomp(const list_type *a, const list_type *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;
}
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;
}
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}
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 string_sort_2.c */
P
pete
pete said:
Lf_sort_2.c is almost the same program,
with long doubles instead of strings
using most of the same generic list functions.
/* BEGIN Lf_sort_2.c */
/*
** Demonstration of use of generic list functions
** to sort a list of long double values.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUMBERS \
{15,14,13,7,20,9,8,12,11,6}
#define NMEMB(A) (sizeof (A) / sizeof *(A))
struct list_node {
struct list_node *next;
void *data;
};
typedef struct list_node list_type;
int Lf_comp(const list_type *a, const list_type *b);
int list_fprintf_Lf(const list_type *node, FILE *stream);
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size);
void list_free(list_type *node, void (*free_data)(void *));
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));
static list_type *sort_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)
{
list_type *head;
list_type *tail;
long double numbers[] = NUMBERS;
long double *const after = numbers + NMEMB(numbers);
long double *ptr;
puts("/* BEGIN Lf_sort_2.c output */");
puts("\nOriginal order of list of long doubles:");
tail = head = NULL;
for (ptr = numbers; ptr != after; ++ptr) {
tail = list_append(&head, tail, ptr, sizeof *ptr);
if (tail == NULL) {
puts("malloc trouble!");
break;
}
}
list_fprintf_Lf(head, stdout);
puts("\nList after mergesort:");
head = list_sort(head, Lf_comp);
list_fprintf_Lf(head, stdout);
list_free(head, free);
puts("\n/* END Lf_sort_2.c output */");
return 0;
}
int Lf_comp(const list_type *a, const list_type *b)
{
long double *const a_Lf_ptr = a -> data;
long double *const b_Lf_ptr = b -> data;
return *b_Lf_ptr > *a_Lf_ptr ? -1 : *b_Lf_ptr != *a_Lf_ptr;
}
int list_fprintf_Lf(const list_type *node, FILE *stream)
{
int rc = 0;
while (node != NULL) {
long double *const Lf_ptr = node -> data;
if (0 > (rc = fprintf(stream, "%Lf\n", *Lf_ptr))) {
break;
}
node = node -> next;
}
return rc;
}
list_type *list_append
(list_type **head, list_type *tail, void *data, size_t size)
{
list_type *node;
node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(size);
if (node -> data != NULL) {
memcpy(node -> data, data, size);
if (*head != NULL) {
tail -> next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}
void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;
while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}
list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return head != NULL ? sort_node(head, compar) : head;
}
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 Lf_sort_2.c */
P
pete
pete said:
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
*/
#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 */
P
pete
pete said:
file_parse_2.c is the only one of the bunch
that doesn't do any sorting.
/* BEGIN file_parse_2.c */
/*
From
*/
#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 */
P
pete
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 = 0;
array = 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 */
/* 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 = 0;
array = 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 */