---

12.3.8.8 Doubly linked ordered list of size_t ¶

An ordered list of indices is required in many contexts, one example was discussed at the beginning of Ordered list of size_t. But the list that was introduced there only has one point of entry: you can always only parse the list from smallest to largest. In this section, the doubly-linked gal_list_dosizet_t node is defined which will allow us to parse the values in ascending or descending order.

Type (C struct): gal_list_dosizet_t ¶

Doubly-linked, ordered size_t list node structure. Each node in this Doubly-linked list contains a size_t value and a floating point value. The floating point value is used as a reference to add new nodes in a sorted manner. In the functions here, this linked list can be pointed to by two pointers (largest and smallest) with the following format:

            largest pointer
            |
   NULL <-- (v0,s0) <--> (v1,s1) <--> ... (vn,sn) --> NULL
                                          |
                           smallest pointer

At any moment, the two pointers will point to the nodes containing the “largest” and “smallest” values and the rest of the nodes will be sorted. This is useful when an unknown number of nodes are being added continuously and during the operations it is important to have the nodes in a sorted format.

typedef struct gal_list_dosizet_t
{
  size_t v;                       /* The actual value. */
  float s;                        /* The parameter to sort by. */
  struct gal_list_dosizet_t *prev;
  struct gal_list_dosizet_t *next;
} gal_list_dosizet_t;

Function:
void
gal_list_dosizet_add (gal_list_dosizet_t **largest, gal_list_dosizet_t **smallest, size_t value, float tosort) ¶

Allocate space for a new node in list, and store value and tosort into it. If the list is empty, both largest and smallest must be NULL.

Function:
size_t
gal_list_dosizet_pop_smallest (gal_list_dosizet_t **largest, gal_list_dosizet_t **smallest, float tosort) ¶

Pop the value with the smallest reference from the doubly linked list and store the reference into the space pointed to by tosort. Note that even though only the smallest pointer will be popped, when there was only one node in the list, the largest pointer also has to change, so we need both.

Function:
void
gal_list_dosizet_print (gal_list_dosizet_t *largest, gal_list_dosizet_t *smallest) ¶

Print the largest and smallest values sequentially until the list is parsed.

Function:
void
gal_list_dosizet_to_sizet (gal_list_dosizet_t *in, gal_list_sizet_t **out) ¶

Convert the doubly linked, ordered size_t list into a singly-linked list of size_t.

Function:
void
gal_list_dosizet_free (gal_list_dosizet_t *largest) ¶

Free the doubly linked, ordered sizet_t list.