clist.h File Reference

Circular linked list. More...

Circular linked list.

This file contains a circularly and singly linked list implementation.

Its operations are:

operation | runtime | description |
---|---|---|

clist_lpush() | O(1) | insert as head (leftmost node) |

clist_lpop() | O(1) | remove and return head (leftmost node) |

clist_rpush() | O(1) | append as tail (rightmost node) |

clist_rpop() | O(n) | remove and return tail (rightmost node) |

clist_find() | O(n) | find and return node |

clist_find_before() | O(n) | find node return node pointing to node |

clist_remove() | O(n) | remove and return node |

clist_sort() | O(NlogN) | sort list (stable) |

clist can be used as a traditional list, a queue (FIFO) and a stack (LIFO) using fast O(1) operations.

When used as traditional list, in order to traverse, make sure every element is only visited once.

Example:

void clist_traverse(clist_node_t *list) { clist_node_t *node = list->next; if (! node) { puts("list empty"); return; } do { node = node->next; // do something with node } while (node != list->next); }

Or use the clist_foreach() helper function, e.g.,:

static int _print_node(clist_node_t *node) { printf("0x%08x ", (unsigned)node); return 0; }

[...] clist_foreach(&list, _print_node);

To use clist as a queue, use clist_rpush() for adding elements and clist_lpop() for removal. Using clist_lpush() and clist_rpop() is inefficient due to clist_rpop()'s O(n) runtime.

To use clist as stack, use clist_lpush()/clist_lpop().

Implementation details:

Each list is represented as a "clist_node_t". Its only member, the "next" pointer, points to the last entry in the list, whose "next" pointer points to the first entry. Actual list objects should have a `clist_node_t`

as member and then use the container_of() macro in list operations. See thread_add_to_list() as example.

Definition in file clist.h.

Include dependency graph for clist.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

## Typedefs | |

typedef list_node_t | clist_node_t |

List node structure. More... | |

typedef int(* | clist_cmp_func_t) (clist_node_t *a, clist_node_t *b) |

Typedef for comparison function used by clist_sort() More... | |

## Functions | |

static void | clist_rpush (clist_node_t *list, clist_node_t *new_node) |

Appends new_node at the end of *list. More... | |

static void | clist_lpush (clist_node_t *list, clist_node_t *new_node) |

Inserts new_node at the beginning of *list. More... | |

static clist_node_t * | clist_lpop (clist_node_t *list) |

Removes and returns first element from list. More... | |

static void | clist_lpoprpush (clist_node_t *list) |

Advances the circle list. More... | |

static clist_node_t * | clist_lpeek (const clist_node_t *list) |

Returns first element in list. More... | |

static clist_node_t * | clist_rpeek (const clist_node_t *list) |

Returns last element in list. More... | |

static clist_node_t * | clist_rpop (clist_node_t *list) |

Removes and returns last element from list. More... | |

static clist_node_t * | clist_find_before (const clist_node_t *list, const clist_node_t *node) |

Finds node and returns its predecessor. More... | |

static clist_node_t * | clist_find (const clist_node_t *list, const clist_node_t *node) |

Finds and returns node. More... | |

static clist_node_t * | clist_remove (clist_node_t *list, clist_node_t *node) |

Finds and removes node. More... | |

static clist_node_t * | clist_foreach (clist_node_t *list, int(*func)(clist_node_t *, void *), void *arg) |

Traverse clist, call function for each member. More... | |

clist_node_t * | _clist_sort (clist_node_t *list_head, clist_cmp_func_t cmp) |

List sorting helper function. | |

static void | clist_sort (clist_node_t *list, clist_cmp_func_t cmp) |

Sort a list. More... | |