sk_list

sk_list.c

/*
 * desc: yet another simple ANSI-C skip list implement
 * 
 * author: c4pt0r <huangdongxu@gmail.com>
 * date:   2012-10-1
 *
 * */
#include <stdio.h>
#include <memory.h>

#include <stdlib.h>
#include "sk_list.h"
#include <assert.h>
#define _DEBUG_LOG printf

struct sk_list *
sk_new_list() 
{
    struct sk_list * lst;
    int i = 0;

    lst = (struct sk_list *) malloc (sizeof(struct sk_list));
    lst->level = 0;

    lst->header = NewNodeOfLevel(SK_MAX_LEVEL_SIZE);
    for (i = 0; i< SK_MAX_LEVEL_SIZE; i++)
    {
        lst->header->forward[i] = NIL(lst);
    }
    return lst;
}

void
sk_dump_list(struct sk_list * lst)
{
    int i =0;
    struct sk_list_node * p;
    printf("total level: %d\n", lst->level);
    for (i =0 ;i < lst->level; i++)
    {
        printf("level %d\n", i);
        p = lst->header->forward[i];
        while(p != NIL(lst)){
            printf("%d ", p->_val);
            p = p->forward[i];
        }
        printf("\n");
    }
}

int
sk_insert_node(struct sk_list* lst, sk_node_val val)
{
    int i, new_level;
    struct sk_list_node * update[SK_MAX_LEVEL_SIZE];
    struct sk_list_node * node;

    node = lst->header;
    assert(node != NULL);
    for (i = lst->level; i>=0; i--)
    {
        assert(node->forward[i] != NULL);
        while (node->forward[i] != NIL(lst) && node->forward[i]->_val < val)
        {
            node = node->forward[i];
        } 
        update[i] = node;
    }
    /* check level if need update */
    for (new_level = 0; rand() < RAND_MAX / 2 && new_level < SK_MAX_LEVEL_SIZE - 1; new_level++);
    _DEBUG_LOG("new level: %d\n", new_level);    
    if (new_level > lst->level)
    {
        for (i = lst->level + 1; i <= new_level; i++)
            update[i] = NIL(lst);
        lst->level = new_level;
    } 

    /* create new node */
    node = NewNodeOfLevel(new_level);
    memset(node,0, sizeof(struct sk_list_node ) + new_level * sizeof(struct sk_list_node*));
    node->_val = val;

    /* update levels*/
    for(i =0 ; i<= new_level; i++)
    {
        node->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = node;
    }
    return 0;
}

struct sk_list_node*
sk_find_node(struct sk_list * lst,sk_node_val val)
{
    return NULL;
}

sk_list.h

/*
 * desc: yet another simple ANSI-C skip list implement
 * 
 * author: c4pt0r <huangdongxu@gmail.com>
 * date:   2012-10-1
 *
 * */
#ifndef SK_LIST_H
#define SK_LIST_H
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SK_MAX_LEVEL_SIZE 16
#define sk_node_val int
#define NewNodeOfLevel(l) (struct sk_list_node *)malloc(sizeof(struct sk_list_node) + (l)*sizeof(struct sk_list_node*))
#define NIL(lst)  (lst)->header

struct sk_list_node {
    sk_node_val _val;
    struct sk_list_node* forward[1];
};

struct sk_list {
    int level;
    struct sk_list_node * header;
};

struct sk_list* sk_new_list();
void sk_dump_list();
int sk_insert_node(struct sk_list* lst, sk_node_val val);

struct sk_list_node* sk_find_node(struct sk_list * lst, sk_node_val val);

#endif