1 | /* |
---|
2 | * swift_deque.c |
---|
3 | * |
---|
4 | * (c) 2009 Ionut Rosoiu <ionut.rosoiu@gmail.com> |
---|
5 | * |
---|
6 | */ |
---|
7 | |
---|
8 | #include "swift_deque.h" |
---|
9 | #include <stdio.h> |
---|
10 | |
---|
11 | void swift_deque_init(swift_thread_t *thread, swift_deque_t *q, swift_size_t size) { |
---|
12 | //automatically resized to a power of two |
---|
13 | //SWIFT_CHECK(size & (size-1), SWIFT_RETURN_WITH_STATUS(SWIFT_INVALID_PARAM)); |
---|
14 | |
---|
15 | if (size & (size-1)) { |
---|
16 | /* round up to a power of two */ |
---|
17 | swift_size_t newSize = 1; |
---|
18 | |
---|
19 | while (size) { |
---|
20 | size >>= 1; |
---|
21 | newSize <<= 1; |
---|
22 | } |
---|
23 | |
---|
24 | size = newSize; |
---|
25 | } |
---|
26 | |
---|
27 | q->size = size; |
---|
28 | q->size_mask = size - 1; |
---|
29 | q->top = q->bottom = q->top_cached = 0; |
---|
30 | q->elements = (swift_frame_t**) swift_malloc(thread, size * sizeof(swift_frame_t*)); |
---|
31 | } |
---|
32 | |
---|
33 | void swift_deque_push(swift_deque_t *q, swift_frame_t *frame, swift_status_t *status) { |
---|
34 | swift_dword_t t, b; |
---|
35 | SWIFT_CHECK(NULL != q, SWIFT_RETURN_WITH_STATUS(SWIFT_INVALID_PARAM)); |
---|
36 | |
---|
37 | b = q->bottom; |
---|
38 | /* avoid some cache misses by using this local variable */ |
---|
39 | t = q->top_cached; |
---|
40 | |
---|
41 | if (b - t >= q->size_mask) { /* size_mask = size - 1 */ |
---|
42 | /* because we've used a cached value, we might have a false positive */ |
---|
43 | t = q->top; |
---|
44 | q->top_cached = t; |
---|
45 | |
---|
46 | if (b - t >= q->size_mask) { |
---|
47 | //TODO: handle reallocation (...and ALL the problems that come along...) |
---|
48 | // for the moment fail this case |
---|
49 | *status = SWIFT_DEQUE_FULL; |
---|
50 | return; |
---|
51 | } |
---|
52 | } |
---|
53 | |
---|
54 | /* push the new value at the bottom */ |
---|
55 | q->elements[b & q->size_mask] = frame; |
---|
56 | q->bottom = b + 1; |
---|
57 | |
---|
58 | *status = SWIFT_SUCCESS; |
---|
59 | } |
---|
60 | |
---|
61 | swift_frame_t* swift_deque_pop(swift_deque_t *q, swift_status_t *status) { |
---|
62 | swift_frame_t *ret = NULL; |
---|
63 | swift_dword_t b, t; |
---|
64 | long size; |
---|
65 | |
---|
66 | SWIFT_CHECK(NULL != q, *status = SWIFT_INVALID_PARAM; return NULL); |
---|
67 | |
---|
68 | b = q->bottom; |
---|
69 | |
---|
70 | b--; |
---|
71 | q->bottom = b; |
---|
72 | |
---|
73 | /* top must be read _after_ bottom is written (i.e. incremented) */ |
---|
74 | swift_memory_write_barrier(); |
---|
75 | |
---|
76 | t = q->top; |
---|
77 | q->top_cached = t; |
---|
78 | |
---|
79 | size = (long)(b - t); |
---|
80 | |
---|
81 | if (size < 0) { |
---|
82 | q->bottom = t; |
---|
83 | |
---|
84 | *status = SWIFT_DEQUE_EMPTY; |
---|
85 | return NULL; |
---|
86 | } |
---|
87 | |
---|
88 | /* get a reference to the element to return */ |
---|
89 | ret = q->elements[b & q->size_mask]; |
---|
90 | |
---|
91 | /* enough active elements left in the array */ |
---|
92 | if (size > 0) { |
---|
93 | return ret; |
---|
94 | } |
---|
95 | |
---|
96 | /* check to see if the last element was concurrently stolen */ |
---|
97 | if (! SWIFT_CAS(q->top, t, t+1)) { |
---|
98 | /* someone has stolen our element */ |
---|
99 | *status = SWIFT_DEQUE_EMPTY; |
---|
100 | ret = NULL; |
---|
101 | } |
---|
102 | |
---|
103 | /* the array is empty and q->top is t+1; adjust bottom */ |
---|
104 | q->bottom = t + 1; |
---|
105 | q->top_cached = t + 1; |
---|
106 | |
---|
107 | return ret; |
---|
108 | } |
---|
109 | |
---|
110 | swift_frame_t* swift_deque_steal(swift_deque_t *q, swift_status_t *status) { |
---|
111 | swift_dword_t t, b; |
---|
112 | swift_frame_t *ret = NULL; |
---|
113 | |
---|
114 | SWIFT_CHECK(NULL != q, *status = SWIFT_INVALID_PARAM; return NULL); |
---|
115 | |
---|
116 | t = q->top; |
---|
117 | |
---|
118 | /* a read barrier is needed to guarantee a consistent view of the memory |
---|
119 | * see also the write_barrier() in the pop() |
---|
120 | */ |
---|
121 | swift_memory_read_barrier(); |
---|
122 | |
---|
123 | b = q->bottom; |
---|
124 | |
---|
125 | if ((long)(b - t) <= 0) { |
---|
126 | *status = SWIFT_DEQUE_EMPTY; |
---|
127 | return NULL; |
---|
128 | } |
---|
129 | |
---|
130 | /* get a reference to the element _before_ trying the CAS |
---|
131 | * (i.e. _before_ checking we've won the race); |
---|
132 | * if not, in case we win, we might get a reference to a newly |
---|
133 | * push()-ed element instead of the current one |
---|
134 | */ |
---|
135 | ret = q->elements[t & q->size_mask]; |
---|
136 | |
---|
137 | if (! SWIFT_CAS(q->top, t, t+1)) { |
---|
138 | *status = SWIFT_DEQUE_ABORT; |
---|
139 | return NULL; |
---|
140 | } |
---|
141 | |
---|
142 | *status = SWIFT_SUCCESS; |
---|
143 | return ret; |
---|
144 | } |
---|
145 | |
---|
146 | void swift_deque_destroy(swift_thread_t *thread, swift_deque_t *q) { |
---|
147 | swift_free(thread, q->elements); |
---|
148 | } |
---|