Re: Using a link list over an array.

pete wrote:
Ben Bacarisse wrote:
CBFalconer <cbfalconer@xxxxxxxxx> writes:

pete wrote:
pereges wrote:
Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:

With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key
code. Maybe the problem is in that part not shown.
Now, its working after I made some changes. Some changes
head = mergesort(head, cmp);

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}
It makes more sense to prototype mergesort this way:

node *mergesort(node *, int (*)(node *, node *));

and to also make the corresponding changes
in the function definition.

Then you can write cmp without casts:
I disagree. The code module I posted can be compiled and linked
into whatever needs a mergesort.

Only if the data is indirect -- can be pointed to by a void *.

It doesn't need to know anything
about the data.

You can't use it (portably) to sort a list of ints where the int is
inside the node or indeed any node that contains the actual data. I
suspect this sort of thing matters to pete.

Other way.
You can use it to sort a list of pointers to any type.

/*
** sort a list of pointers to string representations of long unsigned
*/

/* BEGIN file_sort_2.c */
/*
From news:comp.lang.c

> program that reads 3 list of numbers,
> which are stored in three seperate files,
> and creates one sorted list.
> Each file should contain not more than 15 numbers.
*/
#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) * 69069LU + 362437 & 0XFFFFFFFF)
#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);
int list_fputs(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_list (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)
{
int rc;
char fn[L_tmpnam];
FILE *fp;
long unsigned index, line;
long unsigned lu_seed = LU_RAND_SEED;
char *buff = NULL;
size_t size = 0;
list_type *head = NULL;
list_type *tail = NULL;

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.
*/
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, rc);
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;
/*
** The (char) casts in this function are not required
** by the rules of the C programming language.
*/
count = 0;
while ((rc = getc(stream)) != EOF
|| !feof(stream) && !ferror(stream))
{
++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 || !feof(stream) && !ferror(stream)) {
rc = INT_MAX > count ? count : INT_MAX;
} else {
if (*n > count) {
(*lineptr)[count] = '\0';
}
}
return rc;
}

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_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_list(head, compar) : head;
}

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

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

Relevant Pages