Changeset 235d31d in mainline for kernel/generic/include/adt/list.h

Timestamp:

2014-12-22T17:47:40Z (9 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

8c7d5ad

Parents:

eae91e0 (diff), 759ea0d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge the CHT pre-integration branch

This branch contains:

• the merge of lp:~adam-hraska+lp/helenos/rcu, which brings:

• a new preemptible kernel RCU variant called A-RCU,
• a preemptible variant of Podzimek's non-preemptible kernel RCU and
• a new variant of usersace RCU,
• a new concurrent hash table (CHT) implementation based on RCU,
• a deployment of CHT in kernel futex handling,
• a deployment of the userspace RCU in the implementation of upgradable futexes,

all described in Adam Hraska's master thesis named Read-Copy-Update
for HelenOS, defended in 2013 at MFF UK; furthemore, the branch
fixes two synchronization bugs in condvars and waitq, respectively:

• revid:adam.hraska+hos@gmail.com-20121116144921-3to9u1tn1sg07rg7
• revid:adam.hraska+hos@gmail.com-20121116173623-km7gwtqixwudpe66

• build fixes required to pass make check
• overhaul of ia64 and sparc64 trap handling, to allow exc_dispatch() to be used now when the kernel is more picky about CPU state accounting
• an important fix of the sparc64/sun4v preemptible trap handler
• various other fixes of issues discovered on non-x86 architectures

File:

• kernel/generic/include/adt/list.h (modified) (4 diffs)

kernel/generic/include/adt/list.h

@@ -52 +52 @@
 } list_t;
 
+
+extern int list_member(const link_t *, const list_t *);
+extern void list_splice(list_t *, link_t *);
+extern unsigned int list_count(const list_t *);
+
+
 /** Declare and initialize statically allocated list.
  *
@@ -80 +86 @@
             _link != &(list).head; _link = _link->prev)
 
+/** Unlike list_foreach(), allows removing items while traversing a list.
+ * 
+ * @code
+ * list_t mylist;
+ * typedef struct item {
+ *     int value;
+ *     link_t item_link;
+ * } item_t;
+ * 
+ * //..
+ * 
+ * // Print each list element's value and remove the element from the list.
+ * list_foreach_safe(mylist, cur_link, next_link) {
+ *     item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
+ *     printf("%d\n", cur_item->value);
+ *     list_remove(cur_link);
+ * }
+ * @endcode
+ * 
+ * @param list List to traverse.
+ * @param iterator Iterator to the current element of the list.
+ *             The item this iterator points may be safely removed
+ *             from the list.
+ * @param next_iter Iterator to the next element of the list.
+ */
+#define list_foreach_safe(list, iterator, next_iter) \
+        for (link_t *iterator = (list).head.next, \
+                *next_iter = iterator->next; \
+                iterator != &(list).head; \
+                iterator = next_iter, next_iter = iterator->next)
+
+        
 #define assert_link_not_used(link) \
         ASSERT(!link_used(link))
@@ -289 +327 @@
 {
         headless_list_split_or_concat(part1, part2);
+}
+
+/** Concatenate two lists
+ *
+ * Concatenate lists @a list1 and @a list2, producing a single
+ * list @a list1 containing items from both (in @a list1, @a list2
+ * order) and empty list @a list2.
+ *
+ * @param list1         First list and concatenated output
+ * @param list2         Second list and empty output.
+ *
+ */
+NO_TRACE static inline void list_concat(list_t *list1, list_t *list2)
+{
+        list_splice(list2, list1->head.prev);
 }
 
@@ -340 +393 @@
 }
 
-extern int list_member(const link_t *, const list_t *);
-extern void list_concat(list_t *, list_t *);
-extern unsigned int list_count(const list_t *);
-
 #endif