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

typedef struct links {
    struct links * next;
    struct links * prev;
} links;

typedef struct outer_node {
  links l; // links to outer_node.l
  struct inner_node * children;
} outer_node;

typedef struct inner_node {
  links l; // links to inner_node.l
  char type;
  void * item;
} inner_node;

void linkNodes(links* l1, links* l2)
{
  links* tmp = l1->prev;
  l1->next->prev = l2->prev;
  l1->next = l2;

  l2->prev->next = tmp;
  l2->prev = l1;
}

inner_node* createNode(char type, void* item, inner_node* sibling)
{
  inner_node* n = malloc(sizeof(*n));
  n->type = type;
  n->item = item;
  n->l.prev = &n->l;
  n->l.next = &n->l;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;
}

outer_node* createOuterNode(inner_node* child, outer_node* sibling)
{
  outer_node* n = malloc(sizeof(*n));
  n->l.prev = &n->l;
  n->l.next = &n->l;
  n->children = child;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;  
}

void PrintList(links* l, int level)
{
  links* l2 = l;
  do
  {
    if (level == 0)
    {
      outer_node* n = (void*)((char*)l2 + offsetof(outer_node, l));
      printf("{\n");
      PrintList(&n->children->l, level + 1);
      printf("}\n");
    }
    else
    {
      inner_node* n = (void*)((char*)l2 + offsetof(inner_node, l));
      printf("  type: %d, item: %s\n", n->type, (char*)n->item);
    }
    l2 = l2->next;
  } while (l2 != l);
}

int main(void)
{
  outer_node* root = 
    createOuterNode(
      createNode(0, "something",
        NULL
      ),
      createOuterNode(
        createNode(1, "foo",
          createNode(2, "bar",
            NULL
          )
        ),
        createOuterNode(
          createNode(3, "red",
            createNode(3, "green",
              createNode(3, "blue",
                NULL
              )
            )
          ),
          createOuterNode(
            createNode(4, "cat",
              createNode(5, "dog",
                createNode(6, "raven",
                  createNode(7, "shark",
                    NULL
                  )
                )
              )
            ),
            NULL
          )
        )
      )
    );

  PrintList(&root->l, 0);

  return 0;
}