parlib: Add parlib_assert_perror()
[akaros.git] / user / parlib / waitfreelist.c
1 /* Copyright (c) 2014 The Regents of the University of California
2  * Kevin Klues <klueska@cs.berkeley.edu>
3  * Andrew Waterman <waterman@cs.berkeley.edu>
4  * See LICENSE for details.
5  */
6
7 #include <parlib/assert.h>
8 #include <stdlib.h>
9 #include <parlib/arch/atomic.h>
10 #include <parlib/waitfreelist.h>
11
12 void wfl_init(struct wfl *list)
13 {
14   list->first.next = NULL;
15   list->first.data = NULL;
16   list->head = &list->first;
17 }
18
19 void wfl_destroy(struct wfl *list)
20 {
21   assert(list->first.data == NULL);
22   struct wfl_entry *p = list->first.next; // don't free the first element
23   while (p != NULL) {
24     assert(p->data == NULL);
25     struct wfl_entry *tmp = p;
26     p = p->next;
27     free(tmp);
28   }
29 }
30
31 size_t wfl_capacity(struct wfl *list)
32 {
33   size_t res = 0;
34   for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
35     res++;
36   return res;
37 }
38
39 size_t wfl_size(struct wfl *list)
40 {
41   size_t res = 0;
42   for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
43     res += p->data != NULL;
44   return res;
45 }
46
47 #if 0
48 void wfl_insert(struct wfl *list, void *data)
49 {
50 retry:
51   struct wfl_entry *p = list->head; // list head is never null
52   struct wfl_entry *new_entry = NULL;
53   while (1) {
54     if (p->data == NULL) {
55       if (__sync_bool_compare_and_swap(&p->data, NULL, data)) {
56         free(new_entry);
57         return;
58       }
59     }
60
61     if (p->next != NULL) {
62       p = p->next;
63       continue;
64     }
65
66     if (new_entry == NULL) {
67       new_entry = malloc(sizeof(struct wfl_entry));
68       if (new_entry == NULL)
69         abort();
70       new_entry->data = data;
71       new_entry->next = NULL;
72       wmb();
73     }
74  
75     if (__sync_bool_compare_and_swap(&p->next, NULL, new_entry))
76       return;
77     goto retry;
78     p = list->head;
79   }
80 }
81 #endif
82
83 void wfl_insert(struct wfl *list, void *data)
84 {
85   struct wfl_entry *p = list->head; // list head is never null
86   while (1) {
87     if (p->data == NULL) {
88       if (__sync_bool_compare_and_swap(&p->data, NULL, data))
89         return;
90     }
91
92     if (p->next == NULL)
93       break;
94
95     p = p->next;
96   }
97
98   struct wfl_entry *new_entry = malloc(sizeof(struct wfl_entry));
99   if (new_entry == NULL)
100     abort();
101   new_entry->data = data;
102   new_entry->next = NULL;
103
104   wmb();
105
106   struct wfl_entry *next;
107   while ((next = __sync_val_compare_and_swap(&p->next, NULL, new_entry)))
108     p = next;
109 }
110
111 void *wfl_remove(struct wfl *list)
112 {
113   for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
114     if (p->data != NULL) {
115       void *data = atomic_swap_ptr(&p->data, 0);
116       if (data != NULL)
117         return data;
118     }
119   }
120   return NULL;
121 }
122
123 size_t wfl_remove_all(struct wfl *list, void *data)
124 {
125   size_t n = 0;
126   for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
127     if (p->data == data)
128       n += __sync_bool_compare_and_swap(&p->data, data, NULL);
129   }
130   return n;
131 }