the data structure -- doubly linked chains:

[Sergei Organov]

"Bert"<doclzs at 21cn.com> writes:

> (1)what is the order of nodes in the chains?
> it is like the head, the first, the second, ...,
> the last, the tail or the head is also the first
> and the tail is also the last?

I'd say neither of these. I think head and tail aren't members of the chain at
all, i.e., they are used as chain boundaries that aren't included into the
chain. It's similar to an open integer interval, say, ]0..5[, where 0 is the
head and 5 is the tail, but neither of them belongs to the interval [1..4].

I believe the structure is as follows [1], where both head and tail are put
into the Chain_Control structure called CHAIN on the drawing:

|       +-----+     +----+  +----+       +----+
|       |CHAIN|     |1'st|  |2'nd|       |last|
|       +-----+     +----+  +----+       +----+
|       |first*---->|next*->|next*->...->|next*----+
|   +--->null |<----*prev|<-*prev|<-...<-*prev|<-+ |
|   | +-*last |     +----+  +----+       +----+  | |
|   | | +-----+                                  | |
|   | +------------------------------------------+ |
|   +----------------------------------------------+

> (2)the function:
>
> RTEMS_INLINE_ROUTINE Chain_Node *_Chain_Tail(
> Chain_Control *the_chain
> )
> {
>   return (Chain_Node *) &the_chain->permanent_null;
> }
>
> is it necessary to use the operator "&" ?

Yes.  Without '&' the function will return the value stored in the
'permanent_null' field that is undefined before initialization and is always
NULL after initialization.

> is it right to implement the function as follows:
>   return (Chain_Node *) (the_chain->last)->next;

Maybe, but there is no reason to implement it like this due to the following
two deficiencies:

1. The latter implementation is less efficient as it requires two pointer
   dereferences to fetch actual value, while the former requires only adding
   constant offset to the value of 'the_chain'.

2. The latter implementation won't bring correct result until Chain_Control is
   correctly initialized while the former brings correct result always.

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

[1] I'd like to figure out what actual advantages does the structure have over
more usual and straightforward circular doubly-linked list implementation[2]:

|       +----+      +----+  +----+       +----+
|       |TOP |      |1'st|  |2'nd|       |last|
|       +----+      +----+  +----+       +----+
|   +-->|next*----->|next*->|next*->...->|next*----+
|   | +-*prev|<-----*prev|<-*prev|<-...<-*prev|<-+ |
|   | | +----+      +----+  +----+       +----+  | |
|   | +------------------------------------------+ |
|   +----------------------------------------------+

where TOP itself is of type Chain_Node (making Chain_Control type somewhat
redundant) and both _Chain_Head and _Chain_Tail are defined as just:

  return the_chain;

Does anybody have a clue?

[2] The only advantage I see is that _Chain_Has_only_one_node() that currently
is implemented like:

  return the_chain->first == the_chain->last;

would become

  return the_chain->first == the_chain->last && the_chain->first != the_chain;

that is less efficient. However, most (if not all) the usages of this routine
are under condition '!_Chain_Is_empty()' and so they could be replaced by
something called _Chain_Has_less_than_two_nodes() which implementation is

  return the_chain->first == the_chain->last;

I don't suggest to change current implementation for a practical reason that
it works and clarity and simplicity aside the usual implementation doesn't
have sound advantages.

Anyway, my feeling is that advantages of the usual approach overweight
those of the current implementation if we were to decide which one to use from
scratch. Am I missing something?

-- 
Sergei.