lttv/modules/text/sstack.c

   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 }