5 /* This is the implementation of sstack, a data structure that holds
6 * operations done on a stack in order to play them on a stack a short
7 * while later. They are played when dependencies are fulfilled. The
8 * operations are held in a queue.
10 * Operations include PUSH of data, POP, as well as other special markers.
12 * Stack operations are defined by a struct sstack_item. Each struct
13 * sstack_item has 3 flags:
18 * Finished is raised when all the dependencies of the operation are
19 * fulfilled. POPs are always created finished because they have no
20 * dependencies. PUSHes are marked finished when their corresponding
21 * POP is added to the queueit is the PUSHes
22 * that contain the and EVENTs are always created finished.
24 * Once an operation is finished
27 void (*print_sstack_item_data
)(struct sstack_item
*);
29 /* Debugging function: print a queue item */
31 static void print_item(struct sstack_item
*item
)
35 if(item
->data_type
== SSTACK_TYPE_PUSH
) {
38 else if(item
->data_type
== SSTACK_TYPE_POP
) {
45 printf("%-10s %-2u%-2u%-2u", label
, item
->finished
, item
->processable
, item
->deletable
);
46 /* hack: call this external, application-dependant function to show the private data in the item */
47 print_sstack_item_data(item
);
50 /* Debugging function: print the queue as it is now */
52 void print_stack(struct sstack
*stack
)
56 printf("************************\n");
57 printf("** %-10s F P D\n", "label");
58 for(i
=0; i
<stack
->array
->len
; i
++) {
59 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, i
);
61 printf("** %-3d- ", i
);
67 static void try_start_deleting(struct sstack
*stack
)
69 int index
= stack
->array
->len
-1;
71 while(index
>= 0 && g_array_index(stack
->array
, struct sstack_item
*, index
)->deletable
) {
72 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
74 if(item
->delete_data_val
)
75 item
->delete_data_val(item
->data_val
);
77 //g_array_free(item->depends, FALSE);
78 //g_array_free(item->rev_depends, FALSE);
81 g_array_remove_index(stack
->array
, index
);
85 if(stack
->proc_index
> stack
->array
->len
)
86 stack
->proc_index
= stack
->array
->len
;
89 /* An item is deletable as soon as it is processed. However, all the items after it
90 * in the list must be deleted before it can be deleted.
92 * After this function, try_start_deleting must be called.
95 static void mark_deletable(struct sstack
*stack
, int index
)
97 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
101 // if(index == stack->array->len - 1) {
102 // start_deleting(stack);
107 /* Called to process an index of the queue */
109 static void process(struct sstack
*stack
, int index
)
111 g_assert(stack
->proc_index
== index
);
113 //printf("sstack: starting to process\n");
114 while(stack
->proc_index
< stack
->array
->len
) {
115 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, stack
->proc_index
);
117 if(!item
->processable
)
120 //printf("sstack: processing ");
123 if(stack
->process_func
) {
124 stack
->process_func(stack
->process_func_arg
, item
);
127 printf("warning: no process func\n");
132 mark_deletable(stack
, stack
->proc_index
-1);
133 if(item
->pushpop
>= 0 && item
->pushpop
< stack
->proc_index
-1) {
134 mark_deletable(stack
, item
->pushpop
);
136 try_start_deleting(stack
);
138 //printf("sstack: stopping processing\n");
141 /* Called to mark an index of the queue as processable */
143 static void mark_processable(struct sstack
*stack
, int index
)
145 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
147 item
->processable
= 1;
149 if(stack
->proc_index
<= stack
->array
->len
&& stack
->proc_index
== index
) {
150 process(stack
, index
);
154 /* Called to check whether an index of the queue could be marked processable. If so,
155 * mark it processable.
157 * To be processable, an item must:
159 * - have its push/pop dependency fulfilled
160 * - have its other dependencies fulfilled
163 static void try_mark_processable(struct sstack
*stack
, int index
)
166 int all_finished
= 1;
168 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
170 //for(i=0; i<stack->array->len; i++) {
171 // if(!g_array_index(stack->array, struct sstack_item *, index)->finished) {
177 /* Theoritically, we should confirm that the push/pop dependency is
178 * finished, but in practice, it's not necessary. If we are a push, the
179 * corresponding pop is always finished. If we are a pop and we exist,
180 * the corresponding push is necessarily finished.
185 mark_processable(stack
, index
);
190 /* Called to mark an index of the queue as finished */
192 static void mark_finished(struct sstack
*stack
, int index
)
194 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
198 try_mark_processable(stack
, index
);
202 /* --------------------- */
204 static void try_advance_processing(struct sstack
*stack
)
206 //g_assert(stack->proc_index == index);
208 //printf("sstack: starting to process\n");
209 while(stack
->proc_index
< stack
->array
->len
) {
210 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, stack
->proc_index
);
212 //if(!item->finished) {
216 //printf("sstack: processing ");
219 if(stack
->process_func
) {
220 stack
->process_func(stack
->process_func_arg
, item
);
223 printf("warning: no process func\n");
228 if(item
->data_type
== SSTACK_TYPE_POP
)
229 mark_deletable(stack
, stack
->proc_index
-1);
230 if(item
->pushpop
>= 0 && item
->pushpop
< stack
->proc_index
-1) {
231 mark_deletable(stack
, item
->pushpop
);
234 try_start_deleting(stack
);
235 //printf("sstack: stopping processing\n");
239 /* Add an item to the queue */
241 void sstack_add_item(struct sstack
*stack
, struct sstack_item
*item
)
245 g_array_append_val(stack
->array
, item
);
247 //printf("stack after adding\n");
248 //print_stack(stack);
250 index
= stack
->array
->len
-1;
252 if(item
->data_type
== SSTACK_TYPE_PUSH
) {
253 int top_of_wait_pop_stack
;
255 if(stack
->wait_pop_stack
->len
&& g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1)) {
256 /* if the preceding is a wait_for_pop (and there is a preceding), push a wait_for_pop */
258 g_array_append_val(stack
->wait_pop_stack
, one
);
261 /* otherwise, push what the item wants */
262 g_array_append_val(stack
->wait_pop_stack
, item
->wait_pop
);
265 top_of_wait_pop_stack
= g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1);
267 g_array_append_val(stack
->pushes
, index
);
269 //printf("after pushing:\n");
270 //print_stack(stack);
271 if(top_of_wait_pop_stack
== 0) {
272 try_advance_processing(stack
);
273 /* ASSERT that we processed the whole sstack */
275 //printf("after processing:\n");
276 //print_stack(stack);
278 else if(item
->data_type
== SSTACK_TYPE_POP
) {
281 if(stack
->pushes
->len
> 0) {
282 /* FIXME: confirm we are popping what we expected to pop */
283 item
->pushpop
= g_array_index(stack
->pushes
, int, stack
->pushes
->len
-1);
284 g_array_index(stack
->array
, struct sstack_item
*, item
->pushpop
)->pushpop
= index
;
285 g_array_index(stack
->array
, struct sstack_item
*, item
->pushpop
)->finished
= 1;
287 g_array_remove_index(stack
->pushes
, stack
->pushes
->len
-1);
290 if(stack
->wait_pop_stack
->len
> 0) {
291 int top_of_wait_pop_stack
;
293 g_array_remove_index(stack
->wait_pop_stack
, stack
->wait_pop_stack
->len
-1);
295 if(stack
->wait_pop_stack
->len
> 0) {
296 top_of_wait_pop_stack
= g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1);
298 if(top_of_wait_pop_stack
== 0)
299 try_advance_processing(stack
);
302 try_advance_processing(stack
);
306 try_advance_processing(stack
);
310 //printf("stack after processing\n");
311 //print_stack(stack);
314 /* Force processing of all items */
316 void sstack_force_flush(struct sstack
*stack
)
320 for(i
=0; i
<stack
->array
->len
; i
++) {
321 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, i
);
323 if(!item
->finished
) {
328 try_advance_processing(stack
);
331 /* Create a new sstack */
333 struct sstack
*sstack_new(void)
335 struct sstack
*retval
;
337 retval
= (struct sstack
*) g_malloc(sizeof(struct sstack
));
339 retval
->array
= g_array_new(FALSE
, FALSE
, sizeof(struct sstack_item
*));
340 retval
->pushes
= g_array_new(FALSE
, FALSE
, sizeof(int));
341 retval
->wait_pop_stack
= g_array_new(FALSE
, FALSE
, sizeof(int));
342 retval
->proc_index
= 0;
343 retval
->process_func
= NULL
;
348 /* Create a new sstack_item. Normally not invoked directly. See other functions below. */
350 struct sstack_item
*sstack_item_new(void)
352 struct sstack_item
*retval
;
354 retval
= (struct sstack_item
*) g_malloc(sizeof(struct sstack_item
));
355 retval
->finished
= 0;
356 retval
->processable
= 0;
357 retval
->deletable
= 0;
358 retval
->data_type
= 0;
359 retval
->data_val
= NULL
;
360 retval
->delete_data_val
= NULL
;
361 retval
->pushpop
= -1;
362 retval
->wait_pop
= 0;
363 //retval->depends = g_array_new(FALSE, FALSE, sizeof(int));
364 //retval->rev_depends = g_array_new(FALSE, FALSE, sizeof(int));
369 /* Create a new sstack_item that will represent a PUSH operation */
371 struct sstack_item
*sstack_item_new_push(unsigned char wait_pop
)
373 struct sstack_item
*retval
= sstack_item_new();
375 retval
->data_type
= SSTACK_TYPE_PUSH
;
376 retval
->wait_pop
= wait_pop
;
381 /* Create a new sstack_item that will represent a POP operation */
383 struct sstack_item
*sstack_item_new_pop(void)
385 struct sstack_item
*retval
= sstack_item_new();
387 retval
->data_type
= SSTACK_TYPE_POP
;
388 retval
->finished
= 1;
393 /* Create a new sstack_item that will represent an EVENT operation */
395 struct sstack_item
*sstack_item_new_event(void)
397 struct sstack_item
*retval
= sstack_item_new();
399 retval
->data_type
= SSTACK_TYPE_EVENT
;
400 retval
->finished
= 1;
401 retval
->processable
= 1;
402 retval
->deletable
= 1;
This page took 0.038896 seconds and 5 git commands to generate.