Redis之跳表源码阅读

typedef char *sds; //sds.h

/* ZSETs use a specialized version of Skiplists */
  typedef struct zskiplistNode {
      sds ele; 
      double score;
      struct zskiplistNode *backward;                                                                                                
      struct zskiplistLevel {
          struct zskiplistNode *forward;
          unsigned long span;
      } level[];
  } zskiplistNode;
  
  typedef struct zskiplist {
      struct zskiplistNode *header, *tail;
      unsigned long length;
      int level;
  } zskiplist;

  /* Create a new skiplist. */
  zskiplist *zslCreate(void) {
      int j;
      zskiplist *zsl;
  
      zsl = zmalloc(sizeof(*zsl));
      zsl->level = 1; 
      zsl->length = 0; 
      zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
      for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
          zsl->header->level[j].forward = NULL;
          zsl->header->level[j].span = 0; 
      }    
      zsl->header->backward = NULL;                                                                                                  
      zsl->tail = NULL;
      return zsl; 
  }

//看一下zmalloc
static void (*zmalloc_oom_handler)(size_t) = zmalloc_default_oom;
void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);

    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}
//看一下zmalloc_default_oom
static void zmalloc_default_oom(size_t size) {
    fprintf(stderr, "zmalloc: Out of memory trying to allocate %zu bytes\n",
        size);
    fflush(stderr);
    abort();
}

  /* Create a skiplist node with the specified number of levels.
   * The SDS string 'ele' is referenced by the node after the call. */
  zskiplistNode *zslCreateNode(int level, double score, sds ele) {                                                                   
      zskiplistNode *zn =
          zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
      zn->score = score;
      zn->ele = ele;
      return zn;
  }

/* Free the specified skiplist node. The referenced SDS string representation
   * of the element is freed too, unless node->ele is set to NULL before calling
   * this function. */
  void zslFreeNode(zskiplistNode *node) {
      sdsfree(node->ele);
      zfree(node);
  }
//跟进一下sdsfree函数
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}
//再跟进一下s_free函数
#define s_free zfree
//竟然是个宏定义？算了继续跟进zfree函数
void zfree(void *ptr) {                                                                                                              
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
    size_t oldsize;
#endif

    if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_free(zmalloc_size(ptr));
    free(ptr);
#else     
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    free(realptr);
#endif
}
//不跟了，太多调用关系了

  /* Free a whole skiplist. */                                                                                                       
  void zslFree(zskiplist *zsl) {
      zskiplistNode *node = zsl->header->level[0].forward, *next;
  
      zfree(zsl->header);
      while(node) {
          next = node->level[0].forward;
          zslFreeNode(node);
          node = next;
      }
      zfree(zsl);
  }
//可以看到先通过头结点得到第一个结点，然后头结点就没用了，直接销毁
//然后就是利用最低级指针遍历所有结点，
//通过销毁节点函数一一销毁
//最后是zfree掉 跳表这个变量

/* Insert a new node in the skiplist. Assumes the element does not already
   * exist (up to the caller to enforce that). The skiplist takes ownership
   * of the passed SDS string 'ele'. */
  zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
      zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
      unsigned int rank[ZSKIPLIST_MAXLEVEL];
      int i, level;
  
      serverAssert(!isnan(score));
      x = zsl->header;
      for (i = zsl->level-1; i >= 0; i--) {
          /* store rank that is crossed to reach the insert position */
          rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
          while (x->level[i].forward &&
                  (x->level[i].forward->score < score ||
                      (x->level[i].forward->score == score &&
                      sdscmp(x->level[i].forward->ele,ele) < 0)))
          {
              rank[i] += x->level[i].span;
              x = x->level[i].forward;
          }
          update[i] = x;
      }
      /* we assume the element is not already inside, since we allow duplicated
       * scores, reinserting the same element should never happen since the
       * caller of zslInsert() should test in the hash table if the element is
       * already inside or not. */
      level = zslRandomLevel();
      if (level > zsl->level) {
          for (i = zsl->level; i < level; i++) {
              rank[i] = 0;
              update[i] = zsl->header;
              update[i]->level[i].span = zsl->length;
          }
          zsl->level = level;
      }
      x = zslCreateNode(level,score,ele);
      for (i = 0; i < level; i++) {
          x->level[i].forward = update[i]->level[i].forward;
          update[i]->level[i].forward = x;
  
          /* update span covered by update[i] as x is inserted here */
          x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
          update[i]->level[i].span = (rank[0] - rank[i]) + 1;
      }
  
      /* increment span for untouched levels */
      for (i = level; i < zsl->level; i++) {
          update[i]->level[i].span++;
      }
  
      x->backward = (update[0] == zsl->header) ? NULL : update[0];
      if (x->level[0].forward)
          x->level[0].forward->backward = x;
      else
          zsl->tail = x;
      zsl->length++;
      return x;
  }

  /* Returns a random level for the new skiplist node we are going to create.
   * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
   * (both inclusive), with a powerlaw-alike distribution where higher
   * levels are less likely to be returned. */
  int zslRandomLevel(void) {
      int level = 1;
      while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
          level += 1;
      return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
  }