1 /* The ziplist is a specially encoded dually linked list that is designed
2 * to be very memory efficient. It stores both strings and integer values,
3 * where integers are encoded as actual integers instead of a series of
4 * characters. It allows push and pop operations on either side of the list
5 * in O(1) time. However, because every operation requires a reallocation of
6 * the memory used by the ziplist, the actual complexity is related to the
7 * amount of memory used by the ziplist.
8 *
9 * ----------------------------------------------------------------------------
10 *
11 * ZIPLIST OVERALL LAYOUT
12 * ======================
13 *
14 * The general layout of the ziplist is as follows:
15 *
16 * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
17 *
18 * NOTE: all fields are stored in little endian, if not specified otherwise.
19 *
20 * <uint32_t zlbytes> is an unsigned integer to hold the number of bytes that
21 * the ziplist occupies, including the four bytes of the zlbytes field itself.
22 * This value needs to be stored to be able to resize the entire structure
23 * without the need to traverse it first.
24 *
25 * <uint32_t zltail> is the offset to the last entry in the list. This allows
26 * a pop operation on the far side of the list without the need for full
27 * traversal.
28 *
29 * <uint16_t zllen> is the number of entries. When there are more than
30 * 2^16-2 entries, this value is set to 2^16-1 and we need to traverse the
31 * entire list to know how many items it holds.
32 *
33 * <uint8_t zlend> is a special entry representing the end of the ziplist.
34 * Is encoded as a single byte equal to 255. No other normal entry starts
35 * with a byte set to the value of 255.
36 *
37 * ZIPLIST ENTRIES
38 * ===============
39 *
40 * Every entry in the ziplist is prefixed by metadata that contains two pieces
41 * of information. First, the length of the previous entry is stored to be
42 * able to traverse the list from back to front. Second, the entry encoding is
43 * provided. It represents the entry type, integer or string, and in the case
44 * of strings it also represents the length of the string payload.
45 * So a complete entry is stored like this:
46 *
47 * <prevlen> <encoding> <entry-data>
48 *
49 * Sometimes the encoding represents the entry itself, like for small integers
50 * as we'll see later. In such a case the <entry-data> part is missing, and we
51 * could have just:
52 *
53 * <prevlen> <encoding>
54 *
55 * The length of the previous entry, <prevlen>, is encoded in the following way:
56 * If this length is smaller than 254 bytes, it will only consume a single
57 * byte representing the length as an unsinged 8 bit integer. When the length
58 * is greater than or equal to 254, it will consume 5 bytes. The first byte is
59 * set to 254 (FE) to indicate a larger value is following. The remaining 4
60 * bytes take the length of the previous entry as value.
61 *
62 * So practically an entry is encoded in the following way:
63 *
64 * <prevlen from 0 to 253> <encoding> <entry>
65 *
66 * Or alternatively if the previous entry length is greater than 253 bytes
67 * the following encoding is used:
68 *
69 * 0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>
70 *
71 * The encoding field of the entry depends on the content of the
72 * entry. When the entry is a string, the first 2 bits of the encoding first
73 * byte will hold the type of encoding used to store the length of the string,
74 * followed by the actual length of the string. When the entry is an integer
75 * the first 2 bits are both set to 1. The following 2 bits are used to specify
76 * what kind of integer will be stored after this header. An overview of the
77 * different types and encodings is as follows. The first byte is always enough
78 * to determine the kind of entry.
79 *
80 * |00pppppp| - 1 byte
81 * String value with length less than or equal to 63 bytes (6 bits).
82 * "pppppp" represents the unsigned 6 bit length.
83 * |01pppppp|qqqqqqqq| - 2 bytes
84 * String value with length less than or equal to 16383 bytes (14 bits).
85 * IMPORTANT: The 14 bit number is stored in big endian.
86 * |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
87 * String value with length greater than or equal to 16384 bytes.
88 * Only the 4 bytes following the first byte represents the length
89 * up to 32^2-1. The 6 lower bits of the first byte are not used and
90 * are set to zero.
91 * IMPORTANT: The 32 bit number is stored in big endian.
92 * |11000000| - 3 bytes
93 * Integer encoded as int16_t (2 bytes).
94 * |11010000| - 5 bytes
95 * Integer encoded as int32_t (4 bytes).
96 * |11100000| - 9 bytes
97 * Integer encoded as int64_t (8 bytes).
98 * |11110000| - 4 bytes
99 * Integer encoded as 24 bit signed (3 bytes).
100 * |11111110| - 2 bytes
101 * Integer encoded as 8 bit signed (1 byte).
102 * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
103 * Unsigned integer from 0 to 12. The encoded value is actually from
104 * 1 to 13 because 0000 and 1111 can not be used, so 1 should be
105 * subtracted from the encoded 4 bit value to obtain the right value.
106 * |11111111| - End of ziplist special entry.
107 *
108 * Like for the ziplist header, all the integers are represented in little
109 * endian byte order, even when this code is compiled in big endian systems.
110 *
111 * EXAMPLES OF ACTUAL ZIPLISTS
112 * ===========================
113 *
114 * The following is a ziplist containing the two elements representing
115 * the strings "2" and "5". It is composed of 15 bytes, that we visually
116 * split into sections:
117 *
118 * [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
119 * | | | | | |
120 * zlbytes zltail entries "2" "5" end
121 *
122 * The first 4 bytes represent the number 15, that is the number of bytes
123 * the whole ziplist is composed of. The second 4 bytes are the offset
124 * at which the last ziplist entry is found, that is 12, in fact the
125 * last entry, that is "5", is at offset 12 inside the ziplist.
126 * The next 16 bit integer represents the number of elements inside the
127 * ziplist, its value is 2 since there are just two elements inside.
128 * Finally "00 f3" is the first entry representing the number 2. It is
129 * composed of the previous entry length, which is zero because this is
130 * our first entry, and the byte F3 which corresponds to the encoding
131 * |1111xxxx| with xxxx between 0001 and 1101. We need to remove the "F"
132 * higher order bits 1111, and subtract 1 from the "3", so the entry value
133 * is "2". The next entry has a prevlen of 02, since the first entry is
134 * composed of exactly two bytes. The entry itself, F6, is encoded exactly
135 * like the first entry, and 6-1 = 5, so the value of the entry is 5.
136 * Finally the special entry FF signals the end of the ziplist.
137 *
138 * Adding another element to the above string with the value "Hello World"
139 * allows us to show how the ziplist encodes small strings. We'll just show
140 * the hex dump of the entry itself. Imagine the bytes as following the
141 * entry that stores "5" in the ziplist above:
142 *
143 * [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
144 *
145 * The first byte, 02, is the length of the previous entry. The next
146 * byte represents the encoding in the pattern |00pppppp| that means
147 * that the entry is a string of length <pppppp>, so 0B means that
148 * an 11 bytes string follows. From the third byte (48) to the last (64)
149 * there are just the ASCII characters for "Hello World".
150 *
151 * ----------------------------------------------------------------------------
152 *
153 * Copyright (c) 2009-2012, Pieter Noordhuis <pcnoordhuis at gmail dot com>
154 * Copyright (c) 2009-2017, Salvatore Sanfilippo <antirez at gmail dot com>
155 * All rights reserved.
156 *
157 * Redistribution and use in source and binary forms, with or without
158 * modification, are permitted provided that the following conditions are met:
159 *
160 * * Redistributions of source code must retain the above copyright notice,
161 * this list of conditions and the following disclaimer.
162 * * Redistributions in binary form must reproduce the above copyright
163 * notice, this list of conditions and the following disclaimer in the
164 * documentation and/or other materials provided with the distribution.
165 * * Neither the name of Redis nor the names of its contributors may be used
166 * to endorse or promote products derived from this software without
167 * specific prior written permission.
168 *
169 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
170 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
171 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
172 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
173 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
174 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
175 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
176 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
177 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
178 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
179 * POSSIBILITY OF SUCH DAMAGE.
180 */
181
182 #include <stdio.h>
183 #include <stdlib.h>
184 #include <string.h>
185 #include <stdint.h>
186 #include <limits.h>
187 #include "zmalloc.h"
188 #include "util.h"
189 #include "ziplist.h"
190 #include "endianconv.h"
191 #include "redisassert.h"
192
193 #define ZIP_END 255 /* Special "end of ziplist" entry. */
194 #define ZIP_BIG_PREVLEN 254 /* Max number of bytes of the previous entry, for
195 the "prevlen" field prefixing each entry, to be
196 represented with just a single byte. Otherwise
197 it is represented as FF AA BB CC DD, where
198 AA BB CC DD are a 4 bytes unsigned integer
199 representing the previous entry len. */
200
201 /* Different encoding/length possibilities */
202 #define ZIP_STR_MASK 0xc0
203 #define ZIP_INT_MASK 0x30
204 #define ZIP_STR_06B (0 << 6)
205 #define ZIP_STR_14B (1 << 6)
206 #define ZIP_STR_32B (2 << 6)
207 #define ZIP_INT_16B (0xc0 | 0<<4)
208 #define ZIP_INT_32B (0xc0 | 1<<4)
209 #define ZIP_INT_64B (0xc0 | 2<<4)
210 #define ZIP_INT_24B (0xc0 | 3<<4)
211 #define ZIP_INT_8B 0xfe
212
213 /* 4 bit integer immediate encoding |1111xxxx| with xxxx between
214 * 0001 and 1101. */
215 #define ZIP_INT_IMM_MASK 0x0f /* Mask to extract the 4 bits value. To add
216 one is needed to reconstruct the value. */
217 #define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */
218 #define ZIP_INT_IMM_MAX 0xfd /* 11111101 */
219
220 #define INT24_MAX 0x7fffff
221 #define INT24_MIN (-INT24_MAX - 1)
222
223 /* Macro to determine if the entry is a string. String entries never start
224 * with "11" as most significant bits of the first byte. */
225 #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
226
227 /* Utility macros.*/
228
229 /* Return total bytes a ziplist is composed of. */
230 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
231
232 /* Return the offset of the last item inside the ziplist. */
233 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
234
235 /* Return the length of a ziplist, or UINT16_MAX if the length cannot be
236 * determined without scanning the whole ziplist. */
237 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
238
239 /* The size of a ziplist header: two 32 bit integers for the total
240 * bytes count and last item offset. One 16 bit integer for the number
241 * of items field. */
242 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
243
244 /* Size of the "end of ziplist" entry. Just one byte. */
245 #define ZIPLIST_END_SIZE (sizeof(uint8_t))
246
247 /* Return the pointer to the first entry of a ziplist. */
248 #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
249
250 /* Return the pointer to the last entry of a ziplist, using the
251 * last entry offset inside the ziplist header. */
252 #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
253
254 /* Return the pointer to the last byte of a ziplist, which is, the
255 * end of ziplist FF entry. */
256 #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
257
258 /* Increment the number of items field in the ziplist header. Note that this
259 * macro should never overflow the unsigned 16 bit integer, since entries are
260 * always pushed one at a time. When UINT16_MAX is reached we want the count
261 * to stay there to signal that a full scan is needed to get the number of
262 * items inside the ziplist. */
263 #define ZIPLIST_INCR_LENGTH(zl,incr) { \
264 if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) \
265 ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
266 }
267
268 /* Don't let ziplists grow over 1GB in any case, don't wanna risk overflow in
269 * zlbytes*/
270 #define ZIPLIST_MAX_SAFETY_SIZE (1<<30)
ziplistSafeToAdd(unsigned char * zl,size_t add)271 int ziplistSafeToAdd(unsigned char* zl, size_t add) {
272 size_t len = zl? ziplistBlobLen(zl): 0;
273 if (len + add > ZIPLIST_MAX_SAFETY_SIZE)
274 return 0;
275 return 1;
276 }
277
278
279 /* We use this function to receive information about a ziplist entry.
280 * Note that this is not how the data is actually encoded, is just what we
281 * get filled by a function in order to operate more easily. */
282 typedef struct zlentry {
283 unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
284 unsigned int prevrawlen; /* Previous entry len. */
285 unsigned int lensize; /* Bytes used to encode this entry type/len.
286 For example strings have a 1, 2 or 5 bytes
287 header. Integers always use a single byte.*/
288 unsigned int len; /* Bytes used to represent the actual entry.
289 For strings this is just the string length
290 while for integers it is 1, 2, 3, 4, 8 or
291 0 (for 4 bit immediate) depending on the
292 number range. */
293 unsigned int headersize; /* prevrawlensize + lensize. */
294 unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
295 the entry encoding. However for 4 bits
296 immediate integers this can assume a range
297 of values and must be range-checked. */
298 unsigned char *p; /* Pointer to the very start of the entry, that
299 is, this points to prev-entry-len field. */
300 } zlentry;
301
302 #define ZIPLIST_ENTRY_ZERO(zle) { \
303 (zle)->prevrawlensize = (zle)->prevrawlen = 0; \
304 (zle)->lensize = (zle)->len = (zle)->headersize = 0; \
305 (zle)->encoding = 0; \
306 (zle)->p = NULL; \
307 }
308
309 /* Extract the encoding from the byte pointed by 'ptr' and set it into
310 * 'encoding' field of the zlentry structure. */
311 #define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
312 (encoding) = (ptr[0]); \
313 if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
314 } while(0)
315
316 /* Return bytes needed to store integer encoded by 'encoding'. */
zipIntSize(unsigned char encoding)317 unsigned int zipIntSize(unsigned char encoding) {
318 switch(encoding) {
319 case ZIP_INT_8B: return 1;
320 case ZIP_INT_16B: return 2;
321 case ZIP_INT_24B: return 3;
322 case ZIP_INT_32B: return 4;
323 case ZIP_INT_64B: return 8;
324 }
325 if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
326 return 0; /* 4 bit immediate */
327 panic("Invalid integer encoding 0x%02X", encoding);
328 return 0;
329 }
330
331 /* Write the encoidng header of the entry in 'p'. If p is NULL it just returns
332 * the amount of bytes required to encode such a length. Arguments:
333 *
334 * 'encoding' is the encoding we are using for the entry. It could be
335 * ZIP_INT_* or ZIP_STR_* or between ZIP_INT_IMM_MIN and ZIP_INT_IMM_MAX
336 * for single-byte small immediate integers.
337 *
338 * 'rawlen' is only used for ZIP_STR_* encodings and is the length of the
339 * srting that this entry represents.
340 *
341 * The function returns the number of bytes used by the encoding/length
342 * header stored in 'p'. */
zipStoreEntryEncoding(unsigned char * p,unsigned char encoding,unsigned int rawlen)343 unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
344 unsigned char len = 1, buf[5];
345
346 if (ZIP_IS_STR(encoding)) {
347 /* Although encoding is given it may not be set for strings,
348 * so we determine it here using the raw length. */
349 if (rawlen <= 0x3f) {
350 if (!p) return len;
351 buf[0] = ZIP_STR_06B | rawlen;
352 } else if (rawlen <= 0x3fff) {
353 len += 1;
354 if (!p) return len;
355 buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
356 buf[1] = rawlen & 0xff;
357 } else {
358 len += 4;
359 if (!p) return len;
360 buf[0] = ZIP_STR_32B;
361 buf[1] = (rawlen >> 24) & 0xff;
362 buf[2] = (rawlen >> 16) & 0xff;
363 buf[3] = (rawlen >> 8) & 0xff;
364 buf[4] = rawlen & 0xff;
365 }
366 } else {
367 /* Implies integer encoding, so length is always 1. */
368 if (!p) return len;
369 buf[0] = encoding;
370 }
371
372 /* Store this length at p. */
373 memcpy(p,buf,len);
374 return len;
375 }
376
377 /* Decode the entry encoding type and data length (string length for strings,
378 * number of bytes used for the integer for integer entries) encoded in 'ptr'.
379 * The 'encoding' variable will hold the entry encoding, the 'lensize'
380 * variable will hold the number of bytes required to encode the entry
381 * length, and the 'len' variable will hold the entry length. */
382 #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
383 ZIP_ENTRY_ENCODING((ptr), (encoding)); \
384 if ((encoding) < ZIP_STR_MASK) { \
385 if ((encoding) == ZIP_STR_06B) { \
386 (lensize) = 1; \
387 (len) = (ptr)[0] & 0x3f; \
388 } else if ((encoding) == ZIP_STR_14B) { \
389 (lensize) = 2; \
390 (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
391 } else if ((encoding) == ZIP_STR_32B) { \
392 (lensize) = 5; \
393 (len) = ((ptr)[1] << 24) | \
394 ((ptr)[2] << 16) | \
395 ((ptr)[3] << 8) | \
396 ((ptr)[4]); \
397 } else { \
398 panic("Invalid string encoding 0x%02X", (encoding)); \
399 } \
400 } else { \
401 (lensize) = 1; \
402 (len) = zipIntSize(encoding); \
403 } \
404 } while(0);
405
406 /* Encode the length of the previous entry and write it to "p". This only
407 * uses the larger encoding (required in __ziplistCascadeUpdate). */
zipStorePrevEntryLengthLarge(unsigned char * p,unsigned int len)408 int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
409 if (p != NULL) {
410 p[0] = ZIP_BIG_PREVLEN;
411 memcpy(p+1,&len,sizeof(len));
412 memrev32ifbe(p+1);
413 }
414 return 1+sizeof(len);
415 }
416
417 /* Encode the length of the previous entry and write it to "p". Return the
418 * number of bytes needed to encode this length if "p" is NULL. */
zipStorePrevEntryLength(unsigned char * p,unsigned int len)419 unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
420 if (p == NULL) {
421 return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
422 } else {
423 if (len < ZIP_BIG_PREVLEN) {
424 p[0] = len;
425 return 1;
426 } else {
427 return zipStorePrevEntryLengthLarge(p,len);
428 }
429 }
430 }
431
432 /* Return the number of bytes used to encode the length of the previous
433 * entry. The length is returned by setting the var 'prevlensize'. */
434 #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
435 if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
436 (prevlensize) = 1; \
437 } else { \
438 (prevlensize) = 5; \
439 } \
440 } while(0);
441
442 /* Return the length of the previous element, and the number of bytes that
443 * are used in order to encode the previous element length.
444 * 'ptr' must point to the prevlen prefix of an entry (that encodes the
445 * length of the previous entry in order to navigate the elements backward).
446 * The length of the previous entry is stored in 'prevlen', the number of
447 * bytes needed to encode the previous entry length are stored in
448 * 'prevlensize'. */
449 #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
450 ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
451 if ((prevlensize) == 1) { \
452 (prevlen) = (ptr)[0]; \
453 } else if ((prevlensize) == 5) { \
454 assert(sizeof((prevlen)) == 4); \
455 memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
456 memrev32ifbe(&prevlen); \
457 } \
458 } while(0);
459
460 /* Given a pointer 'p' to the prevlen info that prefixes an entry, this
461 * function returns the difference in number of bytes needed to encode
462 * the prevlen if the previous entry changes of size.
463 *
464 * So if A is the number of bytes used right now to encode the 'prevlen'
465 * field.
466 *
467 * And B is the number of bytes that are needed in order to encode the
468 * 'prevlen' if the previous element will be updated to one of size 'len'.
469 *
470 * Then the function returns B - A
471 *
472 * So the function returns a positive number if more space is needed,
473 * a negative number if less space is needed, or zero if the same space
474 * is needed. */
zipPrevLenByteDiff(unsigned char * p,unsigned int len)475 int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
476 unsigned int prevlensize;
477 ZIP_DECODE_PREVLENSIZE(p, prevlensize);
478 return zipStorePrevEntryLength(NULL, len) - prevlensize;
479 }
480
481 /* Return the total number of bytes used by the entry pointed to by 'p'. */
zipRawEntryLength(unsigned char * p)482 unsigned int zipRawEntryLength(unsigned char *p) {
483 unsigned int prevlensize, encoding, lensize, len;
484 ZIP_DECODE_PREVLENSIZE(p, prevlensize);
485 ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
486 return prevlensize + lensize + len;
487 }
488
489 /* Check if string pointed to by 'entry' can be encoded as an integer.
490 * Stores the integer value in 'v' and its encoding in 'encoding'. */
zipTryEncoding(unsigned char * entry,unsigned int entrylen,long long * v,unsigned char * encoding)491 int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
492 long long value;
493
494 if (entrylen >= 32 || entrylen == 0) return 0;
495 if (string2ll((char*)entry,entrylen,&value)) {
496 /* Great, the string can be encoded. Check what's the smallest
497 * of our encoding types that can hold this value. */
498 if (value >= 0 && value <= 12) {
499 *encoding = ZIP_INT_IMM_MIN+value;
500 } else if (value >= INT8_MIN && value <= INT8_MAX) {
501 *encoding = ZIP_INT_8B;
502 } else if (value >= INT16_MIN && value <= INT16_MAX) {
503 *encoding = ZIP_INT_16B;
504 } else if (value >= INT24_MIN && value <= INT24_MAX) {
505 *encoding = ZIP_INT_24B;
506 } else if (value >= INT32_MIN && value <= INT32_MAX) {
507 *encoding = ZIP_INT_32B;
508 } else {
509 *encoding = ZIP_INT_64B;
510 }
511 *v = value;
512 return 1;
513 }
514 return 0;
515 }
516
517 /* Store integer 'value' at 'p', encoded as 'encoding' */
zipSaveInteger(unsigned char * p,int64_t value,unsigned char encoding)518 void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
519 int16_t i16;
520 int32_t i32;
521 int64_t i64;
522 if (encoding == ZIP_INT_8B) {
523 ((int8_t*)p)[0] = (int8_t)value;
524 } else if (encoding == ZIP_INT_16B) {
525 i16 = value;
526 memcpy(p,&i16,sizeof(i16));
527 memrev16ifbe(p);
528 } else if (encoding == ZIP_INT_24B) {
529 i32 = value<<8;
530 memrev32ifbe(&i32);
531 memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t));
532 } else if (encoding == ZIP_INT_32B) {
533 i32 = value;
534 memcpy(p,&i32,sizeof(i32));
535 memrev32ifbe(p);
536 } else if (encoding == ZIP_INT_64B) {
537 i64 = value;
538 memcpy(p,&i64,sizeof(i64));
539 memrev64ifbe(p);
540 } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
541 /* Nothing to do, the value is stored in the encoding itself. */
542 } else {
543 assert(NULL);
544 }
545 }
546
547 /* Read integer encoded as 'encoding' from 'p' */
zipLoadInteger(unsigned char * p,unsigned char encoding)548 int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
549 int16_t i16;
550 int32_t i32;
551 int64_t i64, ret = 0;
552 if (encoding == ZIP_INT_8B) {
553 ret = ((int8_t*)p)[0];
554 } else if (encoding == ZIP_INT_16B) {
555 memcpy(&i16,p,sizeof(i16));
556 memrev16ifbe(&i16);
557 ret = i16;
558 } else if (encoding == ZIP_INT_32B) {
559 memcpy(&i32,p,sizeof(i32));
560 memrev32ifbe(&i32);
561 ret = i32;
562 } else if (encoding == ZIP_INT_24B) {
563 i32 = 0;
564 memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t));
565 memrev32ifbe(&i32);
566 ret = i32>>8;
567 } else if (encoding == ZIP_INT_64B) {
568 memcpy(&i64,p,sizeof(i64));
569 memrev64ifbe(&i64);
570 ret = i64;
571 } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
572 ret = (encoding & ZIP_INT_IMM_MASK)-1;
573 } else {
574 assert(NULL);
575 }
576 return ret;
577 }
578
579 /* Return a struct with all information about an entry. */
zipEntry(unsigned char * p,zlentry * e)580 void zipEntry(unsigned char *p, zlentry *e) {
581
582 ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
583 ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
584 e->headersize = e->prevrawlensize + e->lensize;
585 e->p = p;
586 }
587
588 /* Create a new empty ziplist. */
ziplistNew(void)589 unsigned char *ziplistNew(void) {
590 unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
591 unsigned char *zl = zmalloc(bytes);
592 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
593 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
594 ZIPLIST_LENGTH(zl) = 0;
595 zl[bytes-1] = ZIP_END;
596 return zl;
597 }
598
599 /* Resize the ziplist. */
ziplistResize(unsigned char * zl,size_t len)600 unsigned char *ziplistResize(unsigned char *zl, size_t len) {
601 assert(len < UINT32_MAX);
602 zl = zrealloc(zl,len);
603 ZIPLIST_BYTES(zl) = intrev32ifbe(len);
604 zl[len-1] = ZIP_END;
605 return zl;
606 }
607
608 /* When an entry is inserted, we need to set the prevlen field of the next
609 * entry to equal the length of the inserted entry. It can occur that this
610 * length cannot be encoded in 1 byte and the next entry needs to be grow
611 * a bit larger to hold the 5-byte encoded prevlen. This can be done for free,
612 * because this only happens when an entry is already being inserted (which
613 * causes a realloc and memmove). However, encoding the prevlen may require
614 * that this entry is grown as well. This effect may cascade throughout
615 * the ziplist when there are consecutive entries with a size close to
616 * ZIP_BIG_PREVLEN, so we need to check that the prevlen can be encoded in
617 * every consecutive entry.
618 *
619 * Note that this effect can also happen in reverse, where the bytes required
620 * to encode the prevlen field can shrink. This effect is deliberately ignored,
621 * because it can cause a "flapping" effect where a chain prevlen fields is
622 * first grown and then shrunk again after consecutive inserts. Rather, the
623 * field is allowed to stay larger than necessary, because a large prevlen
624 * field implies the ziplist is holding large entries anyway.
625 *
626 * The pointer "p" points to the first entry that does NOT need to be
627 * updated, i.e. consecutive fields MAY need an update. */
__ziplistCascadeUpdate(unsigned char * zl,unsigned char * p)628 unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
629 size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
630 size_t offset, noffset, extra;
631 unsigned char *np;
632 zlentry cur, next;
633
634 while (p[0] != ZIP_END) {
635 zipEntry(p, &cur);
636 rawlen = cur.headersize + cur.len;
637 rawlensize = zipStorePrevEntryLength(NULL,rawlen);
638
639 /* Abort if there is no next entry. */
640 if (p[rawlen] == ZIP_END) break;
641 zipEntry(p+rawlen, &next);
642
643 /* Abort when "prevlen" has not changed. */
644 if (next.prevrawlen == rawlen) break;
645
646 if (next.prevrawlensize < rawlensize) {
647 /* The "prevlen" field of "next" needs more bytes to hold
648 * the raw length of "cur". */
649 offset = p-zl;
650 extra = rawlensize-next.prevrawlensize;
651 zl = ziplistResize(zl,curlen+extra);
652 p = zl+offset;
653
654 /* Current pointer and offset for next element. */
655 np = p+rawlen;
656 noffset = np-zl;
657
658 /* Update tail offset when next element is not the tail element. */
659 if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
660 ZIPLIST_TAIL_OFFSET(zl) =
661 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
662 }
663
664 /* Move the tail to the back. */
665 memmove(np+rawlensize,
666 np+next.prevrawlensize,
667 curlen-noffset-next.prevrawlensize-1);
668 zipStorePrevEntryLength(np,rawlen);
669
670 /* Advance the cursor */
671 p += rawlen;
672 curlen += extra;
673 } else {
674 if (next.prevrawlensize > rawlensize) {
675 /* This would result in shrinking, which we want to avoid.
676 * So, set "rawlen" in the available bytes. */
677 zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
678 } else {
679 zipStorePrevEntryLength(p+rawlen,rawlen);
680 }
681
682 /* Stop here, as the raw length of "next" has not changed. */
683 break;
684 }
685 }
686 return zl;
687 }
688
689 /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
__ziplistDelete(unsigned char * zl,unsigned char * p,unsigned int num)690 unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
691 unsigned int i, totlen, deleted = 0;
692 size_t offset;
693 int nextdiff = 0;
694 zlentry first, tail;
695
696 zipEntry(p, &first);
697 for (i = 0; p[0] != ZIP_END && i < num; i++) {
698 p += zipRawEntryLength(p);
699 deleted++;
700 }
701
702 totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
703 if (totlen > 0) {
704 if (p[0] != ZIP_END) {
705 /* Storing `prevrawlen` in this entry may increase or decrease the
706 * number of bytes required compare to the current `prevrawlen`.
707 * There always is room to store this, because it was previously
708 * stored by an entry that is now being deleted. */
709 nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
710
711 /* Note that there is always space when p jumps backward: if
712 * the new previous entry is large, one of the deleted elements
713 * had a 5 bytes prevlen header, so there is for sure at least
714 * 5 bytes free and we need just 4. */
715 p -= nextdiff;
716 zipStorePrevEntryLength(p,first.prevrawlen);
717
718 /* Update offset for tail */
719 ZIPLIST_TAIL_OFFSET(zl) =
720 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
721
722 /* When the tail contains more than one entry, we need to take
723 * "nextdiff" in account as well. Otherwise, a change in the
724 * size of prevlen doesn't have an effect on the *tail* offset. */
725 zipEntry(p, &tail);
726 if (p[tail.headersize+tail.len] != ZIP_END) {
727 ZIPLIST_TAIL_OFFSET(zl) =
728 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
729 }
730
731 /* Move tail to the front of the ziplist */
732 memmove(first.p,p,
733 intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
734 } else {
735 /* The entire tail was deleted. No need to move memory. */
736 ZIPLIST_TAIL_OFFSET(zl) =
737 intrev32ifbe((first.p-zl)-first.prevrawlen);
738 }
739
740 /* Resize and update length */
741 offset = first.p-zl;
742 zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
743 ZIPLIST_INCR_LENGTH(zl,-deleted);
744 p = zl+offset;
745
746 /* When nextdiff != 0, the raw length of the next entry has changed, so
747 * we need to cascade the update throughout the ziplist */
748 if (nextdiff != 0)
749 zl = __ziplistCascadeUpdate(zl,p);
750 }
751 return zl;
752 }
753
754 /* Insert item at "p". */
__ziplistInsert(unsigned char * zl,unsigned char * p,unsigned char * s,unsigned int slen)755 unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
756 size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
757 unsigned int prevlensize, prevlen = 0;
758 size_t offset;
759 int nextdiff = 0;
760 unsigned char encoding = 0;
761 long long value = 123456789; /* initialized to avoid warning. Using a value
762 that is easy to see if for some reason
763 we use it uninitialized. */
764 zlentry tail;
765
766 /* Find out prevlen for the entry that is inserted. */
767 if (p[0] != ZIP_END) {
768 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
769 } else {
770 unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
771 if (ptail[0] != ZIP_END) {
772 prevlen = zipRawEntryLength(ptail);
773 }
774 }
775
776 /* See if the entry can be encoded */
777 if (zipTryEncoding(s,slen,&value,&encoding)) {
778 /* 'encoding' is set to the appropriate integer encoding */
779 reqlen = zipIntSize(encoding);
780 } else {
781 /* 'encoding' is untouched, however zipStoreEntryEncoding will use the
782 * string length to figure out how to encode it. */
783 reqlen = slen;
784 }
785 /* We need space for both the length of the previous entry and
786 * the length of the payload. */
787 reqlen += zipStorePrevEntryLength(NULL,prevlen);
788 reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
789
790 /* When the insert position is not equal to the tail, we need to
791 * make sure that the next entry can hold this entry's length in
792 * its prevlen field. */
793 int forcelarge = 0;
794 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
795 if (nextdiff == -4 && reqlen < 4) {
796 nextdiff = 0;
797 forcelarge = 1;
798 }
799
800 /* Store offset because a realloc may change the address of zl. */
801 offset = p-zl;
802 zl = ziplistResize(zl,curlen+reqlen+nextdiff);
803 p = zl+offset;
804
805 /* Apply memory move when necessary and update tail offset. */
806 if (p[0] != ZIP_END) {
807 /* Subtract one because of the ZIP_END bytes */
808 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
809
810 /* Encode this entry's raw length in the next entry. */
811 if (forcelarge)
812 zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
813 else
814 zipStorePrevEntryLength(p+reqlen,reqlen);
815
816 /* Update offset for tail */
817 ZIPLIST_TAIL_OFFSET(zl) =
818 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
819
820 /* When the tail contains more than one entry, we need to take
821 * "nextdiff" in account as well. Otherwise, a change in the
822 * size of prevlen doesn't have an effect on the *tail* offset. */
823 zipEntry(p+reqlen, &tail);
824 if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
825 ZIPLIST_TAIL_OFFSET(zl) =
826 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
827 }
828 } else {
829 /* This element will be the new tail. */
830 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
831 }
832
833 /* When nextdiff != 0, the raw length of the next entry has changed, so
834 * we need to cascade the update throughout the ziplist */
835 if (nextdiff != 0) {
836 offset = p-zl;
837 zl = __ziplistCascadeUpdate(zl,p+reqlen);
838 p = zl+offset;
839 }
840
841 /* Write the entry */
842 p += zipStorePrevEntryLength(p,prevlen);
843 p += zipStoreEntryEncoding(p,encoding,slen);
844 if (ZIP_IS_STR(encoding)) {
845 memcpy(p,s,slen);
846 } else {
847 zipSaveInteger(p,value,encoding);
848 }
849 ZIPLIST_INCR_LENGTH(zl,1);
850 return zl;
851 }
852
853 /* Merge ziplists 'first' and 'second' by appending 'second' to 'first'.
854 *
855 * NOTE: The larger ziplist is reallocated to contain the new merged ziplist.
856 * Either 'first' or 'second' can be used for the result. The parameter not
857 * used will be free'd and set to NULL.
858 *
859 * After calling this function, the input parameters are no longer valid since
860 * they are changed and free'd in-place.
861 *
862 * The result ziplist is the contents of 'first' followed by 'second'.
863 *
864 * On failure: returns NULL if the merge is impossible.
865 * On success: returns the merged ziplist (which is expanded version of either
866 * 'first' or 'second', also frees the other unused input ziplist, and sets the
867 * input ziplist argument equal to newly reallocated ziplist return value. */
ziplistMerge(unsigned char ** first,unsigned char ** second)868 unsigned char *ziplistMerge(unsigned char **first, unsigned char **second) {
869 /* If any params are null, we can't merge, so NULL. */
870 if (first == NULL || *first == NULL || second == NULL || *second == NULL)
871 return NULL;
872
873 /* Can't merge same list into itself. */
874 if (*first == *second)
875 return NULL;
876
877 size_t first_bytes = intrev32ifbe(ZIPLIST_BYTES(*first));
878 size_t first_len = intrev16ifbe(ZIPLIST_LENGTH(*first));
879
880 size_t second_bytes = intrev32ifbe(ZIPLIST_BYTES(*second));
881 size_t second_len = intrev16ifbe(ZIPLIST_LENGTH(*second));
882
883 int append;
884 unsigned char *source, *target;
885 size_t target_bytes, source_bytes;
886 /* Pick the largest ziplist so we can resize easily in-place.
887 * We must also track if we are now appending or prepending to
888 * the target ziplist. */
889 if (first_len >= second_len) {
890 /* retain first, append second to first. */
891 target = *first;
892 target_bytes = first_bytes;
893 source = *second;
894 source_bytes = second_bytes;
895 append = 1;
896 } else {
897 /* else, retain second, prepend first to second. */
898 target = *second;
899 target_bytes = second_bytes;
900 source = *first;
901 source_bytes = first_bytes;
902 append = 0;
903 }
904
905 /* Calculate final bytes (subtract one pair of metadata) */
906 size_t zlbytes = first_bytes + second_bytes -
907 ZIPLIST_HEADER_SIZE - ZIPLIST_END_SIZE;
908 size_t zllength = first_len + second_len;
909
910 /* Combined zl length should be limited within UINT16_MAX */
911 zllength = zllength < UINT16_MAX ? zllength : UINT16_MAX;
912
913 /* larger values can't be stored into ZIPLIST_BYTES */
914 assert(zlbytes < UINT32_MAX);
915
916 /* Save offset positions before we start ripping memory apart. */
917 size_t first_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*first));
918 size_t second_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*second));
919
920 /* Extend target to new zlbytes then append or prepend source. */
921 target = zrealloc(target, zlbytes);
922 if (append) {
923 /* append == appending to target */
924 /* Copy source after target (copying over original [END]):
925 * [TARGET - END, SOURCE - HEADER] */
926 memcpy(target + target_bytes - ZIPLIST_END_SIZE,
927 source + ZIPLIST_HEADER_SIZE,
928 source_bytes - ZIPLIST_HEADER_SIZE);
929 } else {
930 /* !append == prepending to target */
931 /* Move target *contents* exactly size of (source - [END]),
932 * then copy source into vacataed space (source - [END]):
933 * [SOURCE - END, TARGET - HEADER] */
934 memmove(target + source_bytes - ZIPLIST_END_SIZE,
935 target + ZIPLIST_HEADER_SIZE,
936 target_bytes - ZIPLIST_HEADER_SIZE);
937 memcpy(target, source, source_bytes - ZIPLIST_END_SIZE);
938 }
939
940 /* Update header metadata. */
941 ZIPLIST_BYTES(target) = intrev32ifbe(zlbytes);
942 ZIPLIST_LENGTH(target) = intrev16ifbe(zllength);
943 /* New tail offset is:
944 * + N bytes of first ziplist
945 * - 1 byte for [END] of first ziplist
946 * + M bytes for the offset of the original tail of the second ziplist
947 * - J bytes for HEADER because second_offset keeps no header. */
948 ZIPLIST_TAIL_OFFSET(target) = intrev32ifbe(
949 (first_bytes - ZIPLIST_END_SIZE) +
950 (second_offset - ZIPLIST_HEADER_SIZE));
951
952 /* __ziplistCascadeUpdate just fixes the prev length values until it finds a
953 * correct prev length value (then it assumes the rest of the list is okay).
954 * We tell CascadeUpdate to start at the first ziplist's tail element to fix
955 * the merge seam. */
956 target = __ziplistCascadeUpdate(target, target+first_offset);
957
958 /* Now free and NULL out what we didn't realloc */
959 if (append) {
960 zfree(*second);
961 *second = NULL;
962 *first = target;
963 } else {
964 zfree(*first);
965 *first = NULL;
966 *second = target;
967 }
968 return target;
969 }
970
ziplistPush(unsigned char * zl,unsigned char * s,unsigned int slen,int where)971 unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
972 unsigned char *p;
973 p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
974 return __ziplistInsert(zl,p,s,slen);
975 }
976
977 /* Returns an offset to use for iterating with ziplistNext. When the given
978 * index is negative, the list is traversed back to front. When the list
979 * doesn't contain an element at the provided index, NULL is returned. */
ziplistIndex(unsigned char * zl,int index)980 unsigned char *ziplistIndex(unsigned char *zl, int index) {
981 unsigned char *p;
982 unsigned int prevlensize, prevlen = 0;
983 if (index < 0) {
984 index = (-index)-1;
985 p = ZIPLIST_ENTRY_TAIL(zl);
986 if (p[0] != ZIP_END) {
987 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
988 while (prevlen > 0 && index--) {
989 p -= prevlen;
990 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
991 }
992 }
993 } else {
994 p = ZIPLIST_ENTRY_HEAD(zl);
995 while (p[0] != ZIP_END && index--) {
996 p += zipRawEntryLength(p);
997 }
998 }
999 return (p[0] == ZIP_END || index > 0) ? NULL : p;
1000 }
1001
1002 /* Return pointer to next entry in ziplist.
1003 *
1004 * zl is the pointer to the ziplist
1005 * p is the pointer to the current element
1006 *
1007 * The element after 'p' is returned, otherwise NULL if we are at the end. */
ziplistNext(unsigned char * zl,unsigned char * p)1008 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
1009 ((void) zl);
1010
1011 /* "p" could be equal to ZIP_END, caused by ziplistDelete,
1012 * and we should return NULL. Otherwise, we should return NULL
1013 * when the *next* element is ZIP_END (there is no next entry). */
1014 if (p[0] == ZIP_END) {
1015 return NULL;
1016 }
1017
1018 p += zipRawEntryLength(p);
1019 if (p[0] == ZIP_END) {
1020 return NULL;
1021 }
1022
1023 return p;
1024 }
1025
1026 /* Return pointer to previous entry in ziplist. */
ziplistPrev(unsigned char * zl,unsigned char * p)1027 unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
1028 unsigned int prevlensize, prevlen = 0;
1029
1030 /* Iterating backwards from ZIP_END should return the tail. When "p" is
1031 * equal to the first element of the list, we're already at the head,
1032 * and should return NULL. */
1033 if (p[0] == ZIP_END) {
1034 p = ZIPLIST_ENTRY_TAIL(zl);
1035 return (p[0] == ZIP_END) ? NULL : p;
1036 } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
1037 return NULL;
1038 } else {
1039 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
1040 assert(prevlen > 0);
1041 return p-prevlen;
1042 }
1043 }
1044
1045 /* Get entry pointed to by 'p' and store in either '*sstr' or 'sval' depending
1046 * on the encoding of the entry. '*sstr' is always set to NULL to be able
1047 * to find out whether the string pointer or the integer value was set.
1048 * Return 0 if 'p' points to the end of the ziplist, 1 otherwise. */
ziplistGet(unsigned char * p,unsigned char ** sstr,unsigned int * slen,long long * sval)1049 unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
1050 zlentry entry;
1051 if (p == NULL || p[0] == ZIP_END) return 0;
1052 if (sstr) *sstr = NULL;
1053
1054 zipEntry(p, &entry);
1055 if (ZIP_IS_STR(entry.encoding)) {
1056 if (sstr) {
1057 *slen = entry.len;
1058 *sstr = p+entry.headersize;
1059 }
1060 } else {
1061 if (sval) {
1062 *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
1063 }
1064 }
1065 return 1;
1066 }
1067
1068 /* Insert an entry at "p". */
ziplistInsert(unsigned char * zl,unsigned char * p,unsigned char * s,unsigned int slen)1069 unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
1070 return __ziplistInsert(zl,p,s,slen);
1071 }
1072
1073 /* Delete a single entry from the ziplist, pointed to by *p.
1074 * Also update *p in place, to be able to iterate over the
1075 * ziplist, while deleting entries. */
ziplistDelete(unsigned char * zl,unsigned char ** p)1076 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
1077 size_t offset = *p-zl;
1078 zl = __ziplistDelete(zl,*p,1);
1079
1080 /* Store pointer to current element in p, because ziplistDelete will
1081 * do a realloc which might result in a different "zl"-pointer.
1082 * When the delete direction is back to front, we might delete the last
1083 * entry and end up with "p" pointing to ZIP_END, so check this. */
1084 *p = zl+offset;
1085 return zl;
1086 }
1087
1088 /* Delete a range of entries from the ziplist. */
ziplistDeleteRange(unsigned char * zl,int index,unsigned int num)1089 unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num) {
1090 unsigned char *p = ziplistIndex(zl,index);
1091 return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
1092 }
1093
1094 /* Compare entry pointer to by 'p' with 'sstr' of length 'slen'. */
1095 /* Return 1 if equal. */
ziplistCompare(unsigned char * p,unsigned char * sstr,unsigned int slen)1096 unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
1097 zlentry entry;
1098 unsigned char sencoding;
1099 long long zval, sval;
1100 if (p[0] == ZIP_END) return 0;
1101
1102 zipEntry(p, &entry);
1103 if (ZIP_IS_STR(entry.encoding)) {
1104 /* Raw compare */
1105 if (entry.len == slen) {
1106 return memcmp(p+entry.headersize,sstr,slen) == 0;
1107 } else {
1108 return 0;
1109 }
1110 } else {
1111 /* Try to compare encoded values. Don't compare encoding because
1112 * different implementations may encoded integers differently. */
1113 if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
1114 zval = zipLoadInteger(p+entry.headersize,entry.encoding);
1115 return zval == sval;
1116 }
1117 }
1118 return 0;
1119 }
1120
1121 /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
1122 * between every comparison. Returns NULL when the field could not be found. */
ziplistFind(unsigned char * p,unsigned char * vstr,unsigned int vlen,unsigned int skip)1123 unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
1124 int skipcnt = 0;
1125 unsigned char vencoding = 0;
1126 long long vll = 0;
1127
1128 while (p[0] != ZIP_END) {
1129 unsigned int prevlensize, encoding, lensize, len;
1130 unsigned char *q;
1131
1132 ZIP_DECODE_PREVLENSIZE(p, prevlensize);
1133 ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
1134 q = p + prevlensize + lensize;
1135
1136 if (skipcnt == 0) {
1137 /* Compare current entry with specified entry */
1138 if (ZIP_IS_STR(encoding)) {
1139 if (len == vlen && memcmp(q, vstr, vlen) == 0) {
1140 return p;
1141 }
1142 } else {
1143 /* Find out if the searched field can be encoded. Note that
1144 * we do it only the first time, once done vencoding is set
1145 * to non-zero and vll is set to the integer value. */
1146 if (vencoding == 0) {
1147 if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
1148 /* If the entry can't be encoded we set it to
1149 * UCHAR_MAX so that we don't retry again the next
1150 * time. */
1151 vencoding = UCHAR_MAX;
1152 }
1153 /* Must be non-zero by now */
1154 assert(vencoding);
1155 }
1156
1157 /* Compare current entry with specified entry, do it only
1158 * if vencoding != UCHAR_MAX because if there is no encoding
1159 * possible for the field it can't be a valid integer. */
1160 if (vencoding != UCHAR_MAX) {
1161 long long ll = zipLoadInteger(q, encoding);
1162 if (ll == vll) {
1163 return p;
1164 }
1165 }
1166 }
1167
1168 /* Reset skip count */
1169 skipcnt = skip;
1170 } else {
1171 /* Skip entry */
1172 skipcnt--;
1173 }
1174
1175 /* Move to next entry */
1176 p = q + len;
1177 }
1178
1179 return NULL;
1180 }
1181
1182 /* Return length of ziplist. */
ziplistLen(unsigned char * zl)1183 unsigned int ziplistLen(unsigned char *zl) {
1184 unsigned int len = 0;
1185 if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
1186 len = intrev16ifbe(ZIPLIST_LENGTH(zl));
1187 } else {
1188 unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
1189 while (*p != ZIP_END) {
1190 p += zipRawEntryLength(p);
1191 len++;
1192 }
1193
1194 /* Re-store length if small enough */
1195 if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
1196 }
1197 return len;
1198 }
1199
1200 /* Return ziplist blob size in bytes. */
ziplistBlobLen(unsigned char * zl)1201 size_t ziplistBlobLen(unsigned char *zl) {
1202 return intrev32ifbe(ZIPLIST_BYTES(zl));
1203 }
1204
ziplistRepr(unsigned char * zl)1205 void ziplistRepr(unsigned char *zl) {
1206 unsigned char *p;
1207 int index = 0;
1208 zlentry entry;
1209
1210 printf(
1211 "{total bytes %d} "
1212 "{num entries %u}\n"
1213 "{tail offset %u}\n",
1214 intrev32ifbe(ZIPLIST_BYTES(zl)),
1215 intrev16ifbe(ZIPLIST_LENGTH(zl)),
1216 intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)));
1217 p = ZIPLIST_ENTRY_HEAD(zl);
1218 while(*p != ZIP_END) {
1219 zipEntry(p, &entry);
1220 printf(
1221 "{\n"
1222 "\taddr 0x%08lx,\n"
1223 "\tindex %2d,\n"
1224 "\toffset %5ld,\n"
1225 "\thdr+entry len: %5u,\n"
1226 "\thdr len%2u,\n"
1227 "\tprevrawlen: %5u,\n"
1228 "\tprevrawlensize: %2u,\n"
1229 "\tpayload %5u\n",
1230 (long unsigned)p,
1231 index,
1232 (unsigned long) (p-zl),
1233 entry.headersize+entry.len,
1234 entry.headersize,
1235 entry.prevrawlen,
1236 entry.prevrawlensize,
1237 entry.len);
1238 printf("\tbytes: ");
1239 for (unsigned int i = 0; i < entry.headersize+entry.len; i++) {
1240 printf("%02x|",p[i]);
1241 }
1242 printf("\n");
1243 p += entry.headersize;
1244 if (ZIP_IS_STR(entry.encoding)) {
1245 printf("\t[str]");
1246 if (entry.len > 40) {
1247 if (fwrite(p,40,1,stdout) == 0) perror("fwrite");
1248 printf("...");
1249 } else {
1250 if (entry.len &&
1251 fwrite(p,entry.len,1,stdout) == 0) perror("fwrite");
1252 }
1253 } else {
1254 printf("\t[int]%lld", (long long) zipLoadInteger(p,entry.encoding));
1255 }
1256 printf("\n}\n");
1257 p += entry.len;
1258 index++;
1259 }
1260 printf("{end}\n\n");
1261 }
1262
1263 #ifdef REDIS_TEST
1264 #include <sys/time.h>
1265 #include "adlist.h"
1266 #include "sds.h"
1267
1268 #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); }
1269
createList()1270 static unsigned char *createList() {
1271 unsigned char *zl = ziplistNew();
1272 zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
1273 zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
1274 zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
1275 zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL);
1276 return zl;
1277 }
1278
createIntList()1279 static unsigned char *createIntList() {
1280 unsigned char *zl = ziplistNew();
1281 char buf[32];
1282
1283 sprintf(buf, "100");
1284 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
1285 sprintf(buf, "128000");
1286 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
1287 sprintf(buf, "-100");
1288 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
1289 sprintf(buf, "4294967296");
1290 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
1291 sprintf(buf, "non integer");
1292 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
1293 sprintf(buf, "much much longer non integer");
1294 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
1295 return zl;
1296 }
1297
usec(void)1298 static long long usec(void) {
1299 struct timeval tv;
1300 gettimeofday(&tv,NULL);
1301 return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
1302 }
1303
stress(int pos,int num,int maxsize,int dnum)1304 static void stress(int pos, int num, int maxsize, int dnum) {
1305 int i,j,k;
1306 unsigned char *zl;
1307 char posstr[2][5] = { "HEAD", "TAIL" };
1308 long long start;
1309 for (i = 0; i < maxsize; i+=dnum) {
1310 zl = ziplistNew();
1311 for (j = 0; j < i; j++) {
1312 zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL);
1313 }
1314
1315 /* Do num times a push+pop from pos */
1316 start = usec();
1317 for (k = 0; k < num; k++) {
1318 zl = ziplistPush(zl,(unsigned char*)"quux",4,pos);
1319 zl = ziplistDeleteRange(zl,0,1);
1320 }
1321 printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n",
1322 i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start);
1323 zfree(zl);
1324 }
1325 }
1326
pop(unsigned char * zl,int where)1327 static unsigned char *pop(unsigned char *zl, int where) {
1328 unsigned char *p, *vstr;
1329 unsigned int vlen;
1330 long long vlong;
1331
1332 p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1);
1333 if (ziplistGet(p,&vstr,&vlen,&vlong)) {
1334 if (where == ZIPLIST_HEAD)
1335 printf("Pop head: ");
1336 else
1337 printf("Pop tail: ");
1338
1339 if (vstr) {
1340 if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite");
1341 }
1342 else {
1343 printf("%lld", vlong);
1344 }
1345
1346 printf("\n");
1347 return ziplistDelete(zl,&p);
1348 } else {
1349 printf("ERROR: Could not pop\n");
1350 exit(1);
1351 }
1352 }
1353
randstring(char * target,unsigned int min,unsigned int max)1354 static int randstring(char *target, unsigned int min, unsigned int max) {
1355 int p = 0;
1356 int len = min+rand()%(max-min+1);
1357 int minval, maxval;
1358 switch(rand() % 3) {
1359 case 0:
1360 minval = 0;
1361 maxval = 255;
1362 break;
1363 case 1:
1364 minval = 48;
1365 maxval = 122;
1366 break;
1367 case 2:
1368 minval = 48;
1369 maxval = 52;
1370 break;
1371 default:
1372 assert(NULL);
1373 }
1374
1375 while(p < len)
1376 target[p++] = minval+rand()%(maxval-minval+1);
1377 return len;
1378 }
1379
verify(unsigned char * zl,zlentry * e)1380 static void verify(unsigned char *zl, zlentry *e) {
1381 int len = ziplistLen(zl);
1382 zlentry _e;
1383
1384 ZIPLIST_ENTRY_ZERO(&_e);
1385
1386 for (int i = 0; i < len; i++) {
1387 memset(&e[i], 0, sizeof(zlentry));
1388 zipEntry(ziplistIndex(zl, i), &e[i]);
1389
1390 memset(&_e, 0, sizeof(zlentry));
1391 zipEntry(ziplistIndex(zl, -len+i), &_e);
1392
1393 assert(memcmp(&e[i], &_e, sizeof(zlentry)) == 0);
1394 }
1395 }
1396
ziplistTest(int argc,char ** argv)1397 int ziplistTest(int argc, char **argv) {
1398 unsigned char *zl, *p;
1399 unsigned char *entry;
1400 unsigned int elen;
1401 long long value;
1402
1403 /* If an argument is given, use it as the random seed. */
1404 if (argc == 2)
1405 srand(atoi(argv[1]));
1406
1407 zl = createIntList();
1408 ziplistRepr(zl);
1409
1410 zfree(zl);
1411
1412 zl = createList();
1413 ziplistRepr(zl);
1414
1415 zl = pop(zl,ZIPLIST_TAIL);
1416 ziplistRepr(zl);
1417
1418 zl = pop(zl,ZIPLIST_HEAD);
1419 ziplistRepr(zl);
1420
1421 zl = pop(zl,ZIPLIST_TAIL);
1422 ziplistRepr(zl);
1423
1424 zl = pop(zl,ZIPLIST_TAIL);
1425 ziplistRepr(zl);
1426
1427 zfree(zl);
1428
1429 printf("Get element at index 3:\n");
1430 {
1431 zl = createList();
1432 p = ziplistIndex(zl, 3);
1433 if (!ziplistGet(p, &entry, &elen, &value)) {
1434 printf("ERROR: Could not access index 3\n");
1435 return 1;
1436 }
1437 if (entry) {
1438 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1439 printf("\n");
1440 } else {
1441 printf("%lld\n", value);
1442 }
1443 printf("\n");
1444 zfree(zl);
1445 }
1446
1447 printf("Get element at index 4 (out of range):\n");
1448 {
1449 zl = createList();
1450 p = ziplistIndex(zl, 4);
1451 if (p == NULL) {
1452 printf("No entry\n");
1453 } else {
1454 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1455 return 1;
1456 }
1457 printf("\n");
1458 zfree(zl);
1459 }
1460
1461 printf("Get element at index -1 (last element):\n");
1462 {
1463 zl = createList();
1464 p = ziplistIndex(zl, -1);
1465 if (!ziplistGet(p, &entry, &elen, &value)) {
1466 printf("ERROR: Could not access index -1\n");
1467 return 1;
1468 }
1469 if (entry) {
1470 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1471 printf("\n");
1472 } else {
1473 printf("%lld\n", value);
1474 }
1475 printf("\n");
1476 zfree(zl);
1477 }
1478
1479 printf("Get element at index -4 (first element):\n");
1480 {
1481 zl = createList();
1482 p = ziplistIndex(zl, -4);
1483 if (!ziplistGet(p, &entry, &elen, &value)) {
1484 printf("ERROR: Could not access index -4\n");
1485 return 1;
1486 }
1487 if (entry) {
1488 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1489 printf("\n");
1490 } else {
1491 printf("%lld\n", value);
1492 }
1493 printf("\n");
1494 zfree(zl);
1495 }
1496
1497 printf("Get element at index -5 (reverse out of range):\n");
1498 {
1499 zl = createList();
1500 p = ziplistIndex(zl, -5);
1501 if (p == NULL) {
1502 printf("No entry\n");
1503 } else {
1504 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1505 return 1;
1506 }
1507 printf("\n");
1508 zfree(zl);
1509 }
1510
1511 printf("Iterate list from 0 to end:\n");
1512 {
1513 zl = createList();
1514 p = ziplistIndex(zl, 0);
1515 while (ziplistGet(p, &entry, &elen, &value)) {
1516 printf("Entry: ");
1517 if (entry) {
1518 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1519 } else {
1520 printf("%lld", value);
1521 }
1522 p = ziplistNext(zl,p);
1523 printf("\n");
1524 }
1525 printf("\n");
1526 zfree(zl);
1527 }
1528
1529 printf("Iterate list from 1 to end:\n");
1530 {
1531 zl = createList();
1532 p = ziplistIndex(zl, 1);
1533 while (ziplistGet(p, &entry, &elen, &value)) {
1534 printf("Entry: ");
1535 if (entry) {
1536 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1537 } else {
1538 printf("%lld", value);
1539 }
1540 p = ziplistNext(zl,p);
1541 printf("\n");
1542 }
1543 printf("\n");
1544 zfree(zl);
1545 }
1546
1547 printf("Iterate list from 2 to end:\n");
1548 {
1549 zl = createList();
1550 p = ziplistIndex(zl, 2);
1551 while (ziplistGet(p, &entry, &elen, &value)) {
1552 printf("Entry: ");
1553 if (entry) {
1554 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1555 } else {
1556 printf("%lld", value);
1557 }
1558 p = ziplistNext(zl,p);
1559 printf("\n");
1560 }
1561 printf("\n");
1562 zfree(zl);
1563 }
1564
1565 printf("Iterate starting out of range:\n");
1566 {
1567 zl = createList();
1568 p = ziplistIndex(zl, 4);
1569 if (!ziplistGet(p, &entry, &elen, &value)) {
1570 printf("No entry\n");
1571 } else {
1572 printf("ERROR\n");
1573 }
1574 printf("\n");
1575 zfree(zl);
1576 }
1577
1578 printf("Iterate from back to front:\n");
1579 {
1580 zl = createList();
1581 p = ziplistIndex(zl, -1);
1582 while (ziplistGet(p, &entry, &elen, &value)) {
1583 printf("Entry: ");
1584 if (entry) {
1585 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1586 } else {
1587 printf("%lld", value);
1588 }
1589 p = ziplistPrev(zl,p);
1590 printf("\n");
1591 }
1592 printf("\n");
1593 zfree(zl);
1594 }
1595
1596 printf("Iterate from back to front, deleting all items:\n");
1597 {
1598 zl = createList();
1599 p = ziplistIndex(zl, -1);
1600 while (ziplistGet(p, &entry, &elen, &value)) {
1601 printf("Entry: ");
1602 if (entry) {
1603 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1604 } else {
1605 printf("%lld", value);
1606 }
1607 zl = ziplistDelete(zl,&p);
1608 p = ziplistPrev(zl,p);
1609 printf("\n");
1610 }
1611 printf("\n");
1612 zfree(zl);
1613 }
1614
1615 printf("Delete inclusive range 0,0:\n");
1616 {
1617 zl = createList();
1618 zl = ziplistDeleteRange(zl, 0, 1);
1619 ziplistRepr(zl);
1620 zfree(zl);
1621 }
1622
1623 printf("Delete inclusive range 0,1:\n");
1624 {
1625 zl = createList();
1626 zl = ziplistDeleteRange(zl, 0, 2);
1627 ziplistRepr(zl);
1628 zfree(zl);
1629 }
1630
1631 printf("Delete inclusive range 1,2:\n");
1632 {
1633 zl = createList();
1634 zl = ziplistDeleteRange(zl, 1, 2);
1635 ziplistRepr(zl);
1636 zfree(zl);
1637 }
1638
1639 printf("Delete with start index out of range:\n");
1640 {
1641 zl = createList();
1642 zl = ziplistDeleteRange(zl, 5, 1);
1643 ziplistRepr(zl);
1644 zfree(zl);
1645 }
1646
1647 printf("Delete with num overflow:\n");
1648 {
1649 zl = createList();
1650 zl = ziplistDeleteRange(zl, 1, 5);
1651 ziplistRepr(zl);
1652 zfree(zl);
1653 }
1654
1655 printf("Delete foo while iterating:\n");
1656 {
1657 zl = createList();
1658 p = ziplistIndex(zl,0);
1659 while (ziplistGet(p,&entry,&elen,&value)) {
1660 if (entry && strncmp("foo",(char*)entry,elen) == 0) {
1661 printf("Delete foo\n");
1662 zl = ziplistDelete(zl,&p);
1663 } else {
1664 printf("Entry: ");
1665 if (entry) {
1666 if (elen && fwrite(entry,elen,1,stdout) == 0)
1667 perror("fwrite");
1668 } else {
1669 printf("%lld",value);
1670 }
1671 p = ziplistNext(zl,p);
1672 printf("\n");
1673 }
1674 }
1675 printf("\n");
1676 ziplistRepr(zl);
1677 zfree(zl);
1678 }
1679
1680 printf("Regression test for >255 byte strings:\n");
1681 {
1682 char v1[257] = {0}, v2[257] = {0};
1683 memset(v1,'x',256);
1684 memset(v2,'y',256);
1685 zl = ziplistNew();
1686 zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL);
1687 zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL);
1688
1689 /* Pop values again and compare their value. */
1690 p = ziplistIndex(zl,0);
1691 assert(ziplistGet(p,&entry,&elen,&value));
1692 assert(strncmp(v1,(char*)entry,elen) == 0);
1693 p = ziplistIndex(zl,1);
1694 assert(ziplistGet(p,&entry,&elen,&value));
1695 assert(strncmp(v2,(char*)entry,elen) == 0);
1696 printf("SUCCESS\n\n");
1697 zfree(zl);
1698 }
1699
1700 printf("Regression test deleting next to last entries:\n");
1701 {
1702 char v[3][257] = {{0}};
1703 zlentry e[3] = {{.prevrawlensize = 0, .prevrawlen = 0, .lensize = 0,
1704 .len = 0, .headersize = 0, .encoding = 0, .p = NULL}};
1705 size_t i;
1706
1707 for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) {
1708 memset(v[i], 'a' + i, sizeof(v[0]));
1709 }
1710
1711 v[0][256] = '\0';
1712 v[1][ 1] = '\0';
1713 v[2][256] = '\0';
1714
1715 zl = ziplistNew();
1716 for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) {
1717 zl = ziplistPush(zl, (unsigned char *) v[i], strlen(v[i]), ZIPLIST_TAIL);
1718 }
1719
1720 verify(zl, e);
1721
1722 assert(e[0].prevrawlensize == 1);
1723 assert(e[1].prevrawlensize == 5);
1724 assert(e[2].prevrawlensize == 1);
1725
1726 /* Deleting entry 1 will increase `prevrawlensize` for entry 2 */
1727 unsigned char *p = e[1].p;
1728 zl = ziplistDelete(zl, &p);
1729
1730 verify(zl, e);
1731
1732 assert(e[0].prevrawlensize == 1);
1733 assert(e[1].prevrawlensize == 5);
1734
1735 printf("SUCCESS\n\n");
1736 zfree(zl);
1737 }
1738
1739 printf("Create long list and check indices:\n");
1740 {
1741 zl = ziplistNew();
1742 char buf[32];
1743 int i,len;
1744 for (i = 0; i < 1000; i++) {
1745 len = sprintf(buf,"%d",i);
1746 zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL);
1747 }
1748 for (i = 0; i < 1000; i++) {
1749 p = ziplistIndex(zl,i);
1750 assert(ziplistGet(p,NULL,NULL,&value));
1751 assert(i == value);
1752
1753 p = ziplistIndex(zl,-i-1);
1754 assert(ziplistGet(p,NULL,NULL,&value));
1755 assert(999-i == value);
1756 }
1757 printf("SUCCESS\n\n");
1758 zfree(zl);
1759 }
1760
1761 printf("Compare strings with ziplist entries:\n");
1762 {
1763 zl = createList();
1764 p = ziplistIndex(zl,0);
1765 if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
1766 printf("ERROR: not \"hello\"\n");
1767 return 1;
1768 }
1769 if (ziplistCompare(p,(unsigned char*)"hella",5)) {
1770 printf("ERROR: \"hella\"\n");
1771 return 1;
1772 }
1773
1774 p = ziplistIndex(zl,3);
1775 if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
1776 printf("ERROR: not \"1024\"\n");
1777 return 1;
1778 }
1779 if (ziplistCompare(p,(unsigned char*)"1025",4)) {
1780 printf("ERROR: \"1025\"\n");
1781 return 1;
1782 }
1783 printf("SUCCESS\n\n");
1784 zfree(zl);
1785 }
1786
1787 printf("Merge test:\n");
1788 {
1789 /* create list gives us: [hello, foo, quux, 1024] */
1790 zl = createList();
1791 unsigned char *zl2 = createList();
1792
1793 unsigned char *zl3 = ziplistNew();
1794 unsigned char *zl4 = ziplistNew();
1795
1796 if (ziplistMerge(&zl4, &zl4)) {
1797 printf("ERROR: Allowed merging of one ziplist into itself.\n");
1798 return 1;
1799 }
1800
1801 /* Merge two empty ziplists, get empty result back. */
1802 zl4 = ziplistMerge(&zl3, &zl4);
1803 ziplistRepr(zl4);
1804 if (ziplistLen(zl4)) {
1805 printf("ERROR: Merging two empty ziplists created entries.\n");
1806 return 1;
1807 }
1808 zfree(zl4);
1809
1810 zl2 = ziplistMerge(&zl, &zl2);
1811 /* merge gives us: [hello, foo, quux, 1024, hello, foo, quux, 1024] */
1812 ziplistRepr(zl2);
1813
1814 if (ziplistLen(zl2) != 8) {
1815 printf("ERROR: Merged length not 8, but: %u\n", ziplistLen(zl2));
1816 return 1;
1817 }
1818
1819 p = ziplistIndex(zl2,0);
1820 if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
1821 printf("ERROR: not \"hello\"\n");
1822 return 1;
1823 }
1824 if (ziplistCompare(p,(unsigned char*)"hella",5)) {
1825 printf("ERROR: \"hella\"\n");
1826 return 1;
1827 }
1828
1829 p = ziplistIndex(zl2,3);
1830 if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
1831 printf("ERROR: not \"1024\"\n");
1832 return 1;
1833 }
1834 if (ziplistCompare(p,(unsigned char*)"1025",4)) {
1835 printf("ERROR: \"1025\"\n");
1836 return 1;
1837 }
1838
1839 p = ziplistIndex(zl2,4);
1840 if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
1841 printf("ERROR: not \"hello\"\n");
1842 return 1;
1843 }
1844 if (ziplistCompare(p,(unsigned char*)"hella",5)) {
1845 printf("ERROR: \"hella\"\n");
1846 return 1;
1847 }
1848
1849 p = ziplistIndex(zl2,7);
1850 if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
1851 printf("ERROR: not \"1024\"\n");
1852 return 1;
1853 }
1854 if (ziplistCompare(p,(unsigned char*)"1025",4)) {
1855 printf("ERROR: \"1025\"\n");
1856 return 1;
1857 }
1858 printf("SUCCESS\n\n");
1859 zfree(zl);
1860 }
1861
1862 printf("Stress with random payloads of different encoding:\n");
1863 {
1864 int i,j,len,where;
1865 unsigned char *p;
1866 char buf[1024];
1867 int buflen;
1868 list *ref;
1869 listNode *refnode;
1870
1871 /* Hold temp vars from ziplist */
1872 unsigned char *sstr;
1873 unsigned int slen;
1874 long long sval;
1875
1876 for (i = 0; i < 20000; i++) {
1877 zl = ziplistNew();
1878 ref = listCreate();
1879 listSetFreeMethod(ref,(void (*)(void*))sdsfree);
1880 len = rand() % 256;
1881
1882 /* Create lists */
1883 for (j = 0; j < len; j++) {
1884 where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
1885 if (rand() % 2) {
1886 buflen = randstring(buf,1,sizeof(buf)-1);
1887 } else {
1888 switch(rand() % 3) {
1889 case 0:
1890 buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20);
1891 break;
1892 case 1:
1893 buflen = sprintf(buf,"%lld",(0LL + rand()));
1894 break;
1895 case 2:
1896 buflen = sprintf(buf,"%lld",(0LL + rand()) << 20);
1897 break;
1898 default:
1899 assert(NULL);
1900 }
1901 }
1902
1903 /* Add to ziplist */
1904 zl = ziplistPush(zl, (unsigned char*)buf, buflen, where);
1905
1906 /* Add to reference list */
1907 if (where == ZIPLIST_HEAD) {
1908 listAddNodeHead(ref,sdsnewlen(buf, buflen));
1909 } else if (where == ZIPLIST_TAIL) {
1910 listAddNodeTail(ref,sdsnewlen(buf, buflen));
1911 } else {
1912 assert(NULL);
1913 }
1914 }
1915
1916 assert(listLength(ref) == ziplistLen(zl));
1917 for (j = 0; j < len; j++) {
1918 /* Naive way to get elements, but similar to the stresser
1919 * executed from the Tcl test suite. */
1920 p = ziplistIndex(zl,j);
1921 refnode = listIndex(ref,j);
1922
1923 assert(ziplistGet(p,&sstr,&slen,&sval));
1924 if (sstr == NULL) {
1925 buflen = sprintf(buf,"%lld",sval);
1926 } else {
1927 buflen = slen;
1928 memcpy(buf,sstr,buflen);
1929 buf[buflen] = '\0';
1930 }
1931 assert(memcmp(buf,listNodeValue(refnode),buflen) == 0);
1932 }
1933 zfree(zl);
1934 listRelease(ref);
1935 }
1936 printf("SUCCESS\n\n");
1937 }
1938
1939 printf("Stress with variable ziplist size:\n");
1940 {
1941 stress(ZIPLIST_HEAD,100000,16384,256);
1942 stress(ZIPLIST_TAIL,100000,16384,256);
1943 }
1944
1945 return 0;
1946 }
1947 #endif
1948