redis數(shù)據(jù)結(jié)構(gòu)之intset的實(shí)例詳解

typedef struct intset {
  
  // 編碼方式
  uint32_t encoding;

  // 集合包含的元素?cái)?shù)量
  uint32_t length;

  // 保存元素的數(shù)組
  int8_t contents[];

} intset;

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
  int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
  int64_t cur = -1;

  /* The value can never be found when the set is empty */
  // 處理 is 為空時(shí)的情況
  if (intrev32ifbe(is->length) == 0) {
    if (pos) *pos = 0;
    return 0;
  } else {
    /* Check for the case where we know we cannot find the value,
     * but do know the insert position. */
    // 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最后一個(gè)值都要大
    // 那么 value 肯定不存在于集合中，
    // 并且應(yīng)該將 value 添加到底層數(shù)組的最末端
    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
      if (pos) *pos = intrev32ifbe(is->length);
      return 0;
    // 因?yàn)榈讓訑?shù)組是有序的，如果 value 比數(shù)組中最前一個(gè)值都要小
    // 那么 value 肯定不存在于集合中，
    // 并且應(yīng)該將它添加到底層數(shù)組的最前端
    } else if (value  _intsetGet(is,0)) {
      if (pos) *pos = 0;
      return 0;
    }
  }

  // 在有序數(shù)組中進(jìn)行二分查找
  // T = O(log N)
  while(max >= min) {
    mid = (min+max)/2;
    cur = _intsetGet(is,mid);
    if (value > cur) {
      min = mid+1;
    } else if (value  cur) {
      max = mid-1;
    } else {
      break;
    }
  }

  // 檢查是否已經(jīng)找到了 value
  if (value == cur) {
    if (pos) *pos = mid;
    return 1;
  } else {
    if (pos) *pos = min;
    return 0;
  }
}