Nesting Linked Lists?

[Cyron]

Hello Friends,

I would like to implement a linked list in C that can be re-used to
store various datatypes. In the past, I've declared something like:

typedef TYPE type_of_data_in_list ;

at the top of my header (where type_of_data_in_list was something like
int, char, etc..) and things always worked well. I am now wondering
how I should go about storing a list...which contains a list. For
example, if I have a struct A which contains a List of chars, i would
simply start off my file with typedef TYPE char; But what do I do if I
want to create a List of struct A's? I can't simply add typedef TYPE
struct A ; to the file because that would get rid of the reference a
depends on internally?

Hopefully someone understands what I'm saying and can point me to a
solution.

Thank you in advance,
Mike.

 

[Marc Boyer]

I would like to implement a linked list in C that can be re-used to
store various datatypes. In the past, I've declared something like:

typedef TYPE type_of_data_in_list ;

at the top of my header (where type_of_data_in_list was something like
int, char, etc..) and things always worked well. I am now wondering
how I should go about storing a list...which contains a list. For
example, if I have a struct A which contains a List of chars, i would
simply start off my file with typedef TYPE char; But what do I do if I
want to create a List of struct A's? I can't simply add typedef TYPE
struct A ; to the file because that would get rid of the reference a
depends on internally?

Hopefully someone understands what I'm saying and can point me to a
solution.

I know two kinds of solutions:
1) first is based on void*, that is to say you write a list that
handle pointers on any type (but you loose type checking)
2) second is to generates macro names

You can have a look at my BPL librairy that use the 2d solution:
http://www.enseeiht.fr/~boyer/Tools.html (any feedback welcomed)

Marc Boyer

 

[A. Farber]

Hello Mike,

lists of lists etc. are easy with those macros:
http://www.openbsd.org/cgi-bin/man.cgi?query=queue

contained in this header (which you could copy into you program):
http://www.openbsd.org/cgi-bin/cvsweb/src/sys/sys/queue.h?rev=1.31

(and you can debug with -DQUEUE_MACRO_DEBUG ).

Smth. like (untested):

typedef struct list {
TAILQ_ENTRY(list) entry;
int data;
} list;

typedef struct lol {
TAILQ_ENTRY(lol) entry;
TAILQ_HEAD(, list) head;
} lol;

Regards
Alex

 

[pete]

I am now wondering
how I should go about storing a list...which contains a list.

/* BEGIN listolists.c output */

Man number 1
Initials: O.
Age : 32
Phone numbers:
163-4945
434-9890
785-6541
432-9672

Man number 2
Initials: B.L.
Age : 36
Phone numbers:
945-4349
890-7856
541-4329
672-3216

Man number 3
Initials: J.
Age : 24
Phone numbers:
349-8907

Man number 4
Initials: S.F.G.
Age : 24
Phone numbers:
907-8565
414-3296
723-2165
238-3036
381-0527

Man number 5
Initials: F.G.
Age : 20
Phone numbers:
565-4143
296-7232
165-2383

/* END listolists.c output */


/* BEGIN list_of_lists.c */

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

#define PEOPLE_MAX 5
#define NAME_LENGTH 3
#define UPPER "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069LU + 362437 & 0xffffffff)

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

typedef struct list_node list_type;

struct person {
char name[2 * NAME_LENGTH + 1];
int age;
list_type *phone_numbers;
};

list_type *list_make(long unsigned count);
list_type *man_init(list_type *node, long unsigned seed);
list_type *number_init(list_type *node, long unsigned seed);
void make_name(char *name, size_t length, long unsigned seed);
int man_print(list_type *node);
int number_print(list_type *node);
void list_free(list_type *node, void (*free_data)(void *));
void person_free(void *data);

int main(void)
{
list_type *head;
long unsigned seed = LU_RAND_SEED;

puts("/* BEGIN listolists.c output */");
head = list_make(1 + seed % PEOPLE_MAX);
if (head == NULL) {
puts("No list");
}
seed = LU_RAND(seed);
if (man_init(head, seed) != NULL) {
man_print(head);
}
list_free(head, person_free);
puts("\n/* END listolists.c output */");
return 0;
}

list_type *list_make(long unsigned count)
{
list_type *node, *list;

list = count != 0 ? malloc(sizeof *list) : NULL;
if (list != NULL) {
node = list;
while (--count != 0) {
node -> data = NULL;
node -> next = malloc(sizeof *node -> next);
if (node -> next == NULL) {
list_free(list, free);
return NULL;
} else {
node = node -> next;
}
}
node -> data = NULL;
node -> next = NULL;
}
return list;
}

list_type *man_init(list_type *node, long unsigned seed)
{
list_type *head;
struct person man;

head = node;
while (node != NULL) {
node -> data = malloc(sizeof man);
if (node -> data == NULL) {
puts("man_init malloc problem");
head = NULL;
break;
}
seed = LU_RAND(seed);
make_name(man.name, NAME_LENGTH, seed);
seed = LU_RAND(seed);
man.age = 20 + seed % 20;
seed = LU_RAND(seed);
man.phone_numbers = list_make(1 + seed % PEOPLE_MAX);
if (man.phone_numbers == NULL) {
puts("man.phone_numbers == NULL");
head = NULL;
break;
}
seed = LU_RAND(seed);
if (number_init(man.phone_numbers, seed) == NULL) {
puts("man_init(man.phone_numbers, seed) == NULL");
head = NULL;
break;
}
*(struct person *)node -> data = man;
node = node -> next;
}
return head;
}

list_type *number_init(list_type *node, long unsigned seed)
{
list_type *head;
size_t count;
char *string;

head = node;
while (node != NULL) {
node -> data = malloc(sizeof "xxx-xxxx");
if (node -> data == NULL) {
puts("number_init malloc problem.");
head = NULL;
break;
}
string = node -> data;
count = sizeof "xxx-xxxx" - 1;
while (count-- != sizeof "-xxxx" - 1) {
seed = LU_RAND(seed);
*string++ = (char)('0' + seed % 10);
}
*string++ = '-';
while (count-- != 0) {
seed = LU_RAND(seed);
*string++ = (char)('0' + seed % 10);
}
*string = '\0';
node = node -> next;
}
return head;
}

int man_print(list_type *node)
{
long unsigned count;
struct person *man;
int rc;

for (count = 1; node != NULL; ++count) {
man = node -> data;
rc = printf
("\nMan number %lu\n"
"Initials: %s\n"
"Age : %d\nPhone numbers:\n",
count, man -> name, man -> age);
if (EOF == rc) {
break;
}
number_print(man -> phone_numbers);
node = node -> next;
}
return node == NULL ? 1 : EOF;
}

int number_print(list_type *node)
{
while (node != NULL
&& printf(" %s\n", (char *)node -> data) != EOF)
{
node = node -> next;
}
return node == NULL ? 1 : EOF;
}

void make_name(char *name, size_t length, long unsigned seed)
{
length -= seed % length ;
while (length-- != 0) {
seed = LU_RAND(seed);
*name++ = UPPER[seed % sizeof UPPER];
*name++ = '.';
}
*name = '\0';
}

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

void person_free(void *data)
{
list_free(((struct person *)data) -> phone_numbers, free);
free(data);
}

/* END list_of_lists.c */