lttv/modules/text/sstack.c

   1 #include <glib.h>
   2 #include <stdio.h>
   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 }