Simple Balanced Skip List

Siersan 0 Tallied Votes 144 Views Share

Array based skip lists are a pain to work with. They are error prone and difficult to follow. Worse, they are difficult to extend so that the data structure is deterministic rather than probabilistic (a desirable property). The following implementation uses a linked structure instead of arrays for the levels.

#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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.