[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Node to first or last element of a sequential list in module list/xl
From: |
Bruno Haible |
Subject: |
Re: Node to first or last element of a sequential list in module list/xlist |
Date: |
Sat, 03 Apr 2021 00:49:37 +0200 |
User-agent: |
KMail/5.1.3 (Linux/4.4.0-206-generic; KDE/5.18.0; x86_64; ; ) |
Hi Marc,
> At the moment, there does not seem to be an easy way to retrieve the node
> of the first or the last element in a list.
The purpose of the gl_list_node_t is to write algorithms that work
efficiently with linked-lists, when it is necessary (for performance)
to hold a reference to a linked-list node that is far from the first and
far from the last linked-list node.
For the first and the last node in a list, there is no such performance
problem. Hence what you ask for is not needed.
> This is useful if the list has to be traversed while nodes are added
> because an iterator cannot be used here.
I don't understand. You want to use a list_node_t while adding nodes to
the list? This is invalid, since the comments in gl_list.h say:
/* Type representing the position of an element in the list, in a way that
is more adapted to the list implementation than a plain index.
Note: It is invalidated by insertions and removals! */
typedef struct gl_list_node_impl * gl_list_node_t;
> What is currently possible is to use get_first/set_first (and
> get_last/set_last) to get hold of the first (and last) node but this is
> clearly a hack.
>
> Another way to get hold of the first node is to create an iterator and to
> call its next procedure just once. But this is overkill if the iterator
> isn't used afterward.
Yes these are two existing ways to do what you want. An iterator is a
small stack-allocated object; it is designed for being created and then
thrown away soon afterwards.
> What I want to propose is to allow the NULL value in
> gl_next_node/gl_previous_node. In this case, gl_next_node shall return the
> first node and gl_previous_node shall return the last node.
It's not useful to extend an API
- for a rare fringe use-case,
- when there are already two other ways to do what you ask for (with the
same O(·) performance).
Bruno
- Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/02
- Re: Node to first or last element of a sequential list in module list/xlist,
Bruno Haible <=
- Re: Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Bruno Haible, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Bruno Haible, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Bruno Haible, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/03
- Re: Node to first or last element of a sequential list in module list/xlist, Bruno Haible, 2021/04/03
- Message not available
- Re: Node to first or last element of a sequential list in module list/xlist, Bruno Haible, 2021/04/04
- Re: Node to first or last element of a sequential list in module list/xlist, Marc Nieper-Wißkirchen, 2021/04/05