[lttv.git] / lttv / modules / text / sstack.c

#include <glib.h>
#include <stdio.h>

#include "sstack.h"

/* This is the implementation of sstack, a data structure that holds
 * operations done on a stack in order to play them on a stack a short
 * while later. They are played when dependencies are fulfilled. The
 * operations are held in a queue.
 *
 * Operations include PUSH of data, POP, as well as other special markers.
 *
 * Stack operations are defined by a struct sstack_item. Each struct
 * sstack_item has 3 flags:
 *   - finished
 *   - processable
 *   - deletable
 *
 * Finished is raised when all the dependencies of the operation are
 * fulfilled. POPs are always created finished because they have no
 * dependencies. PUSHes are marked finished when their corresponding
 * POP is added to the queueit is the PUSHes
 * that contain the and EVENTs are always created finished.
 *
 * Once an operation is finished
 */

void (*print_sstack_item_data)(struct sstack_item *);

/* Debugging function: print a queue item */

static void print_item(struct sstack_item *item)
{
	char *label;

	if(item->data_type == SSTACK_TYPE_PUSH) {
		label = "PUSH";
	}
	else if(item->data_type == SSTACK_TYPE_POP) {
		label = "POP";
	}
	else {
		label = "UNKNOWN";
	}

	printf("%-10s    %-2u%-2u%-2u", label, item->finished, item->processable, item->deletable);
	/* hack: call this external, application-dependant function to show the private data in the item */
	print_sstack_item_data(item);
}

/* Debugging function: print the queue as it is now */

void print_stack(struct sstack *stack)
{
	int i;

	printf("************************\n");
	printf("**     %-10s    F P D\n", "label");
	for(i=0; i<stack->array->len; i++) {
		struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, i);

		printf("** %-3d- ", i);
		print_item(item);
	}
	printf("\n");
}

static void try_start_deleting(struct sstack *stack)
{
	int index = stack->array->len-1;

	while(index >= 0 && g_array_index(stack->array, struct sstack_item *, index)->deletable) {
		struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);

		if(item->delete_data_val)
			item->delete_data_val(item->data_val);

		//g_array_free(item->depends, FALSE);
		//g_array_free(item->rev_depends, FALSE);
		g_free(item);

		g_array_remove_index(stack->array, index);
		index--;
	}

	if(stack->proc_index > stack->array->len)
		stack->proc_index = stack->array->len;
}

/* An item is deletable as soon as it is processed. However, all the items after it
 * in the list must be deleted before it can be deleted.
 *
 * After this function, try_start_deleting must be called.
 */

static void mark_deletable(struct sstack *stack, int index)
{
	struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);

	item->deletable = 1;

//	if(index == stack->array->len - 1) {
//		start_deleting(stack);
//	}
}

#if 0
/* Called to process an index of the queue */

static void process(struct sstack *stack, int index)
{
	g_assert(stack->proc_index == index);

	//printf("sstack: starting to process\n");
	while(stack->proc_index < stack->array->len) {
		struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, stack->proc_index);

		if(!item->processable)
			break;

		//printf("sstack: processing ");
		//print_item(item);

		if(stack->process_func) {
			stack->process_func(stack->process_func_arg, item);
		}
		else {
			printf("warning: no process func\n");
		}

		stack->proc_index++;

		mark_deletable(stack, stack->proc_index-1);
		if(item->pushpop >= 0 && item->pushpop < stack->proc_index-1) {
			mark_deletable(stack, item->pushpop);
		}
		try_start_deleting(stack);
	}
	//printf("sstack: stopping processing\n");
}

/* Called to mark an index of the queue as processable */

static void mark_processable(struct sstack *stack, int index)
{
	struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);

	item->processable = 1;

	if(stack->proc_index <= stack->array->len && stack->proc_index == index) {
		process(stack, index);
	}
}

/* Called to check whether an index of the queue could be marked processable. If so,
 * mark it processable.
 *
 * To be processable, an item must:
 * - be finished
 * - have its push/pop dependency fulfilled
 * - have its other dependencies fulfilled
 */

static void try_mark_processable(struct sstack *stack, int index)
{
	int i;
	int all_finished = 1;

	struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);

	//for(i=0; i<stack->array->len; i++) {
	//	if(!g_array_index(stack->array, struct sstack_item *, index)->finished) {
	//		all_finished = 0;
	//		break;
	//	}
	//}

	/* Theoritically, we should confirm that the push/pop dependency is
	 * finished, but in practice, it's not necessary. If we are a push, the
	 * corresponding pop is always finished. If we are a pop and we exist,
	 * the corresponding push is necessarily finished.
	 */

	//if(all_finished) {
	if(item->finished) {
		mark_processable(stack, index);
	}
	//}
}

/* Called to mark an index of the queue as finished */

static void mark_finished(struct sstack *stack, int index)
{
	struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);

	item->finished = 1;

	try_mark_processable(stack, index);
}

#endif
/* --------------------- */

static void try_advance_processing(struct sstack *stack)
{
	//g_assert(stack->proc_index == index);

	//printf("sstack: starting to process\n");
	while(stack->proc_index < stack->array->len) {
		struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, stack->proc_index);

		//if(!item->finished) {
		//	break;
		//}

		//printf("sstack: processing ");
		//print_item(item);

		if(stack->process_func) {
			stack->process_func(stack->process_func_arg, item);
		}
		else {
			printf("warning: no process func\n");
		}

		stack->proc_index++;

		if(item->data_type == SSTACK_TYPE_POP)
			mark_deletable(stack, stack->proc_index-1);
		if(item->pushpop >= 0 && item->pushpop < stack->proc_index-1) {
			mark_deletable(stack, item->pushpop);
		}
	}
	try_start_deleting(stack);
	//printf("sstack: stopping processing\n");
}


/* Add an item to the queue */

void sstack_add_item(struct sstack *stack, struct sstack_item *item)
{
	int index;

	g_array_append_val(stack->array, item);

	//printf("stack after adding\n");
	//print_stack(stack);

	index = stack->array->len-1;

	if(item->data_type == SSTACK_TYPE_PUSH) {
		int top_of_wait_pop_stack;

		if(stack->wait_pop_stack->len && g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1)) {
			/* if the preceding is a wait_for_pop (and there is a preceding), push a wait_for_pop */
			const int one=1;
			g_array_append_val(stack->wait_pop_stack, one);
		}
		else {
			/* otherwise, push what the item wants */
			g_array_append_val(stack->wait_pop_stack, item->wait_pop);
		}

		top_of_wait_pop_stack = g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1);

		g_array_append_val(stack->pushes, index);

		//printf("after pushing:\n");
		//print_stack(stack);
		if(top_of_wait_pop_stack == 0) {
			try_advance_processing(stack);
			/* ASSERT that we processed the whole sstack */
		}
		//printf("after processing:\n");
		//print_stack(stack);
	}
	else if(item->data_type == SSTACK_TYPE_POP) {
		item->finished = 1;

		if(stack->pushes->len > 0) {
			/* FIXME: confirm we are popping what we expected to pop */
			item->pushpop = g_array_index(stack->pushes, int, stack->pushes->len-1);
			g_array_index(stack->array, struct sstack_item *, item->pushpop)->pushpop = index;
			g_array_index(stack->array, struct sstack_item *, item->pushpop)->finished = 1;

			g_array_remove_index(stack->pushes, stack->pushes->len-1);
		}

		if(stack->wait_pop_stack->len > 0) {
			int top_of_wait_pop_stack;

			g_array_remove_index(stack->wait_pop_stack, stack->wait_pop_stack->len-1);

			if(stack->wait_pop_stack->len > 0) {
				top_of_wait_pop_stack = g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1);

				if(top_of_wait_pop_stack == 0)
					try_advance_processing(stack);
			}
			else {
				try_advance_processing(stack);
			}
		}
		else {
			try_advance_processing(stack);
		}
	}

	//printf("stack after processing\n");
	//print_stack(stack);
}

/* Force processing of all items */

void sstack_force_flush(struct sstack *stack)
{
	int i;

	for(i=0; i<stack->array->len; i++) {
		struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, i);

		if(!item->finished) {
			item->finished = 1;
		}
	}

	try_advance_processing(stack);
}

/* Create a new sstack */

struct sstack *sstack_new(void)
{
	struct sstack *retval;

	retval = (struct sstack *) g_malloc(sizeof(struct sstack));

	retval->array = g_array_new(FALSE, FALSE, sizeof(struct sstack_item *));
	retval->pushes = g_array_new(FALSE, FALSE, sizeof(int));
	retval->wait_pop_stack = g_array_new(FALSE, FALSE, sizeof(int));
	retval->proc_index = 0;
	retval->process_func = NULL;

	return retval;
}

/* Create a new sstack_item. Normally not invoked directly. See other functions below. */

struct sstack_item *sstack_item_new(void)
{
	struct sstack_item *retval;

	retval = (struct sstack_item *) g_malloc(sizeof(struct sstack_item));
	retval->finished = 0;
	retval->processable = 0;
	retval->deletable = 0;
	retval->data_type = 0;
	retval->data_val = NULL;
	retval->delete_data_val = NULL;
	retval->pushpop = -1;
	retval->wait_pop = 0;
	//retval->depends = g_array_new(FALSE, FALSE, sizeof(int));
	//retval->rev_depends = g_array_new(FALSE, FALSE, sizeof(int));

	return retval;
}

/* Create a new sstack_item that will represent a PUSH operation */

struct sstack_item *sstack_item_new_push(unsigned char wait_pop)
{
	struct sstack_item *retval = sstack_item_new();

	retval->data_type = SSTACK_TYPE_PUSH;
	retval->wait_pop = wait_pop;

	return retval;
}

/* Create a new sstack_item that will represent a POP operation */

struct sstack_item *sstack_item_new_pop(void)
{
	struct sstack_item *retval = sstack_item_new();

	retval->data_type = SSTACK_TYPE_POP;
	retval->finished = 1;

	return retval;
}

/* Create a new sstack_item that will represent an EVENT operation */

struct sstack_item *sstack_item_new_event(void)
{
	struct sstack_item *retval = sstack_item_new();

	retval->data_type = SSTACK_TYPE_EVENT;
	retval->finished = 1;
	retval->processable = 1;
	retval->deletable = 1;

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