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
140static 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)
145int 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 */
176int 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 * */
242unsigned 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. */
252void lpFree(unsigned char *lp) {
253 lp_free(lp);
254}
255
256/* Shrink the memory to fit. */
257unsigned 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. */
267static 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. */
329static 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. */
347static 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. */
386static 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. */
403static 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. */
428static 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. */
446static 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. */
464unsigned 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. */
474unsigned 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. */
485unsigned 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. */
498unsigned 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. */
507unsigned 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. */
517unsigned 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. */
572static 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
662unsigned 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. */
671unsigned 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. */
686unsigned 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. */
780unsigned 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. */
929unsigned 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. */
937unsigned 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. */
946unsigned 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. */
953unsigned 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(). */
962unsigned 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. */
969unsigned 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'. */
978unsigned 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'. */
986unsigned 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. */
994unsigned 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'. */
999unsigned 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. */
1038unsigned 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. */
1080unsigned 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. */
1163size_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. */
1172unsigned 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. */
1217unsigned 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. */
1226int 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. */
1275static 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. */
1282int 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. */
1332unsigned 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 */
1353static 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 */
1358static 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. */
1368void 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. */
1389void 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. */
1442unsigned 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 */
1480void 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
1540char *mixlist[] = {"hello", "foo", "quux", "1024"};
1541char *intlist[] = {"4294967296", "-100", "100", "128000",
1542 "non integer", "much much longer non integer"};
1543
1544static 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
1553static 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
1564static 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
1570static 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
1598static 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
1619static 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
1645static void verifyEntry(unsigned char *p, unsigned char *s, size_t slen) {
1646 assert(lpCompare(p, s, slen));
1647}
1648
1649static 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
1660int 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