source: proiecte/swift/trunk/src/swift_deque.c @ 176

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 3.3 KB
Line 
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
11void 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
33void 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
61swift_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
110swift_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
146void swift_deque_destroy(swift_thread_t *thread, swift_deque_t *q) {
147        swift_free(thread, q->elements);
148}
Note: See TracBrowser for help on using the repository browser.