kconfig: use pkg-config for ncurses detection
[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
24         while (p != NULL) {
25                 assert(p->data == NULL);
26                 struct wfl_entry *tmp = p;
27                 p = p->next;
28                 free(tmp);
29         }
30 }
31
32 size_t wfl_capacity(struct wfl *list)
33 {
34         size_t res = 0;
35
36         for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
37                 res++;
38         return res;
39 }
40
41 size_t wfl_size(struct wfl *list)
42 {
43         size_t res = 0;
44
45         for (struct wfl_entry *p = list->head; p != NULL; p = p->next)
46                 res += p->data != NULL;
47         return res;
48 }
49
50 #if 0
51 void wfl_insert(struct wfl *list, void *data)
52 {
53 retry:
54   struct wfl_entry *p = list->head; // list head is never null
55   struct wfl_entry *new_entry = NULL;
56   while (1) {
57     if (p->data == NULL) {
58       if (__sync_bool_compare_and_swap(&p->data, NULL, data)) {
59         free(new_entry);
60         return;
61       }
62     }
63
64     if (p->next != NULL) {
65       p = p->next;
66       continue;
67     }
68
69     if (new_entry == NULL) {
70       new_entry = malloc(sizeof(struct wfl_entry));
71       if (new_entry == NULL)
72         abort();
73       new_entry->data = data;
74       new_entry->next = NULL;
75       wmb();
76     }
77  
78     if (__sync_bool_compare_and_swap(&p->next, NULL, new_entry))
79       return;
80     goto retry;
81     p = list->head;
82   }
83 }
84 #endif
85
86 void wfl_insert(struct wfl *list, void *data)
87 {
88         struct wfl_entry *p = list->head; // list head is never null
89         
90         while (1) {
91                 if (p->data == NULL) {
92                         if (__sync_bool_compare_and_swap(&p->data, NULL, data))
93                                 return;
94                 }
95                 
96                 if (p->next == NULL)
97                         break;
98                 
99                 p = p->next;
100         }
101         
102         struct wfl_entry *new_entry = malloc(sizeof(struct wfl_entry));
103
104         if (new_entry == NULL)
105                 abort();
106         new_entry->data = data;
107         new_entry->next = NULL;
108         
109         wmb();
110         
111         struct wfl_entry *next;
112
113         while ((next = __sync_val_compare_and_swap(&p->next, NULL, new_entry)))
114                 p = next;
115 }
116
117 void *wfl_remove(struct wfl *list)
118 {
119         for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
120                 if (p->data != NULL) {
121                         void *data = atomic_swap_ptr(&p->data, 0);
122
123                         if (data != NULL)
124                                 return data;
125                 }
126         }
127         return NULL;
128 }
129
130 size_t wfl_remove_all(struct wfl *list, void *data)
131 {
132         size_t n = 0;
133
134         for (struct wfl_entry *p = list->head; p != NULL; p = p->next) {
135                 if (p->data == data)
136                         n += __sync_bool_compare_and_swap(&p->data, data, NULL);
137         }
138         return n;
139 }