linked lists and a matter of terminology

[Yann E. MORIN]

Michael, Robert,
All,

On Friday 19 May 2006 165, Michael S. Zick wrote:
> On Fri May 19 2006 09:34, Robert P. J. Day wrote:
[--SNIP long discussion on list terminology--]

OK, after a litle bit of documenting on wikipedia.org:

From http://en.wikipedia.org/wiki/List
 Definition:
  "In computer science, a list is usually defined as an instance of an
  "abstract data type (ADT) formalizing the concept of an ordered collection
  "of entities. ...

 Supported operations:
  - constructor
  - is list empty or not?
  - add as first element (cons)
  - get first element (car)
  - get list except first element (cdr)

So, to date, of the above, we do 'implement':
  - the list _*is*_ ordered.
  - the constructor is implicit when adding to an empty list;
  - checking if the list is empty is feasible by testing llist_t.link == NULL
  - "cons" is implemented;
  - car and cdr are same function: llist_pop which return the first element
    and removes it from the list;

We also have:
  - add at the end of the list, which is a requirement for us.
  - delete a list, optionally deleting the data stored in each element.

I'm not really happy with the current llist functions naming either.
What about the following API?

  typedef struct llist_s {
      struct llist_s* prev;    /* See note 1, below */
      struct llist_s* next;
      void*           data;
  } llist_t;

  llist_t *llist_prepend (llist_t *head, void *data);
      adds a new list element, which data is 'data', at the beggining of the
      list pointed to by 'head';

  llist_t *llist_append (llist_t *head, void *data);
      adds a new list element, which data is 'data', at the end of the list
      pointed to by 'head';

  void *llist_first (llist_t *head);
      returns the data in the first element of the list pointed to by 'head';

  void *llist_last (llist_t *head);
      returns the data in the last element of the list pointed to by 'head';

  void *llist_rm_first (llist_t **head);  /* See note 2, below */
      returns the data in the first element of the list pointed to by 'head',
      and removes the first element in the list;

  void *llist_rm_last (llist_t **head);   /* See note 2, below */
      returns the data in the last element of the list pointed to by 'head',
      and removes the last element in the list.

  void llist_free (llist_t* head, void (*freeit)(void *data));
      Recursively free all elements in the linked list.  If freeit != NULL
      call it on each datum in the list

As a convenience, llist_rm_{first,last} return the data stored in the removed
element. Because code already uses that, and because it might generate smaller
code (saves a function call), and because it might generate faster code (saves
calling a function, and in case of llist_rm_last, saves running through the
entire list a second time).

If you just want to shorten the list (from head or tail), then you just have
to discard the data returned by calls to llist_rm_{first,last}.

Running through the list is up to the user, by means of the next and prev fields
of the llist_t structure.

I'm ready to implement this.

Note 1:
The 'prev' field will be conditional to its use in an applet, as discussed
before with Bernhard in this thread:
    http://www.busybox.net/lists/busybox/2006-May/021645.html

Note 2:
I'm not very happy with some functions taking a pointer to an element, and some
others taking a pointer to a pointer to an element... When calling functions
of the same 'kind', I'd rather always use the same 'semantics'.
It could be avoided by carefully writing macros that'd encapsulate the calls to
llist_rm_*, but I don't like macros much more...
Any ideas?
Example, so that all llist_* functions take a pointer to a list element:

  #define llist_rm_first(head) _llist_rm_first(&(head))
  void *_llist_rm_first (llist_t **head);

Note 3:
As for other operations ( llist_insert_{before,after} llist_rm_{prev,next},
and so on ), we don't really need these for now. Anyway it would be easy to
implement once it is required.

Regards,
Yann E. MORIN.

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +0/33 662376056 | Software  Designer | \ / CAMPAIGN     |   ^                |
| --==< °_° >==-- °---.----------------:  X  AGAINST      |  /e\  There is no  |
| web: ymorin.free.fr | SETI at home 3808 | / \ HTML MAIL    |  """  conspiracy.  |
°---------------------°----------------°------------------°--------------------°