Skiplist implementation using C

user_6314387 0
Viewed 1325

Below is my skiplist implementation, The code working fine, but what I need this that when key matches with the existing key in then value to be updated with the new value, but in my case the item inserted twice and the data is not replaced. I want to implement this at the time of update so that i do not have to search the entire list.

Any help in this regard is highly appreciated

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

#ifndef EQ
#define EQ(a, b) (a == b)
#endif

#ifndef LTE
#define LTE(a, b) (a < b)
#endif

struct skipLink
{
    int key;
    int value;
    struct skipLink *next;
    struct skipLink *down;
};

struct skipList
{
    struct skipLink *topSentinel;
    int size;
};

/* the public interface */
void test(void);
void initSkipList(struct skipList *slst);
int containsSkipList(struct skipList *slst, int key);
void removeSkipList(struct skipList *slst, int key);
void addSkipList(struct skipList *slst, int key, int value);
int sizeSkipList(struct skipList *slst);
void printSkipList(struct skipList *slst);

/* internal routines */
int flipSkipLink();
struct skipLink *slideRightSkipList(struct skipLink *current, int key);
struct skipLink *skipLinkAdd(struct skipLink *current, int key, int value);
struct skipLink *newSkipLink(int key, int value, struct skipLink *nextLnk, struct skipLink *downLnk);

/* ************************************************************************
Main Function
 ************************************************************************ */
/* Test function:
 param: no parameters
 pre:   no parameres
 post: prints out the contents of the skip list */

int main()
{
    int i = 0;
    /*srand(time(NULL));*/

    /*  Initialize the skip list */
    struct skipList *sl1 = (struct skipList *)malloc(sizeof(struct skipList));
    initSkipList(sl1);

    /*  Add to the skip list  M = 20 random integers in [0,100] */
    for (i = 0; i < 20; i++)
    {
        addSkipList(sl1, rand() % 101, i + 5);
    }
    addSkipList(sl1, 1, 9);

    /*  Print out the contents of the skip list in the breadth-first order, starting from top.
     While printing the elements, move to a new line every time you reach the end of one level,
     and move down to the lower level of the skip list.
     For example, the print out of a skip list with 5 elements should look like

     7
     7 14 29
     3 7 9 14 20

     */
    printf("---------- skipList 1 -----");
    printf("----- size %d -----\n", sizeSkipList(sl1));
    printSkipList(sl1);
    printf("---------- removed %d from skipList -----", sl1->topSentinel->next->key);
    removeSkipList(sl1, sl1->topSentinel->next->key);
    printf("----- size %d -----\n", sizeSkipList(sl1));
    printSkipList(sl1);

    return 0;
}

/* ************************************************************************
Internal Functions
 ************************************************************************ */

/* Coin toss function:
 param:     no parameters
 pre:   no parameres
 post: output is a random intiger number in {0,1} */
int flipSkipLink(void)
{
    return (rand() % 2);
}

/* Move to the right as long as the next element is smaller than the input key:
 param:     current -- pointer to a place in the list from where we need to slide to the right
 param: key --  input key
 pre:   current is not NULL
 post: returns one link before the link that contains the input key key */
struct skipLink *slideRightSkipList(struct skipLink *current, int key)
{
    while ((current->next != 0) && LTE(current->next->key, key))
        current = current->next;
    return current;
}

/* Create a new skip link for a key
    param: key   -- the key to create a link for
    param: nextLnk   -- the new link's next should point to nextLnk
    param: downLnk -- the new link's down should point to downLnk
    pre:    none
    post:   a link to store the key */
struct skipLink *newSkipLink(int key, int value, struct skipLink *nextLnk, struct skipLink *downLnk)
{
    struct skipLink *tmp = (struct skipLink *)malloc(sizeof(struct skipLink));
    assert(tmp != 0);
    tmp->key = key;
    tmp->value = value;
    tmp->next = nextLnk;
    tmp->down = downLnk;
    return tmp;
}

/* Add a new skip link recursively
 param: current -- pointer to a place in the list where the new element should be inserted
 param: key  -- the key to create a link for
 pre:   current is not NULL
 post: a link to store the key */
struct skipLink *skipLinkAdd(struct skipLink *current, int key, int value)
{
    struct skipLink *newLink, *downLink;
    newLink = 0;
    if (current->down == 0)
    {
        newLink = newSkipLink(key, value, current->next, 0);
        current->next = newLink;
    }
    else
    {
        downLink = skipLinkAdd(slideRightSkipList(current->down, key), key, value);
        if (downLink != 0 && flipSkipLink())
        {
            newLink = newSkipLink(key, value, current->next, downLink);
            current->next = newLink;
        }
    }
    return newLink;
}

/* ************************************************************************
Public Functions
 ************************************************************************ */

/* Initialize skip list:
 param:  slst -- pointer to the skip list
 pre:   slst is not null
 post: the sentinels are allocated, the pointers are set, and the list size equals zero */
void initSkipList(struct skipList *slst)
{
    assert(slst != NULL);
    slst->topSentinel = (struct skipLink *)malloc(sizeof(struct skipLink));
    slst->topSentinel->next = 0;
    slst->topSentinel->down = 0;
    slst->size = 0;
}

/* Checks if an element is in the skip list:
 param: slst -- pointer to the skip list
 param: key -- element to be checked
 pre:   slst is not null
 post: returns true or false  */
int containsSkipList(struct skipList *slst, int key)
{
    struct skipLink *current = slst->topSentinel;
    while (current)
    {
        current = slideRightSkipList(current, key);
        if ((current->next != 0) && EQ(current->next->key, key))
            return 1;
        current = current->down;
    }
    return 0;
}

/* Remove an element from the skip list:
 param: slst -- pointer to the skip list
 param: key -- element to be removed
 pre:   slst is not null
 post: the new element is removed from all internal sorted lists */
void removeSkipList(struct skipList *slst, int key)
{
    struct skipLink *current, *temp;
    current = slst->topSentinel;

    while (current)
    {
        current = slideRightSkipList(current, key);
        if ((current->next != 0) && EQ(current->next->key, key))
        {
            temp = current->next;
            current->next = current->next->next;
            free(temp);
            if (current->down == NULL)
                slst->size--;
        }
        current = current->down;
    }
}

/* Add a new element to the skip list:
    param: slst -- pointer to the skip list
    param: key -- element to be added
    pre:    slst is not null
    post:   the new element is added to the lowest list and randomly to higher-level lists */
void addSkipList(struct skipList *slst, int key, int value)
{
    struct skipLink *downLink, *newLink;
    downLink = skipLinkAdd(slideRightSkipList(slst->topSentinel, key), key, value);
    if (downLink != 0 && flipSkipLink())
    {
        struct skipLink *newTopSentinel = (struct skipLink *)malloc(sizeof(struct skipLink));
        newLink = newSkipLink(key, value, 0, downLink);
        newTopSentinel->next = newLink;
        newTopSentinel->down = slst->topSentinel;
        slst->topSentinel = newTopSentinel;
    }
    slst->size++;
}

/* Find the number of elements in the skip list:
 param: slst -- pointer to the skip list
 pre:   slst is not null
 post: the number of elements */
int sizeSkipList(struct skipList *slst)
{
    return slst->size;
}

/* Print the links in the skip list:
    param: slst -- pointer to the skip list
    pre:    slst is not null and slst is not empty
    post: the links in the skip list are printed breadth-first, top-down */
void printSkipList(struct skipList *slst)
{
    struct skipLink *currentlist = slst->topSentinel;
    struct skipLink *currentlink;
    while (currentlist != NULL)
    {
        currentlink = currentlist->next;
        while (currentlink != NULL)
        {
            printf("{%d, %d}", currentlink->key, currentlink->value);
            currentlink = currentlink->next;
        }
        currentlist = currentlist->down;
        printf("\n");
        printf("\n");
    }
}
data-structures c
1 Answers

Updating existing elements

If you want your code to be able to update existing elements when inserting a new value, then you have to combine the searching you do in containsSkipList() with the creation of a new skipLink. So:

void addSkipList(struct skipList *slst, int key, int value)
{
    
    struct skipLink *current = slst->topSentinel;

    while (current)
    {
        /* Search as usual */
        current = slideRightSkipList(current, key);
        if (current->next != NULL && current->next->key == key)
        {
            /* If found, update the value */
            current->next->value = value;

            /* Also update all the skipLinks downwards from this point */
            ...
            return;
        }

        if (current->down == NULL)
            break;

        current = current->down;
    }

    /* current now points to the closest smaller item to key,
     * add the new item right after it */
    ...

    if (flipSkipLink())
    {
        /* Add to higher level-list as well */
    }
}

Avoid writing macros

You defined two macros that are not very useful, but worse they are incorrect. The problem is that the arguments will be expanded literally, and this can be a problem. Consider this example, where I want to compare if a value has a given bit set:

int value = 0x01;
int mask = 0x10;
int required = 0x10;

printf("%d\n", EQ(value & mask, required));

You would expect that value & mask is zero, which is not equal to required, so you expect it to print 0. However, it prints 1, since after the macro expansion, it says:

printf("%d\n", (value & mask == required));

And since == has a higher precedence than &, it is equivalent to (value & (mask == required)). You would either have to fix the macro:

#define EQ(a, b) ((a) == (b))

Or write a function instead, if you know the type of the arguments:

bool EQ(int a, int b) { return a == b; }

But in this case, the macros are not useful at all, just use == and < directly in your code. For example, instead of:

while ((current->next != 0) && LTE(current->next->key, key))

Just write:

while (current->next != NULL && current->next->key < key)

Use NULL instead of 0 for pointers

While you can compare a pointer against 0, it is better to explicitly write NULL. This helps catch errors if you wanted to check for a NULL pointer, but you accidentily are comparing a non-pointer variable with 0. This will compile without any warnings, but if you had written NULL, then the compiler will give you a warning that this is a potential mistake.

Avoid forward declarations

By changing the order in which functions are defined in your source file, you can avoid having to write forward declarations. This avoids repetition, and reduces potential mistakes.

Make internal routines static

Functions that are only used inside the same .c file and should not be visible in other files can be made static. This avoids namespace polution and might also help the compiler generate better code.

Use const pointers where appropriate

If a function takes a pointer to a skipList, but you are not going to modify that skiplist, then make the pointer const. This allows the compiler to generate errors when you accidentily do write to the skiplist, and it might also generate more optimal code.

Use a consistent prefix for your public interface

To avoid namespace collisions, it helps if all public interfaces functions have a common prefix. Using the name of the struct they operate on is a good choice. Currently, you are using this as a postfix in most cases, but not always. So:

  • skipList_init()
  • skipList_contains()
  • ...

I recommend you also use this for the internal routines, so:

- `skipLink_add()`
- `skipLink_new()`
- ...

Avoid repeating type names

In this line, you repeat the name of the type three times:

struct skipList *sl1 = (struct skipList *)malloc(sizeof(struct skipList));

You can rewrite this to:

struct skipList *sl1 = malloc(sizeof *sl1);

A standards compliant compiler should accept this without any warnings. A cast might be necessary if you compile this with a C++ compiler.

Create a constructor and destructor

You leave it up to the user of the skiplist to allocate memory for a struct skipList, and then have it call initSkipList(). While that might make sense in some cases, there's also the issue of what to do after you are done with the skipList. Does the user just call free() on the skipList variable? But what about all the skipLinks that were allocated? Create a constructor and a destructor function that take care of memory allocation, initialization, and freeing:

struct skipList *skipList_new(void) {
    struct skipList *list = malloc(sizeof *list);
    skipList_init(list);
    return list;
}

void skipList_delete(struct skipList *list) {
    for (/* each skipLink in the list */)
         skipLink_delete(link);

    free(list);
}

Use bool where appropriate

When something returns a true/false value, use the bool type from <stdbool.h>. For example:

bool skipList_contains(const struct skipList *slst, int key)
{
    const struct skipLink *current = slst->topSentinel;
    while (current)
    {
        current = skipList_slideRight(current, key);
        if (current->next != NULL && current->next->key == key)
            return true;
        current = current->down;
    }
    return false;
}
user_54814710
Related