counting linked lists

[Hans Vlems]

Several programs use linked lists of structures:

struct eksample {
<various declarations>;
struct eksample *e_next;
};

There are quite a few of these datastructures and each one uses its
own function that counts the number of elements in the linked list. Is
it possible to have just one function which may be used for all
structs and returns the number of elements in the linked list?
Hans

 

[Eric Sosman]

Several programs use linked lists of structures:

struct eksample {
<various declarations>;
struct eksample *e_next;
};

There are quite a few of these datastructures and each one uses its
own function that counts the number of elements in the linked list. Is
it possible to have just one function which may be used for all
structs and returns the number of elements in the linked list?
Hans

size_t listLength(const void *anyList, size_t linkOffset) {
size_t count = 0;
while (anyList != NULL) {
anyList = *(struct unknown*)
((char*)anyList + linkOffset);
}
return count;
}

Call it like this:

#include <stddef.h>
...
struct eksample *head = ...;
size_t length = listLength(head,
offsetof(struct eksample, next));
...
struct frinstance *list = ...;
size_t census = listLength(list,
offsetof(struct frinstance, link));

 

[bantu]

Put the link as the first field.

    struct genericlist {struct genericlist *e_link;}

Define your other list structs with this as the first field.

    struct list1 {
        struct list1 e_link;
        A a; B b;
    }
    struct list2 {
        struct list2 e_link;
        C c; D d;
    }

You can safely cast (struct listN*) to (struct genericlist*):

    int genericlistLength(struct genericlist *list) {...}
    ...

    #define list1Length(list) (genericlistLength((struct genericlist*)list))
    A list1abba(struct list1 list) {...}

    #define list2Length(list) (genericlistLength((struct genericlist*)list))
    C list2cab(struct list2 list) {...}

--
My name Indigo Montoya.      |    R'lyeh 38o57'6.5''S 102o51'16''E.
You flamed my father.        |       I'm whoever you want me to be.
Prepare to be spanked.       |  Annoying Usenet one post at a time.
Stop posting that!           |    At least I can stay in character.

Thank you for the example.
I am unable to understand the the following two lines marked b/w
'<<<<<<<' and '>>>>>>>'. Could you please help explain them ? Are they
a continuation of the macro definition ? I am confused about the
purpose of list1abba and list2cab in the example.

#define list1Length(list) (genericlistLength((struct
genericlist*)list))
<<<<<<< A list1abba(struct list1 list) {...} >>>>>>>

#define list2Length(list) (genericlistLength((struct
genericlist*)list))
<<<<<<< C list2cab(struct list2 list) {...} >>>>>>>

Best Regards, Naveen

 

[ImpalerCore]

Several programs use linked lists of structures:

struct eksample {
                          <various declarations>;
                          struct eksample *e_next;
                        };

There are quite a few of these datastructures and each one uses its
own function that counts the number of elements in the linked list. Is
it possible to have just one function which may be used for all
structs and returns the number of elements in the linked list?

On the flip side, if you're willing to write a list interface that
uses a void* to point to an object, you can do something along these
lines.

\code snippet
/*!
* \struct c_list
* \brief The \c c_list struct is used as the list node for a
* double-linked list.
*/
struct c_list
{
/*!
* \brief The list node object, which can reference any type, and
* may point to a dynamically allocated object.
*/
void* object;

/*! \brief The link to the previous object in the list. */
struct c_list* prev;

/*! \brief The link to the next object in the list. */
struct c_list* next;
};

/*!
* \brief Get the number of objects in a \c c_list.
* \param list A \c c_list.
* \return The number of objects in the \c c_list.
*
* This function iterates over the whole list to count its objects,
* meaning that it can be slow for large lists.
*/
size_t c_list_length( struct c_list* list )
{
size_t length = 0;

while ( list ) /* equivalent to 'list != NULL' */
{
++length;
list = list->next;
}

return length;
}
\endcode

Whether you prefer linked lists that are embedded in the struct
object, or reference objects from a void* is a matter of preference,
with different pros and cons. Referencing an object from a void*
removes the need to use offsetof and other struct tricks to count
nodes in a list, and c_list_length will be the only function you ever
need to count objects in a double linked list stored using c_list
nodes. Of course this comes with a maintenance cost of manual type
casting (whether directly to the node object or packaging the cast
through a macro), and an extra level of indirection to access a list
node's data. GLib is an example library that uses this style of
linked list.

Best regards,
John D.

 

[Barry Schwarz]

size_t listLength(const void *anyList, size_t linkOffset) {
size_t count = 0;
while (anyList != NULL) {
anyList = *(struct unknown*)
((char*)anyList + linkOffset);

Shouldn't the first cast be (struct unknown**)?

Shouldn't there be a count++; here?

 

[tom st denis]

Several programs use linked lists of structures:

struct eksample {
                          <various declarations>;
                          struct eksample *e_next;
                        };

There are quite a few of these datastructures and each one uses its
own function that counts the number of elements in the linked list. Is
it possible to have just one function which may be used for all
structs and returns the number of elements in the linked list?
Hans

struct hostlist {
int type;
void *members;
struct hostlist *next;
};

Then you can assign whatever struct pointer to members you want and
use type to distinguish between different types.

That would be the clean and portable way to generate a list of
different data types.

Tom

 

[Eric Sosman]

Shouldn't the first cast be (struct unknown**)?

Yes: Typing with too much haste and too little coffee.

Shouldn't there be a count++; here?

Yes: Began with `for(count = 0; anyList != NULL; ++count)',
decided that was confusing, made an incomplete edit, and confused
things even worse.

[Insert unstated correction/improvement/comment here]

Yes, most likely. (Sigh.) Thanks for the catch(es).

 

[Hans Vlems]

On Wed, 11 Apr 2012 08:49:25 -0400, Eric Sosman

Shouldn't the first cast be (struct unknown**)?

     Yes: Typing with too much haste and too little coffee.

Shouldn't there be a count++; here?

     Yes: Began with `for(count = 0; anyList != NULL; ++count)',
decided that was confusing, made an incomplete edit, and confused
things even worse.

     [Insert unstated correction/improvement/comment here]

     Yes, most likely.  (Sigh.)  Thanks for the catch(es).

--
Eric Sosman
(e-mail address removed)- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

No problem Eric, it's not that my programming skills are bad just my
understanding of the finer C syntax issues ;-)
Hans

 

[Hans Vlems]

On the flip side, if you're willing to write a list interface that
uses a void* to point to an object, you can do something along these
lines.

\code snippet
/*!
 * \struct c_list
 * \brief The \c c_list struct is used as the list node for a
 *        double-linked list.
 */
struct c_list
{
  /*!
   * \brief The list node object, which can reference any type, and
   *        may point to a dynamically allocated object.
   */
  void* object;

  /*! \brief The link to the previous object in the list. */
  struct c_list* prev;

  /*! \brief The link to the next object in the list. */
  struct c_list* next;

};

/*!
 * \brief Get the number of objects in a \c c_list.
 * \param list A \c c_list.
 * \return The number of objects in the \c c_list.
 *
 * This function iterates over the whole list to count its objects,
 * meaning that it can be slow for large lists.
 */
size_t c_list_length( struct c_list* list )
{
  size_t length = 0;

  while ( list )  /* equivalent to 'list != NULL' */
  {
    ++length;
    list = list->next;
  }

  return length;}

\endcode

Whether you prefer linked lists that are embedded in the struct
object, or reference objects from a void* is a matter of preference,
with different pros and cons.  Referencing an object from a void*
removes the need to use offsetof and other struct tricks to count
nodes in a list, and c_list_length will be the only function you ever
need to count objects in a double linked list stored using c_list
nodes.  Of course this comes with a maintenance cost of manual type
casting (whether directly to the node object or packaging the cast
through a macro), and an extra level of indirection to access a list
node's data.  GLib is an example library that uses this style of
linked list.

Best regards,
John D.

John,
your example clarifies the issue quite well. It does assume that all
structures
use a linking pointer with the same name, viz. *next.
Of course when the structures were put together, each pointer has a
different name so that a
typing mistake will be caught at compile time.
Thank you and all the others who responded!

Hans

 

[Hans Vlems]

Several programs use linked lists of structures:

struct eksample {
                         <various declarations>;
                         struct eksample *e_next;
                       };

There are quite a few of these datastructures and each one uses its
own function that counts the number of elements in the linked list. Is
it possible to have just one function which may be used for all
structs and returns the number of elements in the linked list?
Hans

i seen the asm file...my implementation of list not double list,
if i see right is this:

one_list:
u32   ThreadValue=0;  0
u32*  ListPointer=0;  4

ListPointeer:
u32   ListNumberOfNodes=0  0
u32*  PointerHeadNode=0    4
u32*  PointerTailNode=0    8

ListNode:
u32*  PointerToNext=0;           0
u8*   PointerToNodeElement=0;    4

where uNumber means one unsigned of Number bits,
and * means pointer to
char is u8
4 char is u32

u32* w; "w" is a place aligned 4 chars
      that contain a value that is an address aligned 4 char
u8*  w; 'w' is a place aligned 4 chars
      that contain a value that is an address aligned   char

i see them as one set of offsets... one set of define numebers
[the numbers in the rights]

in the asm way for doing a void list...
list  dd  0, 0
asm mem space in .data section or in one stack [inside one function]

if a, b are 32 bits and "D" means dword [the space for u32]
D[list+4]=malloc(3*4) if it is ok...
     a=[list+4]| D[a]=0| D[a+4]=malloc(2*4) if it is ok
                         b=[a+4]| D=0| D[b+4]=0

this for me can rapresent in good way simple lists of all data type;
but one have to do an exensive use of malloc() free()

here it seems people differ from me because like more easy
implementation of general list... i'm not agree
for say the true i would erase all these list implementatio my too
for my "double list"

all the function are left for exercise...it seems lists call for
the right functions...

Have good days

Umm, I had to read that twice to understand what you were trying to
tell us.
Let me put it this way, you're obviously a programmer who believes
that you can write assembler
in any language, right?
The way I read your answer is that it kind of offers proof for the
solution China Blue Water Navy offered.

Hans

 

[Hans Vlems]

"io_x" <[email protected]> ha scritto nel messaggio


yes, because that number is in memory, in the C way something as
u32 function(u32*  plist)
{if(NotGood(plist))  return -1;
 return  *(plist[1]);

}

but i'm not sure it is rght...

i seen the asm file...my implementation of list not double list,
if i see right is this:

one_list:
u32   ThreadValue=0;  0
u32*  ListPointer=0;  4

ListPointeer:
u32   ListNumberOfNodes=0  0
u32*  PointerHeadNode=0    4
u32*  PointerTailNode=0    8

ListNode:
u32*  PointerToNext=0;           0
u8*   PointerToNodeElement=0;    4- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

That number may be in memory but doesn't need to be there. That's why
a linked list of struct is preferable over an
array of struct. Unless you've got arrays with dynamic sizes of
course, and the C compiler I have here doesn't do that.
Hans