C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Nesting Linked Lists?

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C Language (Moderated)
View previous topic :: View next topic  
Author Message
Cyron
Guest
PostPosted: Wed Dec 06, 2006 1:55 am    Post subject: Nesting Linked Lists? Reply with quote


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.
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
nutrina9@gmail.com
Guest
PostPosted: Sat Dec 16, 2006 4:57 am    Post subject: Re: Nesting Linked Lists? Reply with quote


Hy,

you might want use macros to create a "generic list", and also macros
for manipulation:


#define CREATE_LIST_NODE(__NodeName,__DataType)\
struct __NodeName\
{\
struct Node *prev;\
struct Node *next;\
__DataType data;\
};


#define CREATE_LIST(__ListName,__DataType)\
CREATE_LIST_NODE(__ListName##Node,__DataType)\
struct __ListName\
{\
struct Node *first;\
struct Node *last;\
};

CREATE_LIST(IntList,int)

int main()
{
struct IntList list;
struct IntListNode node;
list.first = NULL;
list.last = NULL;
node.data = 3;
node.prev = NULL;
node.next = NULL;
........
}


Gerald


Cyron wrote:
Quote:
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.
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
--

comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Michael Tiomkin
Guest
PostPosted: Sat Dec 16, 2006 4:58 am    Post subject: Re: Nesting Linked Lists? Reply with quote


Cyron wrote:
Quote:
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.

Well, the best solution to your problem is using templates in C++.

Another solution is using #define instead of typedef, and giving a
special name for every linked list you use. Don't forget to insert
#undef after #include.
A small example:

#define LIST_TYPE list1_t
#define LIST_ELEMENT_TYPE int

#include "l_list.h"

#undef LIST_TYPE
#undef LIST_ELEMENT_TYPE

#define LIST_ELEMENT_TYPE list1_t
#define LIST_TYPE list2_t

#include "l_list.h"

#undef LIST_TYPE
#undef LIST_ELEMENT_TYPE

Recall that you can create artificial names for your function types -
you can use concatenation of symbols, e.g. list_empty_, list_Get_ and
list_Add_ with LIST_ELEMENT_TYPE.

Michael
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Jonathan Leffler
Guest
PostPosted: Sat Dec 16, 2006 4:58 am    Post subject: Re: Nesting Linked Lists? Reply with quote
Cyron wrote:
Quote:
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 ;

Isn't that backwards? [...yes; you can't do 'typedef TYPE char' as you
suggest below; you do 'typedef char TYPE'!...]

Quote:
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.

[...notes toward a solution - not a complete answer...]

It seems like you might be attempting 'generic programming' which is
realized in C++ with templates - but you are working with C.

There are a couple of options open to you. One is to use a list
structure that contains a generic 'void *' that points to the data
managed by the list. This certainly can be done - I have code written
yonks ago to manage doubly-linked lists (actually, so many yonks ago
that it didn't use 'void *' - or prototypes - because it wasn't portable
at the time!). This is tricky to do, but was done to implement lists of
integers, character strings, doubles and 'decimal' (a structure type for
computing in decimal arithmetic).

That basic list code can then be specialized for the specific types you
need, or you can use the raw structure and rely on careful programming
to keep things consistent.

Your outline solution sounds like you define a type and compile the code
to build a list management system for that type; change the type and
recompile to build a different type of list. That's probably complex to
handle, especially if the function names depend on the type name.

You can deal with structures simply by:
typedef struct whatnot whatever;
typedef whatever TYPE;

Nesting lists should be a non-problem; your structure that contains a
list is simply wrapped as any other structure is.

--
Jonathan Leffler #include <disclaimer.h>
Email: jleffler (AT) earthlink (DOT) net, jleffler (AT) us (DOT) ibm.com
Guardian of DBD::Informix v2005.02 -- http://dbi.perl.org/
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Chris Thomasson
Guest
PostPosted: Tue Mar 06, 2007 2:42 am    Post subject: Re: Nesting Linked Lists? Reply with quote
"Cyron" <mdigitale (AT) yahoo (DOT) com> wrote in message
news:clcm-20061205-0044 (AT) plethora (DOT) net...
Quote:
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:
[...]

Well,

<pseudo-code / very quick sketch>


you can always create a "common" linked-list impl and api. Something like:
-----------------------
typedef struct dlink_s dlink_t;

struct dlink_s {
dlink_t *nx;
dlink_t *pv;
};

#define DLINK_STATICINIT(__nx, __pv) {(__nx), (__pv)}
#define DLINK_STATICINIT_DEFAULT() DLINK_STATICINIT(0, 0)
#define DLINK_CAST(__dlink, __type) ((__type)(__dlink))

extern void dlink_init(dlink_t*);
extern dlink_t* dlink_push_next(dlink_t*, dlink_t*);
extern dlink_t* dlink_push_prev(dlink_t*, dlink_t*);
extern dlink_t* dlink_pop_next(dlink_t*);
extern dlink_t* dlink_pop_prev(dlink_t*);
extern dlink_t* dlink_load_next(dlink_t*);
extern dlink_t* dlink_load_prev(dlink_t*);
extern void dlink_pop(dlink_t*);

#define dlink_push_front dlink_push_next
#define dlink_push_back dlink_push_prev
#define dlink_pop_front dlink_pop_next
#define dlink_pop_back dlink_pop_prev


/*
the actual impl omitted as its all extremely
trivial basic linked-list stuff.
*/
-----------------------



Then you can extend the api to specific types like this:
-----------------------
typedef struct mynode_s mynode_t;

struct mynode_s {
dlink_t dl;
int myint;
};
-----------------------



and use it like:
-----------------------
static dlink_t mylist = DLINK_STATICINIT_DEFAULT();

int main(void) {
mynode_t *mn;

/* push 64 items */
for(int i = 0; i < 64; ++i) {
mn = malloc(sizeof(mn));
mn->myint = i;
dlink_init(&mn->dl);
dlink_push_next(&mylist, &mn->dl);
}

/* iterate and flush the list */
mn = DLINK_CAST(dlink_pop_front(&mylist), mynode_t*);
while(mn) {
printf("(%p)mynode_t::myint = (%d)\n", (void*)mn, mn->myint);
free(mn);
mn = DLINK_CAST(dlink_pop_back(&mylist), mynode_t*);
}

return 0;
}
-----------------------



Any thoughts?
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Chris Thomasson
Guest
PostPosted: Tue Mar 06, 2007 2:42 am    Post subject: Re: Nesting Linked Lists? Reply with quote
ARGH!

There is an error in the following part of the pseudo code I posted:

/* push 64 items */
for(int i = 0; i < 64; ++i) {
mn = malloc(sizeof(mn));
mn->myint = i;
dlink_init(&mn->dl);
dlink_push_next(&mylist, &mn->dl);
}

should be:

/* push 64 items */
for(int i = 0; i < 64; ++i) {
mn = malloc(sizeof(*mn));
mn->myint = i;
dlink_init(&mn->dl);
dlink_push_next(&mylist, &mn->dl);
}

of course!!! Sorry for any confusion.
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Chris Thomasson
Guest
PostPosted: Tue Mar 06, 2007 2:42 am    Post subject: Re: Nesting Linked Lists? Reply with quote
"Cyron" <mdigitale (AT) yahoo (DOT) com> wrote in message
news:clcm-20061205-0044 (AT) plethora (DOT) net...
Quote:
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:

[...]

To answer you question on a list within a list, well, that can be as simple
as this:


<I will use the pseudo-code list implementation I just posted (the dlink
API)>

<quick sketch...>

-----------------------
typedef struct mynode_s mynode_t;
typedef struct myothernode_s myothernode_t;

struct myothernode_s {
dlink_t dl;
short myshort;
};

struct mynode_s {
dlink_t dl;
dlink_t ol;
int myint;
};

-----------------------



and use it like:
-----------------------
static dlink_t mylist = DLINK_STATICINIT_DEFAULT();

int main(void) {
mynode_t *mn;
myothernode_t *on;


/* push 64 items */
for(int i = 0; i < 64; ++i) {
mn = malloc(sizeof(*mn));
mn->myint = i;
dlink_init(&mn->dl);
dlink_init(&mn->ol);

/* push 10 items on the other list */
for(short x = 0; x < 10; ++x) {
on = malloc(sizeof(*on));
on->myshort = x;
dlink_init(&on->dl);
dlink_push_next(&mn->ol, &on->dl);
}

dlink_push_next(&mylist, &mn->dl);
}



/* iterate and flush the list */
mn = DLINK_CAST(dlink_pop_front(&mylist), mynode_t*);
while(mn) {
printf("(%p)mynode_t::myint = (%d)\n", (void*)mn, mn->myint);

/* iterate and flush the other list */
on = DLINK_CAST(dlink_pop_front(&mn->ol), myothernode_t*);
while(on) {
printf(" (%p)myothernode_t::myshort = (%d)\n", (void*)on,
on->myshort);
free(on);
on = DLINK_CAST(dlink_pop_front(&mn->ol), myothernode_t*);
}

free(mn);
mn = DLINK_CAST(dlink_pop_front(&mylist), mynode_t*);
}

return 0;
}
----------------------



Sorry if there are any typos in there.. I just typed this out very quickly!

;^)
--
comp.lang.c.moderated - moderation address: clcm (AT) plethora (DOT) net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C Language (Moderated) All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.