12.3.8.7 Ordered list of size_t ¶

Positions/sizes in a dataset are conventionally in the size_t type (see List of size_t) and it sometimes occurs that you want to parse and read the values in a specific order. For example, you want to start from one pixel and add pixels to the list based on their distance to that pixel. So that ever time you pop an element from the list, you know it is the nearest that has not yet been studied. The gal_list_osizet_t type and its functions in this section are designed to facilitate such operations.

Type (C struct): gal_list_osizet_t ¶

Each node in this singly-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. At any moment, the first popped node in this list will have the smallest tosort value, and subsequent nodes will have larger to values.

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

Function:
void
gal_list_osizet_add (gal_list_osizet_t **list, size_t value, float tosort) ¶

Allocate space for a new node in list, and store value and tosort into it. The new node will not necessarily be at the “top” of the list. If *list!=NULL, then the tosort values of existing nodes is inspected and the given node is placed in the list such that the top element (which is popped with gal_list_osizet_pop) has the smallest tosort value.

Function:
size_t
gal_list_osizet_pop (gal_list_osizet_t **list, float *sortvalue) ¶

Pop a node from the top of list, return the node’s value and put its sort value in the space that sortvalue points to. This function will also free the allocated space for the popped node and after this function, list will point to the next node (which has a larger tosort element).

Function:
void
gal_list_osizet_to_sizet_free (gal_list_osizet_t *in, gal_list_sizet_t **out) ¶

Convert the ordered list of size_ts into an ordinary size_t linked list. This can be useful when all the elements have been added and you just need to pop-out elements and do not care about the sorting values any more. After the conversion is done, this function will free the input list. Note that the out list does not have to be empty. If it already contains some nodes, the new nodes will be added on top of them.