Simple Balanced Skip List

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

struct node {
  int data;
  struct node *right;
  struct node *down;
};

struct list {
  struct node *head;
  int level;
};

/*
  Naive example function
  Don't use in production code
*/
int rand_level(int limit)
{
  int i = 1;

  while (rand() < RAND_MAX / 2 && i < limit) {
    ++i;
  }

  return i;
}

struct node *make_node(int data, struct node *right, struct node *down)
{
  struct node *node = malloc(sizeof *node);

  if (node == NULL) {
    return NULL;
  }

  node->data = data;
  node->right = right;
  node->down = down;

  return node;
}

void destroy_node(struct node *node)
{
  free(node);
}

struct node *is_full(struct node *x)
{
  struct node *root = NULL;
  int i;

  if (x->down != NULL) {
    struct node *it = x->down;

    for (i = 0; it != NULL && i < 3; i++) {
      it = it->right;
    }

    if (it != NULL && i == 3) {
      if ((it->right == NULL && x->right == NULL)
        || (it->right != NULL && x->right != NULL)
        && (it->right->data == x->right->data))
      {
        root = x->down->right->right;
      }
    }
  }

  return root;
}

int insert_node(struct list *list, int data)
{
  struct node *x, *root, *node;

  /* Empty list */
  if (list->head == NULL) {
    node = make_node(0, NULL, make_node(0, NULL, list->head));
    if (node == NULL) {
      return 0;
    }
    list->head = node;
  }

  /* Grow list */
  if ((root = is_full(list->head)) != NULL) {
    node = make_node(root->data, list->head->right, root);
    if (node == NULL) {
      return 0;
    }
    list->head->right = node;

    node = make_node(0, NULL, list->head);
    if (node == NULL) {
      return 0;
    }
    list->head = node;
  }

  x = list->head->down;

  while (x != NULL) {
    while (x->right != NULL && data > x->right->data) {
      x = x->right;
    }

    if (x->right == NULL || data != x->right->data) {
      if ((root = is_full(x)) != NULL) {
        node = make_node(root->data, x->right, root);
        if (node == NULL) {
          return 0;
        }
        x->right = node;
      }

      if (x->down == NULL) {
        node = make_node(data, x->right, NULL);
        if (node == NULL) {
          return 0;
        }
        x->right = node;

        break;
      }
    }

    x = x->down;
  }

  return 1;
}

int remove_node(struct list *list, int data)
{
  int ret = 0;
  struct node *x, *save;

  x = list->head->down;

  while (x != NULL) {
    while (x->right != NULL && data > x->right->data) {
      x = x->right;
    }

    if (x->right != NULL && data == x->right->data) {
      save = x->right;
      x->right = save->right;
      destroy_node(save);

      ret = 1;
    }

    x = x->down;
  }

  while (list->head->down != NULL && list->head->down->right == NULL) {
    save = list->head->down;
    list->head->down = list->head->down->down;
    destroy_node(save);
  }

  return ret;
}

void list_structure(struct list *list)
{
  struct node *x, *y, *z;

  for (x = list->head; x != NULL; x = x->down) {
    for (z = list->head; z->down != NULL; z = z->down) {
    }

    for (y = x; y != NULL; y = y->right) {
      for (; z != NULL && z->data != y->data; z = z->right) {
        printf("-");

        if (z->right != NULL && z->right->data != y->data) {
          printf("--");
        }
      }
      printf("%02d", y->data);
    }
    printf("\n");
  }
}

int main(void)
{
  struct list list = {0};
  int i;

  srand((unsigned int)time(NULL));

  for (i = 0; i < 25; i++) {
    int r = rand() % 99 + 1;
    printf("Insert %d, returned %d\n", r, insert_node(&list, r));

    list_structure(&list);
    printf("\n-------------------------\n");

    getchar();
  }

  return 0;
}