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