Ucwlib defines two basic linked list structures: single-linked lists and circular linked lists. Both of them support insertion of any number of nodes, removal of nodes and various searches. Single-linked lists are a bit simplier (they especially requires smaller nodes) but some operations need assymptoticaly more time.

Linked lists can be used very simply. We define a structure as list’s handle and a common header in all inserted nodes. All routines then accept and return pointers to this handle and node headers.

Single-linked lists

typedef struct snode {
  struct snode *next;
} snode;

Common header for list nodes.

typedef struct slist {
  struct snode head, *last;
} slist;

Single-linked list.

static inline void slist_init(slist *l);

Initialize a new single-linked list. Must be called before any other function.

static inline void *slist_head(slist *l);

Return the first node of l or NULL if l is empty.

static inline void *slist_tail(slist *l);

Return the last node of l or NULL if l is empty.

static inline void *slist_next(snode *n);

Find the next node to n or NULL if n is the last one.

static inline int slist_empty(slist *l);

Return a non-zero value iff l is empty.

static inline void slist_add_head(slist *l, snode *n);

Insert a new node in front of all other nodes.

static inline void slist_add_tail(slist *l, snode *n);

Insert a new node after all other nodes.

static inline void slist_insert_after(slist *l, snode *what, snode *after);

Insert a new node just after the node after. To insert a new head, use slist_add_head() instead.

static inline void slist_remove_after(slist *l, snode *after);

Quickly remove the node next to after. The node may not exist.

static inline void *slist_remove_head(slist *l);

Remove the first node in l. The list can be empty.

#define SLIST_WALK(n,list) for(n=(void*)(list).head.next; (n); (n)=(void*)((snode*)(n))->next)

Loop over all nodes in the list and perform the next C statement on them. The current node is stored in n which must be defined before as pointer to any type. The list should not be changed during this loop command.

#define SLIST_WALK_DELSAFE(n,list,prev) for((prev)=(void*)&(list).head; (n)=(void*)((snode*)prev)->next; (prev)=(((snode*)(prev))->next==(snode*)(n) ? (void*)(n) : (void*)(prev)))

Same as SLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store the pointer to the previous node (useful for slist_remove_after()).

#define SLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; n; n=(void*)((snode*)(n))->next)

Same as SLIST_WALK(), but it defines the variable for the current node in place. type should be a pointer type.

void *slist_prev(slist *l, snode *n);

Find the previous node to n or NULL if n is the first one. Beware linear time complexity.

void slist_insert_before(slist *l, snode *what, snode *before);

Insert a new node just before the node before. To insert a new tail, use slist_add_tail(). Beware linear time complexity.

void slist_remove(slist *l, snode *n);

Remove node n. Beware linear time complexity.

static inline void slist_remove_tail(slist *l);

Remove the last node in l. The list can be empty.

static inline uint slist_size(slist *l);

Compute the number of nodes in l. Beware linear time complexity.

Circular linked lists

typedef struct cnode {
  struct cnode *next, *prev;
} cnode;

Common header for list nodes.

typedef struct clist {
  struct cnode head;
} clist;

Circular doubly linked list.

static inline void clist_init(clist *l);

Initialize a new circular linked list. Must be called before any other function.

static inline void *clist_head(clist *l);

Return the first node on l or NULL if l is empty.

static inline void *clist_tail(clist *l);

Return the last node on l or NULL if l is empty.

static inline void *clist_next(clist *l, cnode *n);

Find the next node to n or NULL if n is the last one.

static inline void *clist_prev(clist *l, cnode *n);

Find the previous node to n or NULL if n is the first one.

static inline int clist_empty(clist *l);

Return a non-zero value iff l is empty.

#define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)

Loop over all nodes in the list and perform the next C statement on them. The current node is stored in n which must be defined before as pointer to any type. The list should not be changed during this loop command.

#define CLIST_WALK_DELSAFE(n,list,tmp) for(n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)

Same as CLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store some temporary pointers.

#define CLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)

Same as CLIST_WALK(), but it defines the variable for the current node in place. type should be a pointer type.

#define CLIST_FOR_EACH_DELSAFE(type,n,list,tmp) for(type n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)

Same as CLIST_WALK_DELSAFE(), but it defines the variable for the current node in place. type should be a pointer type. The temporary variable must be still known before.

#define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)

Reversed version of CLIST_FOR_EACH().

static inline void clist_insert_after(cnode *what, cnode *after);

Insert a new node just after the node after. To insert at the head of the list, use clist_add_head() instead.

static inline void clist_insert_before(cnode *what, cnode *before);

Insert a new node just before the node before. To insert at the tail of the list, use clist_add_tail() instead.

static inline void clist_add_head(clist *l, cnode *n);

Insert a new node in front of all other nodes.

static inline void clist_add_tail(clist *l, cnode *n);

Insert a new node after all other nodes.

static inline void clist_remove(cnode *n);

Remove node n.

static inline void *clist_remove_head(clist *l);

Remove the first node in l, if it exists. Return the pointer to that node or NULL.

static inline void *clist_remove_tail(clist *l);

Remove the last node in l, if it exists. Return the pointer to that node or NULL.

static inline void clist_insert_list_after(clist *what, cnode *after);

Merge two lists by inserting the list what just after the node after in a different list. The first list is then cleared.

static inline void clist_move(clist *to, clist *from);

Move all items from a source list to a destination list. The source list becomes empty, the original contents of the destination list are destroyed.

static inline uint clist_size(clist *l);

Compute the number of nodes in l. Beware of linear time complexity.

Remove a node n and mark it as unlinked by setting the previous and next pointers to NULL.

Remove the first node on l and mark it as unlinked. Return the pointer to that node or NULL.

Remove the last node on l and mark it as unlinked. Return the pointer to that node or NULL.

static inline int clist_is_linked(cnode *n);

Check if a node is linked a list. Unlinked nodes are recognized by having their previous and next pointers equal to NULL. Returns 0 or 1.

Nodes initialized to all zeroes are unlinked, inserting a node anywhere in a list makes it linked. Normal removal functions like clist_remove() do not mark nodes as unlinked, you need to call clist_unlink() instead.

Circular linked lists of simple items

To simplify very common usage of circular linked links, whose nodes can hold only one or two trivial values, we define some generic node types, called the simple nodes.

To avoid some type casts, values in simple nodes are defined as unions of most frequent types.

typedef struct simp_node {
  cnode n;
  union {
    char *s;
    void *p;
    int i;
    uint u;
  };
} simp_node;

Simple node with one value.

typedef struct simp2_node {
  cnode n;
  union {
    char *s1;
    void *p1;
    int i1;
    uint u1;
  };
  union {
    char *s2;
    void *p2;
    int i2;
    uint u2;
  };
} simp2_node;

Simple node with two values.

simp_node *simp_append(struct mempool *mp, clist *l);

Allocate a new one-value node on memory pool mp and insert it to l. The value is undefined and should be changed afterwards.

simp2_node *simp2_append(struct mempool *mp, clist *l);

Allocate a new two-value node on memory pool mp and insert it to l. The values are undefined and should be changed afterwards.

extern struct cf_section cf_string_list_config;

Default definition of the configuration section with one-value string node. Identifier of the value is String.

extern struct cf_section cf_2string_list_config;

Default definition of the configuration section with two-value string node. Identifiers of the values are Src and Dest.