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 | #include "util.h" |
47 | |
48 | #define LP_HDR_SIZE 6 /* 32 bit total len + 16 bit number of elements. */ |
49 | #define LP_HDR_NUMELE_UNKNOWN UINT16_MAX |
50 | #define LP_MAX_INT_ENCODING_LEN 9 |
51 | #define LP_MAX_BACKLEN_SIZE 5 |
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 | #define LP_ENCODING_7BIT_UINT_ENTRY_SIZE 2 |
59 | |
60 | #define LP_ENCODING_6BIT_STR 0x80 |
61 | #define LP_ENCODING_6BIT_STR_MASK 0xC0 |
62 | #define LP_ENCODING_IS_6BIT_STR(byte) (((byte)&LP_ENCODING_6BIT_STR_MASK)==LP_ENCODING_6BIT_STR) |
63 | |
64 | #define LP_ENCODING_13BIT_INT 0xC0 |
65 | #define LP_ENCODING_13BIT_INT_MASK 0xE0 |
66 | #define LP_ENCODING_IS_13BIT_INT(byte) (((byte)&LP_ENCODING_13BIT_INT_MASK)==LP_ENCODING_13BIT_INT) |
67 | #define LP_ENCODING_13BIT_INT_ENTRY_SIZE 3 |
68 | |
69 | #define LP_ENCODING_12BIT_STR 0xE0 |
70 | #define LP_ENCODING_12BIT_STR_MASK 0xF0 |
71 | #define LP_ENCODING_IS_12BIT_STR(byte) (((byte)&LP_ENCODING_12BIT_STR_MASK)==LP_ENCODING_12BIT_STR) |
72 | |
73 | #define LP_ENCODING_16BIT_INT 0xF1 |
74 | #define LP_ENCODING_16BIT_INT_MASK 0xFF |
75 | #define LP_ENCODING_IS_16BIT_INT(byte) (((byte)&LP_ENCODING_16BIT_INT_MASK)==LP_ENCODING_16BIT_INT) |
76 | #define LP_ENCODING_16BIT_INT_ENTRY_SIZE 4 |
77 | |
78 | #define LP_ENCODING_24BIT_INT 0xF2 |
79 | #define LP_ENCODING_24BIT_INT_MASK 0xFF |
80 | #define LP_ENCODING_IS_24BIT_INT(byte) (((byte)&LP_ENCODING_24BIT_INT_MASK)==LP_ENCODING_24BIT_INT) |
81 | #define LP_ENCODING_24BIT_INT_ENTRY_SIZE 5 |
82 | |
83 | #define LP_ENCODING_32BIT_INT 0xF3 |
84 | #define LP_ENCODING_32BIT_INT_MASK 0xFF |
85 | #define LP_ENCODING_IS_32BIT_INT(byte) (((byte)&LP_ENCODING_32BIT_INT_MASK)==LP_ENCODING_32BIT_INT) |
86 | #define LP_ENCODING_32BIT_INT_ENTRY_SIZE 6 |
87 | |
88 | #define LP_ENCODING_64BIT_INT 0xF4 |
89 | #define LP_ENCODING_64BIT_INT_MASK 0xFF |
90 | #define LP_ENCODING_IS_64BIT_INT(byte) (((byte)&LP_ENCODING_64BIT_INT_MASK)==LP_ENCODING_64BIT_INT) |
91 | #define LP_ENCODING_64BIT_INT_ENTRY_SIZE 10 |
92 | |
93 | #define LP_ENCODING_32BIT_STR 0xF0 |
94 | #define LP_ENCODING_32BIT_STR_MASK 0xFF |
95 | #define LP_ENCODING_IS_32BIT_STR(byte) (((byte)&LP_ENCODING_32BIT_STR_MASK)==LP_ENCODING_32BIT_STR) |
96 | |
97 | #define LP_EOF 0xFF |
98 | |
99 | #define LP_ENCODING_6BIT_STR_LEN(p) ((p)[0] & 0x3F) |
100 | #define LP_ENCODING_12BIT_STR_LEN(p) ((((p)[0] & 0xF) << 8) | (p)[1]) |
101 | #define LP_ENCODING_32BIT_STR_LEN(p) (((uint32_t)(p)[1]<<0) | \ |
102 | ((uint32_t)(p)[2]<<8) | \ |
103 | ((uint32_t)(p)[3]<<16) | \ |
104 | ((uint32_t)(p)[4]<<24)) |
105 | |
106 | #define lpGetTotalBytes(p) (((uint32_t)(p)[0]<<0) | \ |
107 | ((uint32_t)(p)[1]<<8) | \ |
108 | ((uint32_t)(p)[2]<<16) | \ |
109 | ((uint32_t)(p)[3]<<24)) |
110 | |
111 | #define lpGetNumElements(p) (((uint32_t)(p)[4]<<0) | \ |
112 | ((uint32_t)(p)[5]<<8)) |
113 | #define lpSetTotalBytes(p,v) do { \ |
114 | (p)[0] = (v)&0xff; \ |
115 | (p)[1] = ((v)>>8)&0xff; \ |
116 | (p)[2] = ((v)>>16)&0xff; \ |
117 | (p)[3] = ((v)>>24)&0xff; \ |
118 | } while(0) |
119 | |
120 | #define lpSetNumElements(p,v) do { \ |
121 | (p)[4] = (v)&0xff; \ |
122 | (p)[5] = ((v)>>8)&0xff; \ |
123 | } while(0) |
124 | |
125 | /* Validates that 'p' is not outside the listpack. |
126 | * All function that return a pointer to an element in the listpack will assert |
127 | * that this element is valid, so it can be freely used. |
128 | * Generally functions such lpNext and lpDelete assume the input pointer is |
129 | * already validated (since it's the return value of another function). */ |
130 | #define ASSERT_INTEGRITY(lp, p) do { \ |
131 | assert((p) >= (lp)+LP_HDR_SIZE && (p) < (lp)+lpGetTotalBytes((lp))); \ |
132 | } while (0) |
133 | |
134 | /* Similar to the above, but validates the entire element length rather than just |
135 | * it's pointer. */ |
136 | #define ASSERT_INTEGRITY_LEN(lp, p, len) do { \ |
137 | assert((p) >= (lp)+LP_HDR_SIZE && (p)+(len) < (lp)+lpGetTotalBytes((lp))); \ |
138 | } while (0) |
139 | |
140 | static inline void lpAssertValidEntry(unsigned char* lp, size_t lpbytes, unsigned char *p); |
141 | |
142 | /* Don't let listpacks grow over 1GB in any case, don't wanna risk overflow in |
143 | * Total Bytes header field */ |
144 | #define LISTPACK_MAX_SAFETY_SIZE (1<<30) |
145 | int lpSafeToAdd(unsigned char* lp, size_t add) { |
146 | size_t len = lp? lpGetTotalBytes(lp): 0; |
147 | if (len + add > LISTPACK_MAX_SAFETY_SIZE) |
148 | return 0; |
149 | return 1; |
150 | } |
151 | |
152 | /* Convert a string into a signed 64 bit integer. |
153 | * The function returns 1 if the string could be parsed into a (non-overflowing) |
154 | * signed 64 bit int, 0 otherwise. The 'value' will be set to the parsed value |
155 | * when the function returns success. |
156 | * |
157 | * Note that this function demands that the string strictly represents |
158 | * a int64 value: no spaces or other characters before or after the string |
159 | * representing the number are accepted, nor zeroes at the start if not |
160 | * for the string "0" representing the zero number. |
161 | * |
162 | * Because of its strictness, it is safe to use this function to check if |
163 | * you can convert a string into a long long, and obtain back the string |
164 | * from the number without any loss in the string representation. * |
165 | * |
166 | * ----------------------------------------------------------------------------- |
167 | * |
168 | * Credits: this function was adapted from the Redis source code, file |
169 | * "utils.c", function string2ll(), and is copyright: |
170 | * |
171 | * Copyright(C) 2011, Pieter Noordhuis |
172 | * Copyright(C) 2011, Salvatore Sanfilippo |
173 | * |
174 | * The function is released under the BSD 3-clause license. |
175 | */ |
176 | int lpStringToInt64(const char *s, unsigned long slen, int64_t *value) { |
177 | const char *p = s; |
178 | unsigned long plen = 0; |
179 | int negative = 0; |
180 | uint64_t v; |
181 | |
182 | /* Abort if length indicates this cannot possibly be an int */ |
183 | if (slen == 0 || slen >= LONG_STR_SIZE) |
184 | return 0; |
185 | |
186 | /* Special case: first and only digit is 0. */ |
187 | if (slen == 1 && p[0] == '0') { |
188 | if (value != NULL) *value = 0; |
189 | return 1; |
190 | } |
191 | |
192 | if (p[0] == '-') { |
193 | negative = 1; |
194 | p++; plen++; |
195 | |
196 | /* Abort on only a negative sign. */ |
197 | if (plen == slen) |
198 | return 0; |
199 | } |
200 | |
201 | /* First digit should be 1-9, otherwise the string should just be 0. */ |
202 | if (p[0] >= '1' && p[0] <= '9') { |
203 | v = p[0]-'0'; |
204 | p++; plen++; |
205 | } else { |
206 | return 0; |
207 | } |
208 | |
209 | while (plen < slen && p[0] >= '0' && p[0] <= '9') { |
210 | if (v > (UINT64_MAX / 10)) /* Overflow. */ |
211 | return 0; |
212 | v *= 10; |
213 | |
214 | if (v > (UINT64_MAX - (p[0]-'0'))) /* Overflow. */ |
215 | return 0; |
216 | v += p[0]-'0'; |
217 | |
218 | p++; plen++; |
219 | } |
220 | |
221 | /* Return if not all bytes were used. */ |
222 | if (plen < slen) |
223 | return 0; |
224 | |
225 | if (negative) { |
226 | if (v > ((uint64_t)(-(INT64_MIN+1))+1)) /* Overflow. */ |
227 | return 0; |
228 | if (value != NULL) *value = -v; |
229 | } else { |
230 | if (v > INT64_MAX) /* Overflow. */ |
231 | return 0; |
232 | if (value != NULL) *value = v; |
233 | } |
234 | return 1; |
235 | } |
236 | |
237 | /* Create a new, empty listpack. |
238 | * On success the new listpack is returned, otherwise an error is returned. |
239 | * Pre-allocate at least `capacity` bytes of memory, |
240 | * over-allocated memory can be shrunk by `lpShrinkToFit`. |
241 | * */ |
242 | unsigned char *lpNew(size_t capacity) { |
243 | unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : LP_HDR_SIZE+1); |
244 | if (lp == NULL) return NULL; |
245 | lpSetTotalBytes(lp,LP_HDR_SIZE+1); |
246 | lpSetNumElements(lp,0); |
247 | lp[LP_HDR_SIZE] = LP_EOF; |
248 | return lp; |
249 | } |
250 | |
251 | /* Free the specified listpack. */ |
252 | void lpFree(unsigned char *lp) { |
253 | lp_free(lp); |
254 | } |
255 | |
256 | /* Shrink the memory to fit. */ |
257 | unsigned char* lpShrinkToFit(unsigned char *lp) { |
258 | size_t size = lpGetTotalBytes(lp); |
259 | if (size < lp_malloc_size(lp)) { |
260 | return lp_realloc(lp, size); |
261 | } else { |
262 | return lp; |
263 | } |
264 | } |
265 | |
266 | /* Stores the integer encoded representation of 'v' in the 'intenc' buffer. */ |
267 | static inline void lpEncodeIntegerGetType(int64_t v, unsigned char *intenc, uint64_t *enclen) { |
268 | if (v >= 0 && v <= 127) { |
269 | /* Single byte 0-127 integer. */ |
270 | intenc[0] = v; |
271 | *enclen = 1; |
272 | } else if (v >= -4096 && v <= 4095) { |
273 | /* 13 bit integer. */ |
274 | if (v < 0) v = ((int64_t)1<<13)+v; |
275 | intenc[0] = (v>>8)|LP_ENCODING_13BIT_INT; |
276 | intenc[1] = v&0xff; |
277 | *enclen = 2; |
278 | } else if (v >= -32768 && v <= 32767) { |
279 | /* 16 bit integer. */ |
280 | if (v < 0) v = ((int64_t)1<<16)+v; |
281 | intenc[0] = LP_ENCODING_16BIT_INT; |
282 | intenc[1] = v&0xff; |
283 | intenc[2] = v>>8; |
284 | *enclen = 3; |
285 | } else if (v >= -8388608 && v <= 8388607) { |
286 | /* 24 bit integer. */ |
287 | if (v < 0) v = ((int64_t)1<<24)+v; |
288 | intenc[0] = LP_ENCODING_24BIT_INT; |
289 | intenc[1] = v&0xff; |
290 | intenc[2] = (v>>8)&0xff; |
291 | intenc[3] = v>>16; |
292 | *enclen = 4; |
293 | } else if (v >= -2147483648 && v <= 2147483647) { |
294 | /* 32 bit integer. */ |
295 | if (v < 0) v = ((int64_t)1<<32)+v; |
296 | intenc[0] = LP_ENCODING_32BIT_INT; |
297 | intenc[1] = v&0xff; |
298 | intenc[2] = (v>>8)&0xff; |
299 | intenc[3] = (v>>16)&0xff; |
300 | intenc[4] = v>>24; |
301 | *enclen = 5; |
302 | } else { |
303 | /* 64 bit integer. */ |
304 | uint64_t uv = v; |
305 | intenc[0] = LP_ENCODING_64BIT_INT; |
306 | intenc[1] = uv&0xff; |
307 | intenc[2] = (uv>>8)&0xff; |
308 | intenc[3] = (uv>>16)&0xff; |
309 | intenc[4] = (uv>>24)&0xff; |
310 | intenc[5] = (uv>>32)&0xff; |
311 | intenc[6] = (uv>>40)&0xff; |
312 | intenc[7] = (uv>>48)&0xff; |
313 | intenc[8] = uv>>56; |
314 | *enclen = 9; |
315 | } |
316 | } |
317 | |
318 | /* Given an element 'ele' of size 'size', determine if the element can be |
319 | * represented inside the listpack encoded as integer, and returns |
320 | * LP_ENCODING_INT if so. Otherwise returns LP_ENCODING_STR if no integer |
321 | * encoding is possible. |
322 | * |
323 | * If the LP_ENCODING_INT is returned, the function stores the integer encoded |
324 | * representation of the element in the 'intenc' buffer. |
325 | * |
326 | * Regardless of the returned encoding, 'enclen' is populated by reference to |
327 | * the number of bytes that the string or integer encoded element will require |
328 | * in order to be represented. */ |
329 | static inline int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, uint64_t *enclen) { |
330 | int64_t v; |
331 | if (lpStringToInt64((const char*)ele, size, &v)) { |
332 | lpEncodeIntegerGetType(v, intenc, enclen); |
333 | return LP_ENCODING_INT; |
334 | } else { |
335 | if (size < 64) *enclen = 1+size; |
336 | else if (size < 4096) *enclen = 2+size; |
337 | else *enclen = 5+(uint64_t)size; |
338 | return LP_ENCODING_STRING; |
339 | } |
340 | } |
341 | |
342 | /* Store a reverse-encoded variable length field, representing the length |
343 | * of the previous element of size 'l', in the target buffer 'buf'. |
344 | * The function returns the number of bytes used to encode it, from |
345 | * 1 to 5. If 'buf' is NULL the function just returns the number of bytes |
346 | * needed in order to encode the backlen. */ |
347 | static inline unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) { |
348 | if (l <= 127) { |
349 | if (buf) buf[0] = l; |
350 | return 1; |
351 | } else if (l < 16383) { |
352 | if (buf) { |
353 | buf[0] = l>>7; |
354 | buf[1] = (l&127)|128; |
355 | } |
356 | return 2; |
357 | } else if (l < 2097151) { |
358 | if (buf) { |
359 | buf[0] = l>>14; |
360 | buf[1] = ((l>>7)&127)|128; |
361 | buf[2] = (l&127)|128; |
362 | } |
363 | return 3; |
364 | } else if (l < 268435455) { |
365 | if (buf) { |
366 | buf[0] = l>>21; |
367 | buf[1] = ((l>>14)&127)|128; |
368 | buf[2] = ((l>>7)&127)|128; |
369 | buf[3] = (l&127)|128; |
370 | } |
371 | return 4; |
372 | } else { |
373 | if (buf) { |
374 | buf[0] = l>>28; |
375 | buf[1] = ((l>>21)&127)|128; |
376 | buf[2] = ((l>>14)&127)|128; |
377 | buf[3] = ((l>>7)&127)|128; |
378 | buf[4] = (l&127)|128; |
379 | } |
380 | return 5; |
381 | } |
382 | } |
383 | |
384 | /* Decode the backlen and returns it. If the encoding looks invalid (more than |
385 | * 5 bytes are used), UINT64_MAX is returned to report the problem. */ |
386 | static inline uint64_t lpDecodeBacklen(unsigned char *p) { |
387 | uint64_t val = 0; |
388 | uint64_t shift = 0; |
389 | do { |
390 | val |= (uint64_t)(p[0] & 127) << shift; |
391 | if (!(p[0] & 128)) break; |
392 | shift += 7; |
393 | p--; |
394 | if (shift > 28) return UINT64_MAX; |
395 | } while(1); |
396 | return val; |
397 | } |
398 | |
399 | /* Encode the string element pointed by 's' of size 'len' in the target |
400 | * buffer 's'. The function should be called with 'buf' having always enough |
401 | * space for encoding the string. This is done by calling lpEncodeGetType() |
402 | * before calling this function. */ |
403 | static inline void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) { |
404 | if (len < 64) { |
405 | buf[0] = len | LP_ENCODING_6BIT_STR; |
406 | memcpy(buf+1,s,len); |
407 | } else if (len < 4096) { |
408 | buf[0] = (len >> 8) | LP_ENCODING_12BIT_STR; |
409 | buf[1] = len & 0xff; |
410 | memcpy(buf+2,s,len); |
411 | } else { |
412 | buf[0] = LP_ENCODING_32BIT_STR; |
413 | buf[1] = len & 0xff; |
414 | buf[2] = (len >> 8) & 0xff; |
415 | buf[3] = (len >> 16) & 0xff; |
416 | buf[4] = (len >> 24) & 0xff; |
417 | memcpy(buf+5,s,len); |
418 | } |
419 | } |
420 | |
421 | /* Return the encoded length of the listpack element pointed by 'p'. |
422 | * This includes the encoding byte, length bytes, and the element data itself. |
423 | * If the element encoding is wrong then 0 is returned. |
424 | * Note that this method may access additional bytes (in case of 12 and 32 bit |
425 | * str), so should only be called when we know 'p' was already validated by |
426 | * lpCurrentEncodedSizeBytes or ASSERT_INTEGRITY_LEN (possibly since 'p' is |
427 | * a return value of another function that validated its return. */ |
428 | static inline uint32_t lpCurrentEncodedSizeUnsafe(unsigned char *p) { |
429 | if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1; |
430 | if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1+LP_ENCODING_6BIT_STR_LEN(p); |
431 | if (LP_ENCODING_IS_13BIT_INT(p[0])) return 2; |
432 | if (LP_ENCODING_IS_16BIT_INT(p[0])) return 3; |
433 | if (LP_ENCODING_IS_24BIT_INT(p[0])) return 4; |
434 | if (LP_ENCODING_IS_32BIT_INT(p[0])) return 5; |
435 | if (LP_ENCODING_IS_64BIT_INT(p[0])) return 9; |
436 | if (LP_ENCODING_IS_12BIT_STR(p[0])) return 2+LP_ENCODING_12BIT_STR_LEN(p); |
437 | if (LP_ENCODING_IS_32BIT_STR(p[0])) return 5+LP_ENCODING_32BIT_STR_LEN(p); |
438 | if (p[0] == LP_EOF) return 1; |
439 | return 0; |
440 | } |
441 | |
442 | /* Return bytes needed to encode the length of the listpack element pointed by 'p'. |
443 | * This includes just the encoding byte, and the bytes needed to encode the length |
444 | * of the element (excluding the element data itself) |
445 | * If the element encoding is wrong then 0 is returned. */ |
446 | static inline uint32_t lpCurrentEncodedSizeBytes(unsigned char *p) { |
447 | if (LP_ENCODING_IS_7BIT_UINT(p[0])) return 1; |
448 | if (LP_ENCODING_IS_6BIT_STR(p[0])) return 1; |
449 | if (LP_ENCODING_IS_13BIT_INT(p[0])) return 1; |
450 | if (LP_ENCODING_IS_16BIT_INT(p[0])) return 1; |
451 | if (LP_ENCODING_IS_24BIT_INT(p[0])) return 1; |
452 | if (LP_ENCODING_IS_32BIT_INT(p[0])) return 1; |
453 | if (LP_ENCODING_IS_64BIT_INT(p[0])) return 1; |
454 | if (LP_ENCODING_IS_12BIT_STR(p[0])) return 2; |
455 | if (LP_ENCODING_IS_32BIT_STR(p[0])) return 5; |
456 | if (p[0] == LP_EOF) return 1; |
457 | return 0; |
458 | } |
459 | |
460 | /* Skip the current entry returning the next. It is invalid to call this |
461 | * function if the current element is the EOF element at the end of the |
462 | * listpack, however, while this function is used to implement lpNext(), |
463 | * it does not return NULL when the EOF element is encountered. */ |
464 | unsigned char *lpSkip(unsigned char *p) { |
465 | unsigned long entrylen = lpCurrentEncodedSizeUnsafe(p); |
466 | entrylen += lpEncodeBacklen(NULL,entrylen); |
467 | p += entrylen; |
468 | return p; |
469 | } |
470 | |
471 | /* If 'p' points to an element of the listpack, calling lpNext() will return |
472 | * the pointer to the next element (the one on the right), or NULL if 'p' |
473 | * already pointed to the last element of the listpack. */ |
474 | unsigned char *lpNext(unsigned char *lp, unsigned char *p) { |
475 | assert(p); |
476 | p = lpSkip(p); |
477 | if (p[0] == LP_EOF) return NULL; |
478 | lpAssertValidEntry(lp, lpBytes(lp), p); |
479 | return p; |
480 | } |
481 | |
482 | /* If 'p' points to an element of the listpack, calling lpPrev() will return |
483 | * the pointer to the previous element (the one on the left), or NULL if 'p' |
484 | * already pointed to the first element of the listpack. */ |
485 | unsigned char *lpPrev(unsigned char *lp, unsigned char *p) { |
486 | assert(p); |
487 | if (p-lp == LP_HDR_SIZE) return NULL; |
488 | p--; /* Seek the first backlen byte of the last element. */ |
489 | uint64_t prevlen = lpDecodeBacklen(p); |
490 | prevlen += lpEncodeBacklen(NULL,prevlen); |
491 | p -= prevlen-1; /* Seek the first byte of the previous entry. */ |
492 | lpAssertValidEntry(lp, lpBytes(lp), p); |
493 | return p; |
494 | } |
495 | |
496 | /* Return a pointer to the first element of the listpack, or NULL if the |
497 | * listpack has no elements. */ |
498 | unsigned char *lpFirst(unsigned char *lp) { |
499 | unsigned char *p = lp + LP_HDR_SIZE; /* Skip the header. */ |
500 | if (p[0] == LP_EOF) return NULL; |
501 | lpAssertValidEntry(lp, lpBytes(lp), p); |
502 | return p; |
503 | } |
504 | |
505 | /* Return a pointer to the last element of the listpack, or NULL if the |
506 | * listpack has no elements. */ |
507 | unsigned char *lpLast(unsigned char *lp) { |
508 | unsigned char *p = lp+lpGetTotalBytes(lp)-1; /* Seek EOF element. */ |
509 | return lpPrev(lp,p); /* Will return NULL if EOF is the only element. */ |
510 | } |
511 | |
512 | /* Return the number of elements inside the listpack. This function attempts |
513 | * to use the cached value when within range, otherwise a full scan is |
514 | * needed. As a side effect of calling this function, the listpack header |
515 | * could be modified, because if the count is found to be already within |
516 | * the 'numele' header field range, the new value is set. */ |
517 | unsigned long lpLength(unsigned char *lp) { |
518 | uint32_t numele = lpGetNumElements(lp); |
519 | if (numele != LP_HDR_NUMELE_UNKNOWN) return numele; |
520 | |
521 | /* Too many elements inside the listpack. We need to scan in order |
522 | * to get the total number. */ |
523 | uint32_t count = 0; |
524 | unsigned char *p = lpFirst(lp); |
525 | while(p) { |
526 | count++; |
527 | p = lpNext(lp,p); |
528 | } |
529 | |
530 | /* If the count is again within range of the header numele field, |
531 | * set it. */ |
532 | if (count < LP_HDR_NUMELE_UNKNOWN) lpSetNumElements(lp,count); |
533 | return count; |
534 | } |
535 | |
536 | /* Return the listpack element pointed by 'p'. |
537 | * |
538 | * The function changes behavior depending on the passed 'intbuf' value. |
539 | * Specifically, if 'intbuf' is NULL: |
540 | * |
541 | * If the element is internally encoded as an integer, the function returns |
542 | * NULL and populates the integer value by reference in 'count'. Otherwise if |
543 | * the element is encoded as a string a pointer to the string (pointing inside |
544 | * the listpack itself) is returned, and 'count' is set to the length of the |
545 | * string. |
546 | * |
547 | * If instead 'intbuf' points to a buffer passed by the caller, that must be |
548 | * at least LP_INTBUF_SIZE bytes, the function always returns the element as |
549 | * it was a string (returning the pointer to the string and setting the |
550 | * 'count' argument to the string length by reference). However if the element |
551 | * is encoded as an integer, the 'intbuf' buffer is used in order to store |
552 | * the string representation. |
553 | * |
554 | * The user should use one or the other form depending on what the value will |
555 | * be used for. If there is immediate usage for an integer value returned |
556 | * by the function, than to pass a buffer (and convert it back to a number) |
557 | * is of course useless. |
558 | * |
559 | * If 'entry_size' is not NULL, *entry_size is set to the entry length of the |
560 | * listpack element pointed by 'p'. This includes the encoding bytes, length |
561 | * bytes, the element data itself, and the backlen bytes. |
562 | * |
563 | * If the function is called against a badly encoded ziplist, so that there |
564 | * is no valid way to parse it, the function returns like if there was an |
565 | * integer encoded with value 12345678900000000 + <unrecognized byte>, this may |
566 | * be an hint to understand that something is wrong. To crash in this case is |
567 | * not sensible because of the different requirements of the application using |
568 | * this lib. |
569 | * |
570 | * Similarly, there is no error returned since the listpack normally can be |
571 | * assumed to be valid, so that would be a very high API cost. */ |
572 | static inline unsigned char *lpGetWithSize(unsigned char *p, int64_t *count, unsigned char *intbuf, uint64_t *entry_size) { |
573 | int64_t val; |
574 | uint64_t uval, negstart, negmax; |
575 | |
576 | assert(p); /* assertion for valgrind (avoid NPD) */ |
577 | if (LP_ENCODING_IS_7BIT_UINT(p[0])) { |
578 | negstart = UINT64_MAX; /* 7 bit ints are always positive. */ |
579 | negmax = 0; |
580 | uval = p[0] & 0x7f; |
581 | if (entry_size) *entry_size = LP_ENCODING_7BIT_UINT_ENTRY_SIZE; |
582 | } else if (LP_ENCODING_IS_6BIT_STR(p[0])) { |
583 | *count = LP_ENCODING_6BIT_STR_LEN(p); |
584 | if (entry_size) *entry_size = 1 + *count + lpEncodeBacklen(NULL, *count + 1); |
585 | return p+1; |
586 | } else if (LP_ENCODING_IS_13BIT_INT(p[0])) { |
587 | uval = ((p[0]&0x1f)<<8) | p[1]; |
588 | negstart = (uint64_t)1<<12; |
589 | negmax = 8191; |
590 | if (entry_size) *entry_size = LP_ENCODING_13BIT_INT_ENTRY_SIZE; |
591 | } else if (LP_ENCODING_IS_16BIT_INT(p[0])) { |
592 | uval = (uint64_t)p[1] | |
593 | (uint64_t)p[2]<<8; |
594 | negstart = (uint64_t)1<<15; |
595 | negmax = UINT16_MAX; |
596 | if (entry_size) *entry_size = LP_ENCODING_16BIT_INT_ENTRY_SIZE; |
597 | } else if (LP_ENCODING_IS_24BIT_INT(p[0])) { |
598 | uval = (uint64_t)p[1] | |
599 | (uint64_t)p[2]<<8 | |
600 | (uint64_t)p[3]<<16; |
601 | negstart = (uint64_t)1<<23; |
602 | negmax = UINT32_MAX>>8; |
603 | if (entry_size) *entry_size = LP_ENCODING_24BIT_INT_ENTRY_SIZE; |
604 | } else if (LP_ENCODING_IS_32BIT_INT(p[0])) { |
605 | uval = (uint64_t)p[1] | |
606 | (uint64_t)p[2]<<8 | |
607 | (uint64_t)p[3]<<16 | |
608 | (uint64_t)p[4]<<24; |
609 | negstart = (uint64_t)1<<31; |
610 | negmax = UINT32_MAX; |
611 | if (entry_size) *entry_size = LP_ENCODING_32BIT_INT_ENTRY_SIZE; |
612 | } else if (LP_ENCODING_IS_64BIT_INT(p[0])) { |
613 | uval = (uint64_t)p[1] | |
614 | (uint64_t)p[2]<<8 | |
615 | (uint64_t)p[3]<<16 | |
616 | (uint64_t)p[4]<<24 | |
617 | (uint64_t)p[5]<<32 | |
618 | (uint64_t)p[6]<<40 | |
619 | (uint64_t)p[7]<<48 | |
620 | (uint64_t)p[8]<<56; |
621 | negstart = (uint64_t)1<<63; |
622 | negmax = UINT64_MAX; |
623 | if (entry_size) *entry_size = LP_ENCODING_64BIT_INT_ENTRY_SIZE; |
624 | } else if (LP_ENCODING_IS_12BIT_STR(p[0])) { |
625 | *count = LP_ENCODING_12BIT_STR_LEN(p); |
626 | if (entry_size) *entry_size = 2 + *count + lpEncodeBacklen(NULL, *count + 2); |
627 | return p+2; |
628 | } else if (LP_ENCODING_IS_32BIT_STR(p[0])) { |
629 | *count = LP_ENCODING_32BIT_STR_LEN(p); |
630 | if (entry_size) *entry_size = 5 + *count + lpEncodeBacklen(NULL, *count + 5); |
631 | return p+5; |
632 | } else { |
633 | uval = 12345678900000000ULL + p[0]; |
634 | negstart = UINT64_MAX; |
635 | negmax = 0; |
636 | } |
637 | |
638 | /* We reach this code path only for integer encodings. |
639 | * Convert the unsigned value to the signed one using two's complement |
640 | * rule. */ |
641 | if (uval >= negstart) { |
642 | /* This three steps conversion should avoid undefined behaviors |
643 | * in the unsigned -> signed conversion. */ |
644 | uval = negmax-uval; |
645 | val = uval; |
646 | val = -val-1; |
647 | } else { |
648 | val = uval; |
649 | } |
650 | |
651 | /* Return the string representation of the integer or the value itself |
652 | * depending on intbuf being NULL or not. */ |
653 | if (intbuf) { |
654 | *count = ll2string((char*)intbuf,LP_INTBUF_SIZE,(long long)val); |
655 | return intbuf; |
656 | } else { |
657 | *count = val; |
658 | return NULL; |
659 | } |
660 | } |
661 | |
662 | unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) { |
663 | return lpGetWithSize(p, count, intbuf, NULL); |
664 | } |
665 | |
666 | /* This is just a wrapper to lpGet() that is able to get entry value directly. |
667 | * When the function returns NULL, it populates the integer value by reference in 'lval'. |
668 | * Otherwise if the element is encoded as a string a pointer to the string (pointing |
669 | * inside the listpack itself) is returned, and 'slen' is set to the length of the |
670 | * string. */ |
671 | unsigned char *lpGetValue(unsigned char *p, unsigned int *slen, long long *lval) { |
672 | unsigned char *vstr; |
673 | int64_t ele_len; |
674 | |
675 | vstr = lpGet(p, &ele_len, NULL); |
676 | if (vstr) { |
677 | *slen = ele_len; |
678 | } else { |
679 | *lval = ele_len; |
680 | } |
681 | return vstr; |
682 | } |
683 | |
684 | /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries |
685 | * between every comparison. Returns NULL when the field could not be found. */ |
686 | unsigned char *lpFind(unsigned char *lp, unsigned char *p, unsigned char *s, |
687 | uint32_t slen, unsigned int skip) { |
688 | int skipcnt = 0; |
689 | unsigned char vencoding = 0; |
690 | unsigned char *value; |
691 | int64_t ll, vll; |
692 | uint64_t entry_size = 123456789; /* initialized to avoid warning. */ |
693 | uint32_t lp_bytes = lpBytes(lp); |
694 | |
695 | assert(p); |
696 | while (p) { |
697 | if (skipcnt == 0) { |
698 | value = lpGetWithSize(p, &ll, NULL, &entry_size); |
699 | if (value) { |
700 | /* check the value doesn't reach outside the listpack before accessing it */ |
701 | assert(p >= lp + LP_HDR_SIZE && p + entry_size < lp + lp_bytes); |
702 | if (slen == ll && memcmp(value, s, slen) == 0) { |
703 | return p; |
704 | } |
705 | } else { |
706 | /* Find out if the searched field can be encoded. Note that |
707 | * we do it only the first time, once done vencoding is set |
708 | * to non-zero and vll is set to the integer value. */ |
709 | if (vencoding == 0) { |
710 | /* If the entry can be encoded as integer we set it to |
711 | * 1, else set it to UCHAR_MAX, so that we don't retry |
712 | * again the next time. */ |
713 | if (slen >= 32 || slen == 0 || !lpStringToInt64((const char*)s, slen, &vll)) { |
714 | vencoding = UCHAR_MAX; |
715 | } else { |
716 | vencoding = 1; |
717 | } |
718 | } |
719 | |
720 | /* Compare current entry with specified entry, do it only |
721 | * if vencoding != UCHAR_MAX because if there is no encoding |
722 | * possible for the field it can't be a valid integer. */ |
723 | if (vencoding != UCHAR_MAX && ll == vll) { |
724 | return p; |
725 | } |
726 | } |
727 | |
728 | /* Reset skip count */ |
729 | skipcnt = skip; |
730 | p += entry_size; |
731 | } else { |
732 | /* Skip entry */ |
733 | skipcnt--; |
734 | |
735 | /* Move to next entry, avoid use `lpNext` due to `ASSERT_INTEGRITY` in |
736 | * `lpNext` will call `lpBytes`, will cause performance degradation */ |
737 | p = lpSkip(p); |
738 | } |
739 | |
740 | /* The next call to lpGetWithSize could read at most 8 bytes past `p` |
741 | * We use the slower validation call only when necessary. */ |
742 | if (p + 8 >= lp + lp_bytes) |
743 | lpAssertValidEntry(lp, lp_bytes, p); |
744 | else |
745 | assert(p >= lp + LP_HDR_SIZE && p < lp + lp_bytes); |
746 | if (p[0] == LP_EOF) break; |
747 | } |
748 | |
749 | return NULL; |
750 | } |
751 | |
752 | /* Insert, delete or replace the specified string element 'elestr' of length |
753 | * 'size' or integer element 'eleint' at the specified position 'p', with 'p' |
754 | * being a listpack element pointer obtained with lpFirst(), lpLast(), lpNext(), |
755 | * lpPrev() or lpSeek(). |
756 | * |
757 | * The element is inserted before, after, or replaces the element pointed |
758 | * by 'p' depending on the 'where' argument, that can be LP_BEFORE, LP_AFTER |
759 | * or LP_REPLACE. |
760 | * |
761 | * If both 'elestr' and `eleint` are NULL, the function removes the element |
762 | * pointed by 'p' instead of inserting one. |
763 | * If `eleint` is non-NULL, 'size' is the length of 'eleint', the function insert |
764 | * or replace with a 64 bit integer, which is stored in the 'eleint' buffer. |
765 | * If 'elestr` is non-NULL, 'size' is the length of 'elestr', the function insert |
766 | * or replace with a string, which is stored in the 'elestr' buffer. |
767 | * |
768 | * Returns NULL on out of memory or when the listpack total length would exceed |
769 | * the max allowed size of 2^32-1, otherwise the new pointer to the listpack |
770 | * holding the new element is returned (and the old pointer passed is no longer |
771 | * considered valid) |
772 | * |
773 | * If 'newp' is not NULL, at the end of a successful call '*newp' will be set |
774 | * to the address of the element just added, so that it will be possible to |
775 | * continue an interaction with lpNext() and lpPrev(). |
776 | * |
777 | * For deletion operations (both 'elestr' and 'eleint' set to NULL) 'newp' is |
778 | * set to the next element, on the right of the deleted one, or to NULL if the |
779 | * deleted element was the last one. */ |
780 | unsigned char *lpInsert(unsigned char *lp, unsigned char *elestr, unsigned char *eleint, |
781 | uint32_t size, unsigned char *p, int where, unsigned char **newp) |
782 | { |
783 | unsigned char intenc[LP_MAX_INT_ENCODING_LEN]; |
784 | unsigned char backlen[LP_MAX_BACKLEN_SIZE]; |
785 | |
786 | uint64_t enclen; /* The length of the encoded element. */ |
787 | int delete = (elestr == NULL && eleint == NULL); |
788 | |
789 | /* when deletion, it is conceptually replacing the element with a |
790 | * zero-length element. So whatever we get passed as 'where', set |
791 | * it to LP_REPLACE. */ |
792 | if (delete) where = LP_REPLACE; |
793 | |
794 | /* If we need to insert after the current element, we just jump to the |
795 | * next element (that could be the EOF one) and handle the case of |
796 | * inserting before. So the function will actually deal with just two |
797 | * cases: LP_BEFORE and LP_REPLACE. */ |
798 | if (where == LP_AFTER) { |
799 | p = lpSkip(p); |
800 | where = LP_BEFORE; |
801 | ASSERT_INTEGRITY(lp, p); |
802 | } |
803 | |
804 | /* Store the offset of the element 'p', so that we can obtain its |
805 | * address again after a reallocation. */ |
806 | unsigned long poff = p-lp; |
807 | |
808 | int enctype; |
809 | if (elestr) { |
810 | /* Calling lpEncodeGetType() results into the encoded version of the |
811 | * element to be stored into 'intenc' in case it is representable as |
812 | * an integer: in that case, the function returns LP_ENCODING_INT. |
813 | * Otherwise if LP_ENCODING_STR is returned, we'll have to call |
814 | * lpEncodeString() to actually write the encoded string on place later. |
815 | * |
816 | * Whatever the returned encoding is, 'enclen' is populated with the |
817 | * length of the encoded element. */ |
818 | enctype = lpEncodeGetType(elestr,size,intenc,&enclen); |
819 | if (enctype == LP_ENCODING_INT) eleint = intenc; |
820 | } else if (eleint) { |
821 | enctype = LP_ENCODING_INT; |
822 | enclen = size; /* 'size' is the length of the encoded integer element. */ |
823 | } else { |
824 | enctype = -1; |
825 | enclen = 0; |
826 | } |
827 | |
828 | /* We need to also encode the backward-parsable length of the element |
829 | * and append it to the end: this allows to traverse the listpack from |
830 | * the end to the start. */ |
831 | unsigned long backlen_size = (!delete) ? lpEncodeBacklen(backlen,enclen) : 0; |
832 | uint64_t old_listpack_bytes = lpGetTotalBytes(lp); |
833 | uint32_t replaced_len = 0; |
834 | if (where == LP_REPLACE) { |
835 | replaced_len = lpCurrentEncodedSizeUnsafe(p); |
836 | replaced_len += lpEncodeBacklen(NULL,replaced_len); |
837 | ASSERT_INTEGRITY_LEN(lp, p, replaced_len); |
838 | } |
839 | |
840 | uint64_t new_listpack_bytes = old_listpack_bytes + enclen + backlen_size |
841 | - replaced_len; |
842 | if (new_listpack_bytes > UINT32_MAX) return NULL; |
843 | |
844 | /* We now need to reallocate in order to make space or shrink the |
845 | * allocation (in case 'when' value is LP_REPLACE and the new element is |
846 | * smaller). However we do that before memmoving the memory to |
847 | * make room for the new element if the final allocation will get |
848 | * larger, or we do it after if the final allocation will get smaller. */ |
849 | |
850 | unsigned char *dst = lp + poff; /* May be updated after reallocation. */ |
851 | |
852 | /* Realloc before: we need more room. */ |
853 | if (new_listpack_bytes > old_listpack_bytes && |
854 | new_listpack_bytes > lp_malloc_size(lp)) { |
855 | if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL; |
856 | dst = lp + poff; |
857 | } |
858 | |
859 | /* Setup the listpack relocating the elements to make the exact room |
860 | * we need to store the new one. */ |
861 | if (where == LP_BEFORE) { |
862 | memmove(dst+enclen+backlen_size,dst,old_listpack_bytes-poff); |
863 | } else { /* LP_REPLACE. */ |
864 | long lendiff = (enclen+backlen_size)-replaced_len; |
865 | memmove(dst+replaced_len+lendiff, |
866 | dst+replaced_len, |
867 | old_listpack_bytes-poff-replaced_len); |
868 | } |
869 | |
870 | /* Realloc after: we need to free space. */ |
871 | if (new_listpack_bytes < old_listpack_bytes) { |
872 | if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL; |
873 | dst = lp + poff; |
874 | } |
875 | |
876 | /* Store the entry. */ |
877 | if (newp) { |
878 | *newp = dst; |
879 | /* In case of deletion, set 'newp' to NULL if the next element is |
880 | * the EOF element. */ |
881 | if (delete && dst[0] == LP_EOF) *newp = NULL; |
882 | } |
883 | if (!delete) { |
884 | if (enctype == LP_ENCODING_INT) { |
885 | memcpy(dst,eleint,enclen); |
886 | } else { |
887 | lpEncodeString(dst,elestr,size); |
888 | } |
889 | dst += enclen; |
890 | memcpy(dst,backlen,backlen_size); |
891 | dst += backlen_size; |
892 | } |
893 | |
894 | /* Update header. */ |
895 | if (where != LP_REPLACE || delete) { |
896 | uint32_t num_elements = lpGetNumElements(lp); |
897 | if (num_elements != LP_HDR_NUMELE_UNKNOWN) { |
898 | if (!delete) |
899 | lpSetNumElements(lp,num_elements+1); |
900 | else |
901 | lpSetNumElements(lp,num_elements-1); |
902 | } |
903 | } |
904 | lpSetTotalBytes(lp,new_listpack_bytes); |
905 | |
906 | #if 0 |
907 | /* This code path is normally disabled: what it does is to force listpack |
908 | * to return *always* a new pointer after performing some modification to |
909 | * the listpack, even if the previous allocation was enough. This is useful |
910 | * in order to spot bugs in code using listpacks: by doing so we can find |
911 | * if the caller forgets to set the new pointer where the listpack reference |
912 | * is stored, after an update. */ |
913 | unsigned char *oldlp = lp; |
914 | lp = lp_malloc(new_listpack_bytes); |
915 | memcpy(lp,oldlp,new_listpack_bytes); |
916 | if (newp) { |
917 | unsigned long offset = (*newp)-oldlp; |
918 | *newp = lp + offset; |
919 | } |
920 | /* Make sure the old allocation contains garbage. */ |
921 | memset(oldlp,'A',new_listpack_bytes); |
922 | lp_free(oldlp); |
923 | #endif |
924 | |
925 | return lp; |
926 | } |
927 | |
928 | /* This is just a wrapper for lpInsert() to directly use a string. */ |
929 | unsigned char *lpInsertString(unsigned char *lp, unsigned char *s, uint32_t slen, |
930 | unsigned char *p, int where, unsigned char **newp) |
931 | { |
932 | return lpInsert(lp, s, NULL, slen, p, where, newp); |
933 | } |
934 | |
935 | /* This is just a wrapper for lpInsert() to directly use a 64 bit integer |
936 | * instead of a string. */ |
937 | unsigned char *lpInsertInteger(unsigned char *lp, long long lval, unsigned char *p, int where, unsigned char **newp) { |
938 | uint64_t enclen; /* The length of the encoded element. */ |
939 | unsigned char intenc[LP_MAX_INT_ENCODING_LEN]; |
940 | |
941 | lpEncodeIntegerGetType(lval, intenc, &enclen); |
942 | return lpInsert(lp, NULL, intenc, enclen, p, where, newp); |
943 | } |
944 | |
945 | /* Append the specified element 's' of length 'slen' at the head of the listpack. */ |
946 | unsigned char *lpPrepend(unsigned char *lp, unsigned char *s, uint32_t slen) { |
947 | unsigned char *p = lpFirst(lp); |
948 | if (!p) return lpAppend(lp, s, slen); |
949 | return lpInsert(lp, s, NULL, slen, p, LP_BEFORE, NULL); |
950 | } |
951 | |
952 | /* Append the specified integer element 'lval' at the head of the listpack. */ |
953 | unsigned char *lpPrependInteger(unsigned char *lp, long long lval) { |
954 | unsigned char *p = lpFirst(lp); |
955 | if (!p) return lpAppendInteger(lp, lval); |
956 | return lpInsertInteger(lp, lval, p, LP_BEFORE, NULL); |
957 | } |
958 | |
959 | /* Append the specified element 'ele' of length 'size' at the end of the |
960 | * listpack. It is implemented in terms of lpInsert(), so the return value is |
961 | * the same as lpInsert(). */ |
962 | unsigned char *lpAppend(unsigned char *lp, unsigned char *ele, uint32_t size) { |
963 | uint64_t listpack_bytes = lpGetTotalBytes(lp); |
964 | unsigned char *eofptr = lp + listpack_bytes - 1; |
965 | return lpInsert(lp,ele,NULL,size,eofptr,LP_BEFORE,NULL); |
966 | } |
967 | |
968 | /* Append the specified integer element 'lval' at the end of the listpack. */ |
969 | unsigned char *lpAppendInteger(unsigned char *lp, long long lval) { |
970 | uint64_t listpack_bytes = lpGetTotalBytes(lp); |
971 | unsigned char *eofptr = lp + listpack_bytes - 1; |
972 | return lpInsertInteger(lp, lval, eofptr, LP_BEFORE, NULL); |
973 | } |
974 | |
975 | /* This is just a wrapper for lpInsert() to directly use a string to replace |
976 | * the current element. The function returns the new listpack as return |
977 | * value, and also updates the current cursor by updating '*p'. */ |
978 | unsigned char *lpReplace(unsigned char *lp, unsigned char **p, unsigned char *s, uint32_t slen) { |
979 | return lpInsert(lp, s, NULL, slen, *p, LP_REPLACE, p); |
980 | } |
981 | |
982 | /* This is just a wrapper for lpInsertInteger() to directly use a 64 bit integer |
983 | * instead of a string to replace the current element. The function returns |
984 | * the new listpack as return value, and also updates the current cursor |
985 | * by updating '*p'. */ |
986 | unsigned char *lpReplaceInteger(unsigned char *lp, unsigned char **p, long long lval) { |
987 | return lpInsertInteger(lp, lval, *p, LP_REPLACE, p); |
988 | } |
989 | |
990 | /* Remove the element pointed by 'p', and return the resulting listpack. |
991 | * If 'newp' is not NULL, the next element pointer (to the right of the |
992 | * deleted one) is returned by reference. If the deleted element was the |
993 | * last one, '*newp' is set to NULL. */ |
994 | unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp) { |
995 | return lpInsert(lp,NULL,NULL,0,p,LP_REPLACE,newp); |
996 | } |
997 | |
998 | /* Delete a range of entries from the listpack start with the element pointed by 'p'. */ |
999 | unsigned char *lpDeleteRangeWithEntry(unsigned char *lp, unsigned char **p, unsigned long num) { |
1000 | size_t bytes = lpBytes(lp); |
1001 | unsigned long deleted = 0; |
1002 | unsigned char *eofptr = lp + bytes - 1; |
1003 | unsigned char *first, *tail; |
1004 | first = tail = *p; |
1005 | |
1006 | if (num == 0) return lp; /* Nothing to delete, return ASAP. */ |
1007 | |
1008 | /* Find the next entry to the last entry that needs to be deleted. |
1009 | * lpLength may be unreliable due to corrupt data, so we cannot |
1010 | * treat 'num' as the number of elements to be deleted. */ |
1011 | while (num--) { |
1012 | deleted++; |
1013 | tail = lpSkip(tail); |
1014 | if (tail[0] == LP_EOF) break; |
1015 | lpAssertValidEntry(lp, bytes, tail); |
1016 | } |
1017 | |
1018 | /* Store the offset of the element 'first', so that we can obtain its |
1019 | * address again after a reallocation. */ |
1020 | unsigned long poff = first-lp; |
1021 | |
1022 | /* Move tail to the front of the listpack */ |
1023 | memmove(first, tail, eofptr - tail + 1); |
1024 | lpSetTotalBytes(lp, bytes - (tail - first)); |
1025 | uint32_t numele = lpGetNumElements(lp); |
1026 | if (numele != LP_HDR_NUMELE_UNKNOWN) |
1027 | lpSetNumElements(lp, numele-deleted); |
1028 | lp = lpShrinkToFit(lp); |
1029 | |
1030 | /* Store the entry. */ |
1031 | *p = lp+poff; |
1032 | if ((*p)[0] == LP_EOF) *p = NULL; |
1033 | |
1034 | return lp; |
1035 | } |
1036 | |
1037 | /* Delete a range of entries from the listpack. */ |
1038 | unsigned char *lpDeleteRange(unsigned char *lp, long index, unsigned long num) { |
1039 | unsigned char *p; |
1040 | uint32_t numele = lpGetNumElements(lp); |
1041 | |
1042 | if (num == 0) return lp; /* Nothing to delete, return ASAP. */ |
1043 | if ((p = lpSeek(lp, index)) == NULL) return lp; |
1044 | |
1045 | /* If we know we're gonna delete beyond the end of the listpack, we can just move |
1046 | * the EOF marker, and there's no need to iterate through the entries, |
1047 | * but if we can't be sure how many entries there are, we rather avoid calling lpLength |
1048 | * since that means an additional iteration on all elements. |
1049 | * |
1050 | * Note that index could overflow, but we use the value after seek, so when we |
1051 | * use it no overflow happens. */ |
1052 | if (numele != LP_HDR_NUMELE_UNKNOWN && index < 0) index = (long)numele + index; |
1053 | if (numele != LP_HDR_NUMELE_UNKNOWN && (numele - (unsigned long)index) <= num) { |
1054 | p[0] = LP_EOF; |
1055 | lpSetTotalBytes(lp, p - lp + 1); |
1056 | lpSetNumElements(lp, index); |
1057 | lp = lpShrinkToFit(lp); |
1058 | } else { |
1059 | lp = lpDeleteRangeWithEntry(lp, &p, num); |
1060 | } |
1061 | |
1062 | return lp; |
1063 | } |
1064 | |
1065 | /* Merge listpacks 'first' and 'second' by appending 'second' to 'first'. |
1066 | * |
1067 | * NOTE: The larger listpack is reallocated to contain the new merged listpack. |
1068 | * Either 'first' or 'second' can be used for the result. The parameter not |
1069 | * used will be free'd and set to NULL. |
1070 | * |
1071 | * After calling this function, the input parameters are no longer valid since |
1072 | * they are changed and free'd in-place. |
1073 | * |
1074 | * The result listpack is the contents of 'first' followed by 'second'. |
1075 | * |
1076 | * On failure: returns NULL if the merge is impossible. |
1077 | * On success: returns the merged listpack (which is expanded version of either |
1078 | * 'first' or 'second', also frees the other unused input listpack, and sets the |
1079 | * input listpack argument equal to newly reallocated listpack return value. */ |
1080 | unsigned char *lpMerge(unsigned char **first, unsigned char **second) { |
1081 | /* If any params are null, we can't merge, so NULL. */ |
1082 | if (first == NULL || *first == NULL || second == NULL || *second == NULL) |
1083 | return NULL; |
1084 | |
1085 | /* Can't merge same list into itself. */ |
1086 | if (*first == *second) |
1087 | return NULL; |
1088 | |
1089 | size_t first_bytes = lpBytes(*first); |
1090 | unsigned long first_len = lpLength(*first); |
1091 | |
1092 | size_t second_bytes = lpBytes(*second); |
1093 | unsigned long second_len = lpLength(*second); |
1094 | |
1095 | int append; |
1096 | unsigned char *source, *target; |
1097 | size_t target_bytes, source_bytes; |
1098 | /* Pick the largest listpack so we can resize easily in-place. |
1099 | * We must also track if we are now appending or prepending to |
1100 | * the target listpack. */ |
1101 | if (first_bytes >= second_bytes) { |
1102 | /* retain first, append second to first. */ |
1103 | target = *first; |
1104 | target_bytes = first_bytes; |
1105 | source = *second; |
1106 | source_bytes = second_bytes; |
1107 | append = 1; |
1108 | } else { |
1109 | /* else, retain second, prepend first to second. */ |
1110 | target = *second; |
1111 | target_bytes = second_bytes; |
1112 | source = *first; |
1113 | source_bytes = first_bytes; |
1114 | append = 0; |
1115 | } |
1116 | |
1117 | /* Calculate final bytes (subtract one pair of metadata) */ |
1118 | unsigned long long lpbytes = (unsigned long long)first_bytes + second_bytes - LP_HDR_SIZE - 1; |
1119 | assert(lpbytes < UINT32_MAX); /* larger values can't be stored */ |
1120 | unsigned long lplength = first_len + second_len; |
1121 | |
1122 | /* Combined lp length should be limited within UINT16_MAX */ |
1123 | lplength = lplength < UINT16_MAX ? lplength : UINT16_MAX; |
1124 | |
1125 | /* Extend target to new lpbytes then append or prepend source. */ |
1126 | target = zrealloc(target, lpbytes); |
1127 | if (append) { |
1128 | /* append == appending to target */ |
1129 | /* Copy source after target (copying over original [END]): |
1130 | * [TARGET - END, SOURCE - HEADER] */ |
1131 | memcpy(target + target_bytes - 1, |
1132 | source + LP_HDR_SIZE, |
1133 | source_bytes - LP_HDR_SIZE); |
1134 | } else { |
1135 | /* !append == prepending to target */ |
1136 | /* Move target *contents* exactly size of (source - [END]), |
1137 | * then copy source into vacated space (source - [END]): |
1138 | * [SOURCE - END, TARGET - HEADER] */ |
1139 | memmove(target + source_bytes - 1, |
1140 | target + LP_HDR_SIZE, |
1141 | target_bytes - LP_HDR_SIZE); |
1142 | memcpy(target, source, source_bytes - 1); |
1143 | } |
1144 | |
1145 | lpSetNumElements(target, lplength); |
1146 | lpSetTotalBytes(target, lpbytes); |
1147 | |
1148 | /* Now free and NULL out what we didn't realloc */ |
1149 | if (append) { |
1150 | zfree(*second); |
1151 | *second = NULL; |
1152 | *first = target; |
1153 | } else { |
1154 | zfree(*first); |
1155 | *first = NULL; |
1156 | *second = target; |
1157 | } |
1158 | |
1159 | return target; |
1160 | } |
1161 | |
1162 | /* Return the total number of bytes the listpack is composed of. */ |
1163 | size_t lpBytes(unsigned char *lp) { |
1164 | return lpGetTotalBytes(lp); |
1165 | } |
1166 | |
1167 | /* Seek the specified element and returns the pointer to the seeked element. |
1168 | * Positive indexes specify the zero-based element to seek from the head to |
1169 | * the tail, negative indexes specify elements starting from the tail, where |
1170 | * -1 means the last element, -2 the penultimate and so forth. If the index |
1171 | * is out of range, NULL is returned. */ |
1172 | unsigned char *lpSeek(unsigned char *lp, long index) { |
1173 | int forward = 1; /* Seek forward by default. */ |
1174 | |
1175 | /* We want to seek from left to right or the other way around |
1176 | * depending on the listpack length and the element position. |
1177 | * However if the listpack length cannot be obtained in constant time, |
1178 | * we always seek from left to right. */ |
1179 | uint32_t numele = lpGetNumElements(lp); |
1180 | if (numele != LP_HDR_NUMELE_UNKNOWN) { |
1181 | if (index < 0) index = (long)numele+index; |
1182 | if (index < 0) return NULL; /* Index still < 0 means out of range. */ |
1183 | if (index >= (long)numele) return NULL; /* Out of range the other side. */ |
1184 | /* We want to scan right-to-left if the element we are looking for |
1185 | * is past the half of the listpack. */ |
1186 | if (index > (long)numele/2) { |
1187 | forward = 0; |
1188 | /* Right to left scanning always expects a negative index. Convert |
1189 | * our index to negative form. */ |
1190 | index -= numele; |
1191 | } |
1192 | } else { |
1193 | /* If the listpack length is unspecified, for negative indexes we |
1194 | * want to always scan right-to-left. */ |
1195 | if (index < 0) forward = 0; |
1196 | } |
1197 | |
1198 | /* Forward and backward scanning is trivially based on lpNext()/lpPrev(). */ |
1199 | if (forward) { |
1200 | unsigned char *ele = lpFirst(lp); |
1201 | while (index > 0 && ele) { |
1202 | ele = lpNext(lp,ele); |
1203 | index--; |
1204 | } |
1205 | return ele; |
1206 | } else { |
1207 | unsigned char *ele = lpLast(lp); |
1208 | while (index < -1 && ele) { |
1209 | ele = lpPrev(lp,ele); |
1210 | index++; |
1211 | } |
1212 | return ele; |
1213 | } |
1214 | } |
1215 | |
1216 | /* Same as lpFirst but without validation assert, to be used right before lpValidateNext. */ |
1217 | unsigned char *lpValidateFirst(unsigned char *lp) { |
1218 | unsigned char *p = lp + LP_HDR_SIZE; /* Skip the header. */ |
1219 | if (p[0] == LP_EOF) return NULL; |
1220 | return p; |
1221 | } |
1222 | |
1223 | /* Validate the integrity of a single listpack entry and move to the next one. |
1224 | * The input argument 'pp' is a reference to the current record and is advanced on exit. |
1225 | * Returns 1 if valid, 0 if invalid. */ |
1226 | int lpValidateNext(unsigned char *lp, unsigned char **pp, size_t lpbytes) { |
1227 | #define OUT_OF_RANGE(p) ( \ |
1228 | (p) < lp + LP_HDR_SIZE || \ |
1229 | (p) > lp + lpbytes - 1) |
1230 | unsigned char *p = *pp; |
1231 | if (!p) |
1232 | return 0; |
1233 | |
1234 | /* Before accessing p, make sure it's valid. */ |
1235 | if (OUT_OF_RANGE(p)) |
1236 | return 0; |
1237 | |
1238 | if (*p == LP_EOF) { |
1239 | *pp = NULL; |
1240 | return 1; |
1241 | } |
1242 | |
1243 | /* check that we can read the encoded size */ |
1244 | uint32_t lenbytes = lpCurrentEncodedSizeBytes(p); |
1245 | if (!lenbytes) |
1246 | return 0; |
1247 | |
1248 | /* make sure the encoded entry length doesn't reach outside the edge of the listpack */ |
1249 | if (OUT_OF_RANGE(p + lenbytes)) |
1250 | return 0; |
1251 | |
1252 | /* get the entry length and encoded backlen. */ |
1253 | unsigned long entrylen = lpCurrentEncodedSizeUnsafe(p); |
1254 | unsigned long encodedBacklen = lpEncodeBacklen(NULL,entrylen); |
1255 | entrylen += encodedBacklen; |
1256 | |
1257 | /* make sure the entry doesn't reach outside the edge of the listpack */ |
1258 | if (OUT_OF_RANGE(p + entrylen)) |
1259 | return 0; |
1260 | |
1261 | /* move to the next entry */ |
1262 | p += entrylen; |
1263 | |
1264 | /* make sure the encoded length at the end patches the one at the beginning. */ |
1265 | uint64_t prevlen = lpDecodeBacklen(p-1); |
1266 | if (prevlen + encodedBacklen != entrylen) |
1267 | return 0; |
1268 | |
1269 | *pp = p; |
1270 | return 1; |
1271 | #undef OUT_OF_RANGE |
1272 | } |
1273 | |
1274 | /* Validate that the entry doesn't reach outside the listpack allocation. */ |
1275 | static inline void lpAssertValidEntry(unsigned char* lp, size_t lpbytes, unsigned char *p) { |
1276 | assert(lpValidateNext(lp, &p, lpbytes)); |
1277 | } |
1278 | |
1279 | /* Validate the integrity of the data structure. |
1280 | * when `deep` is 0, only the integrity of the header is validated. |
1281 | * when `deep` is 1, we scan all the entries one by one. */ |
1282 | int lpValidateIntegrity(unsigned char *lp, size_t size, int deep, |
1283 | listpackValidateEntryCB entry_cb, void *cb_userdata) { |
1284 | /* Check that we can actually read the header. (and EOF) */ |
1285 | if (size < LP_HDR_SIZE + 1) |
1286 | return 0; |
1287 | |
1288 | /* Check that the encoded size in the header must match the allocated size. */ |
1289 | size_t bytes = lpGetTotalBytes(lp); |
1290 | if (bytes != size) |
1291 | return 0; |
1292 | |
1293 | /* The last byte must be the terminator. */ |
1294 | if (lp[size-1] != LP_EOF) |
1295 | return 0; |
1296 | |
1297 | if (!deep) |
1298 | return 1; |
1299 | |
1300 | /* Validate the individual entries. */ |
1301 | uint32_t count = 0; |
1302 | uint32_t numele = lpGetNumElements(lp); |
1303 | unsigned char *p = lp + LP_HDR_SIZE; |
1304 | while(p && p[0] != LP_EOF) { |
1305 | unsigned char *prev = p; |
1306 | |
1307 | /* Validate this entry and move to the next entry in advance |
1308 | * to avoid callback crash due to corrupt listpack. */ |
1309 | if (!lpValidateNext(lp, &p, bytes)) |
1310 | return 0; |
1311 | |
1312 | /* Optionally let the caller validate the entry too. */ |
1313 | if (entry_cb && !entry_cb(prev, numele, cb_userdata)) |
1314 | return 0; |
1315 | |
1316 | count++; |
1317 | } |
1318 | |
1319 | /* Make sure 'p' really does point to the end of the listpack. */ |
1320 | if (p != lp + size - 1) |
1321 | return 0; |
1322 | |
1323 | /* Check that the count in the header is correct */ |
1324 | if (numele != LP_HDR_NUMELE_UNKNOWN && numele != count) |
1325 | return 0; |
1326 | |
1327 | return 1; |
1328 | } |
1329 | |
1330 | /* Compare entry pointer to by 'p' with string 's' of length 'slen'. |
1331 | * Return 1 if equal. */ |
1332 | unsigned int lpCompare(unsigned char *p, unsigned char *s, uint32_t slen) { |
1333 | unsigned char *value; |
1334 | int64_t sz; |
1335 | if (p[0] == LP_EOF) return 0; |
1336 | |
1337 | value = lpGet(p, &sz, NULL); |
1338 | if (value) { |
1339 | return (slen == sz) && memcmp(value,s,slen) == 0; |
1340 | } else { |
1341 | /* We use lpStringToInt64() to get an integer representation of the |
1342 | * string 's' and compare it to 'sval', it's much faster than convert |
1343 | * integer to string and comparing. */ |
1344 | int64_t sval; |
1345 | if (lpStringToInt64((const char*)s, slen, &sval)) |
1346 | return sz == sval; |
1347 | } |
1348 | |
1349 | return 0; |
1350 | } |
1351 | |
1352 | /* uint compare for qsort */ |
1353 | static int uintCompare(const void *a, const void *b) { |
1354 | return (*(unsigned int *) a - *(unsigned int *) b); |
1355 | } |
1356 | |
1357 | /* Helper method to store a string into from val or lval into dest */ |
1358 | static inline void lpSaveValue(unsigned char *val, unsigned int len, int64_t lval, listpackEntry *dest) { |
1359 | dest->sval = val; |
1360 | dest->slen = len; |
1361 | dest->lval = lval; |
1362 | } |
1363 | |
1364 | /* Randomly select a pair of key and value. |
1365 | * total_count is a pre-computed length/2 of the listpack (to avoid calls to lpLength) |
1366 | * 'key' and 'val' are used to store the result key value pair. |
1367 | * 'val' can be NULL if the value is not needed. */ |
1368 | void lpRandomPair(unsigned char *lp, unsigned long total_count, listpackEntry *key, listpackEntry *val) { |
1369 | unsigned char *p; |
1370 | |
1371 | /* Avoid div by zero on corrupt listpack */ |
1372 | assert(total_count); |
1373 | |
1374 | /* Generate even numbers, because listpack saved K-V pair */ |
1375 | int r = (rand() % total_count) * 2; |
1376 | assert((p = lpSeek(lp, r))); |
1377 | key->sval = lpGetValue(p, &(key->slen), &(key->lval)); |
1378 | |
1379 | if (!val) |
1380 | return; |
1381 | assert((p = lpNext(lp, p))); |
1382 | val->sval = lpGetValue(p, &(val->slen), &(val->lval)); |
1383 | } |
1384 | |
1385 | /* Randomly select count of key value pairs and store into 'keys' and |
1386 | * 'vals' args. The order of the picked entries is random, and the selections |
1387 | * are non-unique (repetitions are possible). |
1388 | * The 'vals' arg can be NULL in which case we skip these. */ |
1389 | void lpRandomPairs(unsigned char *lp, unsigned int count, listpackEntry *keys, listpackEntry *vals) { |
1390 | unsigned char *p, *key, *value; |
1391 | unsigned int klen = 0, vlen = 0; |
1392 | long long klval = 0, vlval = 0; |
1393 | |
1394 | /* Notice: the index member must be first due to the use in uintCompare */ |
1395 | typedef struct { |
1396 | unsigned int index; |
1397 | unsigned int order; |
1398 | } rand_pick; |
1399 | rand_pick *picks = zmalloc(sizeof(rand_pick)*count); |
1400 | unsigned int total_size = lpLength(lp)/2; |
1401 | |
1402 | /* Avoid div by zero on corrupt listpack */ |
1403 | assert(total_size); |
1404 | |
1405 | /* create a pool of random indexes (some may be duplicate). */ |
1406 | for (unsigned int i = 0; i < count; i++) { |
1407 | picks[i].index = (rand() % total_size) * 2; /* Generate even indexes */ |
1408 | /* keep track of the order we picked them */ |
1409 | picks[i].order = i; |
1410 | } |
1411 | |
1412 | /* sort by indexes. */ |
1413 | qsort(picks, count, sizeof(rand_pick), uintCompare); |
1414 | |
1415 | /* fetch the elements form the listpack into a output array respecting the original order. */ |
1416 | unsigned int lpindex = picks[0].index, pickindex = 0; |
1417 | p = lpSeek(lp, lpindex); |
1418 | while (p && pickindex < count) { |
1419 | key = lpGetValue(p, &klen, &klval); |
1420 | assert((p = lpNext(lp, p))); |
1421 | value = lpGetValue(p, &vlen, &vlval); |
1422 | while (pickindex < count && lpindex == picks[pickindex].index) { |
1423 | int storeorder = picks[pickindex].order; |
1424 | lpSaveValue(key, klen, klval, &keys[storeorder]); |
1425 | if (vals) |
1426 | lpSaveValue(value, vlen, vlval, &vals[storeorder]); |
1427 | pickindex++; |
1428 | } |
1429 | lpindex += 2; |
1430 | p = lpNext(lp, p); |
1431 | } |
1432 | |
1433 | zfree(picks); |
1434 | } |
1435 | |
1436 | /* Randomly select count of key value pairs and store into 'keys' and |
1437 | * 'vals' args. The selections are unique (no repetitions), and the order of |
1438 | * the picked entries is NOT-random. |
1439 | * The 'vals' arg can be NULL in which case we skip these. |
1440 | * The return value is the number of items picked which can be lower than the |
1441 | * requested count if the listpack doesn't hold enough pairs. */ |
1442 | unsigned int lpRandomPairsUnique(unsigned char *lp, unsigned int count, listpackEntry *keys, listpackEntry *vals) { |
1443 | unsigned char *p, *key; |
1444 | unsigned int klen = 0; |
1445 | long long klval = 0; |
1446 | unsigned int total_size = lpLength(lp)/2; |
1447 | unsigned int index = 0; |
1448 | if (count > total_size) |
1449 | count = total_size; |
1450 | |
1451 | /* To only iterate once, every time we try to pick a member, the probability |
1452 | * we pick it is the quotient of the count left we want to pick and the |
1453 | * count still we haven't visited in the dict, this way, we could make every |
1454 | * member be equally picked.*/ |
1455 | p = lpFirst(lp); |
1456 | unsigned int picked = 0, remaining = count; |
1457 | while (picked < count && p) { |
1458 | double randomDouble = ((double)rand()) / RAND_MAX; |
1459 | double threshold = ((double)remaining) / (total_size - index); |
1460 | if (randomDouble <= threshold) { |
1461 | key = lpGetValue(p, &klen, &klval); |
1462 | lpSaveValue(key, klen, klval, &keys[picked]); |
1463 | assert((p = lpNext(lp, p))); |
1464 | if (vals) { |
1465 | key = lpGetValue(p, &klen, &klval); |
1466 | lpSaveValue(key, klen, klval, &vals[picked]); |
1467 | } |
1468 | remaining--; |
1469 | picked++; |
1470 | } else { |
1471 | assert((p = lpNext(lp, p))); |
1472 | } |
1473 | p = lpNext(lp, p); |
1474 | index++; |
1475 | } |
1476 | return picked; |
1477 | } |
1478 | |
1479 | /* Print info of listpack which is used in debugCommand */ |
1480 | void lpRepr(unsigned char *lp) { |
1481 | unsigned char *p, *vstr; |
1482 | int64_t vlen; |
1483 | unsigned char intbuf[LP_INTBUF_SIZE]; |
1484 | int index = 0; |
1485 | |
1486 | printf("{total bytes %zu} {num entries %lu}\n" , lpBytes(lp), lpLength(lp)); |
1487 | |
1488 | p = lpFirst(lp); |
1489 | while(p) { |
1490 | uint32_t encoded_size_bytes = lpCurrentEncodedSizeBytes(p); |
1491 | uint32_t encoded_size = lpCurrentEncodedSizeUnsafe(p); |
1492 | unsigned long back_len = lpEncodeBacklen(NULL, encoded_size); |
1493 | printf( |
1494 | "{\n" |
1495 | "\taddr: 0x%08lx,\n" |
1496 | "\tindex: %2d,\n" |
1497 | "\toffset: %1lu,\n" |
1498 | "\thdr+entrylen+backlen: %2lu,\n" |
1499 | "\thdrlen: %3u,\n" |
1500 | "\tbacklen: %2lu,\n" |
1501 | "\tpayload: %1u\n" , |
1502 | (long unsigned)p, |
1503 | index, |
1504 | (unsigned long) (p-lp), |
1505 | encoded_size + back_len, |
1506 | encoded_size_bytes, |
1507 | back_len, |
1508 | encoded_size - encoded_size_bytes); |
1509 | printf("\tbytes: " ); |
1510 | for (unsigned int i = 0; i < (encoded_size + back_len); i++) { |
1511 | printf("%02x|" ,p[i]); |
1512 | } |
1513 | printf("\n" ); |
1514 | |
1515 | vstr = lpGet(p, &vlen, intbuf); |
1516 | printf("\t[str]" ); |
1517 | if (vlen > 40) { |
1518 | if (fwrite(vstr, 40, 1, stdout) == 0) perror("fwrite" ); |
1519 | printf("..." ); |
1520 | } else { |
1521 | if (fwrite(vstr, vlen, 1, stdout) == 0) perror("fwrite" ); |
1522 | } |
1523 | printf("\n}\n" ); |
1524 | index++; |
1525 | p = lpNext(lp, p); |
1526 | } |
1527 | printf("{end}\n\n" ); |
1528 | } |
1529 | |
1530 | #ifdef REDIS_TEST |
1531 | |
1532 | #include <sys/time.h> |
1533 | #include "adlist.h" |
1534 | #include "sds.h" |
1535 | #include "testhelp.h" |
1536 | |
1537 | #define UNUSED(x) (void)(x) |
1538 | #define TEST(name) printf("test — %s\n", name); |
1539 | |
1540 | char *mixlist[] = {"hello" , "foo" , "quux" , "1024" }; |
1541 | char *intlist[] = {"4294967296" , "-100" , "100" , "128000" , |
1542 | "non integer" , "much much longer non integer" }; |
1543 | |
1544 | static unsigned char *createList() { |
1545 | unsigned char *lp = lpNew(0); |
1546 | lp = lpAppend(lp, (unsigned char*)mixlist[1], strlen(mixlist[1])); |
1547 | lp = lpAppend(lp, (unsigned char*)mixlist[2], strlen(mixlist[2])); |
1548 | lp = lpPrepend(lp, (unsigned char*)mixlist[0], strlen(mixlist[0])); |
1549 | lp = lpAppend(lp, (unsigned char*)mixlist[3], strlen(mixlist[3])); |
1550 | return lp; |
1551 | } |
1552 | |
1553 | static unsigned char *createIntList() { |
1554 | unsigned char *lp = lpNew(0); |
1555 | lp = lpAppend(lp, (unsigned char*)intlist[2], strlen(intlist[2])); |
1556 | lp = lpAppend(lp, (unsigned char*)intlist[3], strlen(intlist[3])); |
1557 | lp = lpPrepend(lp, (unsigned char*)intlist[1], strlen(intlist[1])); |
1558 | lp = lpPrepend(lp, (unsigned char*)intlist[0], strlen(intlist[0])); |
1559 | lp = lpAppend(lp, (unsigned char*)intlist[4], strlen(intlist[4])); |
1560 | lp = lpAppend(lp, (unsigned char*)intlist[5], strlen(intlist[5])); |
1561 | return lp; |
1562 | } |
1563 | |
1564 | static long long usec(void) { |
1565 | struct timeval tv; |
1566 | gettimeofday(&tv, NULL); |
1567 | return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; |
1568 | } |
1569 | |
1570 | static void stress(int pos, int num, int maxsize, int dnum) { |
1571 | int i, j, k; |
1572 | unsigned char *lp; |
1573 | char posstr[2][5] = { "HEAD" , "TAIL" }; |
1574 | long long start; |
1575 | for (i = 0; i < maxsize; i+=dnum) { |
1576 | lp = lpNew(0); |
1577 | for (j = 0; j < i; j++) { |
1578 | lp = lpAppend(lp, (unsigned char*)"quux" , 4); |
1579 | } |
1580 | |
1581 | /* Do num times a push+pop from pos */ |
1582 | start = usec(); |
1583 | for (k = 0; k < num; k++) { |
1584 | if (pos == 0) { |
1585 | lp = lpPrepend(lp, (unsigned char*)"quux" , 4); |
1586 | } else { |
1587 | lp = lpAppend(lp, (unsigned char*)"quux" , 4); |
1588 | |
1589 | } |
1590 | lp = lpDelete(lp, lpFirst(lp), NULL); |
1591 | } |
1592 | printf("List size: %8d, bytes: %8zu, %dx push+pop (%s): %6lld usec\n" , |
1593 | i, lpBytes(lp), num, posstr[pos], usec()-start); |
1594 | lpFree(lp); |
1595 | } |
1596 | } |
1597 | |
1598 | static unsigned char *pop(unsigned char *lp, int where) { |
1599 | unsigned char *p, *vstr; |
1600 | int64_t vlen; |
1601 | |
1602 | p = lpSeek(lp, where == 0 ? 0 : -1); |
1603 | vstr = lpGet(p, &vlen, NULL); |
1604 | if (where == 0) |
1605 | printf("Pop head: " ); |
1606 | else |
1607 | printf("Pop tail: " ); |
1608 | |
1609 | if (vstr) { |
1610 | if (vlen && fwrite(vstr, vlen, 1, stdout) == 0) perror("fwrite" ); |
1611 | } else { |
1612 | printf("%lld" , (long long)vlen); |
1613 | } |
1614 | |
1615 | printf("\n" ); |
1616 | return lpDelete(lp, p, &p); |
1617 | } |
1618 | |
1619 | static int randstring(char *target, unsigned int min, unsigned int max) { |
1620 | int p = 0; |
1621 | int len = min+rand()%(max-min+1); |
1622 | int minval, maxval; |
1623 | switch(rand() % 3) { |
1624 | case 0: |
1625 | minval = 0; |
1626 | maxval = 255; |
1627 | break; |
1628 | case 1: |
1629 | minval = 48; |
1630 | maxval = 122; |
1631 | break; |
1632 | case 2: |
1633 | minval = 48; |
1634 | maxval = 52; |
1635 | break; |
1636 | default: |
1637 | assert(NULL); |
1638 | } |
1639 | |
1640 | while(p < len) |
1641 | target[p++] = minval+rand()%(maxval-minval+1); |
1642 | return len; |
1643 | } |
1644 | |
1645 | static void verifyEntry(unsigned char *p, unsigned char *s, size_t slen) { |
1646 | assert(lpCompare(p, s, slen)); |
1647 | } |
1648 | |
1649 | static int lpValidation(unsigned char *p, unsigned int head_count, void *userdata) { |
1650 | UNUSED(p); |
1651 | UNUSED(head_count); |
1652 | |
1653 | int ret; |
1654 | long *count = userdata; |
1655 | ret = lpCompare(p, (unsigned char *)mixlist[*count], strlen(mixlist[*count])); |
1656 | (*count)++; |
1657 | return ret; |
1658 | } |
1659 | |
1660 | int listpackTest(int argc, char *argv[], int flags) { |
1661 | UNUSED(argc); |
1662 | UNUSED(argv); |
1663 | |
1664 | int i; |
1665 | unsigned char *lp, *p, *vstr; |
1666 | int64_t vlen; |
1667 | unsigned char intbuf[LP_INTBUF_SIZE]; |
1668 | int accurate = (flags & REDIS_TEST_ACCURATE); |
1669 | |
1670 | TEST("Create int list" ) { |
1671 | lp = createIntList(); |
1672 | assert(lpLength(lp) == 6); |
1673 | lpFree(lp); |
1674 | } |
1675 | |
1676 | TEST("Create list" ) { |
1677 | lp = createList(); |
1678 | assert(lpLength(lp) == 4); |
1679 | lpFree(lp); |
1680 | } |
1681 | |
1682 | TEST("Test lpPrepend" ) { |
1683 | lp = lpNew(0); |
1684 | lp = lpPrepend(lp, (unsigned char*)"abc" , 3); |
1685 | lp = lpPrepend(lp, (unsigned char*)"1024" , 4); |
1686 | verifyEntry(lpSeek(lp, 0), (unsigned char*)"1024" , 4); |
1687 | verifyEntry(lpSeek(lp, 1), (unsigned char*)"abc" , 3); |
1688 | lpFree(lp); |
1689 | } |
1690 | |
1691 | TEST("Test lpPrependInteger" ) { |
1692 | lp = lpNew(0); |
1693 | lp = lpPrependInteger(lp, 127); |
1694 | lp = lpPrependInteger(lp, 4095); |
1695 | lp = lpPrependInteger(lp, 32767); |
1696 | lp = lpPrependInteger(lp, 8388607); |
1697 | lp = lpPrependInteger(lp, 2147483647); |
1698 | lp = lpPrependInteger(lp, 9223372036854775807); |
1699 | verifyEntry(lpSeek(lp, 0), (unsigned char*)"9223372036854775807" , 19); |
1700 | verifyEntry(lpSeek(lp, -1), (unsigned char*)"127" , 3); |
1701 | lpFree(lp); |
1702 | } |
1703 | |
1704 | TEST("Get element at index" ) { |
1705 | lp = createList(); |
1706 | verifyEntry(lpSeek(lp, 0), (unsigned char*)"hello" , 5); |
1707 | verifyEntry(lpSeek(lp, 3), (unsigned char*)"1024" , 4); |
1708 | verifyEntry(lpSeek(lp, -1), (unsigned char*)"1024" , 4); |
1709 | verifyEntry(lpSeek(lp, -4), (unsigned char*)"hello" , 5); |
1710 | assert(lpSeek(lp, 4) == NULL); |
1711 | assert(lpSeek(lp, -5) == NULL); |
1712 | lpFree(lp); |
1713 | } |
1714 | |
1715 | TEST("Pop list" ) { |
1716 | lp = createList(); |
1717 | lp = pop(lp, 1); |
1718 | lp = pop(lp, 0); |
1719 | lp = pop(lp, 1); |
1720 | lp = pop(lp, 1); |
1721 | lpFree(lp); |
1722 | } |
1723 | |
1724 | TEST("Get element at index" ) { |
1725 | lp = createList(); |
1726 | verifyEntry(lpSeek(lp, 0), (unsigned char*)"hello" , 5); |
1727 | verifyEntry(lpSeek(lp, 3), (unsigned char*)"1024" , 4); |
1728 | verifyEntry(lpSeek(lp, -1), (unsigned char*)"1024" , 4); |
1729 | verifyEntry(lpSeek(lp, -4), (unsigned char*)"hello" , 5); |
1730 | assert(lpSeek(lp, 4) == NULL); |
1731 | assert(lpSeek(lp, -5) == NULL); |
1732 | lpFree(lp); |
1733 | } |
1734 | |
1735 | TEST("Iterate list from 0 to end" ) { |
1736 | lp = createList(); |
1737 | p = lpFirst(lp); |
1738 | i = 0; |
1739 | while (p) { |
1740 | verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); |
1741 | p = lpNext(lp, p); |
1742 | i++; |
1743 | } |
1744 | lpFree(lp); |
1745 | } |
1746 | |
1747 | TEST("Iterate list from 1 to end" ) { |
1748 | lp = createList(); |
1749 | i = 1; |
1750 | p = lpSeek(lp, i); |
1751 | while (p) { |
1752 | verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); |
1753 | p = lpNext(lp, p); |
1754 | i++; |
1755 | } |
1756 | lpFree(lp); |
1757 | } |
1758 | |
1759 | TEST("Iterate list from 2 to end" ) { |
1760 | lp = createList(); |
1761 | i = 2; |
1762 | p = lpSeek(lp, i); |
1763 | while (p) { |
1764 | verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); |
1765 | p = lpNext(lp, p); |
1766 | i++; |
1767 | } |
1768 | lpFree(lp); |
1769 | } |
1770 | |
1771 | TEST("Iterate from back to front" ) { |
1772 | lp = createList(); |
1773 | p = lpLast(lp); |
1774 | i = 3; |
1775 | while (p) { |
1776 | verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); |
1777 | p = lpPrev(lp, p); |
1778 | i--; |
1779 | } |
1780 | lpFree(lp); |
1781 | } |
1782 | |
1783 | TEST("Iterate from back to front, deleting all items" ) { |
1784 | lp = createList(); |
1785 | p = lpLast(lp); |
1786 | i = 3; |
1787 | while ((p = lpLast(lp))) { |
1788 | verifyEntry(p, (unsigned char*)mixlist[i], strlen(mixlist[i])); |
1789 | lp = lpDelete(lp, p, &p); |
1790 | assert(p == NULL); |
1791 | i--; |
1792 | } |
1793 | lpFree(lp); |
1794 | } |
1795 | |
1796 | TEST("Delete whole listpack when num == -1" ); |
1797 | { |
1798 | lp = createList(); |
1799 | lp = lpDeleteRange(lp, 0, -1); |
1800 | assert(lpLength(lp) == 0); |
1801 | assert(lp[LP_HDR_SIZE] == LP_EOF); |
1802 | assert(lpBytes(lp) == (LP_HDR_SIZE + 1)); |
1803 | zfree(lp); |
1804 | |
1805 | lp = createList(); |
1806 | unsigned char *ptr = lpFirst(lp); |
1807 | lp = lpDeleteRangeWithEntry(lp, &ptr, -1); |
1808 | assert(lpLength(lp) == 0); |
1809 | assert(lp[LP_HDR_SIZE] == LP_EOF); |
1810 | assert(lpBytes(lp) == (LP_HDR_SIZE + 1)); |
1811 | zfree(lp); |
1812 | } |
1813 | |
1814 | TEST("Delete whole listpack with negative index" ); |
1815 | { |
1816 | lp = createList(); |
1817 | lp = lpDeleteRange(lp, -4, 4); |
1818 | assert(lpLength(lp) == 0); |
1819 | assert(lp[LP_HDR_SIZE] == LP_EOF); |
1820 | assert(lpBytes(lp) == (LP_HDR_SIZE + 1)); |
1821 | zfree(lp); |
1822 | |
1823 | lp = createList(); |
1824 | unsigned char *ptr = lpSeek(lp, -4); |
1825 | lp = lpDeleteRangeWithEntry(lp, &ptr, 4); |
1826 | assert(lpLength(lp) == 0); |
1827 | assert(lp[LP_HDR_SIZE] == LP_EOF); |
1828 | assert(lpBytes(lp) == (LP_HDR_SIZE + 1)); |
1829 | zfree(lp); |
1830 | } |
1831 | |
1832 | TEST("Delete inclusive range 0,0" ); |
1833 | { |
1834 | lp = createList(); |
1835 | lp = lpDeleteRange(lp, 0, 1); |
1836 | assert(lpLength(lp) == 3); |
1837 | assert(lpSkip(lpLast(lp))[0] == LP_EOF); /* check set LP_EOF correctly */ |
1838 | zfree(lp); |
1839 | |
1840 | lp = createList(); |
1841 | unsigned char *ptr = lpFirst(lp); |
1842 | lp = lpDeleteRangeWithEntry(lp, &ptr, 1); |
1843 | assert(lpLength(lp) == 3); |
1844 | assert(lpSkip(lpLast(lp))[0] == LP_EOF); /* check set LP_EOF correctly */ |
1845 | zfree(lp); |
1846 | } |
1847 | |
1848 | TEST("Delete inclusive range 0,1" ); |
1849 | { |
1850 | lp = createList(); |
1851 | lp = lpDeleteRange(lp, 0, 2); |
1852 | assert(lpLength(lp) == 2); |
1853 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[2], strlen(mixlist[2])); |
1854 | zfree(lp); |
1855 | |
1856 | lp = createList(); |
1857 | unsigned char *ptr = lpFirst(lp); |
1858 | lp = lpDeleteRangeWithEntry(lp, &ptr, 2); |
1859 | assert(lpLength(lp) == 2); |
1860 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[2], strlen(mixlist[2])); |
1861 | zfree(lp); |
1862 | } |
1863 | |
1864 | TEST("Delete inclusive range 1,2" ); |
1865 | { |
1866 | lp = createList(); |
1867 | lp = lpDeleteRange(lp, 1, 2); |
1868 | assert(lpLength(lp) == 2); |
1869 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0])); |
1870 | zfree(lp); |
1871 | |
1872 | lp = createList(); |
1873 | unsigned char *ptr = lpSeek(lp, 1); |
1874 | lp = lpDeleteRangeWithEntry(lp, &ptr, 2); |
1875 | assert(lpLength(lp) == 2); |
1876 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0])); |
1877 | zfree(lp); |
1878 | } |
1879 | |
1880 | TEST("Delete with start index out of range" ); |
1881 | { |
1882 | lp = createList(); |
1883 | lp = lpDeleteRange(lp, 5, 1); |
1884 | assert(lpLength(lp) == 4); |
1885 | zfree(lp); |
1886 | } |
1887 | |
1888 | TEST("Delete with num overflow" ); |
1889 | { |
1890 | lp = createList(); |
1891 | lp = lpDeleteRange(lp, 1, 5); |
1892 | assert(lpLength(lp) == 1); |
1893 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0])); |
1894 | zfree(lp); |
1895 | |
1896 | lp = createList(); |
1897 | unsigned char *ptr = lpSeek(lp, 1); |
1898 | lp = lpDeleteRangeWithEntry(lp, &ptr, 5); |
1899 | assert(lpLength(lp) == 1); |
1900 | verifyEntry(lpFirst(lp), (unsigned char*)mixlist[0], strlen(mixlist[0])); |
1901 | zfree(lp); |
1902 | } |
1903 | |
1904 | TEST("Delete foo while iterating" ) { |
1905 | lp = createList(); |
1906 | p = lpFirst(lp); |
1907 | while (p) { |
1908 | if (lpCompare(p, (unsigned char*)"foo" , 3)) { |
1909 | lp = lpDelete(lp, p, &p); |
1910 | } else { |
1911 | p = lpNext(lp, p); |
1912 | } |
1913 | } |
1914 | lpFree(lp); |
1915 | } |
1916 | |
1917 | TEST("Replace with same size" ) { |
1918 | lp = createList(); /* "hello", "foo", "quux", "1024" */ |
1919 | unsigned char *orig_lp = lp; |
1920 | p = lpSeek(lp, 0); |
1921 | lp = lpReplace(lp, &p, (unsigned char*)"zoink" , 5); |
1922 | p = lpSeek(lp, 3); |
1923 | lp = lpReplace(lp, &p, (unsigned char*)"y" , 1); |
1924 | p = lpSeek(lp, 1); |
1925 | lp = lpReplace(lp, &p, (unsigned char*)"65536" , 5); |
1926 | p = lpSeek(lp, 0); |
1927 | assert(!memcmp((char*)p, |
1928 | "\x85zoink\x06" |
1929 | "\xf2\x00\x00\x01\x04" /* 65536 as int24 */ |
1930 | "\x84quux\05" "\x81y\x02" "\xff" , |
1931 | 22)); |
1932 | assert(lp == orig_lp); /* no reallocations have happened */ |
1933 | lpFree(lp); |
1934 | } |
1935 | |
1936 | TEST("Replace with different size" ) { |
1937 | lp = createList(); /* "hello", "foo", "quux", "1024" */ |
1938 | p = lpSeek(lp, 1); |
1939 | lp = lpReplace(lp, &p, (unsigned char*)"squirrel" , 8); |
1940 | p = lpSeek(lp, 0); |
1941 | assert(!strncmp((char*)p, |
1942 | "\x85hello\x06" "\x88squirrel\x09" "\x84quux\x05" |
1943 | "\xc4\x00\x02" "\xff" , |
1944 | 27)); |
1945 | lpFree(lp); |
1946 | } |
1947 | |
1948 | TEST("Regression test for >255 byte strings" ) { |
1949 | char v1[257] = {0}, v2[257] = {0}; |
1950 | memset(v1,'x',256); |
1951 | memset(v2,'y',256); |
1952 | lp = lpNew(0); |
1953 | lp = lpAppend(lp, (unsigned char*)v1 ,strlen(v1)); |
1954 | lp = lpAppend(lp, (unsigned char*)v2 ,strlen(v2)); |
1955 | |
1956 | /* Pop values again and compare their value. */ |
1957 | p = lpFirst(lp); |
1958 | vstr = lpGet(p, &vlen, NULL); |
1959 | assert(strncmp(v1, (char*)vstr, vlen) == 0); |
1960 | p = lpSeek(lp, 1); |
1961 | vstr = lpGet(p, &vlen, NULL); |
1962 | assert(strncmp(v2, (char*)vstr, vlen) == 0); |
1963 | lpFree(lp); |
1964 | } |
1965 | |
1966 | TEST("Create long list and check indices" ) { |
1967 | lp = lpNew(0); |
1968 | char buf[32]; |
1969 | int i,len; |
1970 | for (i = 0; i < 1000; i++) { |
1971 | len = sprintf(buf, "%d" , i); |
1972 | lp = lpAppend(lp, (unsigned char*)buf, len); |
1973 | } |
1974 | for (i = 0; i < 1000; i++) { |
1975 | p = lpSeek(lp, i); |
1976 | vstr = lpGet(p, &vlen, NULL); |
1977 | assert(i == vlen); |
1978 | |
1979 | p = lpSeek(lp, -i-1); |
1980 | vstr = lpGet(p, &vlen, NULL); |
1981 | assert(999-i == vlen); |
1982 | } |
1983 | lpFree(lp); |
1984 | } |
1985 | |
1986 | TEST("Compare strings with listpack entries" ) { |
1987 | lp = createList(); |
1988 | p = lpSeek(lp,0); |
1989 | assert(lpCompare(p,(unsigned char*)"hello" ,5)); |
1990 | assert(!lpCompare(p,(unsigned char*)"hella" ,5)); |
1991 | |
1992 | p = lpSeek(lp,3); |
1993 | assert(lpCompare(p,(unsigned char*)"1024" ,4)); |
1994 | assert(!lpCompare(p,(unsigned char*)"1025" ,4)); |
1995 | lpFree(lp); |
1996 | } |
1997 | |
1998 | TEST("lpMerge two empty listpacks" ) { |
1999 | unsigned char *lp1 = lpNew(0); |
2000 | unsigned char *lp2 = lpNew(0); |
2001 | |
2002 | /* Merge two empty listpacks, get empty result back. */ |
2003 | lp1 = lpMerge(&lp1, &lp2); |
2004 | assert(lpLength(lp1) == 0); |
2005 | zfree(lp1); |
2006 | } |
2007 | |
2008 | TEST("lpMerge two listpacks - first larger than second" ) { |
2009 | unsigned char *lp1 = createIntList(); |
2010 | unsigned char *lp2 = createList(); |
2011 | |
2012 | size_t lp1_bytes = lpBytes(lp1); |
2013 | size_t lp2_bytes = lpBytes(lp2); |
2014 | unsigned long lp1_len = lpLength(lp1); |
2015 | unsigned long lp2_len = lpLength(lp2); |
2016 | |
2017 | unsigned char *lp3 = lpMerge(&lp1, &lp2); |
2018 | assert(lp3 == lp1); |
2019 | assert(lp2 == NULL); |
2020 | assert(lpLength(lp3) == (lp1_len + lp2_len)); |
2021 | assert(lpBytes(lp3) == (lp1_bytes + lp2_bytes - LP_HDR_SIZE - 1)); |
2022 | verifyEntry(lpSeek(lp3, 0), (unsigned char*)"4294967296" , 10); |
2023 | verifyEntry(lpSeek(lp3, 5), (unsigned char*)"much much longer non integer" , 28); |
2024 | verifyEntry(lpSeek(lp3, 6), (unsigned char*)"hello" , 5); |
2025 | verifyEntry(lpSeek(lp3, -1), (unsigned char*)"1024" , 4); |
2026 | zfree(lp3); |
2027 | } |
2028 | |
2029 | TEST("lpMerge two listpacks - second larger than first" ) { |
2030 | unsigned char *lp1 = createList(); |
2031 | unsigned char *lp2 = createIntList(); |
2032 | |
2033 | size_t lp1_bytes = lpBytes(lp1); |
2034 | size_t lp2_bytes = lpBytes(lp2); |
2035 | unsigned long lp1_len = lpLength(lp1); |
2036 | unsigned long lp2_len = lpLength(lp2); |
2037 | |
2038 | unsigned char *lp3 = lpMerge(&lp1, &lp2); |
2039 | assert(lp3 == lp2); |
2040 | assert(lp1 == NULL); |
2041 | assert(lpLength(lp3) == (lp1_len + lp2_len)); |
2042 | assert(lpBytes(lp3) == (lp1_bytes + lp2_bytes - LP_HDR_SIZE - 1)); |
2043 | verifyEntry(lpSeek(lp3, 0), (unsigned char*)"hello" , 5); |
2044 | verifyEntry(lpSeek(lp3, 3), (unsigned char*)"1024" , 4); |
2045 | verifyEntry(lpSeek(lp3, 4), (unsigned char*)"4294967296" , 10); |
2046 | verifyEntry(lpSeek(lp3, -1), (unsigned char*)"much much longer non integer" , 28); |
2047 | zfree(lp3); |
2048 | } |
2049 | |
2050 | TEST("Random pair with one element" ) { |
2051 | listpackEntry key, val; |
2052 | unsigned char *lp = lpNew(0); |
2053 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2054 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2055 | lpRandomPair(lp, 1, &key, &val); |
2056 | assert(memcmp(key.sval, "abc" , key.slen) == 0); |
2057 | assert(val.lval == 123); |
2058 | lpFree(lp); |
2059 | } |
2060 | |
2061 | TEST("Random pair with many elements" ) { |
2062 | listpackEntry key, val; |
2063 | unsigned char *lp = lpNew(0); |
2064 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2065 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2066 | lp = lpAppend(lp, (unsigned char*)"456" , 3); |
2067 | lp = lpAppend(lp, (unsigned char*)"def" , 3); |
2068 | lpRandomPair(lp, 2, &key, &val); |
2069 | if (key.sval) { |
2070 | assert(!memcmp(key.sval, "abc" , key.slen)); |
2071 | assert(key.slen == 3); |
2072 | assert(val.lval == 123); |
2073 | } |
2074 | if (!key.sval) { |
2075 | assert(key.lval == 456); |
2076 | assert(!memcmp(val.sval, "def" , val.slen)); |
2077 | } |
2078 | lpFree(lp); |
2079 | } |
2080 | |
2081 | TEST("Random pairs with one element" ) { |
2082 | int count = 5; |
2083 | unsigned char *lp = lpNew(0); |
2084 | listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); |
2085 | listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); |
2086 | |
2087 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2088 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2089 | lpRandomPairs(lp, count, keys, vals); |
2090 | assert(memcmp(keys[4].sval, "abc" , keys[4].slen) == 0); |
2091 | assert(vals[4].lval == 123); |
2092 | zfree(keys); |
2093 | zfree(vals); |
2094 | lpFree(lp); |
2095 | } |
2096 | |
2097 | TEST("Random pairs with many elements" ) { |
2098 | int count = 5; |
2099 | lp = lpNew(0); |
2100 | listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); |
2101 | listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); |
2102 | |
2103 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2104 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2105 | lp = lpAppend(lp, (unsigned char*)"456" , 3); |
2106 | lp = lpAppend(lp, (unsigned char*)"def" , 3); |
2107 | lpRandomPairs(lp, count, keys, vals); |
2108 | for (int i = 0; i < count; i++) { |
2109 | if (keys[i].sval) { |
2110 | assert(!memcmp(keys[i].sval, "abc" , keys[i].slen)); |
2111 | assert(keys[i].slen == 3); |
2112 | assert(vals[i].lval == 123); |
2113 | } |
2114 | if (!keys[i].sval) { |
2115 | assert(keys[i].lval == 456); |
2116 | assert(!memcmp(vals[i].sval, "def" , vals[i].slen)); |
2117 | } |
2118 | } |
2119 | zfree(keys); |
2120 | zfree(vals); |
2121 | lpFree(lp); |
2122 | } |
2123 | |
2124 | TEST("Random pairs unique with one element" ) { |
2125 | unsigned picked; |
2126 | int count = 5; |
2127 | lp = lpNew(0); |
2128 | listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); |
2129 | listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); |
2130 | |
2131 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2132 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2133 | picked = lpRandomPairsUnique(lp, count, keys, vals); |
2134 | assert(picked == 1); |
2135 | assert(memcmp(keys[0].sval, "abc" , keys[0].slen) == 0); |
2136 | assert(vals[0].lval == 123); |
2137 | zfree(keys); |
2138 | zfree(vals); |
2139 | lpFree(lp); |
2140 | } |
2141 | |
2142 | TEST("Random pairs unique with many elements" ) { |
2143 | unsigned picked; |
2144 | int count = 5; |
2145 | lp = lpNew(0); |
2146 | listpackEntry *keys = zmalloc(sizeof(listpackEntry) * count); |
2147 | listpackEntry *vals = zmalloc(sizeof(listpackEntry) * count); |
2148 | |
2149 | lp = lpAppend(lp, (unsigned char*)"abc" , 3); |
2150 | lp = lpAppend(lp, (unsigned char*)"123" , 3); |
2151 | lp = lpAppend(lp, (unsigned char*)"456" , 3); |
2152 | lp = lpAppend(lp, (unsigned char*)"def" , 3); |
2153 | picked = lpRandomPairsUnique(lp, count, keys, vals); |
2154 | assert(picked == 2); |
2155 | for (int i = 0; i < 2; i++) { |
2156 | if (keys[i].sval) { |
2157 | assert(!memcmp(keys[i].sval, "abc" , keys[i].slen)); |
2158 | assert(keys[i].slen == 3); |
2159 | assert(vals[i].lval == 123); |
2160 | } |
2161 | if (!keys[i].sval) { |
2162 | assert(keys[i].lval == 456); |
2163 | assert(!memcmp(vals[i].sval, "def" , vals[i].slen)); |
2164 | } |
2165 | } |
2166 | zfree(keys); |
2167 | zfree(vals); |
2168 | lpFree(lp); |
2169 | } |
2170 | |
2171 | TEST("push various encodings" ) { |
2172 | lp = lpNew(0); |
2173 | |
2174 | /* Push integer encode element using lpAppend */ |
2175 | lp = lpAppend(lp, (unsigned char*)"127" , 3); |
2176 | assert(LP_ENCODING_IS_7BIT_UINT(lpLast(lp)[0])); |
2177 | lp = lpAppend(lp, (unsigned char*)"4095" , 4); |
2178 | assert(LP_ENCODING_IS_13BIT_INT(lpLast(lp)[0])); |
2179 | lp = lpAppend(lp, (unsigned char*)"32767" , 5); |
2180 | assert(LP_ENCODING_IS_16BIT_INT(lpLast(lp)[0])); |
2181 | lp = lpAppend(lp, (unsigned char*)"8388607" , 7); |
2182 | assert(LP_ENCODING_IS_24BIT_INT(lpLast(lp)[0])); |
2183 | lp = lpAppend(lp, (unsigned char*)"2147483647" , 10); |
2184 | assert(LP_ENCODING_IS_32BIT_INT(lpLast(lp)[0])); |
2185 | lp = lpAppend(lp, (unsigned char*)"9223372036854775807" , 19); |
2186 | assert(LP_ENCODING_IS_64BIT_INT(lpLast(lp)[0])); |
2187 | |
2188 | /* Push integer encode element using lpAppendInteger */ |
2189 | lp = lpAppendInteger(lp, 127); |
2190 | assert(LP_ENCODING_IS_7BIT_UINT(lpLast(lp)[0])); |
2191 | verifyEntry(lpLast(lp), (unsigned char*)"127" , 3); |
2192 | lp = lpAppendInteger(lp, 4095); |
2193 | verifyEntry(lpLast(lp), (unsigned char*)"4095" , 4); |
2194 | assert(LP_ENCODING_IS_13BIT_INT(lpLast(lp)[0])); |
2195 | lp = lpAppendInteger(lp, 32767); |
2196 | verifyEntry(lpLast(lp), (unsigned char*)"32767" , 5); |
2197 | assert(LP_ENCODING_IS_16BIT_INT(lpLast(lp)[0])); |
2198 | lp = lpAppendInteger(lp, 8388607); |
2199 | verifyEntry(lpLast(lp), (unsigned char*)"8388607" , 7); |
2200 | assert(LP_ENCODING_IS_24BIT_INT(lpLast(lp)[0])); |
2201 | lp = lpAppendInteger(lp, 2147483647); |
2202 | verifyEntry(lpLast(lp), (unsigned char*)"2147483647" , 10); |
2203 | assert(LP_ENCODING_IS_32BIT_INT(lpLast(lp)[0])); |
2204 | lp = lpAppendInteger(lp, 9223372036854775807); |
2205 | verifyEntry(lpLast(lp), (unsigned char*)"9223372036854775807" , 19); |
2206 | assert(LP_ENCODING_IS_64BIT_INT(lpLast(lp)[0])); |
2207 | |
2208 | /* string encode */ |
2209 | unsigned char *str = zmalloc(65535); |
2210 | memset(str, 0, 65535); |
2211 | lp = lpAppend(lp, (unsigned char*)str, 63); |
2212 | assert(LP_ENCODING_IS_6BIT_STR(lpLast(lp)[0])); |
2213 | lp = lpAppend(lp, (unsigned char*)str, 4095); |
2214 | assert(LP_ENCODING_IS_12BIT_STR(lpLast(lp)[0])); |
2215 | lp = lpAppend(lp, (unsigned char*)str, 65535); |
2216 | assert(LP_ENCODING_IS_32BIT_STR(lpLast(lp)[0])); |
2217 | zfree(str); |
2218 | lpFree(lp); |
2219 | } |
2220 | |
2221 | TEST("Test lpFind" ) { |
2222 | lp = createList(); |
2223 | assert(lpFind(lp, lpFirst(lp), (unsigned char*)"abc" , 3, 0) == NULL); |
2224 | verifyEntry(lpFind(lp, lpFirst(lp), (unsigned char*)"hello" , 5, 0), (unsigned char*)"hello" , 5); |
2225 | verifyEntry(lpFind(lp, lpFirst(lp), (unsigned char*)"1024" , 4, 0), (unsigned char*)"1024" , 4); |
2226 | lpFree(lp); |
2227 | } |
2228 | |
2229 | TEST("Test lpValidateIntegrity" ) { |
2230 | lp = createList(); |
2231 | long count = 0; |
2232 | assert(lpValidateIntegrity(lp, lpBytes(lp), 1, lpValidation, &count) == 1); |
2233 | lpFree(lp); |
2234 | } |
2235 | |
2236 | TEST("Test number of elements exceeds LP_HDR_NUMELE_UNKNOWN" ) { |
2237 | lp = lpNew(0); |
2238 | for (int i = 0; i < LP_HDR_NUMELE_UNKNOWN + 1; i++) |
2239 | lp = lpAppend(lp, (unsigned char*)"1" , 1); |
2240 | |
2241 | assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN); |
2242 | assert(lpLength(lp) == LP_HDR_NUMELE_UNKNOWN+1); |
2243 | |
2244 | lp = lpDeleteRange(lp, -2, 2); |
2245 | assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN); |
2246 | assert(lpLength(lp) == LP_HDR_NUMELE_UNKNOWN-1); |
2247 | assert(lpGetNumElements(lp) == LP_HDR_NUMELE_UNKNOWN-1); /* update length after lpLength */ |
2248 | lpFree(lp); |
2249 | } |
2250 | |
2251 | TEST("Stress with random payloads of different encoding" ) { |
2252 | unsigned long long start = usec(); |
2253 | int i,j,len,where; |
2254 | unsigned char *p; |
2255 | char buf[1024]; |
2256 | int buflen; |
2257 | list *ref; |
2258 | listNode *refnode; |
2259 | |
2260 | int iteration = accurate ? 20000 : 20; |
2261 | for (i = 0; i < iteration; i++) { |
2262 | lp = lpNew(0); |
2263 | ref = listCreate(); |
2264 | listSetFreeMethod(ref,(void (*)(void*))sdsfree); |
2265 | len = rand() % 256; |
2266 | |
2267 | /* Create lists */ |
2268 | for (j = 0; j < len; j++) { |
2269 | where = (rand() & 1) ? 0 : 1; |
2270 | if (rand() % 2) { |
2271 | buflen = randstring(buf,1,sizeof(buf)-1); |
2272 | } else { |
2273 | switch(rand() % 3) { |
2274 | case 0: |
2275 | buflen = sprintf(buf,"%lld" ,(0LL + rand()) >> 20); |
2276 | break; |
2277 | case 1: |
2278 | buflen = sprintf(buf,"%lld" ,(0LL + rand())); |
2279 | break; |
2280 | case 2: |
2281 | buflen = sprintf(buf,"%lld" ,(0LL + rand()) << 20); |
2282 | break; |
2283 | default: |
2284 | assert(NULL); |
2285 | } |
2286 | } |
2287 | |
2288 | /* Add to listpack */ |
2289 | if (where == 0) { |
2290 | lp = lpPrepend(lp, (unsigned char*)buf, buflen); |
2291 | } else { |
2292 | lp = lpAppend(lp, (unsigned char*)buf, buflen); |
2293 | } |
2294 | |
2295 | /* Add to reference list */ |
2296 | if (where == 0) { |
2297 | listAddNodeHead(ref,sdsnewlen(buf, buflen)); |
2298 | } else if (where == 1) { |
2299 | listAddNodeTail(ref,sdsnewlen(buf, buflen)); |
2300 | } else { |
2301 | assert(NULL); |
2302 | } |
2303 | } |
2304 | |
2305 | assert(listLength(ref) == lpLength(lp)); |
2306 | for (j = 0; j < len; j++) { |
2307 | /* Naive way to get elements, but similar to the stresser |
2308 | * executed from the Tcl test suite. */ |
2309 | p = lpSeek(lp,j); |
2310 | refnode = listIndex(ref,j); |
2311 | |
2312 | vstr = lpGet(p, &vlen, intbuf); |
2313 | assert(memcmp(vstr,listNodeValue(refnode),vlen) == 0); |
2314 | } |
2315 | lpFree(lp); |
2316 | listRelease(ref); |
2317 | } |
2318 | printf("Done. usec=%lld\n\n" , usec()-start); |
2319 | } |
2320 | |
2321 | TEST("Stress with variable listpack size" ) { |
2322 | unsigned long long start = usec(); |
2323 | int maxsize = accurate ? 16384 : 16; |
2324 | stress(0,100000,maxsize,256); |
2325 | stress(1,100000,maxsize,256); |
2326 | printf("Done. usec=%lld\n\n" , usec()-start); |
2327 | } |
2328 | |
2329 | /* Benchmarks */ |
2330 | { |
2331 | int iteration = accurate ? 100000 : 100; |
2332 | lp = lpNew(0); |
2333 | TEST("Benchmark lpAppend" ) { |
2334 | unsigned long long start = usec(); |
2335 | for (int i=0; i<iteration; i++) { |
2336 | char buf[4096] = "asdf" ; |
2337 | lp = lpAppend(lp, (unsigned char*)buf, 4); |
2338 | lp = lpAppend(lp, (unsigned char*)buf, 40); |
2339 | lp = lpAppend(lp, (unsigned char*)buf, 400); |
2340 | lp = lpAppend(lp, (unsigned char*)buf, 4000); |
2341 | lp = lpAppend(lp, (unsigned char*)"1" , 1); |
2342 | lp = lpAppend(lp, (unsigned char*)"10" , 2); |
2343 | lp = lpAppend(lp, (unsigned char*)"100" , 3); |
2344 | lp = lpAppend(lp, (unsigned char*)"1000" , 4); |
2345 | lp = lpAppend(lp, (unsigned char*)"10000" , 5); |
2346 | lp = lpAppend(lp, (unsigned char*)"100000" , 6); |
2347 | } |
2348 | printf("Done. usec=%lld\n" , usec()-start); |
2349 | } |
2350 | |
2351 | TEST("Benchmark lpFind string" ) { |
2352 | unsigned long long start = usec(); |
2353 | for (int i = 0; i < 2000; i++) { |
2354 | unsigned char *fptr = lpFirst(lp); |
2355 | fptr = lpFind(lp, fptr, (unsigned char*)"nothing" , 7, 1); |
2356 | } |
2357 | printf("Done. usec=%lld\n" , usec()-start); |
2358 | } |
2359 | |
2360 | TEST("Benchmark lpFind number" ) { |
2361 | unsigned long long start = usec(); |
2362 | for (int i = 0; i < 2000; i++) { |
2363 | unsigned char *fptr = lpFirst(lp); |
2364 | fptr = lpFind(lp, fptr, (unsigned char*)"99999" , 5, 1); |
2365 | } |
2366 | printf("Done. usec=%lld\n" , usec()-start); |
2367 | } |
2368 | |
2369 | TEST("Benchmark lpSeek" ) { |
2370 | unsigned long long start = usec(); |
2371 | for (int i = 0; i < 2000; i++) { |
2372 | lpSeek(lp, 99999); |
2373 | } |
2374 | printf("Done. usec=%lld\n" , usec()-start); |
2375 | } |
2376 | |
2377 | TEST("Benchmark lpValidateIntegrity" ) { |
2378 | unsigned long long start = usec(); |
2379 | for (int i = 0; i < 2000; i++) { |
2380 | lpValidateIntegrity(lp, lpBytes(lp), 1, NULL, NULL); |
2381 | } |
2382 | printf("Done. usec=%lld\n" , usec()-start); |
2383 | } |
2384 | |
2385 | TEST("Benchmark lpCompare with string" ) { |
2386 | unsigned long long start = usec(); |
2387 | for (int i = 0; i < 2000; i++) { |
2388 | unsigned char *eptr = lpSeek(lp,0); |
2389 | while (eptr != NULL) { |
2390 | lpCompare(eptr,(unsigned char*)"nothing" ,7); |
2391 | eptr = lpNext(lp,eptr); |
2392 | } |
2393 | } |
2394 | printf("Done. usec=%lld\n" , usec()-start); |
2395 | } |
2396 | |
2397 | TEST("Benchmark lpCompare with number" ) { |
2398 | unsigned long long start = usec(); |
2399 | for (int i = 0; i < 2000; i++) { |
2400 | unsigned char *eptr = lpSeek(lp,0); |
2401 | while (eptr != NULL) { |
2402 | lpCompare(lp, (unsigned char*)"99999" , 5); |
2403 | eptr = lpNext(lp,eptr); |
2404 | } |
2405 | } |
2406 | printf("Done. usec=%lld\n" , usec()-start); |
2407 | } |
2408 | |
2409 | lpFree(lp); |
2410 | } |
2411 | |
2412 | return 0; |
2413 | } |
2414 | |
2415 | #endif |
2416 | |