~pbatch/patchwerk

patchwerk/stack.w -rw-r--r-- 7.6 KiB
9c265356 — paul plan9 additions from Sigrid 3 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
@** Buffer Stack.
\mkref{stack}
Buffers from the buffer pool are accessed via a stack-like
interface known as the {\bf buffer stack}.

@<Top@>+=
@<Stack Top@>

@* Buffer Stack Data.
@<Stack Top@>+=
@<Stack Data@>

@
@<Stack Data@>+=
struct pw_stack {
    int pos;
    int size;
    pw_bufferpool *pool;
    pw_buffer **buffers;
};

@ @<Type Declarations@>+= typedef struct pw_stack pw_stack;

@* Buffer Stack Functions.

@ |pw_stack_init| initializes data and variables in the stack. It does
not allocate any memory. In addition to supplying a |pw_stack|, an allocated
|pw_bufferpool| must also be supplied.

The size of the stack by default is 0. It must be allocated with a function
like |pw_stack_alloc|.
@<Stack Top@>+=
void pw_stack_init(pw_stack *stack, pw_bufferpool *pool)
{
    stack->pool = pool;
    stack->pos = 0;
    stack->size = 0;
}

@ @<Header@>+= void pw_stack_init(pw_stack *stack, pw_bufferpool *pool);

@ The function |pw_stack_alloc| allocates memory a static stack.
 The stack holds an array of buffer pointers. On success,
|PW_OK| will be returned. On failure, |PW_NOT_OK| will be returned.

@<Stack Top@>+=
int pw_stack_alloc(pw_patch *patch, pw_stack *stack, int size)
{
    stack->size = size;
    return pw_memory_alloc(patch,
        sizeof(pw_buffer *) * size,
        (void **)&stack->buffers);
}

@ @<Header@>+= int pw_stack_alloc(pw_patch *patch, pw_stack *stack, int size);

@ The function |pw_stack| frees the data previously allocated by |malloc|
in |pw_stack_alloc|.
@<Stack Top@>+=
int pw_stack_free(pw_patch *patch, pw_stack *stack)
{
    return pw_memory_free(patch, (void **)&stack->buffers);
}

@ @<Header@>+= int pw_stack_free(pw_patch *patch, pw_stack *stack);

@ A buffer is pushed to the stack with |pw_stack_push|. The stack will
search the buffer pool for the next free buffer, which will then
get pushed on to the stack. On success, the buffer will then get saved to the
variable |buf|, and the buffer will be stored in the next position in the
stack. The stack position is one-indexed, so the current position can be
used before incrementing the stack position.

If the stack or pool is full, the function will return a value of |PW_NOT_OK|.

% TODO: better error handling

@<Stack Top@>+=
int pw_stack_push(pw_stack *stack, pw_buffer **buf)
{
    pw_buffer *pbuf;
    int rc;

    pbuf = NULL;

    if (stack->pos >= stack->size) {
        return PW_STACK_OVERFLOW;
    }

    rc = pw_bufferpool_nextfree(stack->pool, &pbuf);

    if (rc != PW_OK) return rc;

    stack->buffers[stack->pos] = pbuf;
    stack->pos++;
    if (buf != NULL) *buf = pbuf;
    return PW_OK;
}

@ @<Header@>+= int pw_stack_push(pw_stack *stack, pw_buffer **buf);

@ To push a specific buffer onto the stack, use the function
|pw_stack_push_buffer|. % TODO: use this function inside of pw_stack_push
This particular function is used with the {\it cable}
word defined in the runt patchwerk interface for buffers that have been held.

@<Stack Top@>+=
int pw_stack_push_buffer(pw_stack *stack, pw_buffer *buf)
{
    if(stack->pos >= stack->size) {
        return PW_STACK_OVERFLOW;
    }
    stack->buffers[stack->pos] = buf;
    stack->pos++;
    return PW_OK;
}

@ @<Header@>+= int pw_stack_push_buffer(pw_stack *stack, pw_buffer *buf);

@ A buffer is popped from the stack using |pw_stack_pop|. First, the stack
is checked for any items on the stack. Then, the last item on the stack
is assigned to the variable |buf|.

One thing to note is that the stack position uses one-indexing as opposed to
C's zero-indexing scheme, so the position in the array needs to be
subtracted by one.

Once the stack sucessfully pops a buffer, the buffer must be
unmarked to indicicate it is being read by one less node with
|pw_buffer_unmark|. If the buffer is not actively being read, it will
the return value id of the buffer which will set the |last_free| value.

The |pw_stack_pop| function will save the popped buffer value to the
variable |buf| if it not {\tt NULL}.

@<Stack Top@>+=

static int pop_from_stack(pw_stack *stack, pw_buffer **buf)
{
    if(stack->pos == 0) return PW_NOT_OK;
    *buf = stack->buffers[stack->pos - 1];
    stack->pos--;
    return PW_OK;
}

int pw_stack_pop(pw_stack *stack, pw_buffer **buf)
{
    int rc;
    pw_buffer *tmp;

    rc = pop_from_stack(stack, &tmp);
    if(rc != PW_OK) return PW_NOT_OK;

    rc = pw_buffer_unmark(tmp);
    if(rc >= 0) {
        stack->pool->last_free = rc;
        stack->pool->nactive--;
    }
    if(buf != NULL) *buf = tmp;
    return PW_OK;
}
@ @<Header@>+= int pw_stack_pop(pw_stack *stack, pw_buffer **buf);

@ The last buffer on the stack can be duplicated with |pw_stack_dup|.
This operation copies the buffer memory address, rather than copying
the contents to a new buffer. This is done through a direct assignment
operation. Before this is done, the edge cases are checked to make sure
that there are items on the stack to duplicate {\it and} that there
are enough spaces on the stack.

Since the buffer memory location is being duplicated instead of the contents
of the buffer, the buffer must be marked as being read again.

@<Stack Top@>+=
int pw_stack_dup(pw_stack *stack)
{
    pw_buffer *buf;
    if (stack->pos == 0) {
        return PW_NOT_OK; /* No items on the stack */
    }

    if (stack->pos >= stack->size - 1) {
        return PW_NOT_OK; /* Not enough room on the stack */
    }

    stack->buffers[stack->pos] = stack->buffers[stack->pos - 1];
    buf = stack->buffers[stack->pos];
    pw_buffer_mark(buf);
    stack->pos++;
    return PW_OK;
}
@ @<Header@>+= int pw_stack_dup(pw_stack *stack);

@ The last item on the stack is removed with |pw_stack_drop|. This is done
by subtracting the stack position by one. This function will return an
error of |PW_NOT_OK| if there are no items to drop on the stack.

@<Stack Top@>+=
int pw_stack_drop(pw_stack *stack)
{
    if(stack->pos == 0) return PW_NOT_OK;
    stack->pos--;
    return PW_OK;
}
@ @<Header@>+= int pw_stack_drop(pw_stack *stack);

@ The last two items can swap positions using the function
|pw_stack_swap|. This operation will fail if there aren't enough items on
the stack.

@<Stack Top@>+=
int pw_stack_swap(pw_stack *stack)
{
    pw_buffer *tmp;
    if(stack->pos < 2) return PW_NOT_OK;
    tmp = stack->buffers[stack->pos - 1];
    stack->buffers[stack->pos - 1] = stack->buffers[stack->pos - 2];
    stack->buffers[stack->pos - 2] = tmp;

    return PW_OK;
}
@ @<Header@>+= int pw_stack_swap(pw_stack *stack);

@ Sometimes, there are some cases where a particular buffer needs to be held
indefinitely. The function |pw_stack_hold| implements a hold operation, which
pops the last buffer on the stack and marks it to be held. This buffer will
not be written to again until the buffer is unheld with the function
|pw_buffer_unhold|.

|pw_stack_hold| will save the popped |pw_buffer| into the value |buf|.
@<Stack Top@>+=
int pw_stack_hold(pw_stack *stack, pw_buffer **buf)
{
    if(pop_from_stack(stack, buf) != PW_OK) {
        return PW_NOT_OK;
    }
    pw_buffer_hold(*buf);
    return PW_OK;
}

@ @<Header@>+= int pw_stack_hold(pw_stack *stack, pw_buffer **buf);

@ @<Stack Top@>+=
int pw_stack_size(pw_stack *stack)
{
    return stack->size;
}
@ @<Header@>+= int pw_stack_size(pw_stack *stack);

@ @<Stack Top@>+=
int pw_stack_pos(pw_stack *stack)
{
    return stack->pos;
}

@ The function |pw_stack_pos| returns the current stack position.

@ @<Header@>+= int pw_stack_pos(pw_stack *stack);

@ The function |pw_stack_reset| resets the stack back to zero. This function
is used internally, and is used in for live-coding environments where
on-the-fly re-evaluation required.
@<Header@> +=
void pw_stack_reset(pw_stack *stack);

@
@<Stack Top@>+=
void pw_stack_reset(pw_stack *stack)
{
    stack->pos = 0;
}