C语言SkipList实现访问复杂度意外呈线性，求问题排查

我在部分程序中使用自研库提供的SkipList，近期发现其性能低于预期，于是编写了以下测试程序进行分析：

#include "usflib2.h"
#include <stdio.h>
#include <time.h>

uint64_t test(uint64_t);

int main() {
    uint64_t i, j, avg = 0;

    srand(time(NULL));
    printf("WARN: The skiplist must be made to return number of steps on access for this test to work.\n");

    for (i = 2; i < 10000000; i *= 2) {
        for (j = 0; j < 100; j++) {
            avg += test(i);
        }   

        printf("(%lu, %lu)\n", i, avg/100);
        fflush(stdout);
    }   
    return 0;
}

uint64_t test(uint64_t cycles) {
    uint64_t i;

    usf_skiplist *skp;
    skp = usf_skset(NULL, 0, USFNULL);

    for (i = 0; i < cycles; i++) {
        usf_skset(skp, i, USFDATAU(i));
    }   

    i = usf_skget(skp, i/2).u;

    /* Cleanup */
    usf_freesk(skp);

    return i;
}

测试结果显示，访问中间元素时时间复杂度呈线性增长（可视化后趋势明显）。

我多次检查仍未找到问题所在，怀疑是对SkipList的理解存在偏差。现将usf_skset()、usf_skget()的实现代码及头文件附上，请求协助排查问题：

usf_skset()实现 #

usf_skiplist *usf_skset(usf_skiplist *skiplist, uint64_t i, usf_data data) {
    int j;
    usf_skipnode *node, *next, **ptrs;
    usf_skipnode *position[USF_SKIPLIST_HEADSIZE];

    if (skiplist == NULL) { //创建跳表
        //分配跳表内存
        skiplist = malloc(sizeof(usf_skiplist));
        skiplist -> size = 1; //基础节点数

        node = malloc(sizeof(usf_skipnode)); //头节点

        //分配头节点的指针数组
        node -> nextnodes = calloc(sizeof(usf_skipnode **), USF_SKIPLIST_HEADSIZE);

        //设置基础数据
        node -> index = 0;
        node -> data = USFNULL;

        skiplist -> head = node;
    }

    //在跳表的索引i处插入数据
    node = skiplist -> head; //从头节点开始

    for (j = USF_SKIPLIST_HEADSIZE - 1; j >= 0; j--) {
        next = node -> nextnodes[j];

        while (next && next -> index <= i) {
            node = next;
            next = node -> nextnodes[j];
        }

        //记录当前层的停留位置
        position[j] = node;
    }

    if (node -> index == i) {
        //元素已存在，更新数据
        node -> data = data;
        return skiplist;
    }

    //创建并链接新节点
    node = malloc(sizeof(usf_skipnode));
    node -> index = i;
    node -> data = data;

    //随机决定新节点的层数
    for (j = 1; j < USF_SKIPLIST_HEADSIZE; j++)
        if (rand() & 1) break; //概率性终止层数提升

    ptrs = malloc(sizeof(usf_skipnode *) * j);

    for (j--; j >= 0; j--) {
        ptrs[j] = position[j] -> nextnodes[j]; //链接到下一个节点
        position[j] -> nextnodes[j] = node; //将前一个节点指向当前新节点
    }

    node -> nextnodes = ptrs;
    skiplist -> size++; //元素计数加1
    return skiplist;
}

usf_skget()实现（已修改为返回访问步数） #

usf_data usf_skget(usf_skiplist *skiplist, uint64_t i) {
    uint64_t TEMP = 0; /* 临时变量：统计访问步数 */

    int j;
    usf_skipnode *node, *next;

    node = skiplist -> head;

    for (j = USF_SKIPLIST_HEADSIZE - 1; j >= 0; j--) {
        next = node -> nextnodes[j];

        while (next && next -> index <= i) {
            TEMP++; /* 统计步数 */

            /* 循环展开：每次循环处理两次迭代 */
            node = next;
            if ((next = node -> nextnodes[j]) == NULL || next -> index > i) break;

            node = next;
            next = node -> nextnodes[j];
        }

        if (node -> index == i) break;
    }

    return USFDATAU(TEMP); /* 临时返回步数 */
    if (node -> index != i) return USFNULL;

    return node -> data;
}

头文件usfskiplist.h #

#ifndef USFSKIPLIST_H
#define USFSKIPLIST_H

#include <stdlib.h>
#include "usfdata.h"

#define USF_SKIPLIST_HEADSIZE 24

typedef struct usf_skipnode {
    struct usf_skipnode **nextnodes;
    usf_data data;
    uint64_t index;
} usf_skipnode;

typedef struct usf_skiplist {
    usf_skipnode *head;
    uint64_t size;
} usf_skiplist;

usf_skiplist *usf_skset(usf_skiplist *, uint64_t, usf_data);
usf_data usf_skget(usf_skiplist *, uint64_t);
usf_data usf_skdel(usf_skiplist *, uint64_t);
void usf_freesk(usf_skiplist *); 

#endif

内容的提问来源于stack exchange，提问作者lzg