Commit | Line | Data |
---|---|---|
8c108c1c PMF |
1 | #include <glib.h> |
2 | ||
3 | #include "sstack.h" | |
4 | ||
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. | |
9 | * | |
10 | * Operations include PUSH of data, POP, as well as other special markers. | |
11 | * | |
12 | * Stack operations are defined by a struct sstack_item. Each struct | |
13 | * sstack_item has 3 flags: | |
14 | * - finished | |
15 | * - processable | |
16 | * - deletable | |
17 | * | |
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. | |
23 | * | |
24 | * Once an operation is finished | |
25 | */ | |
26 | ||
27 | void (*print_sstack_item_data)(struct sstack_item *); | |
28 | ||
29 | /* Debugging function: print a queue item */ | |
30 | ||
31 | static void print_item(struct sstack_item *item) | |
32 | { | |
33 | char *label; | |
34 | ||
35 | if(item->data_type == SSTACK_TYPE_PUSH) { | |
36 | label = "PUSH"; | |
37 | } | |
38 | else if(item->data_type == SSTACK_TYPE_POP) { | |
39 | label = "POP"; | |
40 | } | |
41 | else { | |
42 | label = "UNKNOWN"; | |
43 | } | |
44 | ||
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); | |
48 | } | |
49 | ||
50 | /* Debugging function: print the queue as it is now */ | |
51 | ||
52 | void print_stack(struct sstack *stack) | |
53 | { | |
54 | int i; | |
55 | ||
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); | |
60 | ||
61 | printf("** %-3d- ", i); | |
62 | print_item(item); | |
63 | } | |
64 | printf("\n"); | |
65 | } | |
66 | ||
67 | static void try_start_deleting(struct sstack *stack) | |
68 | { | |
69 | int index = stack->array->len-1; | |
70 | ||
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); | |
73 | ||
74 | if(item->delete_data_val) | |
75 | item->delete_data_val(item->data_val); | |
76 | ||
77 | //g_array_free(item->depends, FALSE); | |
78 | //g_array_free(item->rev_depends, FALSE); | |
79 | g_free(item); | |
80 | ||
81 | g_array_remove_index(stack->array, index); | |
82 | index--; | |
83 | } | |
84 | ||
85 | if(stack->proc_index > stack->array->len) | |
86 | stack->proc_index = stack->array->len; | |
87 | } | |
88 | ||
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. | |
91 | * | |
92 | * After this function, try_start_deleting must be called. | |
93 | */ | |
94 | ||
95 | static void mark_deletable(struct sstack *stack, int index) | |
96 | { | |
97 | struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index); | |
98 | ||
99 | item->deletable = 1; | |
100 | ||
101 | // if(index == stack->array->len - 1) { | |
102 | // start_deleting(stack); | |
103 | // } | |
104 | } | |
105 | ||
106 | #if 0 | |
107 | /* Called to process an index of the queue */ | |
108 | ||
109 | static void process(struct sstack *stack, int index) | |
110 | { | |
111 | g_assert(stack->proc_index == index); | |
112 | ||
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); | |
116 | ||
117 | if(!item->processable) | |
118 | break; | |
119 | ||
120 | //printf("sstack: processing "); | |
121 | //print_item(item); | |
122 | ||
123 | if(stack->process_func) { | |
124 | stack->process_func(stack->process_func_arg, item); | |
125 | } | |
126 | else { | |
127 | printf("warning: no process func\n"); | |
128 | } | |
129 | ||
130 | stack->proc_index++; | |
131 | ||
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); | |
135 | } | |
136 | try_start_deleting(stack); | |
137 | } | |
138 | //printf("sstack: stopping processing\n"); | |
139 | } | |
140 | ||
141 | /* Called to mark an index of the queue as processable */ | |
142 | ||
143 | static void mark_processable(struct sstack *stack, int index) | |
144 | { | |
145 | struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index); | |
146 | ||
147 | item->processable = 1; | |
148 | ||
149 | if(stack->proc_index <= stack->array->len && stack->proc_index == index) { | |
150 | process(stack, index); | |
151 | } | |
152 | } | |
153 | ||
154 | /* Called to check whether an index of the queue could be marked processable. If so, | |
155 | * mark it processable. | |
156 | * | |
157 | * To be processable, an item must: | |
158 | * - be finished | |
159 | * - have its push/pop dependency fulfilled | |
160 | * - have its other dependencies fulfilled | |
161 | */ | |
162 | ||
163 | static void try_mark_processable(struct sstack *stack, int index) | |
164 | { | |
165 | int i; | |
166 | int all_finished = 1; | |
167 | ||
168 | struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index); | |
169 | ||
170 | //for(i=0; i<stack->array->len; i++) { | |
171 | // if(!g_array_index(stack->array, struct sstack_item *, index)->finished) { | |
172 | // all_finished = 0; | |
173 | // break; | |
174 | // } | |
175 | //} | |
176 | ||
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. | |
181 | */ | |
182 | ||
183 | //if(all_finished) { | |
184 | if(item->finished) { | |
185 | mark_processable(stack, index); | |
186 | } | |
187 | //} | |
188 | } | |
189 | ||
190 | /* Called to mark an index of the queue as finished */ | |
191 | ||
192 | static void mark_finished(struct sstack *stack, int index) | |
193 | { | |
194 | struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index); | |
195 | ||
196 | item->finished = 1; | |
197 | ||
198 | try_mark_processable(stack, index); | |
199 | } | |
200 | ||
201 | #endif | |
202 | /* --------------------- */ | |
203 | ||
204 | static void try_advance_processing(struct sstack *stack) | |
205 | { | |
206 | //g_assert(stack->proc_index == index); | |
207 | ||
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); | |
211 | ||
212 | //if(!item->finished) { | |
213 | // break; | |
214 | //} | |
215 | ||
216 | //printf("sstack: processing "); | |
217 | //print_item(item); | |
218 | ||
219 | if(stack->process_func) { | |
220 | stack->process_func(stack->process_func_arg, item); | |
221 | } | |
222 | else { | |
223 | printf("warning: no process func\n"); | |
224 | } | |
225 | ||
226 | stack->proc_index++; | |
227 | ||
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); | |
232 | } | |
233 | } | |
234 | try_start_deleting(stack); | |
235 | //printf("sstack: stopping processing\n"); | |
236 | } | |
237 | ||
238 | ||
239 | /* Add an item to the queue */ | |
240 | ||
241 | void sstack_add_item(struct sstack *stack, struct sstack_item *item) | |
242 | { | |
243 | int index; | |
244 | ||
245 | g_array_append_val(stack->array, item); | |
246 | ||
247 | //printf("stack after adding\n"); | |
248 | //print_stack(stack); | |
249 | ||
250 | index = stack->array->len-1; | |
251 | ||
252 | if(item->data_type == SSTACK_TYPE_PUSH) { | |
253 | int top_of_wait_pop_stack; | |
254 | ||
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 */ | |
257 | const int one=1; | |
258 | g_array_append_val(stack->wait_pop_stack, one); | |
259 | } | |
260 | else { | |
261 | /* otherwise, push what the item wants */ | |
262 | g_array_append_val(stack->wait_pop_stack, item->wait_pop); | |
263 | } | |
264 | ||
265 | top_of_wait_pop_stack = g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1); | |
266 | ||
267 | g_array_append_val(stack->pushes, index); | |
268 | ||
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 */ | |
274 | } | |
275 | //printf("after processing:\n"); | |
276 | //print_stack(stack); | |
277 | } | |
278 | else if(item->data_type == SSTACK_TYPE_POP) { | |
279 | item->finished = 1; | |
280 | ||
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; | |
286 | ||
287 | g_array_remove_index(stack->pushes, stack->pushes->len-1); | |
288 | } | |
289 | ||
290 | if(stack->wait_pop_stack->len > 0) { | |
291 | int top_of_wait_pop_stack; | |
292 | ||
293 | g_array_remove_index(stack->wait_pop_stack, stack->wait_pop_stack->len-1); | |
294 | ||
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); | |
297 | ||
298 | if(top_of_wait_pop_stack == 0) | |
299 | try_advance_processing(stack); | |
300 | } | |
301 | else { | |
302 | try_advance_processing(stack); | |
303 | } | |
304 | } | |
305 | else { | |
306 | try_advance_processing(stack); | |
307 | } | |
308 | } | |
309 | ||
310 | //printf("stack after processing\n"); | |
311 | //print_stack(stack); | |
312 | } | |
313 | ||
314 | /* Force processing of all items */ | |
315 | ||
316 | void sstack_force_flush(struct sstack *stack) | |
317 | { | |
318 | int i; | |
319 | ||
320 | for(i=0; i<stack->array->len; i++) { | |
321 | struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, i); | |
322 | ||
323 | if(!item->finished) { | |
324 | item->finished = 1; | |
325 | } | |
326 | } | |
327 | ||
328 | try_advance_processing(stack); | |
329 | } | |
330 | ||
331 | /* Create a new sstack */ | |
332 | ||
333 | struct sstack *sstack_new(void) | |
334 | { | |
335 | struct sstack *retval; | |
336 | ||
337 | retval = (struct sstack *) g_malloc(sizeof(struct sstack)); | |
338 | ||
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; | |
344 | ||
345 | return retval; | |
346 | } | |
347 | ||
348 | /* Create a new sstack_item. Normally not invoked directly. See other functions below. */ | |
349 | ||
350 | struct sstack_item *sstack_item_new(void) | |
351 | { | |
352 | struct sstack_item *retval; | |
353 | ||
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)); | |
365 | ||
366 | return retval; | |
367 | } | |
368 | ||
369 | /* Create a new sstack_item that will represent a PUSH operation */ | |
370 | ||
371 | struct sstack_item *sstack_item_new_push(unsigned char wait_pop) | |
372 | { | |
373 | struct sstack_item *retval = sstack_item_new(); | |
374 | ||
375 | retval->data_type = SSTACK_TYPE_PUSH; | |
376 | retval->wait_pop = wait_pop; | |
377 | ||
378 | return retval; | |
379 | } | |
380 | ||
381 | /* Create a new sstack_item that will represent a POP operation */ | |
382 | ||
383 | struct sstack_item *sstack_item_new_pop(void) | |
384 | { | |
385 | struct sstack_item *retval = sstack_item_new(); | |
386 | ||
387 | retval->data_type = SSTACK_TYPE_POP; | |
388 | retval->finished = 1; | |
389 | ||
390 | return retval; | |
391 | } | |
392 | ||
393 | /* Create a new sstack_item that will represent an EVENT operation */ | |
394 | ||
395 | struct sstack_item *sstack_item_new_event(void) | |
396 | { | |
397 | struct sstack_item *retval = sstack_item_new(); | |
398 | ||
399 | retval->data_type = SSTACK_TYPE_EVENT; | |
400 | retval->finished = 1; | |
401 | retval->processable = 1; | |
402 | retval->deletable = 1; | |
403 | ||
404 | return retval; | |
405 | } |