https://mattn.kaoriya.net/software/lang/c/20181214140011.htm

flatten.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum _type_t {
  INT_T,
  STRING_T,
  LIST_T,
} type_t;

typedef struct _value_t {
  int ref;
  type_t type;
  union {
    int n;
    char *s;
    struct _list_t *l;
  } val;
} value_t;

typedef struct _item_t {
  struct _item_t *next;
  value_t *value;
} item_t;

typedef struct _list_t {
  item_t *first;
} list_t;

static void free_item(item_t *item);

static void
free_value(value_t *v) {
  item_t *i;

  if (v->ref > 1) {
    v->ref--;
    return;
  }

  switch (v->type) {
  case INT_T:
    break;
  case STRING_T:
    free((void*)v->val.s);
    break;
  case LIST_T:
    i = v->val.l->first;
    while (i != NULL) {
      item_t *next = i->next;
      free_item(i);
      i = next;
    }
    free((void*)v->val.l);
    break;
  }
  free((void*)v);
}

static void
free_item(item_t *item) {
  free_value(item->value);
  free(item);
}

static value_t*
new_list_value() {
  value_t *v = malloc(sizeof(value_t));
  v->type = LIST_T;
  v->val.l = malloc(sizeof(list_t));
  v->val.l->first = NULL;
  v->ref = 0;
  return v;
}

item_t*
new_item(value_t *v) {
  item_t *item = malloc(sizeof(item_t));
  item->value = v;
  item->next = NULL;
  ++v->ref;
  return item;
}

static void
list_add_value(list_t *list, value_t *rhs) {
  item_t *i = list->first;

  if (i == NULL) {
    list->first = new_item(rhs);
    return;
  }

  while (i->next != NULL) {
    i = i->next;
  }

  i->next = new_item(rhs);
}

static void
list_insert_value(list_t *list, item_t *before, value_t *value) {
  item_t *next;

  if (before == NULL) {
    list->first = new_item(value);
    return;
  }

  next = before->next;

  before->next = new_item(value);
  before->next->next = next;
}

static void
list_remove_item(list_t *list, item_t *item) {
  item_t *i, *before = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i == item) {
      if (before == NULL)
        list->first = i->next;
      else
        before->next = i->next;

      free_item(item);
      return;
    }
    before = i;
  }
}

static value_t*
new_int_value(int n) {
  value_t *v = malloc(sizeof(value_t));
  v->type = INT_T;
  v->val.n = n;
  v->ref = 0;
  return v;
}

static value_t*
new_string_value(const char* s) {
  value_t *v = malloc(sizeof(value_t));
  v->type = STRING_T;
  v->val.s = strdup(s);
  v->ref = 0;
  return v;
}

static void
print_value(value_t *v) {
  item_t *i;

  switch (v->type) {
  case INT_T:
    printf("%d", v->val.n);
    break;
  case STRING_T:
    /* TODO: escape non-printable */
    printf("\"%s\"", v->val.s);
    break;
  case LIST_T:
    printf("[");
    for (i = v->val.l->first; i != NULL; i = i->next) {
      print_value(i->value);
      if (i->next) printf(", ");
    }
    printf("]");
    break;
  }
}

// static void
// flatten_list(item_t *before, list_t *list) {
//   item_t *i, *j, *prev = NULL;
//
//   for (i = list->first; i != NULL; i = i->next) {
//     if (i->value->type == LIST_T) {
//       flatten_list(i, i->value->val.l);
//       list_remove_item(list, i);
//       return;
//     }
//     if (before != NULL) {
//       list_insert_value(list, before, i->value);
//       before = before->next;
//     }
//   }
// }

static void
flatten_list(list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      item_t *before = i;
      for (j = i->value->val.l->first; j != NULL; j = j->next) {
        list_insert_value(list, before, j->value);
        before = before->next;
      }

      if (prev == NULL)
        list->first = i->next;

      if (prev == NULL)
        prev = i;
      else
        prev->next = i->next;
      free_item(i);
      i = prev;
    }
    prev = i;
  }
}

int
main(int argc, char* argv[]) {
  value_t *list, *sub, *sub2, *sub3;

#if 1
  // [1, "foo", ["bar"], 3]
  list = new_list_value();
  list_add_value(list->val.l, new_int_value(1));
  list_add_value(list->val.l, new_string_value("foo"));

  sub = new_list_value();
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));
#elif 0
  // [1, "foo", 3]
  list = new_list_value();
  list_add_value(list->val.l, new_int_value(1));
  list_add_value(list->val.l, new_string_value("foo"));

  list_add_value(list->val.l, new_int_value(3));
#elif 0
  // [["bar"], 3]
  list = new_list_value();

  sub = new_list_value();
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));
#elif 0
  // ["foo", ["bar", ["baz"]], 3]
  list = new_list_value();
  list_add_value(list->val.l, new_string_value("foo"));

  sub2 = new_list_value();
  list_add_value(sub2->val.l, new_string_value("baz"));

  sub = new_list_value();
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(sub->val.l, sub2);

  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));
#elif 0
  // ["foo", ["bar", ["baz", [3]]]]
  list = new_list_value();
  list_add_value(list->val.l, new_string_value("foo"));

  sub3 = new_list_value();
  list_add_value(sub3->val.l, new_int_value(3));

  sub2 = new_list_value();
  list_add_value(sub2->val.l, new_string_value("baz"));
  list_add_value(sub2->val.l, sub3);

  sub = new_list_value();
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(sub->val.l, sub2);

  list_add_value(list->val.l, sub);
#endif

#if 1
  flatten_list(list->val.l);
#endif

  print_value(list);
  putchar('\n');
  free_value(list);
  return 0;
}

flatten.diff

diff --git a/flatten.c b/flatten.c
index 4c7e935..735549b 100644
--- a/flatten.c
+++ b/flatten.c
@@ -27,11 +27,16 @@ typedef struct _list_t {
   item_t *first;
 } list_t;
 
+static void free_item(item_t *item);
+
 static void
 free_value(value_t *v) {
   item_t *i;
 
-  if (v->ref-- > 0) return;
+  if (v->ref > 1) {
+    v->ref--;
+    return;
+  }
 
   switch (v->type) {
   case INT_T:
@@ -43,8 +48,7 @@ free_value(value_t *v) {
     i = v->val.l->first;
     while (i != NULL) {
       item_t *next = i->next;
-      free_value(i->value);
-      free(i);
+      free_item(i);
       i = next;
     }
     free((void*)v->val.l);
@@ -53,6 +57,12 @@ free_value(value_t *v) {
   free((void*)v);
 }
 
+static void
+free_item(item_t *item) {
+  free_value(item->value);
+  free(item);
+}
+
 static value_t*
 new_list_value() {
   value_t *v = malloc(sizeof(value_t));
@@ -114,8 +124,7 @@ list_remove_item(list_t *list, item_t *item) {
       else
         before->next = i->next;
 
-      free_value(item->value);
-      free(item);
+      free_item(item);
       return;
     }
     before = i;
@@ -184,7 +193,7 @@ static void
 flatten_list(list_t *list) {
   item_t *i, *j, *prev = NULL;
 
-  for (i = list->first; i != NULL; i = i->next) {
+  for (i = list->first; i != NULL;) {
     if (i->value->type == LIST_T) {
       item_t *before = i;
       for (j = i->value->val.l->first; j != NULL; j = j->next) {
@@ -192,20 +201,27 @@ flatten_list(list_t *list) {
         before = before->next;
       }
 
-      if (prev == NULL)
+      if (prev == NULL) {
         list->first = i->next;
+      } else {
+        prev->next = i->next;
+      }
 
-      prev->next = i->next;
-      i = prev;
+      item_t *next = i->next;
+      free_item(i);
+      i = next;
+    } else {
+      prev = i;
+      i = i->next;
     }
-    prev = i;
   }
 }
 
 int
 main(int argc, char* argv[]) {
-  value_t *list, *sub;
+  value_t *list, *sub, *sub2, *sub3;
 
+#if 1
   // [1, "foo", ["bar"], 3]
   list = new_list_value();
   list_add_value(list->val.l, new_int_value(1));
@@ -216,8 +232,59 @@ main(int argc, char* argv[]) {
   list_add_value(list->val.l, sub);
 
   list_add_value(list->val.l, new_int_value(3));
+#elif 0
+  // [1, "foo", 3]
+  list = new_list_value();
+  list_add_value(list->val.l, new_int_value(1));
+  list_add_value(list->val.l, new_string_value("foo"));
+
+  list_add_value(list->val.l, new_int_value(3));
+#elif 0
+  // [["bar"], 3]
+  list = new_list_value();
+
+  sub = new_list_value();
+  list_add_value(sub->val.l, new_string_value("bar"));
+  list_add_value(list->val.l, sub);
+
+  list_add_value(list->val.l, new_int_value(3));
+#elif 0
+  // ["foo", ["bar", ["baz"]], 3]
+  list = new_list_value();
+  list_add_value(list->val.l, new_string_value("foo"));
+
+  sub2 = new_list_value();
+  list_add_value(sub2->val.l, new_string_value("baz"));
+
+  sub = new_list_value();
+  list_add_value(sub->val.l, new_string_value("bar"));
+  list_add_value(sub->val.l, sub2);
+
+  list_add_value(list->val.l, sub);
+
+  list_add_value(list->val.l, new_int_value(3));
+#elif 0
+  // ["foo", ["bar", ["baz", [3]]]]
+  list = new_list_value();
+  list_add_value(list->val.l, new_string_value("foo"));
+
+  sub3 = new_list_value();
+  list_add_value(sub3->val.l, new_int_value(3));
+
+  sub2 = new_list_value();
+  list_add_value(sub2->val.l, new_string_value("baz"));
+  list_add_value(sub2->val.l, sub3);
+
+  sub = new_list_value();
+  list_add_value(sub->val.l, new_string_value("bar"));
+  list_add_value(sub->val.l, sub2);
+
+  list_add_value(list->val.l, sub);
+#endif
 
+#if 1
   flatten_list(list->val.l);
+#endif
 
   print_value(list);
   putchar('\n');