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 unsigned 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 2^32-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 0001 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 | * Copyright (c) 2020, Redis Labs, Inc |
156 | * All rights reserved. |
157 | * |
158 | * Redistribution and use in source and binary forms, with or without |
159 | * modification, are permitted provided that the following conditions are met: |
160 | * |
161 | * * Redistributions of source code must retain the above copyright notice, |
162 | * this list of conditions and the following disclaimer. |
163 | * * Redistributions in binary form must reproduce the above copyright |
164 | * notice, this list of conditions and the following disclaimer in the |
165 | * documentation and/or other materials provided with the distribution. |
166 | * * Neither the name of Redis nor the names of its contributors may be used |
167 | * to endorse or promote products derived from this software without |
168 | * specific prior written permission. |
169 | * |
170 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
171 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
172 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
173 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
174 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
175 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
176 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
177 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
178 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
179 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
180 | * POSSIBILITY OF SUCH DAMAGE. |
181 | */ |
182 | |
183 | #include <stdio.h> |
184 | #include <stdlib.h> |
185 | #include <string.h> |
186 | #include <stdint.h> |
187 | #include <limits.h> |
188 | #include "zmalloc.h" |
189 | #include "util.h" |
190 | #include "ziplist.h" |
191 | #include "config.h" |
192 | #include "endianconv.h" |
193 | #include "redisassert.h" |
194 | |
195 | #define ZIP_END 255 /* Special "end of ziplist" entry. */ |
196 | #define ZIP_BIG_PREVLEN 254 /* ZIP_BIG_PREVLEN - 1 is the max number of bytes of |
197 | the previous entry, for the "prevlen" field prefixing |
198 | each entry, to be represented with just a single byte. |
199 | Otherwise it is represented as FE AA BB CC DD, where |
200 | AA BB CC DD are a 4 bytes unsigned integer |
201 | representing the previous entry len. */ |
202 | |
203 | /* Different encoding/length possibilities */ |
204 | #define ZIP_STR_MASK 0xc0 |
205 | #define ZIP_INT_MASK 0x30 |
206 | #define ZIP_STR_06B (0 << 6) |
207 | #define ZIP_STR_14B (1 << 6) |
208 | #define ZIP_STR_32B (2 << 6) |
209 | #define ZIP_INT_16B (0xc0 | 0<<4) |
210 | #define ZIP_INT_32B (0xc0 | 1<<4) |
211 | #define ZIP_INT_64B (0xc0 | 2<<4) |
212 | #define ZIP_INT_24B (0xc0 | 3<<4) |
213 | #define ZIP_INT_8B 0xfe |
214 | |
215 | /* 4 bit integer immediate encoding |1111xxxx| with xxxx between |
216 | * 0001 and 1101. */ |
217 | #define ZIP_INT_IMM_MASK 0x0f /* Mask to extract the 4 bits value. To add |
218 | one is needed to reconstruct the value. */ |
219 | #define ZIP_INT_IMM_MIN 0xf1 /* 11110001 */ |
220 | #define ZIP_INT_IMM_MAX 0xfd /* 11111101 */ |
221 | |
222 | #define INT24_MAX 0x7fffff |
223 | #define INT24_MIN (-INT24_MAX - 1) |
224 | |
225 | /* Macro to determine if the entry is a string. String entries never start |
226 | * with "11" as most significant bits of the first byte. */ |
227 | #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK) |
228 | |
229 | /* Utility macros.*/ |
230 | |
231 | /* Return total bytes a ziplist is composed of. */ |
232 | #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) |
233 | |
234 | /* Return the offset of the last item inside the ziplist. */ |
235 | #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) |
236 | |
237 | /* Return the length of a ziplist, or UINT16_MAX if the length cannot be |
238 | * determined without scanning the whole ziplist. */ |
239 | #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) |
240 | |
241 | /* The size of a ziplist header: two 32 bit integers for the total |
242 | * bytes count and last item offset. One 16 bit integer for the number |
243 | * of items field. */ |
244 | #define (sizeof(uint32_t)*2+sizeof(uint16_t)) |
245 | |
246 | /* Size of the "end of ziplist" entry. Just one byte. */ |
247 | #define ZIPLIST_END_SIZE (sizeof(uint8_t)) |
248 | |
249 | /* Return the pointer to the first entry of a ziplist. */ |
250 | #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) |
251 | |
252 | /* Return the pointer to the last entry of a ziplist, using the |
253 | * last entry offset inside the ziplist header. */ |
254 | #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) |
255 | |
256 | /* Return the pointer to the last byte of a ziplist, which is, the |
257 | * end of ziplist FF entry. */ |
258 | #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-ZIPLIST_END_SIZE) |
259 | |
260 | /* Increment the number of items field in the ziplist header. Note that this |
261 | * macro should never overflow the unsigned 16 bit integer, since entries are |
262 | * always pushed one at a time. When UINT16_MAX is reached we want the count |
263 | * to stay there to signal that a full scan is needed to get the number of |
264 | * items inside the ziplist. */ |
265 | #define ZIPLIST_INCR_LENGTH(zl,incr) { \ |
266 | if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) \ |
267 | ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \ |
268 | } |
269 | |
270 | /* Don't let ziplists grow over 1GB in any case, don't wanna risk overflow in |
271 | * zlbytes */ |
272 | #define ZIPLIST_MAX_SAFETY_SIZE (1<<30) |
273 | int ziplistSafeToAdd(unsigned char* zl, size_t add) { |
274 | size_t len = zl? ziplistBlobLen(zl): 0; |
275 | if (len + add > ZIPLIST_MAX_SAFETY_SIZE) |
276 | return 0; |
277 | return 1; |
278 | } |
279 | |
280 | |
281 | /* We use this function to receive information about a ziplist entry. |
282 | * Note that this is not how the data is actually encoded, is just what we |
283 | * get filled by a function in order to operate more easily. */ |
284 | typedef struct zlentry { |
285 | unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/ |
286 | unsigned int prevrawlen; /* Previous entry len. */ |
287 | unsigned int lensize; /* Bytes used to encode this entry type/len. |
288 | For example strings have a 1, 2 or 5 bytes |
289 | header. Integers always use a single byte.*/ |
290 | unsigned int len; /* Bytes used to represent the actual entry. |
291 | For strings this is just the string length |
292 | while for integers it is 1, 2, 3, 4, 8 or |
293 | 0 (for 4 bit immediate) depending on the |
294 | number range. */ |
295 | unsigned int ; /* prevrawlensize + lensize. */ |
296 | unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on |
297 | the entry encoding. However for 4 bits |
298 | immediate integers this can assume a range |
299 | of values and must be range-checked. */ |
300 | unsigned char *p; /* Pointer to the very start of the entry, that |
301 | is, this points to prev-entry-len field. */ |
302 | } zlentry; |
303 | |
304 | #define ZIPLIST_ENTRY_ZERO(zle) { \ |
305 | (zle)->prevrawlensize = (zle)->prevrawlen = 0; \ |
306 | (zle)->lensize = (zle)->len = (zle)->headersize = 0; \ |
307 | (zle)->encoding = 0; \ |
308 | (zle)->p = NULL; \ |
309 | } |
310 | |
311 | /* Extract the encoding from the byte pointed by 'ptr' and set it into |
312 | * 'encoding' field of the zlentry structure. */ |
313 | #define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ |
314 | (encoding) = ((ptr)[0]); \ |
315 | if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \ |
316 | } while(0) |
317 | |
318 | #define ZIP_ENCODING_SIZE_INVALID 0xff |
319 | /* Return the number of bytes required to encode the entry type + length. |
320 | * On error, return ZIP_ENCODING_SIZE_INVALID */ |
321 | static inline unsigned int zipEncodingLenSize(unsigned char encoding) { |
322 | if (encoding == ZIP_INT_16B || encoding == ZIP_INT_32B || |
323 | encoding == ZIP_INT_24B || encoding == ZIP_INT_64B || |
324 | encoding == ZIP_INT_8B) |
325 | return 1; |
326 | if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) |
327 | return 1; |
328 | if (encoding == ZIP_STR_06B) |
329 | return 1; |
330 | if (encoding == ZIP_STR_14B) |
331 | return 2; |
332 | if (encoding == ZIP_STR_32B) |
333 | return 5; |
334 | return ZIP_ENCODING_SIZE_INVALID; |
335 | } |
336 | |
337 | #define ZIP_ASSERT_ENCODING(encoding) do { \ |
338 | assert(zipEncodingLenSize(encoding) != ZIP_ENCODING_SIZE_INVALID); \ |
339 | } while (0) |
340 | |
341 | /* Return bytes needed to store integer encoded by 'encoding' */ |
342 | static inline unsigned int zipIntSize(unsigned char encoding) { |
343 | switch(encoding) { |
344 | case ZIP_INT_8B: return 1; |
345 | case ZIP_INT_16B: return 2; |
346 | case ZIP_INT_24B: return 3; |
347 | case ZIP_INT_32B: return 4; |
348 | case ZIP_INT_64B: return 8; |
349 | } |
350 | if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) |
351 | return 0; /* 4 bit immediate */ |
352 | /* bad encoding, covered by a previous call to ZIP_ASSERT_ENCODING */ |
353 | redis_unreachable(); |
354 | return 0; |
355 | } |
356 | |
357 | /* Write the encoding header of the entry in 'p'. If p is NULL it just returns |
358 | * the amount of bytes required to encode such a length. Arguments: |
359 | * |
360 | * 'encoding' is the encoding we are using for the entry. It could be |
361 | * ZIP_INT_* or ZIP_STR_* or between ZIP_INT_IMM_MIN and ZIP_INT_IMM_MAX |
362 | * for single-byte small immediate integers. |
363 | * |
364 | * 'rawlen' is only used for ZIP_STR_* encodings and is the length of the |
365 | * string that this entry represents. |
366 | * |
367 | * The function returns the number of bytes used by the encoding/length |
368 | * header stored in 'p'. */ |
369 | unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) { |
370 | unsigned char len = 1, buf[5]; |
371 | |
372 | if (ZIP_IS_STR(encoding)) { |
373 | /* Although encoding is given it may not be set for strings, |
374 | * so we determine it here using the raw length. */ |
375 | if (rawlen <= 0x3f) { |
376 | if (!p) return len; |
377 | buf[0] = ZIP_STR_06B | rawlen; |
378 | } else if (rawlen <= 0x3fff) { |
379 | len += 1; |
380 | if (!p) return len; |
381 | buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f); |
382 | buf[1] = rawlen & 0xff; |
383 | } else { |
384 | len += 4; |
385 | if (!p) return len; |
386 | buf[0] = ZIP_STR_32B; |
387 | buf[1] = (rawlen >> 24) & 0xff; |
388 | buf[2] = (rawlen >> 16) & 0xff; |
389 | buf[3] = (rawlen >> 8) & 0xff; |
390 | buf[4] = rawlen & 0xff; |
391 | } |
392 | } else { |
393 | /* Implies integer encoding, so length is always 1. */ |
394 | if (!p) return len; |
395 | buf[0] = encoding; |
396 | } |
397 | |
398 | /* Store this length at p. */ |
399 | memcpy(p,buf,len); |
400 | return len; |
401 | } |
402 | |
403 | /* Decode the entry encoding type and data length (string length for strings, |
404 | * number of bytes used for the integer for integer entries) encoded in 'ptr'. |
405 | * The 'encoding' variable is input, extracted by the caller, the 'lensize' |
406 | * variable will hold the number of bytes required to encode the entry |
407 | * length, and the 'len' variable will hold the entry length. |
408 | * On invalid encoding error, lensize is set to 0. */ |
409 | #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \ |
410 | if ((encoding) < ZIP_STR_MASK) { \ |
411 | if ((encoding) == ZIP_STR_06B) { \ |
412 | (lensize) = 1; \ |
413 | (len) = (ptr)[0] & 0x3f; \ |
414 | } else if ((encoding) == ZIP_STR_14B) { \ |
415 | (lensize) = 2; \ |
416 | (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \ |
417 | } else if ((encoding) == ZIP_STR_32B) { \ |
418 | (lensize) = 5; \ |
419 | (len) = ((uint32_t)(ptr)[1] << 24) | \ |
420 | ((uint32_t)(ptr)[2] << 16) | \ |
421 | ((uint32_t)(ptr)[3] << 8) | \ |
422 | ((uint32_t)(ptr)[4]); \ |
423 | } else { \ |
424 | (lensize) = 0; /* bad encoding, should be covered by a previous */ \ |
425 | (len) = 0; /* ZIP_ASSERT_ENCODING / zipEncodingLenSize, or */ \ |
426 | /* match the lensize after this macro with 0. */ \ |
427 | } \ |
428 | } else { \ |
429 | (lensize) = 1; \ |
430 | if ((encoding) == ZIP_INT_8B) (len) = 1; \ |
431 | else if ((encoding) == ZIP_INT_16B) (len) = 2; \ |
432 | else if ((encoding) == ZIP_INT_24B) (len) = 3; \ |
433 | else if ((encoding) == ZIP_INT_32B) (len) = 4; \ |
434 | else if ((encoding) == ZIP_INT_64B) (len) = 8; \ |
435 | else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) \ |
436 | (len) = 0; /* 4 bit immediate */ \ |
437 | else \ |
438 | (lensize) = (len) = 0; /* bad encoding */ \ |
439 | } \ |
440 | } while(0) |
441 | |
442 | /* Encode the length of the previous entry and write it to "p". This only |
443 | * uses the larger encoding (required in __ziplistCascadeUpdate). */ |
444 | int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) { |
445 | uint32_t u32; |
446 | if (p != NULL) { |
447 | p[0] = ZIP_BIG_PREVLEN; |
448 | u32 = len; |
449 | memcpy(p+1,&u32,sizeof(u32)); |
450 | memrev32ifbe(p+1); |
451 | } |
452 | return 1 + sizeof(uint32_t); |
453 | } |
454 | |
455 | /* Encode the length of the previous entry and write it to "p". Return the |
456 | * number of bytes needed to encode this length if "p" is NULL. */ |
457 | unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) { |
458 | if (p == NULL) { |
459 | return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(uint32_t) + 1; |
460 | } else { |
461 | if (len < ZIP_BIG_PREVLEN) { |
462 | p[0] = len; |
463 | return 1; |
464 | } else { |
465 | return zipStorePrevEntryLengthLarge(p,len); |
466 | } |
467 | } |
468 | } |
469 | |
470 | /* Return the number of bytes used to encode the length of the previous |
471 | * entry. The length is returned by setting the var 'prevlensize'. */ |
472 | #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \ |
473 | if ((ptr)[0] < ZIP_BIG_PREVLEN) { \ |
474 | (prevlensize) = 1; \ |
475 | } else { \ |
476 | (prevlensize) = 5; \ |
477 | } \ |
478 | } while(0) |
479 | |
480 | /* Return the length of the previous element, and the number of bytes that |
481 | * are used in order to encode the previous element length. |
482 | * 'ptr' must point to the prevlen prefix of an entry (that encodes the |
483 | * length of the previous entry in order to navigate the elements backward). |
484 | * The length of the previous entry is stored in 'prevlen', the number of |
485 | * bytes needed to encode the previous entry length are stored in |
486 | * 'prevlensize'. */ |
487 | #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \ |
488 | ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \ |
489 | if ((prevlensize) == 1) { \ |
490 | (prevlen) = (ptr)[0]; \ |
491 | } else { /* prevlensize == 5 */ \ |
492 | (prevlen) = ((ptr)[4] << 24) | \ |
493 | ((ptr)[3] << 16) | \ |
494 | ((ptr)[2] << 8) | \ |
495 | ((ptr)[1]); \ |
496 | } \ |
497 | } while(0) |
498 | |
499 | /* Given a pointer 'p' to the prevlen info that prefixes an entry, this |
500 | * function returns the difference in number of bytes needed to encode |
501 | * the prevlen if the previous entry changes of size. |
502 | * |
503 | * So if A is the number of bytes used right now to encode the 'prevlen' |
504 | * field. |
505 | * |
506 | * And B is the number of bytes that are needed in order to encode the |
507 | * 'prevlen' if the previous element will be updated to one of size 'len'. |
508 | * |
509 | * Then the function returns B - A |
510 | * |
511 | * So the function returns a positive number if more space is needed, |
512 | * a negative number if less space is needed, or zero if the same space |
513 | * is needed. */ |
514 | int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { |
515 | unsigned int prevlensize; |
516 | ZIP_DECODE_PREVLENSIZE(p, prevlensize); |
517 | return zipStorePrevEntryLength(NULL, len) - prevlensize; |
518 | } |
519 | |
520 | /* Check if string pointed to by 'entry' can be encoded as an integer. |
521 | * Stores the integer value in 'v' and its encoding in 'encoding'. */ |
522 | int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) { |
523 | long long value; |
524 | |
525 | if (entrylen >= 32 || entrylen == 0) return 0; |
526 | if (string2ll((char*)entry,entrylen,&value)) { |
527 | /* Great, the string can be encoded. Check what's the smallest |
528 | * of our encoding types that can hold this value. */ |
529 | if (value >= 0 && value <= 12) { |
530 | *encoding = ZIP_INT_IMM_MIN+value; |
531 | } else if (value >= INT8_MIN && value <= INT8_MAX) { |
532 | *encoding = ZIP_INT_8B; |
533 | } else if (value >= INT16_MIN && value <= INT16_MAX) { |
534 | *encoding = ZIP_INT_16B; |
535 | } else if (value >= INT24_MIN && value <= INT24_MAX) { |
536 | *encoding = ZIP_INT_24B; |
537 | } else if (value >= INT32_MIN && value <= INT32_MAX) { |
538 | *encoding = ZIP_INT_32B; |
539 | } else { |
540 | *encoding = ZIP_INT_64B; |
541 | } |
542 | *v = value; |
543 | return 1; |
544 | } |
545 | return 0; |
546 | } |
547 | |
548 | /* Store integer 'value' at 'p', encoded as 'encoding' */ |
549 | void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) { |
550 | int16_t i16; |
551 | int32_t i32; |
552 | int64_t i64; |
553 | if (encoding == ZIP_INT_8B) { |
554 | ((int8_t*)p)[0] = (int8_t)value; |
555 | } else if (encoding == ZIP_INT_16B) { |
556 | i16 = value; |
557 | memcpy(p,&i16,sizeof(i16)); |
558 | memrev16ifbe(p); |
559 | } else if (encoding == ZIP_INT_24B) { |
560 | i32 = ((uint64_t)value)<<8; |
561 | memrev32ifbe(&i32); |
562 | memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t)); |
563 | } else if (encoding == ZIP_INT_32B) { |
564 | i32 = value; |
565 | memcpy(p,&i32,sizeof(i32)); |
566 | memrev32ifbe(p); |
567 | } else if (encoding == ZIP_INT_64B) { |
568 | i64 = value; |
569 | memcpy(p,&i64,sizeof(i64)); |
570 | memrev64ifbe(p); |
571 | } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { |
572 | /* Nothing to do, the value is stored in the encoding itself. */ |
573 | } else { |
574 | assert(NULL); |
575 | } |
576 | } |
577 | |
578 | /* Read integer encoded as 'encoding' from 'p' */ |
579 | int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { |
580 | int16_t i16; |
581 | int32_t i32; |
582 | int64_t i64, ret = 0; |
583 | if (encoding == ZIP_INT_8B) { |
584 | ret = ((int8_t*)p)[0]; |
585 | } else if (encoding == ZIP_INT_16B) { |
586 | memcpy(&i16,p,sizeof(i16)); |
587 | memrev16ifbe(&i16); |
588 | ret = i16; |
589 | } else if (encoding == ZIP_INT_32B) { |
590 | memcpy(&i32,p,sizeof(i32)); |
591 | memrev32ifbe(&i32); |
592 | ret = i32; |
593 | } else if (encoding == ZIP_INT_24B) { |
594 | i32 = 0; |
595 | memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t)); |
596 | memrev32ifbe(&i32); |
597 | ret = i32>>8; |
598 | } else if (encoding == ZIP_INT_64B) { |
599 | memcpy(&i64,p,sizeof(i64)); |
600 | memrev64ifbe(&i64); |
601 | ret = i64; |
602 | } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) { |
603 | ret = (encoding & ZIP_INT_IMM_MASK)-1; |
604 | } else { |
605 | assert(NULL); |
606 | } |
607 | return ret; |
608 | } |
609 | |
610 | /* Fills a struct with all information about an entry. |
611 | * This function is the "unsafe" alternative to the one below. |
612 | * Generally, all function that return a pointer to an element in the ziplist |
613 | * will assert that this element is valid, so it can be freely used. |
614 | * Generally functions such ziplistGet assume the input pointer is already |
615 | * validated (since it's the return value of another function). */ |
616 | static inline void zipEntry(unsigned char *p, zlentry *e) { |
617 | ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); |
618 | ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding); |
619 | ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); |
620 | assert(e->lensize != 0); /* check that encoding was valid. */ |
621 | e->headersize = e->prevrawlensize + e->lensize; |
622 | e->p = p; |
623 | } |
624 | |
625 | /* Fills a struct with all information about an entry. |
626 | * This function is safe to use on untrusted pointers, it'll make sure not to |
627 | * try to access memory outside the ziplist payload. |
628 | * Returns 1 if the entry is valid, and 0 otherwise. */ |
629 | static inline int zipEntrySafe(unsigned char* zl, size_t zlbytes, unsigned char *p, zlentry *e, int validate_prevlen) { |
630 | unsigned char *zlfirst = zl + ZIPLIST_HEADER_SIZE; |
631 | unsigned char *zllast = zl + zlbytes - ZIPLIST_END_SIZE; |
632 | #define OUT_OF_RANGE(p) (unlikely((p) < zlfirst || (p) > zllast)) |
633 | |
634 | /* If there's no possibility for the header to reach outside the ziplist, |
635 | * take the fast path. (max lensize and prevrawlensize are both 5 bytes) */ |
636 | if (p >= zlfirst && p + 10 < zllast) { |
637 | ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); |
638 | ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding); |
639 | ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); |
640 | e->headersize = e->prevrawlensize + e->lensize; |
641 | e->p = p; |
642 | /* We didn't call ZIP_ASSERT_ENCODING, so we check lensize was set to 0. */ |
643 | if (unlikely(e->lensize == 0)) |
644 | return 0; |
645 | /* Make sure the entry doesn't reach outside the edge of the ziplist */ |
646 | if (OUT_OF_RANGE(p + e->headersize + e->len)) |
647 | return 0; |
648 | /* Make sure prevlen doesn't reach outside the edge of the ziplist */ |
649 | if (validate_prevlen && OUT_OF_RANGE(p - e->prevrawlen)) |
650 | return 0; |
651 | return 1; |
652 | } |
653 | |
654 | /* Make sure the pointer doesn't reach outside the edge of the ziplist */ |
655 | if (OUT_OF_RANGE(p)) |
656 | return 0; |
657 | |
658 | /* Make sure the encoded prevlen header doesn't reach outside the allocation */ |
659 | ZIP_DECODE_PREVLENSIZE(p, e->prevrawlensize); |
660 | if (OUT_OF_RANGE(p + e->prevrawlensize)) |
661 | return 0; |
662 | |
663 | /* Make sure encoded entry header is valid. */ |
664 | ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding); |
665 | e->lensize = zipEncodingLenSize(e->encoding); |
666 | if (unlikely(e->lensize == ZIP_ENCODING_SIZE_INVALID)) |
667 | return 0; |
668 | |
669 | /* Make sure the encoded entry header doesn't reach outside the allocation */ |
670 | if (OUT_OF_RANGE(p + e->prevrawlensize + e->lensize)) |
671 | return 0; |
672 | |
673 | /* Decode the prevlen and entry len headers. */ |
674 | ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen); |
675 | ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len); |
676 | e->headersize = e->prevrawlensize + e->lensize; |
677 | |
678 | /* Make sure the entry doesn't reach outside the edge of the ziplist */ |
679 | if (OUT_OF_RANGE(p + e->headersize + e->len)) |
680 | return 0; |
681 | |
682 | /* Make sure prevlen doesn't reach outside the edge of the ziplist */ |
683 | if (validate_prevlen && OUT_OF_RANGE(p - e->prevrawlen)) |
684 | return 0; |
685 | |
686 | e->p = p; |
687 | return 1; |
688 | #undef OUT_OF_RANGE |
689 | } |
690 | |
691 | /* Return the total number of bytes used by the entry pointed to by 'p'. */ |
692 | static inline unsigned int zipRawEntryLengthSafe(unsigned char* zl, size_t zlbytes, unsigned char *p) { |
693 | zlentry e; |
694 | assert(zipEntrySafe(zl, zlbytes, p, &e, 0)); |
695 | return e.headersize + e.len; |
696 | } |
697 | |
698 | /* Return the total number of bytes used by the entry pointed to by 'p'. */ |
699 | static inline unsigned int zipRawEntryLength(unsigned char *p) { |
700 | zlentry e; |
701 | zipEntry(p, &e); |
702 | return e.headersize + e.len; |
703 | } |
704 | |
705 | /* Validate that the entry doesn't reach outside the ziplist allocation. */ |
706 | static inline void zipAssertValidEntry(unsigned char* zl, size_t zlbytes, unsigned char *p) { |
707 | zlentry e; |
708 | assert(zipEntrySafe(zl, zlbytes, p, &e, 1)); |
709 | } |
710 | |
711 | /* Create a new empty ziplist. */ |
712 | unsigned char *ziplistNew(void) { |
713 | unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE; |
714 | unsigned char *zl = zmalloc(bytes); |
715 | ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); |
716 | ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); |
717 | ZIPLIST_LENGTH(zl) = 0; |
718 | zl[bytes-1] = ZIP_END; |
719 | return zl; |
720 | } |
721 | |
722 | /* Resize the ziplist. */ |
723 | unsigned char *ziplistResize(unsigned char *zl, size_t len) { |
724 | assert(len < UINT32_MAX); |
725 | zl = zrealloc(zl,len); |
726 | ZIPLIST_BYTES(zl) = intrev32ifbe(len); |
727 | zl[len-1] = ZIP_END; |
728 | return zl; |
729 | } |
730 | |
731 | /* When an entry is inserted, we need to set the prevlen field of the next |
732 | * entry to equal the length of the inserted entry. It can occur that this |
733 | * length cannot be encoded in 1 byte and the next entry needs to be grow |
734 | * a bit larger to hold the 5-byte encoded prevlen. This can be done for free, |
735 | * because this only happens when an entry is already being inserted (which |
736 | * causes a realloc and memmove). However, encoding the prevlen may require |
737 | * that this entry is grown as well. This effect may cascade throughout |
738 | * the ziplist when there are consecutive entries with a size close to |
739 | * ZIP_BIG_PREVLEN, so we need to check that the prevlen can be encoded in |
740 | * every consecutive entry. |
741 | * |
742 | * Note that this effect can also happen in reverse, where the bytes required |
743 | * to encode the prevlen field can shrink. This effect is deliberately ignored, |
744 | * because it can cause a "flapping" effect where a chain prevlen fields is |
745 | * first grown and then shrunk again after consecutive inserts. Rather, the |
746 | * field is allowed to stay larger than necessary, because a large prevlen |
747 | * field implies the ziplist is holding large entries anyway. |
748 | * |
749 | * The pointer "p" points to the first entry that does NOT need to be |
750 | * updated, i.e. consecutive fields MAY need an update. */ |
751 | unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) { |
752 | zlentry cur; |
753 | size_t prevlen, prevlensize, prevoffset; /* Informat of the last changed entry. */ |
754 | size_t firstentrylen; /* Used to handle insert at head. */ |
755 | size_t rawlen, curlen = intrev32ifbe(ZIPLIST_BYTES(zl)); |
756 | size_t = 0, cnt = 0, offset; |
757 | size_t delta = 4; /* Extra bytes needed to update a entry's prevlen (5-1). */ |
758 | unsigned char *tail = zl + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)); |
759 | |
760 | /* Empty ziplist */ |
761 | if (p[0] == ZIP_END) return zl; |
762 | |
763 | zipEntry(p, &cur); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */ |
764 | firstentrylen = prevlen = cur.headersize + cur.len; |
765 | prevlensize = zipStorePrevEntryLength(NULL, prevlen); |
766 | prevoffset = p - zl; |
767 | p += prevlen; |
768 | |
769 | /* Iterate ziplist to find out how many extra bytes do we need to update it. */ |
770 | while (p[0] != ZIP_END) { |
771 | assert(zipEntrySafe(zl, curlen, p, &cur, 0)); |
772 | |
773 | /* Abort when "prevlen" has not changed. */ |
774 | if (cur.prevrawlen == prevlen) break; |
775 | |
776 | /* Abort when entry's "prevlensize" is big enough. */ |
777 | if (cur.prevrawlensize >= prevlensize) { |
778 | if (cur.prevrawlensize == prevlensize) { |
779 | zipStorePrevEntryLength(p, prevlen); |
780 | } else { |
781 | /* This would result in shrinking, which we want to avoid. |
782 | * So, set "prevlen" in the available bytes. */ |
783 | zipStorePrevEntryLengthLarge(p, prevlen); |
784 | } |
785 | break; |
786 | } |
787 | |
788 | /* cur.prevrawlen means cur is the former head entry. */ |
789 | assert(cur.prevrawlen == 0 || cur.prevrawlen + delta == prevlen); |
790 | |
791 | /* Update prev entry's info and advance the cursor. */ |
792 | rawlen = cur.headersize + cur.len; |
793 | prevlen = rawlen + delta; |
794 | prevlensize = zipStorePrevEntryLength(NULL, prevlen); |
795 | prevoffset = p - zl; |
796 | p += rawlen; |
797 | extra += delta; |
798 | cnt++; |
799 | } |
800 | |
801 | /* Extra bytes is zero all update has been done(or no need to update). */ |
802 | if (extra == 0) return zl; |
803 | |
804 | /* Update tail offset after loop. */ |
805 | if (tail == zl + prevoffset) { |
806 | /* When the last entry we need to update is also the tail, update tail offset |
807 | * unless this is the only entry that was updated (so the tail offset didn't change). */ |
808 | if (extra - delta != 0) { |
809 | ZIPLIST_TAIL_OFFSET(zl) = |
810 | intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra-delta); |
811 | } |
812 | } else { |
813 | /* Update the tail offset in cases where the last entry we updated is not the tail. */ |
814 | ZIPLIST_TAIL_OFFSET(zl) = |
815 | intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra); |
816 | } |
817 | |
818 | /* Now "p" points at the first unchanged byte in original ziplist, |
819 | * move data after that to new ziplist. */ |
820 | offset = p - zl; |
821 | zl = ziplistResize(zl, curlen + extra); |
822 | p = zl + offset; |
823 | memmove(p + extra, p, curlen - offset - 1); |
824 | p += extra; |
825 | |
826 | /* Iterate all entries that need to be updated tail to head. */ |
827 | while (cnt) { |
828 | zipEntry(zl + prevoffset, &cur); /* no need for "safe" variant since we already iterated on all these entries above. */ |
829 | rawlen = cur.headersize + cur.len; |
830 | /* Move entry to tail and reset prevlen. */ |
831 | memmove(p - (rawlen - cur.prevrawlensize), |
832 | zl + prevoffset + cur.prevrawlensize, |
833 | rawlen - cur.prevrawlensize); |
834 | p -= (rawlen + delta); |
835 | if (cur.prevrawlen == 0) { |
836 | /* "cur" is the previous head entry, update its prevlen with firstentrylen. */ |
837 | zipStorePrevEntryLength(p, firstentrylen); |
838 | } else { |
839 | /* An entry's prevlen can only increment 4 bytes. */ |
840 | zipStorePrevEntryLength(p, cur.prevrawlen+delta); |
841 | } |
842 | /* Forward to previous entry. */ |
843 | prevoffset -= cur.prevrawlen; |
844 | cnt--; |
845 | } |
846 | return zl; |
847 | } |
848 | |
849 | /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */ |
850 | unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) { |
851 | unsigned int i, totlen, deleted = 0; |
852 | size_t offset; |
853 | int nextdiff = 0; |
854 | zlentry first, tail; |
855 | size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
856 | |
857 | zipEntry(p, &first); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */ |
858 | for (i = 0; p[0] != ZIP_END && i < num; i++) { |
859 | p += zipRawEntryLengthSafe(zl, zlbytes, p); |
860 | deleted++; |
861 | } |
862 | |
863 | assert(p >= first.p); |
864 | totlen = p-first.p; /* Bytes taken by the element(s) to delete. */ |
865 | if (totlen > 0) { |
866 | uint32_t set_tail; |
867 | if (p[0] != ZIP_END) { |
868 | /* Storing `prevrawlen` in this entry may increase or decrease the |
869 | * number of bytes required compare to the current `prevrawlen`. |
870 | * There always is room to store this, because it was previously |
871 | * stored by an entry that is now being deleted. */ |
872 | nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); |
873 | |
874 | /* Note that there is always space when p jumps backward: if |
875 | * the new previous entry is large, one of the deleted elements |
876 | * had a 5 bytes prevlen header, so there is for sure at least |
877 | * 5 bytes free and we need just 4. */ |
878 | p -= nextdiff; |
879 | assert(p >= first.p && p<zl+zlbytes-1); |
880 | zipStorePrevEntryLength(p,first.prevrawlen); |
881 | |
882 | /* Update offset for tail */ |
883 | set_tail = intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen; |
884 | |
885 | /* When the tail contains more than one entry, we need to take |
886 | * "nextdiff" in account as well. Otherwise, a change in the |
887 | * size of prevlen doesn't have an effect on the *tail* offset. */ |
888 | assert(zipEntrySafe(zl, zlbytes, p, &tail, 1)); |
889 | if (p[tail.headersize+tail.len] != ZIP_END) { |
890 | set_tail = set_tail + nextdiff; |
891 | } |
892 | |
893 | /* Move tail to the front of the ziplist */ |
894 | /* since we asserted that p >= first.p. we know totlen >= 0, |
895 | * so we know that p > first.p and this is guaranteed not to reach |
896 | * beyond the allocation, even if the entries lens are corrupted. */ |
897 | size_t bytes_to_move = zlbytes-(p-zl)-1; |
898 | memmove(first.p,p,bytes_to_move); |
899 | } else { |
900 | /* The entire tail was deleted. No need to move memory. */ |
901 | set_tail = (first.p-zl)-first.prevrawlen; |
902 | } |
903 | |
904 | /* Resize the ziplist */ |
905 | offset = first.p-zl; |
906 | zlbytes -= totlen - nextdiff; |
907 | zl = ziplistResize(zl, zlbytes); |
908 | p = zl+offset; |
909 | |
910 | /* Update record count */ |
911 | ZIPLIST_INCR_LENGTH(zl,-deleted); |
912 | |
913 | /* Set the tail offset computed above */ |
914 | assert(set_tail <= zlbytes - ZIPLIST_END_SIZE); |
915 | ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(set_tail); |
916 | |
917 | /* When nextdiff != 0, the raw length of the next entry has changed, so |
918 | * we need to cascade the update throughout the ziplist */ |
919 | if (nextdiff != 0) |
920 | zl = __ziplistCascadeUpdate(zl,p); |
921 | } |
922 | return zl; |
923 | } |
924 | |
925 | /* Insert item at "p". */ |
926 | unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { |
927 | size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, newlen; |
928 | unsigned int prevlensize, prevlen = 0; |
929 | size_t offset; |
930 | int nextdiff = 0; |
931 | unsigned char encoding = 0; |
932 | long long value = 123456789; /* initialized to avoid warning. Using a value |
933 | that is easy to see if for some reason |
934 | we use it uninitialized. */ |
935 | zlentry tail; |
936 | |
937 | /* Find out prevlen for the entry that is inserted. */ |
938 | if (p[0] != ZIP_END) { |
939 | ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); |
940 | } else { |
941 | unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); |
942 | if (ptail[0] != ZIP_END) { |
943 | prevlen = zipRawEntryLengthSafe(zl, curlen, ptail); |
944 | } |
945 | } |
946 | |
947 | /* See if the entry can be encoded */ |
948 | if (zipTryEncoding(s,slen,&value,&encoding)) { |
949 | /* 'encoding' is set to the appropriate integer encoding */ |
950 | reqlen = zipIntSize(encoding); |
951 | } else { |
952 | /* 'encoding' is untouched, however zipStoreEntryEncoding will use the |
953 | * string length to figure out how to encode it. */ |
954 | reqlen = slen; |
955 | } |
956 | /* We need space for both the length of the previous entry and |
957 | * the length of the payload. */ |
958 | reqlen += zipStorePrevEntryLength(NULL,prevlen); |
959 | reqlen += zipStoreEntryEncoding(NULL,encoding,slen); |
960 | |
961 | /* When the insert position is not equal to the tail, we need to |
962 | * make sure that the next entry can hold this entry's length in |
963 | * its prevlen field. */ |
964 | int forcelarge = 0; |
965 | nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; |
966 | if (nextdiff == -4 && reqlen < 4) { |
967 | nextdiff = 0; |
968 | forcelarge = 1; |
969 | } |
970 | |
971 | /* Store offset because a realloc may change the address of zl. */ |
972 | offset = p-zl; |
973 | newlen = curlen+reqlen+nextdiff; |
974 | zl = ziplistResize(zl,newlen); |
975 | p = zl+offset; |
976 | |
977 | /* Apply memory move when necessary and update tail offset. */ |
978 | if (p[0] != ZIP_END) { |
979 | /* Subtract one because of the ZIP_END bytes */ |
980 | memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); |
981 | |
982 | /* Encode this entry's raw length in the next entry. */ |
983 | if (forcelarge) |
984 | zipStorePrevEntryLengthLarge(p+reqlen,reqlen); |
985 | else |
986 | zipStorePrevEntryLength(p+reqlen,reqlen); |
987 | |
988 | /* Update offset for tail */ |
989 | ZIPLIST_TAIL_OFFSET(zl) = |
990 | intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); |
991 | |
992 | /* When the tail contains more than one entry, we need to take |
993 | * "nextdiff" in account as well. Otherwise, a change in the |
994 | * size of prevlen doesn't have an effect on the *tail* offset. */ |
995 | assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1)); |
996 | if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { |
997 | ZIPLIST_TAIL_OFFSET(zl) = |
998 | intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); |
999 | } |
1000 | } else { |
1001 | /* This element will be the new tail. */ |
1002 | ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); |
1003 | } |
1004 | |
1005 | /* When nextdiff != 0, the raw length of the next entry has changed, so |
1006 | * we need to cascade the update throughout the ziplist */ |
1007 | if (nextdiff != 0) { |
1008 | offset = p-zl; |
1009 | zl = __ziplistCascadeUpdate(zl,p+reqlen); |
1010 | p = zl+offset; |
1011 | } |
1012 | |
1013 | /* Write the entry */ |
1014 | p += zipStorePrevEntryLength(p,prevlen); |
1015 | p += zipStoreEntryEncoding(p,encoding,slen); |
1016 | if (ZIP_IS_STR(encoding)) { |
1017 | memcpy(p,s,slen); |
1018 | } else { |
1019 | zipSaveInteger(p,value,encoding); |
1020 | } |
1021 | ZIPLIST_INCR_LENGTH(zl,1); |
1022 | return zl; |
1023 | } |
1024 | |
1025 | /* Merge ziplists 'first' and 'second' by appending 'second' to 'first'. |
1026 | * |
1027 | * NOTE: The larger ziplist is reallocated to contain the new merged ziplist. |
1028 | * Either 'first' or 'second' can be used for the result. The parameter not |
1029 | * used will be free'd and set to NULL. |
1030 | * |
1031 | * After calling this function, the input parameters are no longer valid since |
1032 | * they are changed and free'd in-place. |
1033 | * |
1034 | * The result ziplist is the contents of 'first' followed by 'second'. |
1035 | * |
1036 | * On failure: returns NULL if the merge is impossible. |
1037 | * On success: returns the merged ziplist (which is expanded version of either |
1038 | * 'first' or 'second', also frees the other unused input ziplist, and sets the |
1039 | * input ziplist argument equal to newly reallocated ziplist return value. */ |
1040 | unsigned char *ziplistMerge(unsigned char **first, unsigned char **second) { |
1041 | /* If any params are null, we can't merge, so NULL. */ |
1042 | if (first == NULL || *first == NULL || second == NULL || *second == NULL) |
1043 | return NULL; |
1044 | |
1045 | /* Can't merge same list into itself. */ |
1046 | if (*first == *second) |
1047 | return NULL; |
1048 | |
1049 | size_t first_bytes = intrev32ifbe(ZIPLIST_BYTES(*first)); |
1050 | size_t first_len = intrev16ifbe(ZIPLIST_LENGTH(*first)); |
1051 | |
1052 | size_t second_bytes = intrev32ifbe(ZIPLIST_BYTES(*second)); |
1053 | size_t second_len = intrev16ifbe(ZIPLIST_LENGTH(*second)); |
1054 | |
1055 | int append; |
1056 | unsigned char *source, *target; |
1057 | size_t target_bytes, source_bytes; |
1058 | /* Pick the largest ziplist so we can resize easily in-place. |
1059 | * We must also track if we are now appending or prepending to |
1060 | * the target ziplist. */ |
1061 | if (first_len >= second_len) { |
1062 | /* retain first, append second to first. */ |
1063 | target = *first; |
1064 | target_bytes = first_bytes; |
1065 | source = *second; |
1066 | source_bytes = second_bytes; |
1067 | append = 1; |
1068 | } else { |
1069 | /* else, retain second, prepend first to second. */ |
1070 | target = *second; |
1071 | target_bytes = second_bytes; |
1072 | source = *first; |
1073 | source_bytes = first_bytes; |
1074 | append = 0; |
1075 | } |
1076 | |
1077 | /* Calculate final bytes (subtract one pair of metadata) */ |
1078 | size_t zlbytes = first_bytes + second_bytes - |
1079 | ZIPLIST_HEADER_SIZE - ZIPLIST_END_SIZE; |
1080 | size_t zllength = first_len + second_len; |
1081 | |
1082 | /* Combined zl length should be limited within UINT16_MAX */ |
1083 | zllength = zllength < UINT16_MAX ? zllength : UINT16_MAX; |
1084 | |
1085 | /* larger values can't be stored into ZIPLIST_BYTES */ |
1086 | assert(zlbytes < UINT32_MAX); |
1087 | |
1088 | /* Save offset positions before we start ripping memory apart. */ |
1089 | size_t first_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*first)); |
1090 | size_t second_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*second)); |
1091 | |
1092 | /* Extend target to new zlbytes then append or prepend source. */ |
1093 | target = zrealloc(target, zlbytes); |
1094 | if (append) { |
1095 | /* append == appending to target */ |
1096 | /* Copy source after target (copying over original [END]): |
1097 | * [TARGET - END, SOURCE - HEADER] */ |
1098 | memcpy(target + target_bytes - ZIPLIST_END_SIZE, |
1099 | source + ZIPLIST_HEADER_SIZE, |
1100 | source_bytes - ZIPLIST_HEADER_SIZE); |
1101 | } else { |
1102 | /* !append == prepending to target */ |
1103 | /* Move target *contents* exactly size of (source - [END]), |
1104 | * then copy source into vacated space (source - [END]): |
1105 | * [SOURCE - END, TARGET - HEADER] */ |
1106 | memmove(target + source_bytes - ZIPLIST_END_SIZE, |
1107 | target + ZIPLIST_HEADER_SIZE, |
1108 | target_bytes - ZIPLIST_HEADER_SIZE); |
1109 | memcpy(target, source, source_bytes - ZIPLIST_END_SIZE); |
1110 | } |
1111 | |
1112 | /* Update header metadata. */ |
1113 | ZIPLIST_BYTES(target) = intrev32ifbe(zlbytes); |
1114 | ZIPLIST_LENGTH(target) = intrev16ifbe(zllength); |
1115 | /* New tail offset is: |
1116 | * + N bytes of first ziplist |
1117 | * - 1 byte for [END] of first ziplist |
1118 | * + M bytes for the offset of the original tail of the second ziplist |
1119 | * - J bytes for HEADER because second_offset keeps no header. */ |
1120 | ZIPLIST_TAIL_OFFSET(target) = intrev32ifbe( |
1121 | (first_bytes - ZIPLIST_END_SIZE) + |
1122 | (second_offset - ZIPLIST_HEADER_SIZE)); |
1123 | |
1124 | /* __ziplistCascadeUpdate just fixes the prev length values until it finds a |
1125 | * correct prev length value (then it assumes the rest of the list is okay). |
1126 | * We tell CascadeUpdate to start at the first ziplist's tail element to fix |
1127 | * the merge seam. */ |
1128 | target = __ziplistCascadeUpdate(target, target+first_offset); |
1129 | |
1130 | /* Now free and NULL out what we didn't realloc */ |
1131 | if (append) { |
1132 | zfree(*second); |
1133 | *second = NULL; |
1134 | *first = target; |
1135 | } else { |
1136 | zfree(*first); |
1137 | *first = NULL; |
1138 | *second = target; |
1139 | } |
1140 | return target; |
1141 | } |
1142 | |
1143 | unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { |
1144 | unsigned char *p; |
1145 | p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl); |
1146 | return __ziplistInsert(zl,p,s,slen); |
1147 | } |
1148 | |
1149 | /* Returns an offset to use for iterating with ziplistNext. When the given |
1150 | * index is negative, the list is traversed back to front. When the list |
1151 | * doesn't contain an element at the provided index, NULL is returned. */ |
1152 | unsigned char *ziplistIndex(unsigned char *zl, int index) { |
1153 | unsigned char *p; |
1154 | unsigned int prevlensize, prevlen = 0; |
1155 | size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
1156 | if (index < 0) { |
1157 | index = (-index)-1; |
1158 | p = ZIPLIST_ENTRY_TAIL(zl); |
1159 | if (p[0] != ZIP_END) { |
1160 | /* No need for "safe" check: when going backwards, we know the header |
1161 | * we're parsing is in the range, we just need to assert (below) that |
1162 | * the size we take doesn't cause p to go outside the allocation. */ |
1163 | ZIP_DECODE_PREVLENSIZE(p, prevlensize); |
1164 | assert(p + prevlensize < zl + zlbytes - ZIPLIST_END_SIZE); |
1165 | ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); |
1166 | while (prevlen > 0 && index--) { |
1167 | p -= prevlen; |
1168 | assert(p >= zl + ZIPLIST_HEADER_SIZE && p < zl + zlbytes - ZIPLIST_END_SIZE); |
1169 | ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); |
1170 | } |
1171 | } |
1172 | } else { |
1173 | p = ZIPLIST_ENTRY_HEAD(zl); |
1174 | while (index--) { |
1175 | /* Use the "safe" length: When we go forward, we need to be careful |
1176 | * not to decode an entry header if it's past the ziplist allocation. */ |
1177 | p += zipRawEntryLengthSafe(zl, zlbytes, p); |
1178 | if (p[0] == ZIP_END) |
1179 | break; |
1180 | } |
1181 | } |
1182 | if (p[0] == ZIP_END || index > 0) |
1183 | return NULL; |
1184 | zipAssertValidEntry(zl, zlbytes, p); |
1185 | return p; |
1186 | } |
1187 | |
1188 | /* Return pointer to next entry in ziplist. |
1189 | * |
1190 | * zl is the pointer to the ziplist |
1191 | * p is the pointer to the current element |
1192 | * |
1193 | * The element after 'p' is returned, otherwise NULL if we are at the end. */ |
1194 | unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) { |
1195 | ((void) zl); |
1196 | size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
1197 | |
1198 | /* "p" could be equal to ZIP_END, caused by ziplistDelete, |
1199 | * and we should return NULL. Otherwise, we should return NULL |
1200 | * when the *next* element is ZIP_END (there is no next entry). */ |
1201 | if (p[0] == ZIP_END) { |
1202 | return NULL; |
1203 | } |
1204 | |
1205 | p += zipRawEntryLength(p); |
1206 | if (p[0] == ZIP_END) { |
1207 | return NULL; |
1208 | } |
1209 | |
1210 | zipAssertValidEntry(zl, zlbytes, p); |
1211 | return p; |
1212 | } |
1213 | |
1214 | /* Return pointer to previous entry in ziplist. */ |
1215 | unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) { |
1216 | unsigned int prevlensize, prevlen = 0; |
1217 | |
1218 | /* Iterating backwards from ZIP_END should return the tail. When "p" is |
1219 | * equal to the first element of the list, we're already at the head, |
1220 | * and should return NULL. */ |
1221 | if (p[0] == ZIP_END) { |
1222 | p = ZIPLIST_ENTRY_TAIL(zl); |
1223 | return (p[0] == ZIP_END) ? NULL : p; |
1224 | } else if (p == ZIPLIST_ENTRY_HEAD(zl)) { |
1225 | return NULL; |
1226 | } else { |
1227 | ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); |
1228 | assert(prevlen > 0); |
1229 | p-=prevlen; |
1230 | size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
1231 | zipAssertValidEntry(zl, zlbytes, p); |
1232 | return p; |
1233 | } |
1234 | } |
1235 | |
1236 | /* Get entry pointed to by 'p' and store in either '*sstr' or 'sval' depending |
1237 | * on the encoding of the entry. '*sstr' is always set to NULL to be able |
1238 | * to find out whether the string pointer or the integer value was set. |
1239 | * Return 0 if 'p' points to the end of the ziplist, 1 otherwise. */ |
1240 | unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) { |
1241 | zlentry entry; |
1242 | if (p == NULL || p[0] == ZIP_END) return 0; |
1243 | if (sstr) *sstr = NULL; |
1244 | |
1245 | zipEntry(p, &entry); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */ |
1246 | if (ZIP_IS_STR(entry.encoding)) { |
1247 | if (sstr) { |
1248 | *slen = entry.len; |
1249 | *sstr = p+entry.headersize; |
1250 | } |
1251 | } else { |
1252 | if (sval) { |
1253 | *sval = zipLoadInteger(p+entry.headersize,entry.encoding); |
1254 | } |
1255 | } |
1256 | return 1; |
1257 | } |
1258 | |
1259 | /* Insert an entry at "p". */ |
1260 | unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { |
1261 | return __ziplistInsert(zl,p,s,slen); |
1262 | } |
1263 | |
1264 | /* Delete a single entry from the ziplist, pointed to by *p. |
1265 | * Also update *p in place, to be able to iterate over the |
1266 | * ziplist, while deleting entries. */ |
1267 | unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { |
1268 | size_t offset = *p-zl; |
1269 | zl = __ziplistDelete(zl,*p,1); |
1270 | |
1271 | /* Store pointer to current element in p, because ziplistDelete will |
1272 | * do a realloc which might result in a different "zl"-pointer. |
1273 | * When the delete direction is back to front, we might delete the last |
1274 | * entry and end up with "p" pointing to ZIP_END, so check this. */ |
1275 | *p = zl+offset; |
1276 | return zl; |
1277 | } |
1278 | |
1279 | /* Delete a range of entries from the ziplist. */ |
1280 | unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num) { |
1281 | unsigned char *p = ziplistIndex(zl,index); |
1282 | return (p == NULL) ? zl : __ziplistDelete(zl,p,num); |
1283 | } |
1284 | |
1285 | /* Replaces the entry at p. This is equivalent to a delete and an insert, |
1286 | * but avoids some overhead when replacing a value of the same size. */ |
1287 | unsigned char *ziplistReplace(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { |
1288 | |
1289 | /* get metadata of the current entry */ |
1290 | zlentry entry; |
1291 | zipEntry(p, &entry); |
1292 | |
1293 | /* compute length of entry to store, excluding prevlen */ |
1294 | unsigned int reqlen; |
1295 | unsigned char encoding = 0; |
1296 | long long value = 123456789; /* initialized to avoid warning. */ |
1297 | if (zipTryEncoding(s,slen,&value,&encoding)) { |
1298 | reqlen = zipIntSize(encoding); /* encoding is set */ |
1299 | } else { |
1300 | reqlen = slen; /* encoding == 0 */ |
1301 | } |
1302 | reqlen += zipStoreEntryEncoding(NULL,encoding,slen); |
1303 | |
1304 | if (reqlen == entry.lensize + entry.len) { |
1305 | /* Simply overwrite the element. */ |
1306 | p += entry.prevrawlensize; |
1307 | p += zipStoreEntryEncoding(p,encoding,slen); |
1308 | if (ZIP_IS_STR(encoding)) { |
1309 | memcpy(p,s,slen); |
1310 | } else { |
1311 | zipSaveInteger(p,value,encoding); |
1312 | } |
1313 | } else { |
1314 | /* Fallback. */ |
1315 | zl = ziplistDelete(zl,&p); |
1316 | zl = ziplistInsert(zl,p,s,slen); |
1317 | } |
1318 | return zl; |
1319 | } |
1320 | |
1321 | /* Compare entry pointer to by 'p' with 'sstr' of length 'slen'. */ |
1322 | /* Return 1 if equal. */ |
1323 | unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) { |
1324 | zlentry entry; |
1325 | unsigned char sencoding; |
1326 | long long zval, sval; |
1327 | if (p[0] == ZIP_END) return 0; |
1328 | |
1329 | zipEntry(p, &entry); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */ |
1330 | if (ZIP_IS_STR(entry.encoding)) { |
1331 | /* Raw compare */ |
1332 | if (entry.len == slen) { |
1333 | return memcmp(p+entry.headersize,sstr,slen) == 0; |
1334 | } else { |
1335 | return 0; |
1336 | } |
1337 | } else { |
1338 | /* Try to compare encoded values. Don't compare encoding because |
1339 | * different implementations may encoded integers differently. */ |
1340 | if (zipTryEncoding(sstr,slen,&sval,&sencoding)) { |
1341 | zval = zipLoadInteger(p+entry.headersize,entry.encoding); |
1342 | return zval == sval; |
1343 | } |
1344 | } |
1345 | return 0; |
1346 | } |
1347 | |
1348 | /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries |
1349 | * between every comparison. Returns NULL when the field could not be found. */ |
1350 | unsigned char *ziplistFind(unsigned char *zl, unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) { |
1351 | int skipcnt = 0; |
1352 | unsigned char vencoding = 0; |
1353 | long long vll = 0; |
1354 | size_t zlbytes = ziplistBlobLen(zl); |
1355 | |
1356 | while (p[0] != ZIP_END) { |
1357 | struct zlentry e; |
1358 | unsigned char *q; |
1359 | |
1360 | assert(zipEntrySafe(zl, zlbytes, p, &e, 1)); |
1361 | q = p + e.prevrawlensize + e.lensize; |
1362 | |
1363 | if (skipcnt == 0) { |
1364 | /* Compare current entry with specified entry */ |
1365 | if (ZIP_IS_STR(e.encoding)) { |
1366 | if (e.len == vlen && memcmp(q, vstr, vlen) == 0) { |
1367 | return p; |
1368 | } |
1369 | } else { |
1370 | /* Find out if the searched field can be encoded. Note that |
1371 | * we do it only the first time, once done vencoding is set |
1372 | * to non-zero and vll is set to the integer value. */ |
1373 | if (vencoding == 0) { |
1374 | if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) { |
1375 | /* If the entry can't be encoded we set it to |
1376 | * UCHAR_MAX so that we don't retry again the next |
1377 | * time. */ |
1378 | vencoding = UCHAR_MAX; |
1379 | } |
1380 | /* Must be non-zero by now */ |
1381 | assert(vencoding); |
1382 | } |
1383 | |
1384 | /* Compare current entry with specified entry, do it only |
1385 | * if vencoding != UCHAR_MAX because if there is no encoding |
1386 | * possible for the field it can't be a valid integer. */ |
1387 | if (vencoding != UCHAR_MAX) { |
1388 | long long ll = zipLoadInteger(q, e.encoding); |
1389 | if (ll == vll) { |
1390 | return p; |
1391 | } |
1392 | } |
1393 | } |
1394 | |
1395 | /* Reset skip count */ |
1396 | skipcnt = skip; |
1397 | } else { |
1398 | /* Skip entry */ |
1399 | skipcnt--; |
1400 | } |
1401 | |
1402 | /* Move to next entry */ |
1403 | p = q + e.len; |
1404 | } |
1405 | |
1406 | return NULL; |
1407 | } |
1408 | |
1409 | /* Return length of ziplist. */ |
1410 | unsigned int ziplistLen(unsigned char *zl) { |
1411 | unsigned int len = 0; |
1412 | if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) { |
1413 | len = intrev16ifbe(ZIPLIST_LENGTH(zl)); |
1414 | } else { |
1415 | unsigned char *p = zl+ZIPLIST_HEADER_SIZE; |
1416 | size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
1417 | while (*p != ZIP_END) { |
1418 | p += zipRawEntryLengthSafe(zl, zlbytes, p); |
1419 | len++; |
1420 | } |
1421 | |
1422 | /* Re-store length if small enough */ |
1423 | if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len); |
1424 | } |
1425 | return len; |
1426 | } |
1427 | |
1428 | /* Return ziplist blob size in bytes. */ |
1429 | size_t ziplistBlobLen(unsigned char *zl) { |
1430 | return intrev32ifbe(ZIPLIST_BYTES(zl)); |
1431 | } |
1432 | |
1433 | void ziplistRepr(unsigned char *zl) { |
1434 | unsigned char *p; |
1435 | int index = 0; |
1436 | zlentry entry; |
1437 | size_t zlbytes = ziplistBlobLen(zl); |
1438 | |
1439 | printf( |
1440 | "{total bytes %u} " |
1441 | "{num entries %u}\n" |
1442 | "{tail offset %u}\n" , |
1443 | intrev32ifbe(ZIPLIST_BYTES(zl)), |
1444 | intrev16ifbe(ZIPLIST_LENGTH(zl)), |
1445 | intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))); |
1446 | p = ZIPLIST_ENTRY_HEAD(zl); |
1447 | while(*p != ZIP_END) { |
1448 | assert(zipEntrySafe(zl, zlbytes, p, &entry, 1)); |
1449 | printf( |
1450 | "{\n" |
1451 | "\taddr 0x%08lx,\n" |
1452 | "\tindex %2d,\n" |
1453 | "\toffset %5lu,\n" |
1454 | "\thdr+entry len: %5u,\n" |
1455 | "\thdr len%2u,\n" |
1456 | "\tprevrawlen: %5u,\n" |
1457 | "\tprevrawlensize: %2u,\n" |
1458 | "\tpayload %5u\n" , |
1459 | (long unsigned)p, |
1460 | index, |
1461 | (unsigned long) (p-zl), |
1462 | entry.headersize+entry.len, |
1463 | entry.headersize, |
1464 | entry.prevrawlen, |
1465 | entry.prevrawlensize, |
1466 | entry.len); |
1467 | printf("\tbytes: " ); |
1468 | for (unsigned int i = 0; i < entry.headersize+entry.len; i++) { |
1469 | printf("%02x|" ,p[i]); |
1470 | } |
1471 | printf("\n" ); |
1472 | p += entry.headersize; |
1473 | if (ZIP_IS_STR(entry.encoding)) { |
1474 | printf("\t[str]" ); |
1475 | if (entry.len > 40) { |
1476 | if (fwrite(p,40,1,stdout) == 0) perror("fwrite" ); |
1477 | printf("..." ); |
1478 | } else { |
1479 | if (entry.len && |
1480 | fwrite(p,entry.len,1,stdout) == 0) perror("fwrite" ); |
1481 | } |
1482 | } else { |
1483 | printf("\t[int]%lld" , (long long) zipLoadInteger(p,entry.encoding)); |
1484 | } |
1485 | printf("\n}\n" ); |
1486 | p += entry.len; |
1487 | index++; |
1488 | } |
1489 | printf("{end}\n\n" ); |
1490 | } |
1491 | |
1492 | /* Validate the integrity of the data structure. |
1493 | * when `deep` is 0, only the integrity of the header is validated. |
1494 | * when `deep` is 1, we scan all the entries one by one. */ |
1495 | int ziplistValidateIntegrity(unsigned char *zl, size_t size, int deep, |
1496 | ziplistValidateEntryCB entry_cb, void *cb_userdata) { |
1497 | /* check that we can actually read the header. (and ZIP_END) */ |
1498 | if (size < ZIPLIST_HEADER_SIZE + ZIPLIST_END_SIZE) |
1499 | return 0; |
1500 | |
1501 | /* check that the encoded size in the header must match the allocated size. */ |
1502 | size_t bytes = intrev32ifbe(ZIPLIST_BYTES(zl)); |
1503 | if (bytes != size) |
1504 | return 0; |
1505 | |
1506 | /* the last byte must be the terminator. */ |
1507 | if (zl[size - ZIPLIST_END_SIZE] != ZIP_END) |
1508 | return 0; |
1509 | |
1510 | /* make sure the tail offset isn't reaching outside the allocation. */ |
1511 | if (intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)) > size - ZIPLIST_END_SIZE) |
1512 | return 0; |
1513 | |
1514 | if (!deep) |
1515 | return 1; |
1516 | |
1517 | unsigned int count = 0; |
1518 | unsigned int = intrev16ifbe(ZIPLIST_LENGTH(zl)); |
1519 | unsigned char *p = ZIPLIST_ENTRY_HEAD(zl); |
1520 | unsigned char *prev = NULL; |
1521 | size_t prev_raw_size = 0; |
1522 | while(*p != ZIP_END) { |
1523 | struct zlentry e; |
1524 | /* Decode the entry headers and fail if invalid or reaches outside the allocation */ |
1525 | if (!zipEntrySafe(zl, size, p, &e, 1)) |
1526 | return 0; |
1527 | |
1528 | /* Make sure the record stating the prev entry size is correct. */ |
1529 | if (e.prevrawlen != prev_raw_size) |
1530 | return 0; |
1531 | |
1532 | /* Optionally let the caller validate the entry too. */ |
1533 | if (entry_cb && !entry_cb(p, header_count, cb_userdata)) |
1534 | return 0; |
1535 | |
1536 | /* Move to the next entry */ |
1537 | prev_raw_size = e.headersize + e.len; |
1538 | prev = p; |
1539 | p += e.headersize + e.len; |
1540 | count++; |
1541 | } |
1542 | |
1543 | /* Make sure 'p' really does point to the end of the ziplist. */ |
1544 | if (p != zl + bytes - ZIPLIST_END_SIZE) |
1545 | return 0; |
1546 | |
1547 | /* Make sure the <zltail> entry really do point to the start of the last entry. */ |
1548 | if (prev != NULL && prev != ZIPLIST_ENTRY_TAIL(zl)) |
1549 | return 0; |
1550 | |
1551 | /* Check that the count in the header is correct */ |
1552 | if (header_count != UINT16_MAX && count != header_count) |
1553 | return 0; |
1554 | |
1555 | return 1; |
1556 | } |
1557 | |
1558 | /* Randomly select a pair of key and value. |
1559 | * total_count is a pre-computed length/2 of the ziplist (to avoid calls to ziplistLen) |
1560 | * 'key' and 'val' are used to store the result key value pair. |
1561 | * 'val' can be NULL if the value is not needed. */ |
1562 | void ziplistRandomPair(unsigned char *zl, unsigned long total_count, ziplistEntry *key, ziplistEntry *val) { |
1563 | int ret; |
1564 | unsigned char *p; |
1565 | |
1566 | /* Avoid div by zero on corrupt ziplist */ |
1567 | assert(total_count); |
1568 | |
1569 | /* Generate even numbers, because ziplist saved K-V pair */ |
1570 | int r = (rand() % total_count) * 2; |
1571 | p = ziplistIndex(zl, r); |
1572 | ret = ziplistGet(p, &key->sval, &key->slen, &key->lval); |
1573 | assert(ret != 0); |
1574 | |
1575 | if (!val) |
1576 | return; |
1577 | p = ziplistNext(zl, p); |
1578 | ret = ziplistGet(p, &val->sval, &val->slen, &val->lval); |
1579 | assert(ret != 0); |
1580 | } |
1581 | |
1582 | /* int compare for qsort */ |
1583 | int uintCompare(const void *a, const void *b) { |
1584 | return (*(unsigned int *) a - *(unsigned int *) b); |
1585 | } |
1586 | |
1587 | /* Helper method to store a string into from val or lval into dest */ |
1588 | static inline void ziplistSaveValue(unsigned char *val, unsigned int len, long long lval, ziplistEntry *dest) { |
1589 | dest->sval = val; |
1590 | dest->slen = len; |
1591 | dest->lval = lval; |
1592 | } |
1593 | |
1594 | /* Randomly select count of key value pairs and store into 'keys' and |
1595 | * 'vals' args. The order of the picked entries is random, and the selections |
1596 | * are non-unique (repetitions are possible). |
1597 | * The 'vals' arg can be NULL in which case we skip these. */ |
1598 | void ziplistRandomPairs(unsigned char *zl, unsigned int count, ziplistEntry *keys, ziplistEntry *vals) { |
1599 | unsigned char *p, *key, *value; |
1600 | unsigned int klen = 0, vlen = 0; |
1601 | long long klval = 0, vlval = 0; |
1602 | |
1603 | /* Notice: the index member must be first due to the use in uintCompare */ |
1604 | typedef struct { |
1605 | unsigned int index; |
1606 | unsigned int order; |
1607 | } rand_pick; |
1608 | rand_pick *picks = zmalloc(sizeof(rand_pick)*count); |
1609 | unsigned int total_size = ziplistLen(zl)/2; |
1610 | |
1611 | /* Avoid div by zero on corrupt ziplist */ |
1612 | assert(total_size); |
1613 | |
1614 | /* create a pool of random indexes (some may be duplicate). */ |
1615 | for (unsigned int i = 0; i < count; i++) { |
1616 | picks[i].index = (rand() % total_size) * 2; /* Generate even indexes */ |
1617 | /* keep track of the order we picked them */ |
1618 | picks[i].order = i; |
1619 | } |
1620 | |
1621 | /* sort by indexes. */ |
1622 | qsort(picks, count, sizeof(rand_pick), uintCompare); |
1623 | |
1624 | /* fetch the elements form the ziplist into a output array respecting the original order. */ |
1625 | unsigned int zipindex = picks[0].index, pickindex = 0; |
1626 | p = ziplistIndex(zl, zipindex); |
1627 | while (ziplistGet(p, &key, &klen, &klval) && pickindex < count) { |
1628 | p = ziplistNext(zl, p); |
1629 | assert(ziplistGet(p, &value, &vlen, &vlval)); |
1630 | while (pickindex < count && zipindex == picks[pickindex].index) { |
1631 | int storeorder = picks[pickindex].order; |
1632 | ziplistSaveValue(key, klen, klval, &keys[storeorder]); |
1633 | if (vals) |
1634 | ziplistSaveValue(value, vlen, vlval, &vals[storeorder]); |
1635 | pickindex++; |
1636 | } |
1637 | zipindex += 2; |
1638 | p = ziplistNext(zl, p); |
1639 | } |
1640 | |
1641 | zfree(picks); |
1642 | } |
1643 | |
1644 | /* Randomly select count of key value pairs and store into 'keys' and |
1645 | * 'vals' args. The selections are unique (no repetitions), and the order of |
1646 | * the picked entries is NOT-random. |
1647 | * The 'vals' arg can be NULL in which case we skip these. |
1648 | * The return value is the number of items picked which can be lower than the |
1649 | * requested count if the ziplist doesn't hold enough pairs. */ |
1650 | unsigned int ziplistRandomPairsUnique(unsigned char *zl, unsigned int count, ziplistEntry *keys, ziplistEntry *vals) { |
1651 | unsigned char *p, *key; |
1652 | unsigned int klen = 0; |
1653 | long long klval = 0; |
1654 | unsigned int total_size = ziplistLen(zl)/2; |
1655 | unsigned int index = 0; |
1656 | if (count > total_size) |
1657 | count = total_size; |
1658 | |
1659 | /* To only iterate once, every time we try to pick a member, the probability |
1660 | * we pick it is the quotient of the count left we want to pick and the |
1661 | * count still we haven't visited in the dict, this way, we could make every |
1662 | * member be equally picked.*/ |
1663 | p = ziplistIndex(zl, 0); |
1664 | unsigned int picked = 0, remaining = count; |
1665 | while (picked < count && p) { |
1666 | double randomDouble = ((double)rand()) / RAND_MAX; |
1667 | double threshold = ((double)remaining) / (total_size - index); |
1668 | if (randomDouble <= threshold) { |
1669 | assert(ziplistGet(p, &key, &klen, &klval)); |
1670 | ziplistSaveValue(key, klen, klval, &keys[picked]); |
1671 | p = ziplistNext(zl, p); |
1672 | assert(p); |
1673 | if (vals) { |
1674 | assert(ziplistGet(p, &key, &klen, &klval)); |
1675 | ziplistSaveValue(key, klen, klval, &vals[picked]); |
1676 | } |
1677 | remaining--; |
1678 | picked++; |
1679 | } else { |
1680 | p = ziplistNext(zl, p); |
1681 | assert(p); |
1682 | } |
1683 | p = ziplistNext(zl, p); |
1684 | index++; |
1685 | } |
1686 | return picked; |
1687 | } |
1688 | |
1689 | #ifdef REDIS_TEST |
1690 | #include <sys/time.h> |
1691 | #include "adlist.h" |
1692 | #include "sds.h" |
1693 | #include "testhelp.h" |
1694 | |
1695 | #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); } |
1696 | |
1697 | static unsigned char *createList() { |
1698 | unsigned char *zl = ziplistNew(); |
1699 | zl = ziplistPush(zl, (unsigned char*)"foo" , 3, ZIPLIST_TAIL); |
1700 | zl = ziplistPush(zl, (unsigned char*)"quux" , 4, ZIPLIST_TAIL); |
1701 | zl = ziplistPush(zl, (unsigned char*)"hello" , 5, ZIPLIST_HEAD); |
1702 | zl = ziplistPush(zl, (unsigned char*)"1024" , 4, ZIPLIST_TAIL); |
1703 | return zl; |
1704 | } |
1705 | |
1706 | static unsigned char *createIntList() { |
1707 | unsigned char *zl = ziplistNew(); |
1708 | char buf[32]; |
1709 | |
1710 | sprintf(buf, "100" ); |
1711 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); |
1712 | sprintf(buf, "128000" ); |
1713 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); |
1714 | sprintf(buf, "-100" ); |
1715 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); |
1716 | sprintf(buf, "4294967296" ); |
1717 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); |
1718 | sprintf(buf, "non integer" ); |
1719 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); |
1720 | sprintf(buf, "much much longer non integer" ); |
1721 | zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); |
1722 | return zl; |
1723 | } |
1724 | |
1725 | static long long usec(void) { |
1726 | struct timeval tv; |
1727 | gettimeofday(&tv,NULL); |
1728 | return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; |
1729 | } |
1730 | |
1731 | static void stress(int pos, int num, int maxsize, int dnum) { |
1732 | int i,j,k; |
1733 | unsigned char *zl; |
1734 | char posstr[2][5] = { "HEAD" , "TAIL" }; |
1735 | long long start; |
1736 | for (i = 0; i < maxsize; i+=dnum) { |
1737 | zl = ziplistNew(); |
1738 | for (j = 0; j < i; j++) { |
1739 | zl = ziplistPush(zl,(unsigned char*)"quux" ,4,ZIPLIST_TAIL); |
1740 | } |
1741 | |
1742 | /* Do num times a push+pop from pos */ |
1743 | start = usec(); |
1744 | for (k = 0; k < num; k++) { |
1745 | zl = ziplistPush(zl,(unsigned char*)"quux" ,4,pos); |
1746 | zl = ziplistDeleteRange(zl,0,1); |
1747 | } |
1748 | printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n" , |
1749 | i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start); |
1750 | zfree(zl); |
1751 | } |
1752 | } |
1753 | |
1754 | static unsigned char *pop(unsigned char *zl, int where) { |
1755 | unsigned char *p, *vstr; |
1756 | unsigned int vlen; |
1757 | long long vlong; |
1758 | |
1759 | p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1); |
1760 | if (ziplistGet(p,&vstr,&vlen,&vlong)) { |
1761 | if (where == ZIPLIST_HEAD) |
1762 | printf("Pop head: " ); |
1763 | else |
1764 | printf("Pop tail: " ); |
1765 | |
1766 | if (vstr) { |
1767 | if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite" ); |
1768 | } |
1769 | else { |
1770 | printf("%lld" , vlong); |
1771 | } |
1772 | |
1773 | printf("\n" ); |
1774 | return ziplistDelete(zl,&p); |
1775 | } else { |
1776 | printf("ERROR: Could not pop\n" ); |
1777 | exit(1); |
1778 | } |
1779 | } |
1780 | |
1781 | static int randstring(char *target, unsigned int min, unsigned int max) { |
1782 | int p = 0; |
1783 | int len = min+rand()%(max-min+1); |
1784 | int minval, maxval; |
1785 | switch(rand() % 3) { |
1786 | case 0: |
1787 | minval = 0; |
1788 | maxval = 255; |
1789 | break; |
1790 | case 1: |
1791 | minval = 48; |
1792 | maxval = 122; |
1793 | break; |
1794 | case 2: |
1795 | minval = 48; |
1796 | maxval = 52; |
1797 | break; |
1798 | default: |
1799 | assert(NULL); |
1800 | } |
1801 | |
1802 | while(p < len) |
1803 | target[p++] = minval+rand()%(maxval-minval+1); |
1804 | return len; |
1805 | } |
1806 | |
1807 | static void verify(unsigned char *zl, zlentry *e) { |
1808 | int len = ziplistLen(zl); |
1809 | zlentry _e; |
1810 | |
1811 | ZIPLIST_ENTRY_ZERO(&_e); |
1812 | |
1813 | for (int i = 0; i < len; i++) { |
1814 | memset(&e[i], 0, sizeof(zlentry)); |
1815 | zipEntry(ziplistIndex(zl, i), &e[i]); |
1816 | |
1817 | memset(&_e, 0, sizeof(zlentry)); |
1818 | zipEntry(ziplistIndex(zl, -len+i), &_e); |
1819 | |
1820 | assert(memcmp(&e[i], &_e, sizeof(zlentry)) == 0); |
1821 | } |
1822 | } |
1823 | |
1824 | static unsigned char *insertHelper(unsigned char *zl, char ch, size_t len, unsigned char *pos) { |
1825 | assert(len <= ZIP_BIG_PREVLEN); |
1826 | unsigned char data[ZIP_BIG_PREVLEN] = {0}; |
1827 | memset(data, ch, len); |
1828 | return ziplistInsert(zl, pos, data, len); |
1829 | } |
1830 | |
1831 | static int compareHelper(unsigned char *zl, char ch, size_t len, int index) { |
1832 | assert(len <= ZIP_BIG_PREVLEN); |
1833 | unsigned char data[ZIP_BIG_PREVLEN] = {0}; |
1834 | memset(data, ch, len); |
1835 | unsigned char *p = ziplistIndex(zl, index); |
1836 | assert(p != NULL); |
1837 | return ziplistCompare(p, data, len); |
1838 | } |
1839 | |
1840 | static size_t strEntryBytesSmall(size_t slen) { |
1841 | return slen + zipStorePrevEntryLength(NULL, 0) + zipStoreEntryEncoding(NULL, 0, slen); |
1842 | } |
1843 | |
1844 | static size_t strEntryBytesLarge(size_t slen) { |
1845 | return slen + zipStorePrevEntryLength(NULL, ZIP_BIG_PREVLEN) + zipStoreEntryEncoding(NULL, 0, slen); |
1846 | } |
1847 | |
1848 | /* ./redis-server test ziplist <randomseed> */ |
1849 | int ziplistTest(int argc, char **argv, int flags) { |
1850 | int accurate = (flags & REDIS_TEST_ACCURATE); |
1851 | unsigned char *zl, *p; |
1852 | unsigned char *entry; |
1853 | unsigned int elen; |
1854 | long long value; |
1855 | int iteration; |
1856 | |
1857 | /* If an argument is given, use it as the random seed. */ |
1858 | if (argc >= 4) |
1859 | srand(atoi(argv[3])); |
1860 | |
1861 | zl = createIntList(); |
1862 | ziplistRepr(zl); |
1863 | |
1864 | zfree(zl); |
1865 | |
1866 | zl = createList(); |
1867 | ziplistRepr(zl); |
1868 | |
1869 | zl = pop(zl,ZIPLIST_TAIL); |
1870 | ziplistRepr(zl); |
1871 | |
1872 | zl = pop(zl,ZIPLIST_HEAD); |
1873 | ziplistRepr(zl); |
1874 | |
1875 | zl = pop(zl,ZIPLIST_TAIL); |
1876 | ziplistRepr(zl); |
1877 | |
1878 | zl = pop(zl,ZIPLIST_TAIL); |
1879 | ziplistRepr(zl); |
1880 | |
1881 | zfree(zl); |
1882 | |
1883 | printf("Get element at index 3:\n" ); |
1884 | { |
1885 | zl = createList(); |
1886 | p = ziplistIndex(zl, 3); |
1887 | if (!ziplistGet(p, &entry, &elen, &value)) { |
1888 | printf("ERROR: Could not access index 3\n" ); |
1889 | return 1; |
1890 | } |
1891 | if (entry) { |
1892 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
1893 | printf("\n" ); |
1894 | } else { |
1895 | printf("%lld\n" , value); |
1896 | } |
1897 | printf("\n" ); |
1898 | zfree(zl); |
1899 | } |
1900 | |
1901 | printf("Get element at index 4 (out of range):\n" ); |
1902 | { |
1903 | zl = createList(); |
1904 | p = ziplistIndex(zl, 4); |
1905 | if (p == NULL) { |
1906 | printf("No entry\n" ); |
1907 | } else { |
1908 | printf("ERROR: Out of range index should return NULL, returned offset: %ld\n" , (long)(p-zl)); |
1909 | return 1; |
1910 | } |
1911 | printf("\n" ); |
1912 | zfree(zl); |
1913 | } |
1914 | |
1915 | printf("Get element at index -1 (last element):\n" ); |
1916 | { |
1917 | zl = createList(); |
1918 | p = ziplistIndex(zl, -1); |
1919 | if (!ziplistGet(p, &entry, &elen, &value)) { |
1920 | printf("ERROR: Could not access index -1\n" ); |
1921 | return 1; |
1922 | } |
1923 | if (entry) { |
1924 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
1925 | printf("\n" ); |
1926 | } else { |
1927 | printf("%lld\n" , value); |
1928 | } |
1929 | printf("\n" ); |
1930 | zfree(zl); |
1931 | } |
1932 | |
1933 | printf("Get element at index -4 (first element):\n" ); |
1934 | { |
1935 | zl = createList(); |
1936 | p = ziplistIndex(zl, -4); |
1937 | if (!ziplistGet(p, &entry, &elen, &value)) { |
1938 | printf("ERROR: Could not access index -4\n" ); |
1939 | return 1; |
1940 | } |
1941 | if (entry) { |
1942 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
1943 | printf("\n" ); |
1944 | } else { |
1945 | printf("%lld\n" , value); |
1946 | } |
1947 | printf("\n" ); |
1948 | zfree(zl); |
1949 | } |
1950 | |
1951 | printf("Get element at index -5 (reverse out of range):\n" ); |
1952 | { |
1953 | zl = createList(); |
1954 | p = ziplistIndex(zl, -5); |
1955 | if (p == NULL) { |
1956 | printf("No entry\n" ); |
1957 | } else { |
1958 | printf("ERROR: Out of range index should return NULL, returned offset: %ld\n" , (long)(p-zl)); |
1959 | return 1; |
1960 | } |
1961 | printf("\n" ); |
1962 | zfree(zl); |
1963 | } |
1964 | |
1965 | printf("Iterate list from 0 to end:\n" ); |
1966 | { |
1967 | zl = createList(); |
1968 | p = ziplistIndex(zl, 0); |
1969 | while (ziplistGet(p, &entry, &elen, &value)) { |
1970 | printf("Entry: " ); |
1971 | if (entry) { |
1972 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
1973 | } else { |
1974 | printf("%lld" , value); |
1975 | } |
1976 | p = ziplistNext(zl,p); |
1977 | printf("\n" ); |
1978 | } |
1979 | printf("\n" ); |
1980 | zfree(zl); |
1981 | } |
1982 | |
1983 | printf("Iterate list from 1 to end:\n" ); |
1984 | { |
1985 | zl = createList(); |
1986 | p = ziplistIndex(zl, 1); |
1987 | while (ziplistGet(p, &entry, &elen, &value)) { |
1988 | printf("Entry: " ); |
1989 | if (entry) { |
1990 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
1991 | } else { |
1992 | printf("%lld" , value); |
1993 | } |
1994 | p = ziplistNext(zl,p); |
1995 | printf("\n" ); |
1996 | } |
1997 | printf("\n" ); |
1998 | zfree(zl); |
1999 | } |
2000 | |
2001 | printf("Iterate list from 2 to end:\n" ); |
2002 | { |
2003 | zl = createList(); |
2004 | p = ziplistIndex(zl, 2); |
2005 | while (ziplistGet(p, &entry, &elen, &value)) { |
2006 | printf("Entry: " ); |
2007 | if (entry) { |
2008 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
2009 | } else { |
2010 | printf("%lld" , value); |
2011 | } |
2012 | p = ziplistNext(zl,p); |
2013 | printf("\n" ); |
2014 | } |
2015 | printf("\n" ); |
2016 | zfree(zl); |
2017 | } |
2018 | |
2019 | printf("Iterate starting out of range:\n" ); |
2020 | { |
2021 | zl = createList(); |
2022 | p = ziplistIndex(zl, 4); |
2023 | if (!ziplistGet(p, &entry, &elen, &value)) { |
2024 | printf("No entry\n" ); |
2025 | } else { |
2026 | printf("ERROR\n" ); |
2027 | } |
2028 | printf("\n" ); |
2029 | zfree(zl); |
2030 | } |
2031 | |
2032 | printf("Iterate from back to front:\n" ); |
2033 | { |
2034 | zl = createList(); |
2035 | p = ziplistIndex(zl, -1); |
2036 | while (ziplistGet(p, &entry, &elen, &value)) { |
2037 | printf("Entry: " ); |
2038 | if (entry) { |
2039 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
2040 | } else { |
2041 | printf("%lld" , value); |
2042 | } |
2043 | p = ziplistPrev(zl,p); |
2044 | printf("\n" ); |
2045 | } |
2046 | printf("\n" ); |
2047 | zfree(zl); |
2048 | } |
2049 | |
2050 | printf("Iterate from back to front, deleting all items:\n" ); |
2051 | { |
2052 | zl = createList(); |
2053 | p = ziplistIndex(zl, -1); |
2054 | while (ziplistGet(p, &entry, &elen, &value)) { |
2055 | printf("Entry: " ); |
2056 | if (entry) { |
2057 | if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite" ); |
2058 | } else { |
2059 | printf("%lld" , value); |
2060 | } |
2061 | zl = ziplistDelete(zl,&p); |
2062 | p = ziplistPrev(zl,p); |
2063 | printf("\n" ); |
2064 | } |
2065 | printf("\n" ); |
2066 | zfree(zl); |
2067 | } |
2068 | |
2069 | printf("Delete inclusive range 0,0:\n" ); |
2070 | { |
2071 | zl = createList(); |
2072 | zl = ziplistDeleteRange(zl, 0, 1); |
2073 | ziplistRepr(zl); |
2074 | zfree(zl); |
2075 | } |
2076 | |
2077 | printf("Delete inclusive range 0,1:\n" ); |
2078 | { |
2079 | zl = createList(); |
2080 | zl = ziplistDeleteRange(zl, 0, 2); |
2081 | ziplistRepr(zl); |
2082 | zfree(zl); |
2083 | } |
2084 | |
2085 | printf("Delete inclusive range 1,2:\n" ); |
2086 | { |
2087 | zl = createList(); |
2088 | zl = ziplistDeleteRange(zl, 1, 2); |
2089 | ziplistRepr(zl); |
2090 | zfree(zl); |
2091 | } |
2092 | |
2093 | printf("Delete with start index out of range:\n" ); |
2094 | { |
2095 | zl = createList(); |
2096 | zl = ziplistDeleteRange(zl, 5, 1); |
2097 | ziplistRepr(zl); |
2098 | zfree(zl); |
2099 | } |
2100 | |
2101 | printf("Delete with num overflow:\n" ); |
2102 | { |
2103 | zl = createList(); |
2104 | zl = ziplistDeleteRange(zl, 1, 5); |
2105 | ziplistRepr(zl); |
2106 | zfree(zl); |
2107 | } |
2108 | |
2109 | printf("Delete foo while iterating:\n" ); |
2110 | { |
2111 | zl = createList(); |
2112 | p = ziplistIndex(zl,0); |
2113 | while (ziplistGet(p,&entry,&elen,&value)) { |
2114 | if (entry && strncmp("foo" ,(char*)entry,elen) == 0) { |
2115 | printf("Delete foo\n" ); |
2116 | zl = ziplistDelete(zl,&p); |
2117 | } else { |
2118 | printf("Entry: " ); |
2119 | if (entry) { |
2120 | if (elen && fwrite(entry,elen,1,stdout) == 0) |
2121 | perror("fwrite" ); |
2122 | } else { |
2123 | printf("%lld" ,value); |
2124 | } |
2125 | p = ziplistNext(zl,p); |
2126 | printf("\n" ); |
2127 | } |
2128 | } |
2129 | printf("\n" ); |
2130 | ziplistRepr(zl); |
2131 | zfree(zl); |
2132 | } |
2133 | |
2134 | printf("Replace with same size:\n" ); |
2135 | { |
2136 | zl = createList(); /* "hello", "foo", "quux", "1024" */ |
2137 | unsigned char *orig_zl = zl; |
2138 | p = ziplistIndex(zl, 0); |
2139 | zl = ziplistReplace(zl, p, (unsigned char*)"zoink" , 5); |
2140 | p = ziplistIndex(zl, 3); |
2141 | zl = ziplistReplace(zl, p, (unsigned char*)"yy" , 2); |
2142 | p = ziplistIndex(zl, 1); |
2143 | zl = ziplistReplace(zl, p, (unsigned char*)"65536" , 5); |
2144 | p = ziplistIndex(zl, 0); |
2145 | assert(!memcmp((char*)p, |
2146 | "\x00\x05zoink" |
2147 | "\x07\xf0\x00\x00\x01" /* 65536 as int24 */ |
2148 | "\x05\x04quux" "\x06\x02yy" "\xff" , |
2149 | 23)); |
2150 | assert(zl == orig_zl); /* no reallocations have happened */ |
2151 | zfree(zl); |
2152 | printf("SUCCESS\n\n" ); |
2153 | } |
2154 | |
2155 | printf("Replace with different size:\n" ); |
2156 | { |
2157 | zl = createList(); /* "hello", "foo", "quux", "1024" */ |
2158 | p = ziplistIndex(zl, 1); |
2159 | zl = ziplistReplace(zl, p, (unsigned char*)"squirrel" , 8); |
2160 | p = ziplistIndex(zl, 0); |
2161 | assert(!strncmp((char*)p, |
2162 | "\x00\x05hello" "\x07\x08squirrel" "\x0a\x04quux" |
2163 | "\x06\xc0\x00\x04" "\xff" , |
2164 | 28)); |
2165 | zfree(zl); |
2166 | printf("SUCCESS\n\n" ); |
2167 | } |
2168 | |
2169 | printf("Regression test for >255 byte strings:\n" ); |
2170 | { |
2171 | char v1[257] = {0}, v2[257] = {0}; |
2172 | memset(v1,'x',256); |
2173 | memset(v2,'y',256); |
2174 | zl = ziplistNew(); |
2175 | zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL); |
2176 | zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL); |
2177 | |
2178 | /* Pop values again and compare their value. */ |
2179 | p = ziplistIndex(zl,0); |
2180 | assert(ziplistGet(p,&entry,&elen,&value)); |
2181 | assert(strncmp(v1,(char*)entry,elen) == 0); |
2182 | p = ziplistIndex(zl,1); |
2183 | assert(ziplistGet(p,&entry,&elen,&value)); |
2184 | assert(strncmp(v2,(char*)entry,elen) == 0); |
2185 | printf("SUCCESS\n\n" ); |
2186 | zfree(zl); |
2187 | } |
2188 | |
2189 | printf("Regression test deleting next to last entries:\n" ); |
2190 | { |
2191 | char v[3][257] = {{0}}; |
2192 | zlentry e[3] = {{.prevrawlensize = 0, .prevrawlen = 0, .lensize = 0, |
2193 | .len = 0, .headersize = 0, .encoding = 0, .p = NULL}}; |
2194 | size_t i; |
2195 | |
2196 | for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { |
2197 | memset(v[i], 'a' + i, sizeof(v[0])); |
2198 | } |
2199 | |
2200 | v[0][256] = '\0'; |
2201 | v[1][ 1] = '\0'; |
2202 | v[2][256] = '\0'; |
2203 | |
2204 | zl = ziplistNew(); |
2205 | for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) { |
2206 | zl = ziplistPush(zl, (unsigned char *) v[i], strlen(v[i]), ZIPLIST_TAIL); |
2207 | } |
2208 | |
2209 | verify(zl, e); |
2210 | |
2211 | assert(e[0].prevrawlensize == 1); |
2212 | assert(e[1].prevrawlensize == 5); |
2213 | assert(e[2].prevrawlensize == 1); |
2214 | |
2215 | /* Deleting entry 1 will increase `prevrawlensize` for entry 2 */ |
2216 | unsigned char *p = e[1].p; |
2217 | zl = ziplistDelete(zl, &p); |
2218 | |
2219 | verify(zl, e); |
2220 | |
2221 | assert(e[0].prevrawlensize == 1); |
2222 | assert(e[1].prevrawlensize == 5); |
2223 | |
2224 | printf("SUCCESS\n\n" ); |
2225 | zfree(zl); |
2226 | } |
2227 | |
2228 | printf("Create long list and check indices:\n" ); |
2229 | { |
2230 | unsigned long long start = usec(); |
2231 | zl = ziplistNew(); |
2232 | char buf[32]; |
2233 | int i,len; |
2234 | for (i = 0; i < 1000; i++) { |
2235 | len = sprintf(buf,"%d" ,i); |
2236 | zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL); |
2237 | } |
2238 | for (i = 0; i < 1000; i++) { |
2239 | p = ziplistIndex(zl,i); |
2240 | assert(ziplistGet(p,NULL,NULL,&value)); |
2241 | assert(i == value); |
2242 | |
2243 | p = ziplistIndex(zl,-i-1); |
2244 | assert(ziplistGet(p,NULL,NULL,&value)); |
2245 | assert(999-i == value); |
2246 | } |
2247 | printf("SUCCESS. usec=%lld\n\n" , usec()-start); |
2248 | zfree(zl); |
2249 | } |
2250 | |
2251 | printf("Compare strings with ziplist entries:\n" ); |
2252 | { |
2253 | zl = createList(); |
2254 | p = ziplistIndex(zl,0); |
2255 | if (!ziplistCompare(p,(unsigned char*)"hello" ,5)) { |
2256 | printf("ERROR: not \"hello\"\n" ); |
2257 | return 1; |
2258 | } |
2259 | if (ziplistCompare(p,(unsigned char*)"hella" ,5)) { |
2260 | printf("ERROR: \"hella\"\n" ); |
2261 | return 1; |
2262 | } |
2263 | |
2264 | p = ziplistIndex(zl,3); |
2265 | if (!ziplistCompare(p,(unsigned char*)"1024" ,4)) { |
2266 | printf("ERROR: not \"1024\"\n" ); |
2267 | return 1; |
2268 | } |
2269 | if (ziplistCompare(p,(unsigned char*)"1025" ,4)) { |
2270 | printf("ERROR: \"1025\"\n" ); |
2271 | return 1; |
2272 | } |
2273 | printf("SUCCESS\n\n" ); |
2274 | zfree(zl); |
2275 | } |
2276 | |
2277 | printf("Merge test:\n" ); |
2278 | { |
2279 | /* create list gives us: [hello, foo, quux, 1024] */ |
2280 | zl = createList(); |
2281 | unsigned char *zl2 = createList(); |
2282 | |
2283 | unsigned char *zl3 = ziplistNew(); |
2284 | unsigned char *zl4 = ziplistNew(); |
2285 | |
2286 | if (ziplistMerge(&zl4, &zl4)) { |
2287 | printf("ERROR: Allowed merging of one ziplist into itself.\n" ); |
2288 | return 1; |
2289 | } |
2290 | |
2291 | /* Merge two empty ziplists, get empty result back. */ |
2292 | zl4 = ziplistMerge(&zl3, &zl4); |
2293 | ziplistRepr(zl4); |
2294 | if (ziplistLen(zl4)) { |
2295 | printf("ERROR: Merging two empty ziplists created entries.\n" ); |
2296 | return 1; |
2297 | } |
2298 | zfree(zl4); |
2299 | |
2300 | zl2 = ziplistMerge(&zl, &zl2); |
2301 | /* merge gives us: [hello, foo, quux, 1024, hello, foo, quux, 1024] */ |
2302 | ziplistRepr(zl2); |
2303 | |
2304 | if (ziplistLen(zl2) != 8) { |
2305 | printf("ERROR: Merged length not 8, but: %u\n" , ziplistLen(zl2)); |
2306 | return 1; |
2307 | } |
2308 | |
2309 | p = ziplistIndex(zl2,0); |
2310 | if (!ziplistCompare(p,(unsigned char*)"hello" ,5)) { |
2311 | printf("ERROR: not \"hello\"\n" ); |
2312 | return 1; |
2313 | } |
2314 | if (ziplistCompare(p,(unsigned char*)"hella" ,5)) { |
2315 | printf("ERROR: \"hella\"\n" ); |
2316 | return 1; |
2317 | } |
2318 | |
2319 | p = ziplistIndex(zl2,3); |
2320 | if (!ziplistCompare(p,(unsigned char*)"1024" ,4)) { |
2321 | printf("ERROR: not \"1024\"\n" ); |
2322 | return 1; |
2323 | } |
2324 | if (ziplistCompare(p,(unsigned char*)"1025" ,4)) { |
2325 | printf("ERROR: \"1025\"\n" ); |
2326 | return 1; |
2327 | } |
2328 | |
2329 | p = ziplistIndex(zl2,4); |
2330 | if (!ziplistCompare(p,(unsigned char*)"hello" ,5)) { |
2331 | printf("ERROR: not \"hello\"\n" ); |
2332 | return 1; |
2333 | } |
2334 | if (ziplistCompare(p,(unsigned char*)"hella" ,5)) { |
2335 | printf("ERROR: \"hella\"\n" ); |
2336 | return 1; |
2337 | } |
2338 | |
2339 | p = ziplistIndex(zl2,7); |
2340 | if (!ziplistCompare(p,(unsigned char*)"1024" ,4)) { |
2341 | printf("ERROR: not \"1024\"\n" ); |
2342 | return 1; |
2343 | } |
2344 | if (ziplistCompare(p,(unsigned char*)"1025" ,4)) { |
2345 | printf("ERROR: \"1025\"\n" ); |
2346 | return 1; |
2347 | } |
2348 | printf("SUCCESS\n\n" ); |
2349 | zfree(zl); |
2350 | } |
2351 | |
2352 | printf("Stress with random payloads of different encoding:\n" ); |
2353 | { |
2354 | unsigned long long start = usec(); |
2355 | int i,j,len,where; |
2356 | unsigned char *p; |
2357 | char buf[1024]; |
2358 | int buflen; |
2359 | list *ref; |
2360 | listNode *refnode; |
2361 | |
2362 | /* Hold temp vars from ziplist */ |
2363 | unsigned char *sstr; |
2364 | unsigned int slen; |
2365 | long long sval; |
2366 | |
2367 | iteration = accurate ? 20000 : 20; |
2368 | for (i = 0; i < iteration; i++) { |
2369 | zl = ziplistNew(); |
2370 | ref = listCreate(); |
2371 | listSetFreeMethod(ref,(void (*)(void*))sdsfree); |
2372 | len = rand() % 256; |
2373 | |
2374 | /* Create lists */ |
2375 | for (j = 0; j < len; j++) { |
2376 | where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL; |
2377 | if (rand() % 2) { |
2378 | buflen = randstring(buf,1,sizeof(buf)-1); |
2379 | } else { |
2380 | switch(rand() % 3) { |
2381 | case 0: |
2382 | buflen = sprintf(buf,"%lld" ,(0LL + rand()) >> 20); |
2383 | break; |
2384 | case 1: |
2385 | buflen = sprintf(buf,"%lld" ,(0LL + rand())); |
2386 | break; |
2387 | case 2: |
2388 | buflen = sprintf(buf,"%lld" ,(0LL + rand()) << 20); |
2389 | break; |
2390 | default: |
2391 | assert(NULL); |
2392 | } |
2393 | } |
2394 | |
2395 | /* Add to ziplist */ |
2396 | zl = ziplistPush(zl, (unsigned char*)buf, buflen, where); |
2397 | |
2398 | /* Add to reference list */ |
2399 | if (where == ZIPLIST_HEAD) { |
2400 | listAddNodeHead(ref,sdsnewlen(buf, buflen)); |
2401 | } else if (where == ZIPLIST_TAIL) { |
2402 | listAddNodeTail(ref,sdsnewlen(buf, buflen)); |
2403 | } else { |
2404 | assert(NULL); |
2405 | } |
2406 | } |
2407 | |
2408 | assert(listLength(ref) == ziplistLen(zl)); |
2409 | for (j = 0; j < len; j++) { |
2410 | /* Naive way to get elements, but similar to the stresser |
2411 | * executed from the Tcl test suite. */ |
2412 | p = ziplistIndex(zl,j); |
2413 | refnode = listIndex(ref,j); |
2414 | |
2415 | assert(ziplistGet(p,&sstr,&slen,&sval)); |
2416 | if (sstr == NULL) { |
2417 | buflen = sprintf(buf,"%lld" ,sval); |
2418 | } else { |
2419 | buflen = slen; |
2420 | memcpy(buf,sstr,buflen); |
2421 | buf[buflen] = '\0'; |
2422 | } |
2423 | assert(memcmp(buf,listNodeValue(refnode),buflen) == 0); |
2424 | } |
2425 | zfree(zl); |
2426 | listRelease(ref); |
2427 | } |
2428 | printf("Done. usec=%lld\n\n" , usec()-start); |
2429 | } |
2430 | |
2431 | printf("Stress with variable ziplist size:\n" ); |
2432 | { |
2433 | unsigned long long start = usec(); |
2434 | int maxsize = accurate ? 16384 : 16; |
2435 | stress(ZIPLIST_HEAD,100000,maxsize,256); |
2436 | stress(ZIPLIST_TAIL,100000,maxsize,256); |
2437 | printf("Done. usec=%lld\n\n" , usec()-start); |
2438 | } |
2439 | |
2440 | /* Benchmarks */ |
2441 | { |
2442 | zl = ziplistNew(); |
2443 | iteration = accurate ? 100000 : 100; |
2444 | for (int i=0; i<iteration; i++) { |
2445 | char buf[4096] = "asdf" ; |
2446 | zl = ziplistPush(zl, (unsigned char*)buf, 4, ZIPLIST_TAIL); |
2447 | zl = ziplistPush(zl, (unsigned char*)buf, 40, ZIPLIST_TAIL); |
2448 | zl = ziplistPush(zl, (unsigned char*)buf, 400, ZIPLIST_TAIL); |
2449 | zl = ziplistPush(zl, (unsigned char*)buf, 4000, ZIPLIST_TAIL); |
2450 | zl = ziplistPush(zl, (unsigned char*)"1" , 1, ZIPLIST_TAIL); |
2451 | zl = ziplistPush(zl, (unsigned char*)"10" , 2, ZIPLIST_TAIL); |
2452 | zl = ziplistPush(zl, (unsigned char*)"100" , 3, ZIPLIST_TAIL); |
2453 | zl = ziplistPush(zl, (unsigned char*)"1000" , 4, ZIPLIST_TAIL); |
2454 | zl = ziplistPush(zl, (unsigned char*)"10000" , 5, ZIPLIST_TAIL); |
2455 | zl = ziplistPush(zl, (unsigned char*)"100000" , 6, ZIPLIST_TAIL); |
2456 | } |
2457 | |
2458 | printf("Benchmark ziplistFind:\n" ); |
2459 | { |
2460 | unsigned long long start = usec(); |
2461 | for (int i = 0; i < 2000; i++) { |
2462 | unsigned char *fptr = ziplistIndex(zl, ZIPLIST_HEAD); |
2463 | fptr = ziplistFind(zl, fptr, (unsigned char*)"nothing" , 7, 1); |
2464 | } |
2465 | printf("%lld\n" , usec()-start); |
2466 | } |
2467 | |
2468 | printf("Benchmark ziplistIndex:\n" ); |
2469 | { |
2470 | unsigned long long start = usec(); |
2471 | for (int i = 0; i < 2000; i++) { |
2472 | ziplistIndex(zl, 99999); |
2473 | } |
2474 | printf("%lld\n" , usec()-start); |
2475 | } |
2476 | |
2477 | printf("Benchmark ziplistValidateIntegrity:\n" ); |
2478 | { |
2479 | unsigned long long start = usec(); |
2480 | for (int i = 0; i < 2000; i++) { |
2481 | ziplistValidateIntegrity(zl, ziplistBlobLen(zl), 1, NULL, NULL); |
2482 | } |
2483 | printf("%lld\n" , usec()-start); |
2484 | } |
2485 | |
2486 | printf("Benchmark ziplistCompare with string\n" ); |
2487 | { |
2488 | unsigned long long start = usec(); |
2489 | for (int i = 0; i < 2000; i++) { |
2490 | unsigned char *eptr = ziplistIndex(zl,0); |
2491 | while (eptr != NULL) { |
2492 | ziplistCompare(eptr,(unsigned char*)"nothing" ,7); |
2493 | eptr = ziplistNext(zl,eptr); |
2494 | } |
2495 | } |
2496 | printf("Done. usec=%lld\n" , usec()-start); |
2497 | } |
2498 | |
2499 | printf("Benchmark ziplistCompare with number\n" ); |
2500 | { |
2501 | unsigned long long start = usec(); |
2502 | for (int i = 0; i < 2000; i++) { |
2503 | unsigned char *eptr = ziplistIndex(zl,0); |
2504 | while (eptr != NULL) { |
2505 | ziplistCompare(eptr,(unsigned char*)"99999" ,5); |
2506 | eptr = ziplistNext(zl,eptr); |
2507 | } |
2508 | } |
2509 | printf("Done. usec=%lld\n" , usec()-start); |
2510 | } |
2511 | |
2512 | zfree(zl); |
2513 | } |
2514 | |
2515 | printf("Stress __ziplistCascadeUpdate:\n" ); |
2516 | { |
2517 | char data[ZIP_BIG_PREVLEN]; |
2518 | zl = ziplistNew(); |
2519 | iteration = accurate ? 100000 : 100; |
2520 | for (int i = 0; i < iteration; i++) { |
2521 | zl = ziplistPush(zl, (unsigned char*)data, ZIP_BIG_PREVLEN-4, ZIPLIST_TAIL); |
2522 | } |
2523 | unsigned long long start = usec(); |
2524 | zl = ziplistPush(zl, (unsigned char*)data, ZIP_BIG_PREVLEN-3, ZIPLIST_HEAD); |
2525 | printf("Done. usec=%lld\n\n" , usec()-start); |
2526 | zfree(zl); |
2527 | } |
2528 | |
2529 | printf("Edge cases of __ziplistCascadeUpdate:\n" ); |
2530 | { |
2531 | /* Inserting a entry with data length greater than ZIP_BIG_PREVLEN-4 |
2532 | * will leads to cascade update. */ |
2533 | size_t s1 = ZIP_BIG_PREVLEN-4, s2 = ZIP_BIG_PREVLEN-3; |
2534 | zl = ziplistNew(); |
2535 | |
2536 | zlentry e[4] = {{.prevrawlensize = 0, .prevrawlen = 0, .lensize = 0, |
2537 | .len = 0, .headersize = 0, .encoding = 0, .p = NULL}}; |
2538 | |
2539 | zl = insertHelper(zl, 'a', s1, ZIPLIST_ENTRY_HEAD(zl)); |
2540 | verify(zl, e); |
2541 | |
2542 | assert(e[0].prevrawlensize == 1 && e[0].prevrawlen == 0); |
2543 | assert(compareHelper(zl, 'a', s1, 0)); |
2544 | ziplistRepr(zl); |
2545 | |
2546 | /* No expand. */ |
2547 | zl = insertHelper(zl, 'b', s1, ZIPLIST_ENTRY_HEAD(zl)); |
2548 | verify(zl, e); |
2549 | |
2550 | assert(e[0].prevrawlensize == 1 && e[0].prevrawlen == 0); |
2551 | assert(compareHelper(zl, 'b', s1, 0)); |
2552 | |
2553 | assert(e[1].prevrawlensize == 1 && e[1].prevrawlen == strEntryBytesSmall(s1)); |
2554 | assert(compareHelper(zl, 'a', s1, 1)); |
2555 | |
2556 | ziplistRepr(zl); |
2557 | |
2558 | /* Expand(tail included). */ |
2559 | zl = insertHelper(zl, 'c', s2, ZIPLIST_ENTRY_HEAD(zl)); |
2560 | verify(zl, e); |
2561 | |
2562 | assert(e[0].prevrawlensize == 1 && e[0].prevrawlen == 0); |
2563 | assert(compareHelper(zl, 'c', s2, 0)); |
2564 | |
2565 | assert(e[1].prevrawlensize == 5 && e[1].prevrawlen == strEntryBytesSmall(s2)); |
2566 | assert(compareHelper(zl, 'b', s1, 1)); |
2567 | |
2568 | assert(e[2].prevrawlensize == 5 && e[2].prevrawlen == strEntryBytesLarge(s1)); |
2569 | assert(compareHelper(zl, 'a', s1, 2)); |
2570 | |
2571 | ziplistRepr(zl); |
2572 | |
2573 | /* Expand(only previous head entry). */ |
2574 | zl = insertHelper(zl, 'd', s2, ZIPLIST_ENTRY_HEAD(zl)); |
2575 | verify(zl, e); |
2576 | |
2577 | assert(e[0].prevrawlensize == 1 && e[0].prevrawlen == 0); |
2578 | assert(compareHelper(zl, 'd', s2, 0)); |
2579 | |
2580 | assert(e[1].prevrawlensize == 5 && e[1].prevrawlen == strEntryBytesSmall(s2)); |
2581 | assert(compareHelper(zl, 'c', s2, 1)); |
2582 | |
2583 | assert(e[2].prevrawlensize == 5 && e[2].prevrawlen == strEntryBytesLarge(s2)); |
2584 | assert(compareHelper(zl, 'b', s1, 2)); |
2585 | |
2586 | assert(e[3].prevrawlensize == 5 && e[3].prevrawlen == strEntryBytesLarge(s1)); |
2587 | assert(compareHelper(zl, 'a', s1, 3)); |
2588 | |
2589 | ziplistRepr(zl); |
2590 | |
2591 | /* Delete from mid. */ |
2592 | unsigned char *p = ziplistIndex(zl, 2); |
2593 | zl = ziplistDelete(zl, &p); |
2594 | verify(zl, e); |
2595 | |
2596 | assert(e[0].prevrawlensize == 1 && e[0].prevrawlen == 0); |
2597 | assert(compareHelper(zl, 'd', s2, 0)); |
2598 | |
2599 | assert(e[1].prevrawlensize == 5 && e[1].prevrawlen == strEntryBytesSmall(s2)); |
2600 | assert(compareHelper(zl, 'c', s2, 1)); |
2601 | |
2602 | assert(e[2].prevrawlensize == 5 && e[2].prevrawlen == strEntryBytesLarge(s2)); |
2603 | assert(compareHelper(zl, 'a', s1, 2)); |
2604 | |
2605 | ziplistRepr(zl); |
2606 | |
2607 | zfree(zl); |
2608 | } |
2609 | |
2610 | printf("__ziplistInsert nextdiff == -4 && reqlen < 4 (issue #7170):\n" ); |
2611 | { |
2612 | zl = ziplistNew(); |
2613 | |
2614 | /* We set some values to almost reach the critical point - 254 */ |
2615 | char A_252[253] = {0}, A_250[251] = {0}; |
2616 | memset(A_252, 'A', 252); |
2617 | memset(A_250, 'A', 250); |
2618 | |
2619 | /* After the rpush, the list look like: [one two A_252 A_250 three 10] */ |
2620 | zl = ziplistPush(zl, (unsigned char*)"one" , 3, ZIPLIST_TAIL); |
2621 | zl = ziplistPush(zl, (unsigned char*)"two" , 3, ZIPLIST_TAIL); |
2622 | zl = ziplistPush(zl, (unsigned char*)A_252, strlen(A_252), ZIPLIST_TAIL); |
2623 | zl = ziplistPush(zl, (unsigned char*)A_250, strlen(A_250), ZIPLIST_TAIL); |
2624 | zl = ziplistPush(zl, (unsigned char*)"three" , 5, ZIPLIST_TAIL); |
2625 | zl = ziplistPush(zl, (unsigned char*)"10" , 2, ZIPLIST_TAIL); |
2626 | ziplistRepr(zl); |
2627 | |
2628 | p = ziplistIndex(zl, 2); |
2629 | if (!ziplistCompare(p, (unsigned char*)A_252, strlen(A_252))) { |
2630 | printf("ERROR: not \"A_252\"\n" ); |
2631 | return 1; |
2632 | } |
2633 | |
2634 | /* When we remove A_252, the list became: [one two A_250 three 10] |
2635 | * A_250's prev node became node two, because node two quite small |
2636 | * So A_250's prevlenSize shrink to 1, A_250's total size became 253(1+2+250) |
2637 | * The prev node of node three is still node A_250. |
2638 | * We will not shrink the node three's prevlenSize, keep it at 5 bytes */ |
2639 | zl = ziplistDelete(zl, &p); |
2640 | ziplistRepr(zl); |
2641 | |
2642 | p = ziplistIndex(zl, 3); |
2643 | if (!ziplistCompare(p, (unsigned char*)"three" , 5)) { |
2644 | printf("ERROR: not \"three\"\n" ); |
2645 | return 1; |
2646 | } |
2647 | |
2648 | /* We want to insert a node after A_250, the list became: [one two A_250 10 three 10] |
2649 | * Because the new node is quite small, node three prevlenSize will shrink to 1 */ |
2650 | zl = ziplistInsert(zl, p, (unsigned char*)"10" , 2); |
2651 | ziplistRepr(zl); |
2652 | |
2653 | /* Last element should equal 10 */ |
2654 | p = ziplistIndex(zl, -1); |
2655 | if (!ziplistCompare(p, (unsigned char*)"10" , 2)) { |
2656 | printf("ERROR: not \"10\"\n" ); |
2657 | return 1; |
2658 | } |
2659 | |
2660 | zfree(zl); |
2661 | } |
2662 | |
2663 | printf("ALL TESTS PASSED!\n" ); |
2664 | return 0; |
2665 | } |
2666 | #endif |
2667 | |