Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Jump table (skiplist) of code     - How to manage your to-do list with the Go For It on Ubuntu (Linux)

- Web cache basics: terminology, HTTP headers, and caching policies (Server)

- Getting Started with Linux system to learn: How do I know which processes are running on the CPU core (Linux)

- Linux crontab commands and detailed usage examples (Linux)

- Install GAMIT / GLOBK 10.50 software under Ubuntu 14.04 (Linux)

- Install the open source database PostgreSQL 9.4 and phpMyAdmin on Ubuntu (Database)

- Samba public folder permissions (Server)

- Linux find command to find files (Linux)

- How to remove the files inside the privacy of data on Linux (Linux)

- MySQL and MariaDB traditional master-slave cluster configuration (Database)

- Create several practical points of high security PHP site (Linux)

- Linux operating system security management skills (Linux)

- Linux pwd command learning experience (Linux)

- How to enable curl command HTTP2 support (Linux)

- How to find an IP address through the command line (Linux)

- Linux, see picture not resolve the problem (Linux)

- Build and verify MongoDB3.0.7 version (shard + replica) Cluster (Database)

- Oracle 10g relations with the constraint of column properties NULLABLE (Database)

- Android Service Lifecycle and usage (Programming)

- Analysis of MySQL Dockerfile 5.6 (Database)

 
         
  Jump table (skiplist) of code
     
  Add Date : 2017-08-31      
         
         
         
  Jump table (skiplist) is a very good data structure is simple, insert, delete, find complexity are O (logN). LevelDB core data structure is implemented jump table, redis sorted set of data structures it is also a jump table implementation.

Find all operations step by step from the top down, the upper span of the larger one next operation. Its implementation is a typical space for time.

Specific details, refer to Wikipedia http://en.wikipedia.org/wiki/Skip_list

The author of the sorted set will redis code sorting, will realize jump table portion extracted for reference.

skiplist.h

#ifndef __SKIPLIST_H
#define __SKIPLIST_H

#define SKIPLIST_MAXLEVEL 8

typedef struct skiplistNode {
    double score;
    struct skiplistNode * backward;
    struct skiplistLevel {
        struct skiplistNode * forward;
    } Level [];
} SkiplistNode;

typedef struct skiplist {
    struct skiplistNode * header, * tail;
    unsigned long length;
    int level;
} Skiplist;

#endif

skiplist.c

#include "skiplist.h"
#include < stdlib.h>
#include < stdio.h>

skiplistNode * slCreateNode (int level, double score) {
    skiplistNode * sn = malloc (sizeof (* sn) + level * sizeof (struct skiplistLevel));
    sn-> score = score;
    return sn;
}

skiplist * slCreate (void) {
    int j;
    skiplist * sl;

    sl = malloc (sizeof (* sl));
    sl-> level = 1;
    sl-> length = 0;
    sl-> header = slCreateNode (SKIPLIST_MAXLEVEL, 0);
    for (j = 0; j < SKIPLIST_MAXLEVEL; j ++) {
        sl-> header-> level [j] .forward = NULL;
    }
    sl-> header-> backward = NULL;
    sl-> tail = NULL;
    return sl;
}

void slFreeNode (skiplistNode * sn) {
    free (sn);
}

void slFree (skiplist * sl) {
    skiplistNode * node = sl-> header-> level [0] .forward, * next;

    free (sl-> header);
    while (node) {
        next = node-> level [0] .forward;
        slFreeNode (node);
        node = next;
    }
    free (sl);
}

int slRandomLevel (void) {
    int level = 1;
    while ((rand () & 0xFFFF) < (0.5 * 0xFFFF))
        level + = 1;
    ? Return (level < SKIPLIST_MAXLEVEL) level: SKIPLIST_MAXLEVEL;
}

skiplistNode * slInsert (skiplist * sl, double score) {
    skiplistNode * update [SKIPLIST_MAXLEVEL];
    skiplistNode * node;

    node = sl-> header;
    int i, level;
    for (i = sl-> level-1; i> = 0; i--) {
        while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
            node = node-> level [i] .forward;
        }
        update [i] = node;
    }
    level = slRandomLevel ();
    if (level> sl-> level) {
        for (i = sl-> level; i < level; i ++) {
            update [i] = sl-> header;
        }
        sl-> level = level;
    }
    node = slCreateNode (level, score);
    for (i = 0; i < level; i ++) {
        node-> level [i] .forward = update [i] -> level [i] .forward;
        update [i] -> level [i] .forward = node;
    }

    node-> backward = (update [0] == sl-> header NULL:? update [0]);
    if (node-> level [0] .forward)
        node-> level [0] .forward-> backward = node;
    else
        sl-> tail = node;
    sl-> length ++;
    return node;
}

void slDeleteNode (skiplist * sl, skiplistNode * x, skiplistNode ** update) {
    int i;
    for (i = 0; i < sl-> level; i ++) {
        if (update [i] -> level [i] .forward == x) {
            update [i] -> level [i] .forward = x-> level [i] .forward;
        }
    }
    if (x-> level [0] .forward) {
        x-> level [0] .forward-> backward = x-> backward;
    } Else {
        sl-> tail = x-> backward;
    }
    while (sl-> level> 1 && sl-> header-> level [sl-> level-1] .forward == NULL)
        sl-> level--;
    sl-> length--;
}

int slDelete (skiplist * sl, double score) {
    skiplistNode * update [SKIPLIST_MAXLEVEL], * node;
    int i;

    node = sl-> header;
    for (i = sl-> level-1; i> = 0; i--) {
        while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
            node = node-> level [i] .forward;
        }
        update [i] = node;
    }
    node = node-> level [0] .forward;
    if (node && score == node-> score) {
        slDeleteNode (sl, node, update);
        slFreeNode (node);
        return 1;
    } Else {
        return 0;
    }
    return 0;
}

int slSearch (skiplist * sl, double score) {
    skiplistNode * node;
    int i;

    node = sl-> header;
    for (i = sl-> level-1; i> = 0; i--) {
        while (node-> level [i] .forward && node-> level [i] .forward-> score < score) {
            node = node-> level [i] .forward;
        }
    }
    node = node-> level [0] .forward;
    if (node && score == node-> score) {
        printf ( "Found% d \ n", (int) node-> score);
        return 1;
    } Else {
        printf ( "Not found% d \ n", (int) score);
        return 0;
    }
}

void slPrint (skiplist * sl) {
    skiplistNode * node;
    int i;
    for (i = 0; i < SKIPLIST_MAXLEVEL; i ++) {
        printf ( "LEVEL [% d]:", i);
        node = sl-> header-> level [i] .forward;
        while (node) {
            printf ( "% d ->", (int) (node-> score));
            node = node-> level [i] .forward;
        }
        printf ( "NULL \ n");
    }
}

#ifdef SKIP_LIST_TEST_MAIN
int main () {
    srand ((unsigned) time (0));
    int count = 20, i;

    printf ( "### Function Test ### \ n");

    printf ( "=== Init Skip List === \ n");
    skiplist * sl = slCreate ();
    for (i = 0; i < count; i ++) {
        slInsert (sl, i);
    }
    printf ( "=== Print Skip List === \ n");
    slPrint (sl);

    printf ( "=== Search Skip List === \ n");
    for (i = 0; i < count; i ++) {
        int value = rand ()% (count + 10);
        slSearch (sl, value);
    }
    printf ( "=== Delete Skip List === \ n");
    for (i = 0; i < count + 10; i + = 2) {
        printf ( "Delete [% d]:% s \ n", i, slDelete (sl, i) "SUCCESS":? "NOT FOUND");
    }
    slPrint (sl);

    slFree (sl);
    sl = NULL;
}
#endif

Test results are as follows:

### Function Test ###
=== Init Skip List ===
=== Print Skip List ===
LEVEL [0]: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
LEVEL [1]: 0 -> 2 -> 4 -> 7 -> 9 -> 10 -> 11 -> 12 -> 14 -> 15 -> 17 -> 18 -> NULL
LEVEL [2]: 7 -> 10 -> 12 -> 14 -> 15 -> NULL
LEVEL [3]: 10 -> 14 -> 15 -> NULL
LEVEL [4]: 10 -> 14 -> NULL
LEVEL [5]: NULL
LEVEL [6]: NULL
LEVEL [7]: NULL
=== Search Skip List ===
Found 1
Found 18
Not found 21
Not found 24
Found 10
Not found 20
Found 14
Found 10
Found 19
Found 18
Not found 27
Found 5
Found 0
Found 0
Found 18
Not found 26
Found 13
Not found 28
Not found 29
Not found 23
=== Delete Skip List ===
Delete [0]: SUCCESS
Delete [2]: SUCCESS
Delete [4]: SUCCESS
Delete [6]: SUCCESS
Delete [8]: SUCCESS
Delete [10]: SUCCESS
Delete [12]: SUCCESS
Delete [14]: SUCCESS
Delete [16]: SUCCESS
Delete [18]: SUCCESS
Delete [20]: NOT FOUND
Delete [22]: NOT FOUND
Delete [24]: NOT FOUND
Delete [26]: NOT FOUND
Delete [28]: NOT FOUND
LEVEL [0]: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> NULL
LEVEL [1]: 7 -> 9 -> 11 -> 15 -> 17 -> NULL
LEVEL [2]: 7 -> 15 -> NULL
LEVEL [3]: 15 -> NULL
LEVEL [4]: NULL
LEVEL [5]: NULL
LEVEL [6]: NULL
LEVEL [7]: NULL
     
         
         
         
  More:      
 
- Install Apache streaming media services on CentOS 6.4 (Server)
- The most concise explanation of JavaScript closures (Programming)
- Nginx multi-domain certificate HTTPS (Server)
- Source code to compile and install MySQL 5.7.9 (Database)
- Linux process or thread is bound to a CPU (Programming)
- Ubuntu install Vendetta Online 14.04 (Linux)
- How to use the character in C ++ without pressing the Enter key to enter the Show (Programming)
- Use ldap implement Windows Remote Desktop Ubuntu Linux (Linux)
- C # dynamic class notes --- (Dynamic) Applications (Programming)
- Linux regex awk Comments (Linux)
- How to manage Vim plugin (Linux)
- MySQL IO SSD attempt at optimization (Database)
- How to publish projects to the Jcenter repository using Gradle in Android Studio (Programming)
- Detailed Linux network security policies and protection measures (Linux)
- Linux system security configuration Collection (Linux)
- Linux itself disguised illusion strengthen security (Linux)
- Redis-2.8.17 installation and configuration process some errors (Linux)
- Linux iptables firewall settings whitelist (RHEL 6 and CentOS 7) (Linux)
- How Bluetooth turned off by default in Ubuntu 14.04 (Linux)
- Single list summarizes the basic operation (Programming)
     
           
     
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.