redis源码阅读之intset

点击( 此处 )折叠或打开

1. typedef struct intset {
2.     uint32_t encoding ; / / 编码规则，具体见下面三个宏定义
3.     uint32_t length ; / / 所存元素个数
4.     int8_t contents [ ] ; / / 元素存储位置
5. } intset ;
6. #define INTSET_ENC_INT16 ( sizeof ( int16_t ) )
7. #define INTSET_ENC_INT32 ( sizeof ( int32_t ) )
8. #define INTSET_ENC_INT64 ( sizeof ( int64_t ) )

点击( 此处 )折叠或打开

1. / * Insert an integer in the intset * /
2. intset * intsetAdd ( intset * is , int64_t value , uint8_t * success ) {
3.     uint8_t valenc = _intsetValueEncoding ( value ) ;
4.     uint32_t pos ;
5.      if ( success ) * success = 1 ;
7.      / * Upgrade encoding if necessary . If we need to upgrade , we know that
8.       * this value should be either appended ( if > 0 ) or prepended ( if < 0 ) ,
9.       * because it lies outside the range of existing values . * /
10.      if ( valenc > intrev32ifbe ( is - > encoding ) ) {
11.          / * This always succeeds , so we don ' t need to curry * success . * /
12.         return intsetUpgradeAndAdd ( is , value ) ;
13.      } else {
14.          / * Abort if the value is already present in the set .
15.           * This call will populate "pos" with the right position to insert
16.           * the value when it cannot be found . * /
17.          if ( intsetSearch ( is , value , & pos ) ) {
18.              if ( success ) * success = 0 ;
19.             return is ;
20.          }
22.          is = intsetResize ( is , intrev32ifbe ( is - > length ) + 1 ) ;
23.          if ( pos < intrev32ifbe ( is - > length ) ) intsetMoveTail ( is , pos , pos + 1 ) ;
24.      }
26.     _intsetSet ( is , pos , value ) ;
27.      is - > length = intrev32ifbe ( intrev32ifbe ( is - > length ) + 1 ) ;
28.     return is ;
29. }

点击( 此处 )折叠或打开

1. / * Upgrades the intset to a larger encoding and inserts the given integer . * /
2. static intset * intsetUpgradeAndAdd ( intset * is , int64_t value ) {
3.     uint8_t curenc = intrev32ifbe ( is - > encoding ) ;
4.     uint8_t newenc = _intsetValueEncoding ( value ) ;
5.      int length = intrev32ifbe ( is - > length ) ;
6.      int prepend = value < 0 ? 1 : 0 ;
8.      / * First set new encoding and resize * /
9.      is - > encoding = intrev32ifbe ( newenc ) ;
10.      is = intsetResize ( is , intrev32ifbe ( is - > length ) + 1 ) ;
12.      / * Upgrade back - to - front so we don ' t overwrite values .
13.       * Note that the "prepend" variable is used to make sure we have an empty
14.       * space at either the beginning or the end of the intset .  
15.      * 通俗的将就是对新插入的元素，我们应该插在头部还是插在尾部 * /
16.      while ( length - - )
17.         _intsetSet ( is , length + prepend , _intsetGetEncoded ( is , length , curenc ) ) ;
19.      / * Set the value at the beginning or the end . * /
20.      if ( prepend )
21.         _intsetSet ( is , 0 , value ) ;
22.      else
23.         _intsetSet ( is , intrev32ifbe ( is - > length ) , value ) ;
24.      is - > length = intrev32ifbe ( intrev32ifbe ( is - > length ) + 1 ) ;
25.     return is ;
26. }

点击( 此处 )折叠或打开

1. / * Delete integer from intset * /
2. intset * intsetRemove ( intset * is , int64_t value , int * success ) {
3.     uint8_t valenc = _intsetValueEncoding ( value ) ;
4.     uint32_t pos ;
5.      if ( success ) * success = 0 ;
7.      if ( valenc < = intrev32ifbe ( is - > encoding ) & & intsetSearch ( is , value , & pos ) ) {
8.         uint32_t len = intrev32ifbe ( is - > length ) ;
10.          / * We know we can delete * /
11.          if ( success ) * success = 1 ;
13.          / * Overwrite value with tail and update length * /
14.          if ( pos < ( len - 1 ) ) intsetMoveTail ( is , pos + 1 , pos ) ;
15.          is = intsetResize ( is , len - 1 ) ;
16.          is - > length = intrev32ifbe ( len - 1 ) ;
17.      }
18.     return is ;
19. }