bgets_mp(): Added a non-intuitive warning to documentation.

[libucw.git] / ucw / clists.h

diff --git a/ucw/clists.h b/ucw/clists.h
index bc8779d9d9e764ba7cbc4de9dd3cfd8f95782c7a..809c480dea4303820edce351ad0dfc518931a3fb 100644 (file)
--- a/ucw/clists.h
+++ b/ucw/clists.h
@@ -1,7 +1,8 @@
 /*
  *     UCW Library -- Circular Linked Lists
  *
- *     (c) 2003--2007 Martin Mares <mj@ucw.cz>
+ *     (c) 2003--2010 Martin Mares <mj@ucw.cz>
+ *     (c) 2017 Pavel Charvat <pchar@ucw.cz>
  *
  *     This software may be freely distributed and used according to the terms
  *     of the GNU Lesser General Public License.
@@ -18,7 +19,7 @@ typedef struct cnode {
 } cnode;
 
 /**
- * Circilar linked list.
+ * Circular doubly linked list.
  **/
 typedef struct clist {
   struct cnode head;
@@ -73,15 +74,34 @@ static inline int clist_empty(clist *l)
   return (l->head.next == &l->head);
 }
 
+/**
+ * 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(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
+
+/**
+ * Same as @CLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store some temporary pointers.
+ **/
 #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 it defines the variable for the current node in place. @type should be a pointer type.
+ **/
 #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_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_DELSAFE(type,n,list,tmp) for(type n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)
 
+/**
+ * Reversed version of @CLIST_FOR_EACH().
+ **/
 #define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)
 
 /**
- * Insert a new node just after the node @after. To insert a new head, use @clist_add_head() instead.
+ * 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_after(cnode *what, cnode *after)
 {
@@ -93,7 +113,7 @@ static inline void clist_insert_after(cnode *what, cnode *after)
 }
 
 /**
- * Insert a new node just before the node @before. To insert a new tail, use @clist_add_tail() instead.
+ * 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_insert_before(cnode *what, cnode *before)
 {
@@ -132,7 +152,7 @@ static inline void clist_remove(cnode *n)
 }
 
 /**
- * Remove the first node in @l. The list can be empty.
+ * Remove the first node in @l, if it exists. Return the pointer to that node or NULL.
  **/
 static inline void *clist_remove_head(clist *l)
 {
@@ -143,7 +163,7 @@ static inline void *clist_remove_head(clist *l)
 }
 
 /**
- * Remove the last node in @l. The list can be empty.
+ * Remove the last node in @l, if it exists. Return the pointer to that node or NULL.
  **/
 static inline void *clist_remove_tail(clist *l)
 {
@@ -171,14 +191,89 @@ static inline void clist_insert_list_after(clist *what, cnode *after)
 }
 
 /**
- * Compute the number of nodes in @l. Beware linear time complexity.
+ * Merge two lists by inserting the list @what in front of all other nodes in a different list @l.
+ * The first list is then cleared.
  **/
-static inline uns clist_size(clist *l)
+static inline void clist_add_list_head(clist *l, clist *what)
 {
-  uns i = 0;
+  clist_insert_list_after(what, &l->head);
+}
+
+/**
+ * Merge two lists by inserting the list @what after all other nodes in a different list @l.
+ * The first list is then cleared.
+ **/
+static inline void clist_add_list_tail(clist *l, clist *what)
+{
+  clist_insert_list_after(what, l->head.prev);
+}
+
+/**
+ * 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 void clist_move(clist *to, clist *from)
+{
+  clist_init(to);
+  clist_insert_list_after(from, &to->head);
+  clist_init(from);
+}
+
+/**
+ * Compute the number of nodes in @l. Beware of linear time complexity.
+ **/
+static inline uint clist_size(clist *l)
+{
+  uint i = 0;
   CLIST_FOR_EACH(cnode *, n, *l)
     i++;
   return i;
 }
 
+/**
+ * Remove a node @n and mark it as unlinked by setting the previous and next pointers to NULL.
+ **/
+static inline void clist_unlink(cnode *n)
+{
+  clist_remove(n);
+  n->prev = n->next = NULL;
+}
+
+/**
+ * Remove the first node on @l and mark it as unlinked.
+ * Return the pointer to that node or NULL.
+ **/
+static inline void *clist_unlink_head(clist *l)
+{
+  cnode *n = clist_head(l);
+  if (n)
+    clist_unlink(n);
+  return n;
+}
+
+/**
+ * Remove the last node on @l and mark it as unlinked.
+ * Return the pointer to that node or NULL.
+ **/
+static inline void *clist_unlink_tail(clist *l)
+{
+  cnode *n = clist_tail(l);
+  if (n)
+    clist_unlink(n);
+  return 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.
+ **/
+static inline int clist_is_linked(cnode *n)
+{
+  return !!n->next;
+}
+
 #endif