fork download 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. struct node {
  5.     struct node *next;
  6.     int value;
  7. };
  8.  
  9. typedef int (*remove_fn) (const struct node *n);
  10.  
  11. void remove_if_twostar (struct node **first, remove_fn cond, int *count)
  12. {
  13.     struct node **prev_next = first;
  14.     struct node *cur = *first;
  15.  
  16.     while (cur) {
  17.         if (cond(cur)) {
  18.             (*count)++;
  19.             *prev_next = cur->next;
  20.             cur = cur->next;
  21.         } else {
  22.             prev_next = &cur->next;
  23.             cur = cur->next;
  24.         }
  25.     }
  26. }
  27.  
  28. void remove_if_onestar (struct node **first, remove_fn cond, int *count)
  29. {
  30.     struct node *prev = NULL;
  31.     struct node *cur = *first;
  32.  
  33.     while (cur) {
  34.         if (cond(cur)) {
  35.             (*count)++;
  36.             if (prev) {
  37.                 prev->next = cur->next;
  38.             } else {
  39.                 *first = cur->next;
  40.             }
  41.             cur = cur->next;
  42.         } else {
  43.             prev = cur;
  44.             cur = cur->next;
  45.         }
  46.     }
  47. }
  48.  
  49. void build_twostar (struct node **first, struct node *nodes, size_t num_nodes)
  50. {
  51.     struct node **prev_next = first;
  52.  
  53.     for (size_t i = 0; i < num_nodes; i++) {
  54.         *prev_next = &nodes[i];
  55.         prev_next = &nodes[i].next;
  56.     }
  57.  
  58.     *prev_next = NULL;
  59. }
  60.  
  61. void build_onestar (struct node **first, struct node *nodes, size_t num_nodes)
  62. {
  63.     if (num_nodes == 0) {
  64.         *first = NULL;
  65.     } else {
  66.         *first = &nodes[0];
  67.  
  68.         for (size_t i = 0; i < num_nodes - 1; i++) {
  69.             nodes[i].next = &nodes[i + 1];
  70.         }
  71.  
  72.         nodes[num_nodes - 1].next = NULL;
  73.     }
  74. }
  75.  
  76. int remove_func (const struct node *n)
  77. {
  78.     return rand() > RAND_MAX / 2;
  79. }
  80.  
  81. int main (int argc, char *argv[])
  82. {
  83.     if (argc != 3) {
  84.         printf("Need two arguments.\n");
  85.         return 1;
  86.     }
  87.  
  88.     size_t num_nodes = atoi(argv[1]);
  89.     int num_iter = atoi(argv[2]);
  90.  
  91.     struct node *nodes = malloc(num_nodes * sizeof(nodes[0]));
  92.  
  93.     int all_count = 0;
  94.  
  95.     for (int i = 0; i < num_iter; i++) {
  96.         struct node *first;
  97.         build_onestar(&first, nodes, num_nodes);
  98.         remove_if_onestar(&first, remove_func, &all_count);
  99.     }
  100.  
  101.     printf("Total removed: %d\n", all_count);
  102.  
  103.     return 0;
  104. }
  105.  
Runtime error #stdin #stdout 0.01s 1720KB
comments (?)
stdin 
Standard input is empty
stdout 
Need two arguments.
https://ideone.com/D7bzmo
language:
C99 (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!