6 /* This is the implementation of sstack, a data structure that holds
7 * operations done on a stack in order to play them on a stack a short
8 * while later. They are played when dependencies are fulfilled. The
9 * operations are held in a queue.
11 * Operations include PUSH of data, POP, as well as other special markers.
13 * Stack operations are defined by a struct sstack_item. Each struct
14 * sstack_item has 3 flags:
19 * Finished is raised when all the dependencies of the operation are
20 * fulfilled. POPs are always created finished because they have no
21 * dependencies. PUSHes are marked finished when their corresponding
22 * POP is added to the queueit is the PUSHes
23 * that contain the and EVENTs are always created finished.
25 * Once an operation is finished
28 void (*print_sstack_item_data
)(struct sstack_item
*);
30 /* Debugging function: print a queue item */
32 static void print_item(struct sstack_item
*item
)
36 if(item
->data_type
== SSTACK_TYPE_PUSH
) {
39 else if(item
->data_type
== SSTACK_TYPE_POP
) {
46 printf("%-10s %-2u%-2u%-2u", label
, item
->finished
, item
->processable
, item
->deletable
);
47 /* hack: call this external, application-dependant function to show the private data in the item */
48 print_sstack_item_data(item
);
51 /* Debugging function: print the queue as it is now */
53 void print_stack(struct sstack
*stack
)
57 printf("************************\n");
58 printf("** %-10s F P D\n", "label");
59 for(i
=0; i
<stack
->array
->len
; i
++) {
60 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, i
);
62 printf("** %-3d- ", i
);
68 static void try_start_deleting(struct sstack
*stack
)
70 int index
= stack
->array
->len
-1;
72 while(index
>= 0 && g_array_index(stack
->array
, struct sstack_item
*, index
)->deletable
) {
73 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
75 if(item
->delete_data_val
)
76 item
->delete_data_val(item
->data_val
);
78 //g_array_free(item->depends, FALSE);
79 //g_array_free(item->rev_depends, FALSE);
82 g_array_remove_index(stack
->array
, index
);
86 if(stack
->proc_index
> stack
->array
->len
)
87 stack
->proc_index
= stack
->array
->len
;
90 /* An item is deletable as soon as it is processed. However, all the items after it
91 * in the list must be deleted before it can be deleted.
93 * After this function, try_start_deleting must be called.
96 static void mark_deletable(struct sstack
*stack
, int index
)
98 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
102 // if(index == stack->array->len - 1) {
103 // start_deleting(stack);
108 /* Called to process an index of the queue */
110 static void process(struct sstack
*stack
, int index
)
112 g_assert(stack
->proc_index
== index
);
114 //printf("sstack: starting to process\n");
115 while(stack
->proc_index
< stack
->array
->len
) {
116 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, stack
->proc_index
);
118 if(!item
->processable
)
121 //printf("sstack: processing ");
124 if(stack
->process_func
) {
125 stack
->process_func(stack
->process_func_arg
, item
);
128 printf("warning: no process func\n");
133 mark_deletable(stack
, stack
->proc_index
-1);
134 if(item
->pushpop
>= 0 && item
->pushpop
< stack
->proc_index
-1) {
135 mark_deletable(stack
, item
->pushpop
);
137 try_start_deleting(stack
);
139 //printf("sstack: stopping processing\n");
142 /* Called to mark an index of the queue as processable */
144 static void mark_processable(struct sstack
*stack
, int index
)
146 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
148 item
->processable
= 1;
150 if(stack
->proc_index
<= stack
->array
->len
&& stack
->proc_index
== index
) {
151 process(stack
, index
);
155 /* Called to check whether an index of the queue could be marked processable. If so,
156 * mark it processable.
158 * To be processable, an item must:
160 * - have its push/pop dependency fulfilled
161 * - have its other dependencies fulfilled
164 static void try_mark_processable(struct sstack
*stack
, int index
)
167 int all_finished
= 1;
169 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
171 //for(i=0; i<stack->array->len; i++) {
172 // if(!g_array_index(stack->array, struct sstack_item *, index)->finished) {
178 /* Theoritically, we should confirm that the push/pop dependency is
179 * finished, but in practice, it's not necessary. If we are a push, the
180 * corresponding pop is always finished. If we are a pop and we exist,
181 * the corresponding push is necessarily finished.
186 mark_processable(stack
, index
);
191 /* Called to mark an index of the queue as finished */
193 static void mark_finished(struct sstack
*stack
, int index
)
195 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, index
);
199 try_mark_processable(stack
, index
);
203 /* --------------------- */
205 static void try_advance_processing(struct sstack
*stack
)
207 //g_assert(stack->proc_index == index);
209 //printf("sstack: starting to process\n");
210 while(stack
->proc_index
< stack
->array
->len
) {
211 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, stack
->proc_index
);
213 //if(!item->finished) {
217 //printf("sstack: processing ");
220 if(stack
->process_func
) {
221 stack
->process_func(stack
->process_func_arg
, item
);
224 printf("warning: no process func\n");
229 if(item
->data_type
== SSTACK_TYPE_POP
)
230 mark_deletable(stack
, stack
->proc_index
-1);
231 if(item
->pushpop
>= 0 && item
->pushpop
< stack
->proc_index
-1) {
232 mark_deletable(stack
, item
->pushpop
);
235 try_start_deleting(stack
);
236 //printf("sstack: stopping processing\n");
240 /* Add an item to the queue */
242 void sstack_add_item(struct sstack
*stack
, struct sstack_item
*item
)
246 g_array_append_val(stack
->array
, item
);
248 //printf("stack after adding\n");
249 //print_stack(stack);
251 index
= stack
->array
->len
-1;
253 if(item
->data_type
== SSTACK_TYPE_PUSH
) {
254 int top_of_wait_pop_stack
;
256 if(stack
->wait_pop_stack
->len
&& g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1)) {
257 /* if the preceding is a wait_for_pop (and there is a preceding), push a wait_for_pop */
259 g_array_append_val(stack
->wait_pop_stack
, one
);
262 /* otherwise, push what the item wants */
263 g_array_append_val(stack
->wait_pop_stack
, item
->wait_pop
);
266 top_of_wait_pop_stack
= g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1);
268 g_array_append_val(stack
->pushes
, index
);
270 //printf("after pushing:\n");
271 //print_stack(stack);
272 if(top_of_wait_pop_stack
== 0) {
273 try_advance_processing(stack
);
274 /* ASSERT that we processed the whole sstack */
276 //printf("after processing:\n");
277 //print_stack(stack);
279 else if(item
->data_type
== SSTACK_TYPE_POP
) {
282 if(stack
->pushes
->len
> 0) {
283 /* FIXME: confirm we are popping what we expected to pop */
284 item
->pushpop
= g_array_index(stack
->pushes
, int, stack
->pushes
->len
-1);
285 g_array_index(stack
->array
, struct sstack_item
*, item
->pushpop
)->pushpop
= index
;
286 g_array_index(stack
->array
, struct sstack_item
*, item
->pushpop
)->finished
= 1;
288 g_array_remove_index(stack
->pushes
, stack
->pushes
->len
-1);
291 if(stack
->wait_pop_stack
->len
> 0) {
292 int top_of_wait_pop_stack
;
294 g_array_remove_index(stack
->wait_pop_stack
, stack
->wait_pop_stack
->len
-1);
296 if(stack
->wait_pop_stack
->len
> 0) {
297 top_of_wait_pop_stack
= g_array_index(stack
->wait_pop_stack
, int, stack
->wait_pop_stack
->len
-1);
299 if(top_of_wait_pop_stack
== 0)
300 try_advance_processing(stack
);
303 try_advance_processing(stack
);
307 try_advance_processing(stack
);
311 //printf("stack after processing\n");
312 //print_stack(stack);
315 /* Force processing of all items */
317 void sstack_force_flush(struct sstack
*stack
)
321 for(i
=0; i
<stack
->array
->len
; i
++) {
322 struct sstack_item
*item
= g_array_index(stack
->array
, struct sstack_item
*, i
);
324 if(!item
->finished
) {
329 try_advance_processing(stack
);
332 /* Create a new sstack */
334 struct sstack
*sstack_new(void)
336 struct sstack
*retval
;
338 retval
= (struct sstack
*) g_malloc(sizeof(struct sstack
));
340 retval
->array
= g_array_new(FALSE
, FALSE
, sizeof(struct sstack_item
*));
341 retval
->pushes
= g_array_new(FALSE
, FALSE
, sizeof(int));
342 retval
->wait_pop_stack
= g_array_new(FALSE
, FALSE
, sizeof(int));
343 retval
->proc_index
= 0;
344 retval
->process_func
= NULL
;
349 /* Create a new sstack_item. Normally not invoked directly. See other functions below. */
351 struct sstack_item
*sstack_item_new(void)
353 struct sstack_item
*retval
;
355 retval
= (struct sstack_item
*) g_malloc(sizeof(struct sstack_item
));
356 retval
->finished
= 0;
357 retval
->processable
= 0;
358 retval
->deletable
= 0;
359 retval
->data_type
= 0;
360 retval
->data_val
= NULL
;
361 retval
->delete_data_val
= NULL
;
362 retval
->pushpop
= -1;
363 retval
->wait_pop
= 0;
364 //retval->depends = g_array_new(FALSE, FALSE, sizeof(int));
365 //retval->rev_depends = g_array_new(FALSE, FALSE, sizeof(int));
370 /* Create a new sstack_item that will represent a PUSH operation */
372 struct sstack_item
*sstack_item_new_push(unsigned char wait_pop
)
374 struct sstack_item
*retval
= sstack_item_new();
376 retval
->data_type
= SSTACK_TYPE_PUSH
;
377 retval
->wait_pop
= wait_pop
;
382 /* Create a new sstack_item that will represent a POP operation */
384 struct sstack_item
*sstack_item_new_pop(void)
386 struct sstack_item
*retval
= sstack_item_new();
388 retval
->data_type
= SSTACK_TYPE_POP
;
389 retval
->finished
= 1;
394 /* Create a new sstack_item that will represent an EVENT operation */
396 struct sstack_item
*sstack_item_new_event(void)
398 struct sstack_item
*retval
= sstack_item_new();
400 retval
->data_type
= SSTACK_TYPE_EVENT
;
401 retval
->finished
= 1;
402 retval
->processable
= 1;
403 retval
->deletable
= 1;
This page took 0.036509 seconds and 4 git commands to generate.