关键词搜索

源码搜索 ×
×

漫话Redis源码之五十三

发布2022-01-09浏览541次

详情内容

这里主要讲一些列的字符串序列化，其实很简单。

  1. /* Listpack -- A lists of strings serialization format
  2.  *
  3.  * This file implements the specification you can find at:
  4.  *
  5.  *  https://github.com/antirez/listpack
  6.  *
  7.  * Copyright (c) 2017, Salvatore Sanfilippo <antirez at gmail dot com>
  8.  * Copyright (c) 2020, Redis Labs, Inc
  9.  * All rights reserved.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions are met:
  13.  *
  14.  *   * Redistributions of source code must retain the above copyright notice,
  15.  *     this list of conditions and the following disclaimer.
  16.  *   * Redistributions in binary form must reproduce the above copyright
  17.  *     notice, this list of conditions and the following disclaimer in the
  18.  *     documentation and/or other materials provided with the distribution.
  19.  *   * Neither the name of Redis nor the names of its contributors may be used
  20.  *     to endorse or promote products derived from this software without
  21.  *     specific prior written permission.
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  24.  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26.  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  27.  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  28.  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  29.  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  30.  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  31.  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  32.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33.  * POSSIBILITY OF SUCH DAMAGE.
  34.  */
  35.  
  36. #include <stdint.h>
  37. #include <limits.h>
  38. #include <sys/types.h>
  39. #include <stdlib.h>
  40. #include <string.h>
  41. #include <stdio.h>
  42.  
  43. #include "listpack.h"
  44. #include "listpack_malloc.h"
  45. #include "redisassert.h"
  46.  
  47. #define LP_HDR_SIZE 6       /* 32 bit total len + 16 bit number of elements. */
  48. #define LP_HDR_NUMELE_UNKNOWN UINT16_MAX
  49. #define LP_MAX_INT_ENCODING_LEN 9
  50. #define LP_MAX_BACKLEN_SIZE 5
  51. #define LP_MAX_ENTRY_BACKLEN 34359738367ULL
  52. #define LP_ENCODING_INT 0
  53. #define LP_ENCODING_STRING 1
  54.  
  55. #define LP_ENCODING_7BIT_UINT 0
  56. #define LP_ENCODING_7BIT_UINT_MASK 0x80
  57. #define LP_ENCODING_IS_7BIT_UINT(byte) (((byte)&LP_ENCODING_7BIT_UINT_MASK)==LP_ENCODING_7BIT_UINT)
  58.  
  59. #define LP_ENCODING_6BIT_STR 0x80
  60. #define LP_ENCODING_6BIT_STR_MASK 0xC0
  61. #define LP_ENCODING_IS_6BIT_STR(byte) (((byte)&LP_ENCODING_6BIT_STR_MASK)==LP_ENCODING_6BIT_STR)
  62.  
  63. #define LP_ENCODING_13BIT_INT 0xC0
  64. #define LP_ENCODING_13BIT_INT_MASK 0xE0
  65. #define LP_ENCODING_IS_13BIT_INT(byte) (((byte)&LP_ENCODING_13BIT_INT_MASK)==LP_ENCODING_13BIT_INT)
  66.  
  67. #define LP_ENCODING_12BIT_STR 0xE0
  68. #define LP_ENCODING_12BIT_STR_MASK 0xF0
  69. #define LP_ENCODING_IS_12BIT_STR(byte) (((byte)&LP_ENCODING_12BIT_STR_MASK)==LP_ENCODING_12BIT_STR)
  70.  
  71. #define LP_ENCODING_16BIT_INT 0xF1
  72. #define LP_ENCODING_16BIT_INT_MASK 0xFF
  73. #define LP_ENCODING_IS_16BIT_INT(byte) (((byte)&LP_ENCODING_16BIT_INT_MASK)==LP_ENCODING_16BIT_INT)
  74.  
  75. #define LP_ENCODING_24BIT_INT 0xF2
  76. #define LP_ENCODING_24BIT_INT_MASK 0xFF
  77. #define LP_ENCODING_IS_24BIT_INT(byte) (((byte)&LP_ENCODING_24BIT_INT_MASK)==LP_ENCODING_24BIT_INT)
  78.  
  79. #define LP_ENCODING_32BIT_INT 0xF3
  80. #define LP_ENCODING_32BIT_INT_MASK 0xFF
  81. #define LP_ENCODING_IS_32BIT_INT(byte) (((byte)&LP_ENCODING_32BIT_INT_MASK)==LP_ENCODING_32BIT_INT)
  82.  
  83. #define LP_ENCODING_64BIT_INT 0xF4
  84. #define LP_ENCODING_64BIT_INT_MASK 0xFF
  85. #define LP_ENCODING_IS_64BIT_INT(byte) (((byte)&LP_ENCODING_64BIT_INT_MASK)==LP_ENCODING_64BIT_INT)
  86.  
  87. #define LP_ENCODING_32BIT_STR 0xF0
  88. #define LP_ENCODING_32BIT_STR_MASK 0xFF
  89. #define LP_ENCODING_IS_32BIT_STR(byte) (((byte)&LP_ENCODING_32BIT_STR_MASK)==LP_ENCODING_32BIT_STR)
  90.  
  91. #define LP_EOF 0xFF
  92.  
  93. #define LP_ENCODING_6BIT_STR_LEN(p) ((p)[0] & 0x3F)
  94. #define LP_ENCODING_12BIT_STR_LEN(p) ((((p)[0] & 0xF) << 8) | (p)[1])
  95. #define LP_ENCODING_32BIT_STR_LEN(p) (((uint32_t)(p)[1]<<0) | \
  96.                                       ((uint32_t)(p)[2]<<8) | \
  97.                                       ((uint32_t)(p)[3]<<16) | \
  98.                                       ((uint32_t)(p)[4]<<24))
  99.  
  100. #define lpGetTotalBytes(p)           (((uint32_t)(p)[0]<<0) | \
  101.                                       ((uint32_t)(p)[1]<<8) | \
  102.                                       ((uint32_t)(p)[2]<<16) | \
  103.                                       ((uint32_t)(p)[3]<<24))
  104.  
  105. #define lpGetNumElements(p)          (((uint32_t)(p)[4]<<0) | \
  106.                                       ((uint32_t)(p)[5]<<8))
  107. #define lpSetTotalBytes(p,v) do { \
  108.     (p)[0] = (v)&0xff; \
  109.     (p)[1] = ((v)>>8)&0xff; \
  110.     (p)[2] = ((v)>>16)&0xff; \
  111.     (p)[3] = ((v)>>24)&0xff; \
  112. } while(0)
  113.  
  114. #define lpSetNumElements(p,v) do { \
  115.     (p)[4] = (v)&0xff; \
  116.     (p)[5] = ((v)>>8)&0xff; \
  117. } while(0)
  118.  
  119. /* Validates that 'p' is not ouside the listpack.
  120.  * All function that return a pointer to an element in the listpack will assert
  121.  * that this element is valid, so it can be freely used.
  122.  * Generally functions such lpNext and lpDelete assume the input pointer is
  123.  * already validated (since it's the return value of another function). */
  124. #define ASSERT_INTEGRITY(lp, p) do { \
  125.     assert((p) >= (lp)+LP_HDR_SIZE && (p) < (lp)+lpGetTotalBytes((lp))); \
  126. } while (0)
  127.  
  128. /* Similar to the above, but validates the entire element lenth rather than just
  129.  * it's pointer. */
  130. #define ASSERT_INTEGRITY_LEN(lp, p, len) do { \
  131.     assert((p) >= (lp)+LP_HDR_SIZE && (p)+(len) < (lp)+lpGetTotalBytes((lp))); \
  132. } while (0)
  133.  
  134. static inline void lpAssertValidEntry(unsigned char* lp, size_t lpbytes, unsigned char *p);
  135.  
  136. /* Convert a string into a signed 64 bit integer.
  137.  * The function returns 1 if the string could be parsed into a (non-overflowing)
  138.  * signed 64 bit int, 0 otherwise. The 'value' will be set to the parsed value
  139.  * when the function returns success.
  140.  *
  141.  * Note that this function demands that the string strictly represents
  142.  * a int64 value: no spaces or other characters before or after the string
  143.  * representing the number are accepted, nor zeroes at the start if not
  144.  * for the string "0" representing the zero number.
  145.  *
  146.  * Because of its strictness, it is safe to use this function to check if
  147.  * you can convert a string into a long long, and obtain back the string
  148.  * from the number without any loss in the string representation. *
  149.  *
  150.  * -----------------------------------------------------------------------------
  151.  *
  152.  * Credits: this function was adapted from the Redis source code, file
  153.  * "utils.c", function string2ll(), and is copyright:
  154.  *
  155.  * Copyright(C) 2011, Pieter Noordhuis
  156.  * Copyright(C) 2011, Salvatore Sanfilippo
  157.  *
  158.  * The function is released under the BSD 3-clause license.
  159.  */
  160. int lpStringToInt64(const char *s, unsigned long slen, int64_t *value) {
  161.     const char *p = s;
  162.     unsigned long plen = 0;
  163.     int negative = 0;
  164.     uint64_t v;
  165.  
  166.     if (plen == slen)
  167.         return 0;
  168.  
  169.     /* Special case: first and only digit is 0. */
  170.     if (slen == 1 && p[0] == '0') {
  171.         if (value != NULL) *value = 0;
  172.         return 1;
  173.     }
  174.  
  175.     if (p[0] == '-') {
  176.         negative = 1;
  177.         p++; plen++;
  178.  
  179.         /* Abort on only a negative sign. */
  180.         if (plen == slen)
  181.             return 0;
  182.     }
  183.  
  184.     /* First digit should be 1-9, otherwise the string should just be 0. */
  185.     if (p[0] >= '1' && p[0] <= '9') {
  186.         v = p[0]-'0';
  187.         p++; plen++;
  188.     } else if (p[0] == '0' && slen == 1) {
  189.         *value = 0;
  190.         return 1;
  191.     } else {
  192.         return 0;
  193.     }
  194.  
  195.     while (plen < slen && p[0] >= '0' && p[0] <= '9') {
  196.         if (v > (UINT64_MAX / 10)) /* Overflow. */
  197.             return 0;
  198.         v *= 10;
  199.  
  200.         if (v > (UINT64_MAX - (p[0]-'0'))) /* Overflow. */
  201.             return 0;
  202.         v += p[0]-'0';
  203.  
  204.         p++; plen++;
  205.     }
  206.  
  207.     /* Return if not all bytes were used. */
  208.     if (plen < slen)
  209.         return 0;
  210.  
  211.     if (negative) {
  212.         if (v > ((uint64_t)(-(INT64_MIN+1))+1)) /* Overflow. */
  213.             return 0;
  214.         if (value != NULL) *value = -v;
  215.     } else {
  216.         if (v > INT64_MAX) /* Overflow. */
  217.             return 0;
  218.         if (value != NULL) *value = v;
  219.     }
  220.     return 1;
  221. }
  222.  
  223. /* Create a new, empty listpack.
  224.  * On success the new listpack is returned, otherwise an error is returned.
  225.  * Pre-allocate at least `capacity` bytes of memory,
  226.  * over-allocated memory can be shrinked by `lpShrinkToFit`.
  227.  * */
  228. unsigned char *lpNew(size_t capacity) {
  229.     unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1);
  230.     if (lp == NULL) return NULL;
  231.     lpSetTotalBytes(lp,LP_HDR_SIZE+1);
  232.     lpSetNumElements(lp,0);
  233.     lp[LP_HDR_SIZE] = LP_EOF;
  234.     return lp;
  235. }
  236.  
  237. /* Free the specified listpack. */
  238. void lpFree(unsigned char *lp) {
  239.     lp_free(lp);
  240. }
  241.  
  242. /* Shrink the memory to fit. */
  243. unsigned char* lpShrinkToFit(unsigned char *lp) {
  244.     size_t size = lpGetTotalBytes(lp);
  245.     if (size < lp_malloc_size(lp)) {
  246.         return lp_realloc(lp, size);
  247.     } else {
  248.         return lp;
  249.     }
  250. }
  251.  
  252. /* Given an element 'ele' of size 'size', determine if the element can be
  253.  * represented inside the listpack encoded as integer, and returns
  254.  * LP_ENCODING_INT if so. Otherwise returns LP_ENCODING_STR if no integer
  255.  * encoding is possible.
  256.  *
  257.  * If the LP_ENCODING_INT is returned, the function stores the integer encoded
  258.  * representation of the element in the 'intenc' buffer.
  259.  *
  260.  * Regardless of the returned encoding, 'enclen' is populated by reference to
  261.  * the number of bytes that the string or integer encoded element will require
  262.  * in order to be represented. */
  263. int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, uint64_t *enclen) {
  264.     int64_t v;
  265.     if (lpStringToInt64((const char*)ele, size, &v)) {
  266.         if (v >= 0 && v <= 127) {
  267.             /* Single byte 0-127 integer. */
  268.             intenc[0] = v;
  269.             *enclen = 1;
  270.         } else if (v >= -4096 && v <= 4095) {
  271.             /* 13 bit integer. */
  272.             if (v < 0) v = ((int64_t)1<<13)+v;
  273.             intenc[0] = (v>>8)|LP_ENCODING_13BIT_INT;
  274.             intenc[1] = v&0xff;
  275.             *enclen = 2;
  276.         } else if (v >= -32768 && v <= 32767) {
  277.             /* 16 bit integer. */
  278.             if (v < 0) v = ((int64_t)1<<16)+v;
  279.             intenc[0] = LP_ENCODING_16BIT_INT;
  280.             intenc[1] = v&0xff;
  281.             intenc[2] = v>>8;
  282.             *enclen = 3;
  283.         } else if (v >= -8388608 && v <= 8388607) {
  284.             /* 24 bit integer. */
  285.             if (v < 0) v = ((int64_t)1<<24)+v;
  286.             intenc[0] = LP_ENCODING_24BIT_INT;
  287.             intenc[1] = v&0xff;
  288.             intenc[2] = (v>>8)&0xff;
  289.             intenc[3] = v>>16;
  290.             *enclen = 4;
  291.         } else if (v >= -2147483648 && v <= 2147483647) {
  292.             /* 32 bit integer. */
  293.             if (v < 0) v = ((int64_t)1<<32)+v;
  294.             intenc[0] = LP_ENCODING_32BIT_INT;
  295.             intenc[1] = v&0xff;
  296.             intenc[2] = (v>>8)&0xff;
  297.             intenc[3] = (v>>16)&0xff;
  298.             intenc[4] = v>>24;
  299.             *enclen = 5;
  300.         } else {
  301.             /* 64 bit integer. */
  302.             uint64_t uv = v;
  303.             intenc[0] = LP_ENCODING_64BIT_INT;
  304.             intenc[1] = uv&0xff;
  305.             intenc[2] = (uv>>8)&0xff;
  306.             intenc[3] = (uv>>16)&0xff;
  307.             intenc[4] = (uv>>24)&0xff;
  308.             intenc[5] = (uv>>32)&0xff;
  309.             intenc[6] = (uv>>40)&0xff;
  310.             intenc[7] = (uv>>48)&0xff;
  311.             intenc[8] = uv>>56;
  312.             *enclen = 9;
  313.         }
  314.         return LP_ENCODING_INT;
  315.     } else {
  316.         if (size < 64) *enclen = 1+size;
  317.         else if (size < 4096) *enclen = 2+size;
  318.         else *enclen = 5+(uint64_t)size;
  319.         return LP_ENCODING_STRING;
  320.     }
  321. }
  322.  
  323. /* Store a reverse-encoded variable length field, representing the length
  324.  * of the previous element of size 'l', in the target buffer 'buf'.
  325.  * The function returns the number of bytes used to encode it, from
  326.  * 1 to 5. If 'buf' is NULL the function just returns the number of bytes
  327.  * needed in order to encode the backlen. */
  328. unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) {
  329.     if (l <= 127) {
  330.         if (buf) buf[0] = l;
  331.         return 1;
  332.     } else if (l < 16383) {
  333.         if (buf) {
  334.             buf[0] = l>>7;
  335.             buf[1] = (l&127)|128;
  336.         }
  337.         return 2;
  338.     } else if (l < 2097151) {
  339.         if (buf) {
  340.             buf[0] = l>>14;
  341.             buf[1] = ((l>>7)&127)|128;
  342.             buf[2] = (l&127)|128;
  343.         }
  344.         return 3;
  345.     } else if (l < 268435455) {
  346.         if (buf) {
  347.             buf[0] = l>>21;
  348.             buf[1] = ((l>>14)&127)|128;
  349.             buf[2] = ((l>>7)&127)|128;
  350.             buf[3] = (l&127)|128;
  351.         }
  352.         return 4;
  353.     } else {
  354.         if (buf) {
  355.             buf[0] = l>>28;
  356.             buf[1] = ((l>>21)&127)|128;
  357.             buf[2] = ((l>>14)&127)|128;
  358.             buf[3] = ((l>>7)&127)|128;
  359.             buf[4] = (l&127)|128;
  360.         }
  361.         return 5;
  362.     }
  363. }
  364.  
  365. /* Decode the backlen and returns it. If the encoding looks invalid (more than
  366.  * 5 bytes are used), UINT64_MAX is returned to report the problem. */
  367. uint64_t lpDecodeBacklen(unsigned char *p) {
  368.     uint64_t val = 0;
  369.     uint64_t shift = 0;
  370.     do {
  371.         val |= (uint64_t)(p[0] & 127) << shift;
  372.         if (!(p[0] & 128)) break;
  373.         shift += 7;
  374.         p--;
  375.         if (shift > 28) return UINT64_MAX;
  376.     } while(1);
  377.     return val;
  378. }
  379.  
  380. /* Encode the string element pointed by 's' of size 'len' in the target
  381.  * buffer 's'. The function should be called with 'buf' having always enough
  382.  * space for encoding the string. This is done by calling lpEncodeGetType()
  383.  * before calling this function. */
  384. void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) {
  385.     if (len < 64) {
  386.         buf[0] = len | LP_ENCODING_6BIT_STR;
  387.         memcpy(buf+1,s,len);
  388.     } else if (len < 4096) {
  389.         buf[0] = (len >> 8) | LP_ENCODING_12BIT_STR;
  390.         buf[1] = len & 0xff;
  391.         memcpy(buf+2,s,len);
  392.     } else {
  393.         buf[0] = LP_ENCODING_32BIT_STR;
  394.         buf[1] = len & 0xff;
  395.         buf[2] = (len >> 8) & 0xff;
  396.         buf[3] = (len >> 16) & 0xff;
  397.         buf[4] = (len >> 24) & 0xff;
  398.         memcpy(buf+5,s,len);
  399.     }
  400. }
  401.  
  402. /* Return the encoded length of the listpack element pointed by 'p'.
  403.  * This includes the encoding byte, length bytes, and the element data itself.
  404.  * If the element encoding is wrong then 0 is returned.
  405.  * Note that this method may access additional bytes (in case of 12 and 32 bit
  406.  * str), so should only be called when we know 'p' was already validated by
  407.  * lpCurrentEncodedSizeBytes or ASSERT_INTEGRITY_LEN (possibly since 'p' is
  408.  * a return value of another function that validated its return. */
  409. uint32_t lpCurrentEncodedSizeUnsafe(unsigned char *p) {
  410.     if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1;
  411.     if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1+LP_ENCODING_6BIT_STR_LEN(p);
  412.     if (LP_ENCODING_IS_13BIT_INT(p[0])) return 2;
  413.     if (LP_ENCODING_IS_16BIT_INT(p[0])) return 3;
  414.     if (LP_ENCODING_IS_24BIT_INT(p[0])) return 4;
  415.     if (LP_ENCODING_IS_32BIT_INT(p[0])) return 5;
  416.     if (LP_ENCODING_IS_64BIT_INT(p[0])) return 9;
  417.     if (LP_ENCODING_IS_12BIT_STR(p[0])) return 2+LP_ENCODING_12BIT_STR_LEN(p);
  418.     if (LP_ENCODING_IS_32BIT_STR(p[0])) return 5+LP_ENCODING_32BIT_STR_LEN(p);
  419.     if (p[0] == LP_EOF) return 1;
  420.     return 0;
  421. }
  422.  
  423. /* Return bytes needed to encode the length of the listpack element pointed by 'p'.
  424.  * This includes just the encodign byte, and the bytes needed to encode the length
  425.  * of the element (excluding the element data itself)
  426.  * If the element encoding is wrong then 0 is returned. */
  427. uint32_t lpCurrentEncodedSizeBytes(unsigned char *p) {
  428.     if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1;
  429.     if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1;
  430.     if (LP_ENCODING_IS_13BIT_INT(p[0])) return 1;
  431.     if (LP_ENCODING_IS_16BIT_INT(p[0])) return 1;
  432.     if (LP_ENCODING_IS_24BIT_INT(p[0])) return 1;
  433.     if (LP_ENCODING_IS_32BIT_INT(p[0])) return 1;
  434.     if (LP_ENCODING_IS_64BIT_INT(p[0])) return 1;
  435.     if (LP_ENCODING_IS_12BIT_STR(p[0])) return 2;
  436.     if (LP_ENCODING_IS_32BIT_STR(p[0])) return 5;
  437.     if (p[0] == LP_EOF) return 1;
  438.     return 0;
  439. }
  440.  
  441. /* Skip the current entry returning the next. It is invalid to call this
  442.  * function if the current element is the EOF element at the end of the
  443.  * listpack, however, while this function is used to implement lpNext(),
  444.  * it does not return NULL when the EOF element is encountered. */
  445. unsigned char *lpSkip(unsigned char *p) {
  446.     unsigned long entrylen = lpCurrentEncodedSizeUnsafe(p);
  447.     entrylen += lpEncodeBacklen(NULL,entrylen);
  448.     p += entrylen;
  449.     return p;
  450. }
  451.  
  452. /* If 'p' points to an element of the listpack, calling lpNext() will return
  453.  * the pointer to the next element (the one on the right), or NULL if 'p'
  454.  * already pointed to the last element of the listpack. */
  455. unsigned char *lpNext(unsigned char *lp, unsigned char *p) {
  456.     assert(p);
  457.     p = lpSkip(p);
  458.     if (p[0] == LP_EOF) return NULL;
  459.     lpAssertValidEntry(lp, lpBytes(lp), p);
  460.     return p;
  461. }
  462.  
  463. /* If 'p' points to an element of the listpack, calling lpPrev() will return
  464.  * the pointer to the previous element (the one on the left), or NULL if 'p'
  465.  * already pointed to the first element of the listpack. */
  466. unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
  467.     assert(p);
  468.     if (p-lp == LP_HDR_SIZE) return NULL;
  469.     p--; /* Seek the first backlen byte of the last element. */
  470.     uint64_t prevlen = lpDecodeBacklen(p);
  471.     prevlen += lpEncodeBacklen(NULL,prevlen);
  472.     p -= prevlen-1; /* Seek the first byte of the previous entry. */
  473.     lpAssertValidEntry(lp, lpBytes(lp), p);
  474.     return p;
  475. }
  476.  
  477. /* Return a pointer to the first element of the listpack, or NULL if the
  478.  * listpack has no elements. */
  479. unsigned char *lpFirst(unsigned char *lp) {
  480.     unsigned char *p = lp + LP_HDR_SIZE; /* Skip the header. */
  481.     if (p[0] == LP_EOF) return NULL;
  482.     lpAssertValidEntry(lp, lpBytes(lp), p);
  483.     return p;
  484. }
  485.  
  486. /* Return a pointer to the last element of the listpack, or NULL if the
  487.  * listpack has no elements. */
  488. unsigned char *lpLast(unsigned char *lp) {
  489.     unsigned char *p = lp+lpGetTotalBytes(lp)-1; /* Seek EOF element. */
  490.     return lpPrev(lp,p); /* Will return NULL if EOF is the only element. */
  491. }
  492.  
  493. /* Return the number of elements inside the listpack. This function attempts
  494.  * to use the cached value when within range, otherwise a full scan is
  495.  * needed. As a side effect of calling this function, the listpack header
  496.  * could be modified, because if the count is found to be already within
  497.  * the 'numele' header field range, the new value is set. */
  498. uint32_t lpLength(unsigned char *lp) {
  499.     uint32_t numele = lpGetNumElements(lp);
  500.     if (numele != LP_HDR_NUMELE_UNKNOWN) return numele;
  501.  
  502.     /* Too many elements inside the listpack. We need to scan in order
  503.      * to get the total number. */
  504.     uint32_t count = 0;
  505.     unsigned char *p = lpFirst(lp);
  506.     while(p) {
  507.         count++;
  508.         p = lpNext(lp,p);
  509.     }
  510.  
  511.     /* If the count is again within range of the header numele field,
  512.      * set it. */
  513.     if (count < LP_HDR_NUMELE_UNKNOWN) lpSetNumElements(lp,count);
  514.     return count;
  515. }
  516.  
  517. /* Return the listpack element pointed by 'p'.
  518.  *
  519.  * The function changes behavior depending on the passed 'intbuf' value.
  520.  * Specifically, if 'intbuf' is NULL:
  521.  *
  522.  * If the element is internally encoded as an integer, the function returns
  523.  * NULL and populates the integer value by reference in 'count'. Otherwise if
  524.  * the element is encoded as a string a pointer to the string (pointing inside
  525.  * the listpack itself) is returned, and 'count' is set to the length of the
  526.  * string.
  527.  *
  528.  * If instead 'intbuf' points to a buffer passed by the caller, that must be
  529.  * at least LP_INTBUF_SIZE bytes, the function always returns the element as
  530.  * it was a string (returning the pointer to the string and setting the
  531.  * 'count' argument to the string length by reference). However if the element
  532.  * is encoded as an integer, the 'intbuf' buffer is used in order to store
  533.  * the string representation.
  534.  *
  535.  * The user should use one or the other form depending on what the value will
  536.  * be used for. If there is immediate usage for an integer value returned
  537.  * by the function, than to pass a buffer (and convert it back to a number)
  538.  * is of course useless.
  539.  *
  540.  * If the function is called against a badly encoded ziplist, so that there
  541.  * is no valid way to parse it, the function returns like if there was an
  542.  * integer encoded with value 12345678900000000 + <unrecognized byte>, this may
  543.  * be an hint to understand that something is wrong. To crash in this case is
  544.  * not sensible because of the different requirements of the application using
  545.  * this lib.
  546.  *
  547.  * Similarly, there is no error returned since the listpack normally can be
  548.  * assumed to be valid, so that would be a very high API cost. However a function
  549.  * in order to check the integrity of the listpack at load time is provided,
  550.  * check lpIsValid(). */
  551. unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) {
  552.     int64_t val;
  553.     uint64_t uval, negstart, negmax;
  554.  
  555.     assert(p); /* assertion for valgrind (avoid NPD) */
  556.     if (LP_ENCODING_IS_7BIT_UINT(p[0])) {
  557.         negstart = UINT64_MAX; /* 7 bit ints are always positive. */
  558.         negmax = 0;
  559.         uval = p[0] & 0x7f;
  560.     } else if (LP_ENCODING_IS_6BIT_STR(p[0])) {
  561.         *count = LP_ENCODING_6BIT_STR_LEN(p);
  562.         return p+1;
  563.     } else if (LP_ENCODING_IS_13BIT_INT(p[0])) {
  564.         uval = ((p[0]&0x1f)<<8) | p[1];
  565.         negstart = (uint64_t)1<<12;
  566.         negmax = 8191;
  567.     } else if (LP_ENCODING_IS_16BIT_INT(p[0])) {
  568.         uval = (uint64_t)p[1] |
  569.                (uint64_t)p[2]<<8;
  570.         negstart = (uint64_t)1<<15;
  571.         negmax = UINT16_MAX;
  572.     } else if (LP_ENCODING_IS_24BIT_INT(p[0])) {
  573.         uval = (uint64_t)p[1] |
  574.                (uint64_t)p[2]<<8 |
  575.                (uint64_t)p[3]<<16;
  576.         negstart = (uint64_t)1<<23;
  577.         negmax = UINT32_MAX>>8;
  578.     } else if (LP_ENCODING_IS_32BIT_INT(p[0])) {
  579.         uval = (uint64_t)p[1] |
  580.                (uint64_t)p[2]<<8 |
  581.                (uint64_t)p[3]<<16 |
  582.                (uint64_t)p[4]<<24;
  583.         negstart = (uint64_t)1<<31;
  584.         negmax = UINT32_MAX;
  585.     } else if (LP_ENCODING_IS_64BIT_INT(p[0])) {
  586.         uval = (uint64_t)p[1] |
  587.                (uint64_t)p[2]<<8 |
  588.                (uint64_t)p[3]<<16 |
  589.                (uint64_t)p[4]<<24 |
  590.                (uint64_t)p[5]<<32 |
  591.                (uint64_t)p[6]<<40 |
  592.                (uint64_t)p[7]<<48 |
  593.                (uint64_t)p[8]<<56;
  594.         negstart = (uint64_t)1<<63;
  595.         negmax = UINT64_MAX;
  596.     } else if (LP_ENCODING_IS_12BIT_STR(p[0])) {
  597.         *count = LP_ENCODING_12BIT_STR_LEN(p);
  598.         return p+2;
  599.     } else if (LP_ENCODING_IS_32BIT_STR(p[0])) {
  600.         *count = LP_ENCODING_32BIT_STR_LEN(p);
  601.         return p+5;
  602.     } else {
  603.         uval = 12345678900000000ULL + p[0];
  604.         negstart = UINT64_MAX;
  605.         negmax = 0;
  606.     }
  607.  
  608.     /* We reach this code path only for integer encodings.
  609.      * Convert the unsigned value to the signed one using two's complement
  610.      * rule. */
  611.     if (uval >= negstart) {
  612.         /* This three steps conversion should avoid undefined behaviors
  613.          * in the unsigned -> signed conversion. */
  614.         uval = negmax-uval;
  615.         val = uval;
  616.         val = -val-1;
  617.     } else {
  618.         val = uval;
  619.     }
  620.  
  621.     /* Return the string representation of the integer or the value itself
  622.      * depending on intbuf being NULL or not. */
  623.     if (intbuf) {
  624.         *count = snprintf((char*)intbuf,LP_INTBUF_SIZE,"%lld",(long long)val);
  625.         return intbuf;
  626.     } else {
  627.         *count = val;
  628.         return NULL;
  629.     }
  630. }
  631.  
  632. /* Insert, delete or replace the specified element 'ele' of length 'len' at
  633.  * the specified position 'p', with 'p' being a listpack element pointer
  634.  * obtained with lpFirst(), lpLast(), lpNext(), lpPrev() or lpSeek().
  635.  *
  636.  * The element is inserted before, after, or replaces the element pointed
  637.  * by 'p' depending on the 'where' argument, that can be LP_BEFORE, LP_AFTER
  638.  * or LP_REPLACE.
  639.  *
  640.  * If 'ele' is set to NULL, the function removes the element pointed by 'p'
  641.  * instead of inserting one.
  642.  *
  643.  * Returns NULL on out of memory or when the listpack total length would exceed
  644.  * the max allowed size of 2^32-1, otherwise the new pointer to the listpack
  645.  * holding the new element is returned (and the old pointer passed is no longer
  646.  * considered valid)
  647.  *
  648.  * If 'newp' is not NULL, at the end of a successful call '*newp' will be set
  649.  * to the address of the element just added, so that it will be possible to
  650.  * continue an interation with lpNext() and lpPrev().
  651.  *
  652.  * For deletion operations ('ele' set to NULL) 'newp' is set to the next
  653.  * element, on the right of the deleted one, or to NULL if the deleted element
  654.  * was the last one. */
  655. unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, unsigned char *p, int where, unsigned char **newp) {
  656.     unsigned char intenc[LP_MAX_INT_ENCODING_LEN];
  657.     unsigned char backlen[LP_MAX_BACKLEN_SIZE];
  658.  
  659.     uint64_t enclen; /* The length of the encoded element. */
  660.  
  661.     /* An element pointer set to NULL means deletion, which is conceptually
  662.      * replacing the element with a zero-length element. So whatever we
  663.      * get passed as 'where', set it to LP_REPLACE. */
  664.     if (ele == NULL) where = LP_REPLACE;
  665.  
  666.     /* If we need to insert after the current element, we just jump to the
  667.      * next element (that could be the EOF one) and handle the case of
  668.      * inserting before. So the function will actually deal with just two
  669.      * cases: LP_BEFORE and LP_REPLACE. */
  670.     if (where == LP_AFTER) {
  671.         p = lpSkip(p);
  672.         where = LP_BEFORE;
  673.         ASSERT_INTEGRITY(lp, p);
  674.     }
  675.  
  676.     /* Store the offset of the element 'p', so that we can obtain its
  677.      * address again after a reallocation. */
  678.     unsigned long poff = p-lp;
  679.  
  680.     /* Calling lpEncodeGetType() results into the encoded version of the
  681.      * element to be stored into 'intenc' in case it is representable as
  682.      * an integer: in that case, the function returns LP_ENCODING_INT.
  683.      * Otherwise if LP_ENCODING_STR is returned, we'll have to call
  684.      * lpEncodeString() to actually write the encoded string on place later.
  685.      *
  686.      * Whatever the returned encoding is, 'enclen' is populated with the
  687.      * length of the encoded element. */
  688.     int enctype;
  689.     if (ele) {
  690.         enctype = lpEncodeGetType(ele,size,intenc,&enclen);
  691.     } else {
  692.         enctype = -1;
  693.         enclen = 0;
  694.     }
  695.  
  696.     /* We need to also encode the backward-parsable length of the element
  697.      * and append it to the end: this allows to traverse the listpack from
  698.      * the end to the start. */
  699.     unsigned long backlen_size = ele ? lpEncodeBacklen(backlen,enclen) : 0;
  700.     uint64_t old_listpack_bytes = lpGetTotalBytes(lp);
  701.     uint32_t replaced_len  = 0;
  702.     if (where == LP_REPLACE) {
  703.         replaced_len = lpCurrentEncodedSizeUnsafe(p);
  704.         replaced_len += lpEncodeBacklen(NULL,replaced_len);
  705.         ASSERT_INTEGRITY_LEN(lp, p, replaced_len);
  706.     }
  707.  
  708.     uint64_t new_listpack_bytes = old_listpack_bytes + enclen + backlen_size
  709.                                   - replaced_len;
  710.     if (new_listpack_bytes > UINT32_MAX) return NULL;
  711.  
  712.     /* We now need to reallocate in order to make space or shrink the
  713.      * allocation (in case 'when' value is LP_REPLACE and the new element is
  714.      * smaller). However we do that before memmoving the memory to
  715.      * make room for the new element if the final allocation will get
  716.      * larger, or we do it after if the final allocation will get smaller. */
  717.  
  718.     unsigned char *dst = lp + poff; /* May be updated after reallocation. */
  719.  
  720.     /* Realloc before: we need more room. */
  721.     if (new_listpack_bytes > old_listpack_bytes &&
  722.         new_listpack_bytes > lp_malloc_size(lp)) {
  723.         if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
  724.         dst = lp + poff;
  725.     }
  726.  
  727.     /* Setup the listpack relocating the elements to make the exact room
  728.      * we need to store the new one. */
  729.     if (where == LP_BEFORE) {
  730.         memmove(dst+enclen+backlen_size,dst,old_listpack_bytes-poff);
  731.     } else { /* LP_REPLACE. */
  732.         long lendiff = (enclen+backlen_size)-replaced_len;
  733.         memmove(dst+replaced_len+lendiff,
  734.                 dst+replaced_len,
  735.                 old_listpack_bytes-poff-replaced_len);
  736.     }
  737.  
  738.     /* Realloc after: we need to free space. */
  739.     if (new_listpack_bytes < old_listpack_bytes) {
  740.         if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
  741.         dst = lp + poff;
  742.     }
  743.  
  744.     /* Store the entry. */
  745.     if (newp) {
  746.         *newp = dst;
  747.         /* In case of deletion, set 'newp' to NULL if the next element is
  748.          * the EOF element. */
  749.         if (!ele && dst[0] == LP_EOF) *newp = NULL;
  750.     }
  751.     if (ele) {
  752.         if (enctype == LP_ENCODING_INT) {
  753.             memcpy(dst,intenc,enclen);
  754.         } else {
  755.             lpEncodeString(dst,ele,size);
  756.         }
  757.         dst += enclen;
  758.         memcpy(dst,backlen,backlen_size);
  759.         dst += backlen_size;
  760.     }
  761.  
  762.     /* Update header. */
  763.     if (where != LP_REPLACE || ele == NULL) {
  764.         uint32_t num_elements = lpGetNumElements(lp);
  765.         if (num_elements != LP_HDR_NUMELE_UNKNOWN) {
  766.             if (ele)
  767.                 lpSetNumElements(lp,num_elements+1);
  768.             else
  769.                 lpSetNumElements(lp,num_elements-1);
  770.         }
  771.     }
  772.     lpSetTotalBytes(lp,new_listpack_bytes);
  773.  
  774. #if 0
  775.     /* This code path is normally disabled: what it does is to force listpack
  776.      * to return *always* a new pointer after performing some modification to
  777.      * the listpack, even if the previous allocation was enough. This is useful
  778.      * in order to spot bugs in code using listpacks: by doing so we can find
  779.      * if the caller forgets to set the new pointer where the listpack reference
  780.      * is stored, after an update. */
  781.     unsigned char *oldlp = lp;
  782.     lp = lp_malloc(new_listpack_bytes);
  783.     memcpy(lp,oldlp,new_listpack_bytes);
  784.     if (newp) {
  785.         unsigned long offset = (*newp)-oldlp;
  786.         *newp = lp + offset;
  787.     }
  788.     /* Make sure the old allocation contains garbage. */
  789.     memset(oldlp,'A',new_listpack_bytes);
  790.     lp_free(oldlp);
  791. #endif
  792.  
  793.     return lp;
  794. }
  795.  
  796. /* Append the specified element 'ele' of length 'len' at the end of the
  797.  * listpack. It is implemented in terms of lpInsert(), so the return value is
  798.  * the same as lpInsert(). */
  799. unsigned char *lpAppend(unsigned char *lp, unsigned char *ele, uint32_t size) {
  800.     uint64_t listpack_bytes = lpGetTotalBytes(lp);
  801.     unsigned char *eofptr = lp + listpack_bytes - 1;
  802.     return lpInsert(lp,ele,size,eofptr,LP_BEFORE,NULL);
  803. }
  804.  
  805. /* Remove the element pointed by 'p', and return the resulting listpack.
  806.  * If 'newp' is not NULL, the next element pointer (to the right of the
  807.  * deleted one) is returned by reference. If the deleted element was the
  808.  * last one, '*newp' is set to NULL. */
  809. unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp) {
  810.     return lpInsert(lp,NULL,0,p,LP_REPLACE,newp);
  811. }
  812.  
  813. /* Return the total number of bytes the listpack is composed of. */
  814. uint32_t lpBytes(unsigned char *lp) {
  815.     return lpGetTotalBytes(lp);
  816. }
  817.  
  818. /* Seek the specified element and returns the pointer to the seeked element.
  819.  * Positive indexes specify the zero-based element to seek from the head to
  820.  * the tail, negative indexes specify elements starting from the tail, where
  821.  * -1 means the last element, -2 the penultimate and so forth. If the index
  822.  * is out of range, NULL is returned. */
  823. unsigned char *lpSeek(unsigned char *lp, long index) {
  824.     int forward = 1; /* Seek forward by default. */
  825.  
  826.     /* We want to seek from left to right or the other way around
  827.      * depending on the listpack length and the element position.
  828.      * However if the listpack length cannot be obtained in constant time,
  829.      * we always seek from left to right. */
  830.     uint32_t numele = lpGetNumElements(lp);
  831.     if (numele != LP_HDR_NUMELE_UNKNOWN) {
  832.         if (index < 0) index = (long)numele+index;
  833.         if (index < 0) return NULL; /* Index still < 0 means out of range. */
  834.         if (index >= (long)numele) return NULL; /* Out of range the other side. */
  835.         /* We want to scan right-to-left if the element we are looking for
  836.          * is past the half of the listpack. */
  837.         if (index > (long)numele/2) {
  838.             forward = 0;
  839.             /* Right to left scanning always expects a negative index. Convert
  840.              * our index to negative form. */
  841.             index -= numele;
  842.         }
  843.     } else {
  844.         /* If the listpack length is unspecified, for negative indexes we
  845.          * want to always scan right-to-left. */
  846.         if (index < 0) forward = 0;
  847.     }
  848.  
  849.     /* Forward and backward scanning is trivially based on lpNext()/lpPrev(). */
  850.     if (forward) {
  851.         unsigned char *ele = lpFirst(lp);
  852.         while (index > 0 && ele) {
  853.             ele = lpNext(lp,ele);
  854.             index--;
  855.         }
  856.         return ele;
  857.     } else {
  858.         unsigned char *ele = lpLast(lp);
  859.         while (index < -1 && ele) {
  860.             ele = lpPrev(lp,ele);
  861.             index++;
  862.         }
  863.         return ele;
  864.     }
  865. }
  866.  
  867. /* Same as lpFirst but without validation assert, to be used right before lpValidateNext. */
  868. unsigned char *lpValidateFirst(unsigned char *lp) {
  869.     unsigned char *p = lp + LP_HDR_SIZE; /* Skip the header. */
  870.     if (p[0] == LP_EOF) return NULL;
  871.     return p;
  872. }
  873.  
  874. /* Validate the integrity of a single listpack entry and move to the next one.
  875.  * The input argument 'pp' is a reference to the current record and is advanced on exit.
  876.  * Returns 1 if valid, 0 if invalid. */
  877. int lpValidateNext(unsigned char *lp, unsigned char **pp, size_t lpbytes) {
  878. #define OUT_OF_RANGE(p) ( \
  879.         (p) < lp + LP_HDR_SIZE || \
  880.         (p) > lp + lpbytes - 1)
  881.     unsigned char *p = *pp;
  882.     if (!p)
  883.         return 0;
  884.  
  885.     /* Before accessing p, make sure it's valid. */
  886.     if (OUT_OF_RANGE(p))
  887.         return 0;
  888.  
  889.     if (*p == LP_EOF) {
  890.         *pp = NULL;
  891.         return 1;
  892.     }
  893.  
  894.     /* check that we can read the encoded size */
  895.     uint32_t lenbytes = lpCurrentEncodedSizeBytes(p);
  896.     if (!lenbytes)
  897.         return 0;
  898.  
  899.     /* make sure the encoded entry length doesn't rech outside the edge of the listpack */
  900.     if (OUT_OF_RANGE(p + lenbytes))
  901.         return 0;
  902.  
  903.     /* get the entry length and encoded backlen. */
  904.     unsigned long entrylen = lpCurrentEncodedSizeUnsafe(p);
  905.     unsigned long encodedBacklen = lpEncodeBacklen(NULL,entrylen);
  906.     entrylen += encodedBacklen;
  907.  
  908.     /* make sure the entry doesn't rech outside the edge of the listpack */
  909.     if (OUT_OF_RANGE(p + entrylen))
  910.         return 0;
  911.  
  912.     /* move to the next entry */
  913.     p += entrylen;
  914.  
  915.     /* make sure the encoded length at the end patches the one at the beginning. */
  916.     uint64_t prevlen = lpDecodeBacklen(p-1);
  917.     if (prevlen + encodedBacklen != entrylen)
  918.         return 0;
  919.  
  920.     *pp = p;
  921.     return 1;
  922. #undef OUT_OF_RANGE
  923. }
  924.  
  925. /* Validate that the entry doesn't reach outside the listpack allocation. */
  926. static inline void lpAssertValidEntry(unsigned char* lp, size_t lpbytes, unsigned char *p) {
  927.     assert(lpValidateNext(lp, &p, lpbytes));
  928. }
  929.  
  930. /* Validate the integrity of the data structure.
  931.  * when `deep` is 0, only the integrity of the header is validated.
  932.  * when `deep` is 1, we scan all the entries one by one. */
  933. int lpValidateIntegrity(unsigned char *lp, size_t size, int deep){
  934.     /* Check that we can actually read the header. (and EOF) */
  935.     if (size < LP_HDR_SIZE + 1)
  936.         return 0;
  937.  
  938.     /* Check that the encoded size in the header must match the allocated size. */
  939.     size_t bytes = lpGetTotalBytes(lp);
  940.     if (bytes != size)
  941.         return 0;
  942.  
  943.     /* The last byte must be the terminator. */
  944.     if (lp[size-1] != LP_EOF)
  945.         return 0;
  946.  
  947.     if (!deep)
  948.         return 1;
  949.  
  950.     /* Validate the invividual entries. */
  951.     uint32_t count = 0;
  952.     unsigned char *p = lp + LP_HDR_SIZE;
  953.     while(p && p[0] != LP_EOF) {
  954.         if (!lpValidateNext(lp, &p, bytes))
  955.             return 0;
  956.         count++;
  957.     }
  958.  
  959.     /* Check that the count in the header is correct */
  960.     uint32_t numele = lpGetNumElements(lp);
  961.     if (numele != LP_HDR_NUMELE_UNKNOWN && numele != count)
  962.         return 0;
  963.  
  964.     return 1;
  965. }

相关技术文章

最新源码

下载排行榜
点击QQ咨询
开通会员
返回顶部
×
微信扫码支付 元
微信扫码支付
确定支付下载
请使用微信描二维码支付
×

提示信息

×

选择支付方式

  • 微信支付
  • 支付宝付款
确定支付下载