\u672c\u7ae0\u6765\u770b\u8df3\u8dc3\u8868<\/p>\n\n\n\n
#define ZSKIPLIST_MAXLEVEL 32 \/\/ \u8df3\u8dc3\u8868\u6700\u5927\u5c42\u6570\n\n\/\/ \u8df3\u8868\u7ed3\u6784\u4f53\ntypedef struct zskiplist\n{\n struct zskiplistNode *header, *tail; \/\/ \u5934\u8282\u70b9,\u5c3e\u8282\u70b9\n unsigned long length; \/\/ \u8282\u70b9\u6570\u91cf\n int level; \/\/\u6700\u5927\u5c42\u6570\n} zskiplist;\n\n\/\/ \u8df3\u8868\u4e00\u4e2a\u8282\u70b9\u7684\u7ed3\u6784\u4f53\ntypedef struct zskiplistNode\n{\n robj *obj; \/\/ \u6210\u5458\u5bf9\u8c61\n double score; \/\/ \u5206\u6570\n struct zskiplistNode *backward; \/\/ \u540e\u9000\u6307\u9488\n struct zskiplistLevel \/\/ \u6bcf\u4e00\u5c42\u7684\u7ed3\u6784\n {\n struct zskiplistNode *forward; \/\/ \u524d\u8fdb\u6307\u9488\n unsigned int span; \/\/ \u8be5\u5c42\u8de8\u8d8a\u7684\u8282\u70b9\u6570\u91cf\n } level[];\n} zskiplistNode;\n\n\/\/ \u521b\u5efa\u4e00\u4e2a\u8df3\u8868 \/\/ \u6700\u574f O(1)\nzskiplist *zslCreate(void)\n{\n int j;\n zskiplist *zsl;\n zsl = zmalloc(sizeof(*zsl));\n zsl->level = 1; \/\/ \u521d\u59cb\u5c42\u6570?\n zsl->length = 0; \/\/ \u6709\u591a\u5c11\u4e2a\u6570\u636e\u8282\u70b9?\n zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, NULL); \/\/ \u521d\u59cb\u5316\u8868\u5934\u8282\u70b9\n for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++)\n {\n zsl->header->level[j].forward = NULL;\n zsl->header->level[j].span = 0;\n }\n zsl->header->backward = NULL;\n \/\/ \u8bbe\u7f6e\u8868\u5c3e\n zsl->tail = NULL;\n return zsl;\n}\n\n\/\/\u521b\u5efa\u4e00\u4e2a\u8df3\u8dc3\u8868\u7684\u7ed3\u70b9 \/\/\u6700\u574f O(1)\nzskiplistNode *zslCreateNode(int level, double score, robj *obj)\n{\n \/\/ \u5206\u914d\u7a7a\u95f4\n zskiplistNode *zn = zmalloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));\n\n \/\/ \u8bbe\u7f6e\u5c5e\u6027\n zn->score = score;\n zn->obj = obj;\n\n return zn;\n}\n\n\/\/ \u63d2\u5165\u4e00\u4e2a\u8282\u70b9 \/\/\u6700\u574f O(N) \u5e73\u5747 O(logN)\nzskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj)\n{\n \/\/ update \u6bcf\u4e00\u5c42\u8981\u66f4\u65b0\u7684\u4f4d\u7f6e\u7684\u8282\u70b9\n zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;\n unsigned int rank[ZSKIPLIST_MAXLEVEL];\n int i, level;\n redisAssert(!isnan(score));\n x = zsl->header;\n for (i = zsl->level - 1; i >= 0; i--)\n {\n \/* store rank that is crossed to reach the insert position *\/\n rank[i] = i == (zsl->level - 1) ? 0 : rank[i + 1];\n \/\/ \u6cbf\u7740\u524d\u8fdb\u6307\u9488\u904d\u5386\u8df3\u8dc3\u8868\n while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && compareStringObjects(x->level[i].forward->obj, obj) < 0)))\n {\n \/\/ \u8bb0\u5f55\u6cbf\u9014\u8de8\u8d8a\u4e86\u591a\u5c11\u4e2a\u8282\u70b9\n rank[i] += x->level[i].span;\n x = x->level[i].forward;\n }\n \/\/ \u8bb0\u5f55\u5c06\u8981\u548c\u65b0\u8282\u70b9\u76f8\u8fde\u63a5\u7684\u8282\u70b9\n update[i] = x;\n }\n \/\/ \u83b7\u53d6\u4e00\u4e2a\u968f\u673a\u503c\u4f5c\u4e3a\u65b0\u8282\u70b9\u7684\u5c42\u6570\n level = zslRandomLevel();\n\n \/\/ \u5982\u679c\u65b0\u8282\u70b9\u7684\u5c42\u6570\u6bd4\u8868\u4e2d\u5176\u4ed6\u8282\u70b9\u7684\u5c42\u6570\u90fd\u8981\u5927\n \/\/ \u90a3\u4e48\u521d\u59cb\u5316\u8868\u5934\u8282\u70b9\u4e2d\u672a\u4f7f\u7528\u7684\u5c42\uff0c\u5e76\u5c06\u5b83\u4eec\u8bb0\u5f55\u5230 update \u6570\u7ec4\u4e2d\n \/\/ \u5c06\u6765\u4e5f\u6307\u5411\u65b0\u8282\u70b9\n if (level > zsl->level)\n {\n\n \/\/ \u521d\u59cb\u5316\u672a\u4f7f\u7528\u5c42\n for (i = zsl->level; i < level; i++)\n {\n rank[i] = 0;\n update[i] = zsl->header;\n update[i]->level[i].span = zsl->length;\n }\n\n \/\/ \u66f4\u65b0\u8868\u4e2d\u8282\u70b9\u6700\u5927\u5c42\u6570\n zsl->level = level;\n }\n\n \/\/ \u521b\u5efa\u65b0\u8282\u70b9\n x = zslCreateNode(level, score, obj);\n\n \/\/ \u5c06\u524d\u9762\u8bb0\u5f55\u7684\u6307\u9488\u6307\u5411\u65b0\u8282\u70b9\uff0c\u5e76\u505a\u76f8\u5e94\u7684\u8bbe\u7f6e\n for (i = 0; i < level; i++)\n {\n \/\/ \u8bbe\u7f6e\u65b0\u8282\u70b9\u7684 forward \u6307\u9488\n x->level[i].forward = update[i]->level[i].forward;\n\n \/\/ \u5c06\u6cbf\u9014\u8bb0\u5f55\u7684\u5404\u4e2a\u8282\u70b9\u7684 forward \u6307\u9488\u6307\u5411\u65b0\u8282\u70b9\n update[i]->level[i].forward = x;\n\n \/* update span covered by update[i] as x is inserted here *\/\n \/\/ \u8ba1\u7b97\u65b0\u8282\u70b9\u8de8\u8d8a\u7684\u8282\u70b9\u6570\u91cf\n x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);\n\n \/\/ \u66f4\u65b0\u65b0\u8282\u70b9\u63d2\u5165\u4e4b\u540e\uff0c\u6cbf\u9014\u8282\u70b9\u7684 span \u503c\n \/\/ \u5176\u4e2d\u7684 +1 \u8ba1\u7b97\u7684\u662f\u65b0\u8282\u70b9\n update[i]->level[i].span = (rank[0] - rank[i]) + 1;\n }\n\n \/* increment span for untouched levels *\/\n \/\/ \u672a\u63a5\u89e6\u7684\u8282\u70b9\u7684 span \u503c\u4e5f\u9700\u8981\u589e\u4e00\uff0c\u8fd9\u4e9b\u8282\u70b9\u76f4\u63a5\u4ece\u8868\u5934\u6307\u5411\u65b0\u8282\u70b9\n for (i = level; i < zsl->level; i++)\n {\n update[i]->level[i].span++;\n }\n\n \/\/ \u8bbe\u7f6e\u65b0\u8282\u70b9\u7684\u540e\u9000\u6307\u9488\n x->backward = (update[0] == zsl->header) ? NULL : update[0];\n if (x->level[0].forward)\n x->level[0].forward->backward = x;\n else\n zsl->tail = x;\n\n \/\/ \u8df3\u8dc3\u8868\u7684\u8282\u70b9\u8ba1\u6570\u589e\u4e00\n zsl->length++;\n\n return x;\n}\n\n\/\/ \u5220\u9664\u7ed9\u5b9a\u7684\u8df3\u8dc3\u8868\u8282\u70b9 \u6700\u574f O(N)\nvoid zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update)\n{\n int i;\n\n \/\/ \u66f4\u65b0\u6240\u6709\u548c\u88ab\u5220\u9664\u8282\u70b9 x \u6709\u5173\u7684\u8282\u70b9\u7684\u6307\u9488\uff0c\u89e3\u9664\u5b83\u4eec\u4e4b\u95f4\u7684\u5173\u7cfb\n for (i = 0; i < zsl->level; i++)\n {\n if (update[i]->level[i].forward == x)\n {\n update[i]->level[i].span += x->level[i].span - 1;\n update[i]->level[i].forward = x->level[i].forward;\n }\n else\n {\n update[i]->level[i].span -= 1;\n }\n }\n\n \/\/ \u66f4\u65b0\u88ab\u5220\u9664\u8282\u70b9 x \u7684\u524d\u8fdb\u548c\u540e\u9000\u6307\u9488\n if (x->level[0].forward)\n {\n x->level[0].forward->backward = x->backward;\n }\n else\n {\n zsl->tail = x->backward;\n }\n\n \/\/ \u66f4\u65b0\u8df3\u8dc3\u8868\u6700\u5927\u5c42\u6570\uff08\u53ea\u5728\u88ab\u5220\u9664\u8282\u70b9\u662f\u8df3\u8dc3\u8868\u4e2d\u6700\u9ad8\u7684\u8282\u70b9\u65f6\u624d\u6267\u884c\uff09\n while (zsl->level > 1 && zsl->header->level[zsl->level - 1].forward == NULL)\n zsl->level--;\n\n \/\/ \u8df3\u8dc3\u8868\u8282\u70b9\u8ba1\u6570\u5668\u51cf\u4e00\n zsl->length--;\n}\n\n\/* Find the rank for an element by both score and key.\n * Returns 0 when the element cannot be found, rank otherwise.\n * Note that the rank is 1-based due to the span of zsl->header to the\n * first element. \n *\n * T_wrost = O(N), T_avg = O(log N)\n *\/\nunsigned long zslGetRank(zskiplist *zsl, double score, robj *o)\n{\n zskiplistNode *x;\n unsigned long rank = 0;\n int i;\n\n \/\/ \u904d\u5386\u6574\u4e2a\u8df3\u8dc3\u8868\n x = zsl->header;\n for (i = zsl->level - 1; i >= 0; i--)\n {\n\n \/\/ \u904d\u5386\u8282\u70b9\u5e76\u5bf9\u6bd4\u5143\u7d20\n while (x->level[i].forward &&\n (x->level[i].forward->score < score ||\n \/\/ \u6bd4\u5bf9\u5206\u503c\n (x->level[i].forward->score == score &&\n \/\/ \u6bd4\u5bf9\u6210\u5458\u5bf9\u8c61\n compareStringObjects(x->level[i].forward->obj, o) <= 0)))\n {\n\n \/\/ \u7d2f\u79ef\u8de8\u8d8a\u7684\u8282\u70b9\u6570\u91cf\n rank += x->level[i].span;\n\n \/\/ \u6cbf\u7740\u524d\u8fdb\u6307\u9488\u904d\u5386\u8df3\u8dc3\u8868\n x = x->level[i].forward;\n }\n\n \/* x might be equal to zsl->header, so test if obj is non-NULL *\/\n \/\/ \u5fc5\u987b\u786e\u4fdd\u4e0d\u4ec5\u5206\u503c\u76f8\u7b49\uff0c\u800c\u4e14\u6210\u5458\u5bf9\u8c61\u4e5f\u8981\u76f8\u7b49\n \/\/ T = O(N)\n if (x->obj && equalStringObjects(x->obj, o))\n {\n return rank;\n }\n }\n\n \/\/ \u6ca1\u627e\u5230\n return 0;\n}<\/code><\/pre>\n\n\n\n\u57fa\u4e8e\u7248\u672c3.0.0\u7248\u672c,<\/a>\u70b9\u51fb\u4e0b\u8f7dhttps:\/\/download.redis.io\/releases\/redis-3.0.0.tar.gz<\/p>\n\n\n\n