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 : * The general layout of the ziplist is as follows:
13 : * <zlbytes><zltail><zllen><entry><entry><zlend>
14 : *
15 : * <zlbytes> is an unsigned integer to hold the number of bytes that the
16 : * ziplist occupies. This value needs to be stored to be able to resize the
17 : * entire structure without the need to traverse it first.
18 : *
19 : * <zltail> is the offset to the last entry in the list. This allows a pop
20 : * operation on the far side of the list without the need for full traversal.
21 : *
22 : * <zllen> is the number of entries.When this value is larger than 2**16-2,
23 : * we need to traverse the entire list to know how many items it holds.
24 : *
25 : * <zlend> is a single byte special value, equal to 255, which indicates the
26 : * end of the list.
27 : *
28 : * ZIPLIST ENTRIES:
29 : * Every entry in the ziplist is prefixed by a header that contains two pieces
30 : * of information. First, the length of the previous entry is stored to be
31 : * able to traverse the list from back to front. Second, the encoding with an
32 : * optional string length of the entry itself is stored.
33 : *
34 : * The length of the previous entry is encoded in the following way:
35 : * If this length is smaller than 254 bytes, it will only consume a single
36 : * byte that takes the length as value. When the length is greater than or
37 : * equal to 254, it will consume 5 bytes. The first byte is set to 254 to
38 : * indicate a larger value is following. The remaining 4 bytes take the
39 : * length of the previous entry as value.
40 : *
41 : * The other header field of the entry itself depends on the contents of the
42 : * entry. When the entry is a string, the first 2 bits of this header will hold
43 : * the type of encoding used to store the length of the string, followed by the
44 : * actual length of the string. When the entry is an integer the first 2 bits
45 : * are both set to 1. The following 2 bits are used to specify what kind of
46 : * integer will be stored after this header. An overview of the different
47 : * types and encodings is as follows:
48 : *
49 : * |00pppppp| - 1 byte
50 : * String value with length less than or equal to 63 bytes (6 bits).
51 : * |01pppppp|qqqqqqqq| - 2 bytes
52 : * String value with length less than or equal to 16383 bytes (14 bits).
53 : * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
54 : * String value with length greater than or equal to 16384 bytes.
55 : * |1100____| - 1 byte
56 : * Integer encoded as int16_t (2 bytes).
57 : * |1101____| - 1 byte
58 : * Integer encoded as int32_t (4 bytes).
59 : * |1110____| - 1 byte
60 : * Integer encoded as int64_t (8 bytes).
61 : */
62 :
63 : #include <stdio.h>
64 : #include <stdlib.h>
65 : #include <string.h>
66 : #include <stdint.h>
67 : #include <assert.h>
68 : #include <limits.h>
69 : #include "zmalloc.h"
70 : #include "util.h"
71 : #include "ziplist.h"
72 : #include "endianconv.h"
73 :
74 : #define ZIP_END 255
75 : #define ZIP_BIGLEN 254
76 :
77 : /* Different encoding/length possibilities */
78 : #define ZIP_STR_MASK (0xc0)
79 : #define ZIP_INT_MASK (0x30)
80 : #define ZIP_STR_06B (0 << 6)
81 : #define ZIP_STR_14B (1 << 6)
82 : #define ZIP_STR_32B (2 << 6)
83 : #define ZIP_INT_16B (0xc0 | 0<<4)
84 : #define ZIP_INT_32B (0xc0 | 1<<4)
85 : #define ZIP_INT_64B (0xc0 | 2<<4)
86 :
87 : /* Macro to determine type */
88 : #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
89 :
90 : /* Utility macros */
91 : #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
92 : #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
93 : #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
94 : #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
95 : #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
96 : #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
97 : #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
98 :
99 : /* We know a positive increment can only be 1 because entries can only be
100 : * pushed one at a time. */
101 : #define ZIPLIST_INCR_LENGTH(zl,incr) { \
102 : if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
103 : ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
104 : }
105 :
106 : typedef struct zlentry {
107 : unsigned int prevrawlensize, prevrawlen;
108 : unsigned int lensize, len;
109 : unsigned int headersize;
110 : unsigned char encoding;
111 : unsigned char *p;
112 : } zlentry;
113 :
114 : #define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
115 : (encoding) = (ptr[0]) & (ZIP_STR_MASK | ZIP_INT_MASK); \
116 : if (((encoding) & ZIP_STR_MASK) < ZIP_STR_MASK) { \
117 : /* String encoding: 2 MSBs */ \
118 : (encoding) &= ZIP_STR_MASK; \
119 : } \
120 : } while(0)
121 :
122 : /* Return bytes needed to store integer encoded by 'encoding' */
123 6390452 : static unsigned int zipIntSize(unsigned char encoding) {
124 6390452 : switch(encoding) {
125 5117150 : case ZIP_INT_16B: return sizeof(int16_t);
126 493526 : case ZIP_INT_32B: return sizeof(int32_t);
127 779776 : case ZIP_INT_64B: return sizeof(int64_t);
128 : }
129 0 : assert(NULL);
130 : return 0;
131 : }
132 :
133 : /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
134 : * the amount of bytes required to encode such a length. */
135 384290 : static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
136 384290 : unsigned char len = 1, buf[5];
137 :
138 384290 : if (ZIP_IS_STR(encoding)) {
139 : /* Although encoding is given it may not be set for strings,
140 : * so we determine it here using the raw length. */
141 132078 : if (rawlen <= 0x3f) {
142 103038 : if (!p) return len;
143 51519 : buf[0] = ZIP_STR_06B | rawlen;
144 29040 : } else if (rawlen <= 0x3fff) {
145 28118 : len += 1;
146 28118 : if (!p) return len;
147 14059 : buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
148 14059 : buf[1] = rawlen & 0xff;
149 : } else {
150 922 : len += 4;
151 922 : if (!p) return len;
152 461 : buf[0] = ZIP_STR_32B;
153 461 : buf[1] = (rawlen >> 24) & 0xff;
154 461 : buf[2] = (rawlen >> 16) & 0xff;
155 461 : buf[3] = (rawlen >> 8) & 0xff;
156 461 : buf[4] = rawlen & 0xff;
157 : }
158 : } else {
159 : /* Implies integer encoding, so length is always 1. */
160 252212 : if (!p) return len;
161 126106 : buf[0] = encoding;
162 : }
163 :
164 : /* Store this length at p */
165 192145 : memcpy(p,buf,len);
166 192145 : return len;
167 : }
168 :
169 : /* Decode the length encoded in 'ptr'. The 'encoding' variable will hold the
170 : * entries encoding, the 'lensize' variable will hold the number of bytes
171 : * required to encode the entries length, and the 'len' variable will hold the
172 : * entries length. */
173 : #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
174 : ZIP_ENTRY_ENCODING((ptr), (encoding)); \
175 : if ((encoding) < ZIP_STR_MASK) { \
176 : if ((encoding) == ZIP_STR_06B) { \
177 : (lensize) = 1; \
178 : (len) = (ptr)[0] & 0x3f; \
179 : } else if ((encoding) == ZIP_STR_14B) { \
180 : (lensize) = 2; \
181 : (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
182 : } else if (encoding == ZIP_STR_32B) { \
183 : (lensize) = 5; \
184 : (len) = ((ptr)[1] << 24) | \
185 : ((ptr)[2] << 16) | \
186 : ((ptr)[3] << 8) | \
187 : ((ptr)[4]); \
188 : } else { \
189 : assert(NULL); \
190 : } \
191 : } else { \
192 : (lensize) = 1; \
193 : (len) = zipIntSize(encoding); \
194 : } \
195 : } while(0);
196 :
197 : /* Encode the length of the previous entry and write it to "p". Return the
198 : * number of bytes needed to encode this length if "p" is NULL. */
199 472641 : static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) {
200 472641 : if (p == NULL) {
201 236351 : return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1;
202 : } else {
203 236290 : if (len < ZIP_BIGLEN) {
204 235406 : p[0] = len;
205 235406 : return 1;
206 : } else {
207 884 : p[0] = ZIP_BIGLEN;
208 884 : memcpy(p+1,&len,sizeof(len));
209 : memrev32ifbe(p+1);
210 884 : return 1+sizeof(len);
211 : }
212 : }
213 : }
214 :
215 : /* Encode the length of the previous entry and write it to "p". This only
216 : * uses the larger encoding (required in __ziplistCascadeUpdate). */
217 : static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) {
218 0 : if (p == NULL) return;
219 0 : p[0] = ZIP_BIGLEN;
220 0 : memcpy(p+1,&len,sizeof(len));
221 : memrev32ifbe(p+1);
222 : }
223 :
224 : /* Decode the number of bytes required to store the length of the previous
225 : * element, from the perspective of the entry pointed to by 'ptr'. */
226 : #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
227 : if ((ptr)[0] < ZIP_BIGLEN) { \
228 : (prevlensize) = 1; \
229 : } else { \
230 : (prevlensize) = 5; \
231 : } \
232 : } while(0);
233 :
234 : /* Decode the length of the previous element, from the perspective of the entry
235 : * pointed to by 'ptr'. */
236 : #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
237 : ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
238 : if ((prevlensize) == 1) { \
239 : (prevlen) = (ptr)[0]; \
240 : } else if ((prevlensize) == 5) { \
241 : assert(sizeof((prevlensize)) == 4); \
242 : memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
243 : memrev32ifbe(&prevlen); \
244 : } \
245 : } while(0);
246 :
247 : /* Return the difference in number of bytes needed to store the length of the
248 : * previous element 'len', in the entry pointed to by 'p'. */
249 : static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
250 : unsigned int prevlensize;
251 44050 : ZIP_DECODE_PREVLENSIZE(p, prevlensize);
252 44050 : return zipPrevEncodeLength(NULL, len) - prevlensize;
253 : }
254 :
255 : /* Return the total number of bytes used by the entry pointed to by 'p'. */
256 6666733 : static unsigned int zipRawEntryLength(unsigned char *p) {
257 : unsigned int prevlensize, encoding, lensize, len;
258 6666733 : ZIP_DECODE_PREVLENSIZE(p, prevlensize);
259 6666733 : ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
260 6666733 : return prevlensize + lensize + len;
261 : }
262 :
263 : /* Check if string pointed to by 'entry' can be encoded as an integer.
264 : * Stores the integer value in 'v' and its encoding in 'encoding'. */
265 2204782 : static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
266 : long long value;
267 :
268 2204782 : if (entrylen >= 32 || entrylen == 0) return 0;
269 2184922 : if (string2ll((char*)entry,entrylen,&value)) {
270 : /* Great, the string can be encoded. Check what's the smallest
271 : * of our encoding types that can hold this value. */
272 2105440 : if (value >= INT16_MIN && value <= INT16_MAX) {
273 1979386 : *encoding = ZIP_INT_16B;
274 126054 : } else if (value >= INT32_MIN && value <= INT32_MAX) {
275 50228 : *encoding = ZIP_INT_32B;
276 : } else {
277 75826 : *encoding = ZIP_INT_64B;
278 : }
279 2105440 : *v = value;
280 2105440 : return 1;
281 : }
282 79482 : return 0;
283 : }
284 :
285 : /* Store integer 'value' at 'p', encoded as 'encoding' */
286 126106 : static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
287 : int16_t i16;
288 : int32_t i32;
289 : int64_t i64;
290 126106 : if (encoding == ZIP_INT_16B) {
291 33484 : i16 = value;
292 : memcpy(p,&i16,sizeof(i16));
293 : memrev16ifbe(p);
294 92622 : } else if (encoding == ZIP_INT_32B) {
295 34439 : i32 = value;
296 : memcpy(p,&i32,sizeof(i32));
297 : memrev32ifbe(p);
298 58183 : } else if (encoding == ZIP_INT_64B) {
299 58183 : i64 = value;
300 : memcpy(p,&i64,sizeof(i64));
301 : memrev64ifbe(p);
302 : } else {
303 0 : assert(NULL);
304 : }
305 126106 : }
306 :
307 : /* Read integer encoded as 'encoding' from 'p' */
308 2167767 : static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
309 : int16_t i16;
310 : int32_t i32;
311 2167767 : int64_t i64, ret = 0;
312 2167767 : if (encoding == ZIP_INT_16B) {
313 : memcpy(&i16,p,sizeof(i16));
314 : memrev16ifbe(&i16);
315 2028020 : ret = i16;
316 139747 : } else if (encoding == ZIP_INT_32B) {
317 : memcpy(&i32,p,sizeof(i32));
318 : memrev32ifbe(&i32);
319 61400 : ret = i32;
320 78347 : } else if (encoding == ZIP_INT_64B) {
321 : memcpy(&i64,p,sizeof(i64));
322 : memrev64ifbe(&i64);
323 78347 : ret = i64;
324 : } else {
325 0 : assert(NULL);
326 : }
327 2167767 : return ret;
328 : }
329 :
330 : /* Return a struct with all information about an entry. */
331 2837447 : static zlentry zipEntry(unsigned char *p) {
332 : zlentry e;
333 :
334 2837447 : ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);
335 2837447 : ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);
336 2837447 : e.headersize = e.prevrawlensize + e.lensize;
337 2837447 : e.p = p;
338 2837447 : return e;
339 : }
340 :
341 : /* Create a new empty ziplist. */
342 54162 : unsigned char *ziplistNew(void) {
343 54162 : unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
344 54162 : unsigned char *zl = zmalloc(bytes);
345 54162 : ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
346 54162 : ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
347 54162 : ZIPLIST_LENGTH(zl) = 0;
348 54162 : zl[bytes-1] = ZIP_END;
349 54162 : return zl;
350 : }
351 :
352 : /* Resize the ziplist. */
353 : static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
354 246951 : zl = zrealloc(zl,len);
355 246951 : ZIPLIST_BYTES(zl) = intrev32ifbe(len);
356 246951 : zl[len-1] = ZIP_END;
357 246951 : return zl;
358 : }
359 :
360 : /* When an entry is inserted, we need to set the prevlen field of the next
361 : * entry to equal the length of the inserted entry. It can occur that this
362 : * length cannot be encoded in 1 byte and the next entry needs to be grow
363 : * a bit larger to hold the 5-byte encoded prevlen. This can be done for free,
364 : * because this only happens when an entry is already being inserted (which
365 : * causes a realloc and memmove). However, encoding the prevlen may require
366 : * that this entry is grown as well. This effect may cascade throughout
367 : * the ziplist when there are consecutive entries with a size close to
368 : * ZIP_BIGLEN, so we need to check that the prevlen can be encoded in every
369 : * consecutive entry.
370 : *
371 : * Note that this effect can also happen in reverse, where the bytes required
372 : * to encode the prevlen field can shrink. This effect is deliberately ignored,
373 : * because it can cause a "flapping" effect where a chain prevlen fields is
374 : * first grown and then shrunk again after consecutive inserts. Rather, the
375 : * field is allowed to stay larger than necessary, because a large prevlen
376 : * field implies the ziplist is holding large entries anyway.
377 : *
378 : * The pointer "p" points to the first entry that does NOT need to be
379 : * updated, i.e. consecutive fields MAY need an update. */
380 156 : static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
381 156 : size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
382 : size_t offset, noffset, extra;
383 : unsigned char *np;
384 : zlentry cur, next;
385 :
386 312 : while (p[0] != ZIP_END) {
387 156 : cur = zipEntry(p);
388 156 : rawlen = cur.headersize + cur.len;
389 156 : rawlensize = zipPrevEncodeLength(NULL,rawlen);
390 :
391 : /* Abort if there is no next entry. */
392 156 : if (p[rawlen] == ZIP_END) break;
393 95 : next = zipEntry(p+rawlen);
394 :
395 : /* Abort when "prevlen" has not changed. */
396 95 : if (next.prevrawlen == rawlen) break;
397 :
398 95 : if (next.prevrawlensize < rawlensize) {
399 : /* The "prevlen" field of "next" needs more bytes to hold
400 : * the raw length of "cur". */
401 0 : offset = p-zl;
402 0 : extra = rawlensize-next.prevrawlensize;
403 0 : zl = ziplistResize(zl,curlen+extra);
404 0 : p = zl+offset;
405 :
406 : /* Current pointer and offset for next element. */
407 0 : np = p+rawlen;
408 0 : noffset = np-zl;
409 :
410 : /* Update tail offset when next element is not the tail element. */
411 0 : if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
412 0 : ZIPLIST_TAIL_OFFSET(zl) =
413 0 : intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
414 : }
415 :
416 : /* Move the tail to the back. */
417 0 : memmove(np+rawlensize,
418 : np+next.prevrawlensize,
419 0 : curlen-noffset-next.prevrawlensize-1);
420 0 : zipPrevEncodeLength(np,rawlen);
421 :
422 : /* Advance the cursor */
423 0 : p += rawlen;
424 0 : curlen += extra;
425 : } else {
426 95 : if (next.prevrawlensize > rawlensize) {
427 : /* This would result in shrinking, which we want to avoid.
428 : * So, set "rawlen" in the available bytes. */
429 0 : zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
430 : } else {
431 95 : zipPrevEncodeLength(p+rawlen,rawlen);
432 : }
433 :
434 : /* Stop here, as the raw length of "next" has not changed. */
435 : break;
436 : }
437 : }
438 156 : return zl;
439 : }
440 :
441 : /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
442 55360 : static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
443 55360 : unsigned int i, totlen, deleted = 0;
444 : size_t offset;
445 55360 : int nextdiff = 0;
446 : zlentry first, tail;
447 :
448 55360 : first = zipEntry(p);
449 129457 : for (i = 0; p[0] != ZIP_END && i < num; i++) {
450 74097 : p += zipRawEntryLength(p);
451 74097 : deleted++;
452 : }
453 :
454 55360 : totlen = p-first.p;
455 55360 : if (totlen > 0) {
456 54806 : if (p[0] != ZIP_END) {
457 : /* Tricky: storing the prevlen in this entry might reduce or
458 : * increase the number of bytes needed, compared to the current
459 : * prevlen. Note that we can always store this length because
460 : * it was previously stored by an entry that is being deleted. */
461 31690 : nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
462 15845 : zipPrevEncodeLength(p-nextdiff,first.prevrawlen);
463 :
464 : /* Update offset for tail */
465 31690 : ZIPLIST_TAIL_OFFSET(zl) =
466 15845 : intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
467 :
468 : /* When the tail contains more than one entry, we need to take
469 : * "nextdiff" in account as well. Otherwise, a change in the
470 : * size of prevlen doesn't have an effect on the *tail* offset. */
471 15845 : tail = zipEntry(p);
472 15845 : if (p[tail.headersize+tail.len] != ZIP_END) {
473 8536 : ZIPLIST_TAIL_OFFSET(zl) =
474 4268 : intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
475 : }
476 :
477 : /* Move tail to the front of the ziplist */
478 15845 : memmove(first.p,p-nextdiff,
479 15845 : intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1+nextdiff);
480 : } else {
481 : /* The entire tail was deleted. No need to move memory. */
482 38961 : ZIPLIST_TAIL_OFFSET(zl) =
483 : intrev32ifbe((first.p-zl)-first.prevrawlen);
484 : }
485 :
486 : /* Resize and update length */
487 54806 : offset = first.p-zl;
488 109612 : zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
489 54806 : ZIPLIST_INCR_LENGTH(zl,-deleted);
490 54806 : p = zl+offset;
491 :
492 : /* When nextdiff != 0, the raw length of the next entry has changed, so
493 : * we need to cascade the update throughout the ziplist */
494 54806 : if (nextdiff != 0)
495 60 : zl = __ziplistCascadeUpdate(zl,p);
496 : }
497 55360 : return zl;
498 : }
499 :
500 : /* Insert item at "p". */
501 192145 : static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
502 192145 : size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, prevlen = 0;
503 : size_t offset;
504 192145 : int nextdiff = 0;
505 192145 : unsigned char encoding = 0;
506 192145 : long long value = 123456789; /* initialized to avoid warning. Using a value
507 : that is easy to see if for some reason
508 : we use it uninitialized. */
509 : zlentry entry, tail;
510 :
511 : /* Find out prevlen for the entry that is inserted. */
512 192145 : if (p[0] != ZIP_END) {
513 28205 : entry = zipEntry(p);
514 28205 : prevlen = entry.prevrawlen;
515 : } else {
516 163940 : unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
517 163940 : if (ptail[0] != ZIP_END) {
518 112601 : prevlen = zipRawEntryLength(ptail);
519 : }
520 : }
521 :
522 : /* See if the entry can be encoded */
523 192145 : if (zipTryEncoding(s,slen,&value,&encoding)) {
524 : /* 'encoding' is set to the appropriate integer encoding */
525 126106 : reqlen = zipIntSize(encoding);
526 : } else {
527 : /* 'encoding' is untouched, however zipEncodeLength will use the
528 : * string length to figure out how to encode it. */
529 66039 : reqlen = slen;
530 : }
531 : /* We need space for both the length of the previous entry and
532 : * the length of the payload. */
533 192145 : reqlen += zipPrevEncodeLength(NULL,prevlen);
534 192145 : reqlen += zipEncodeLength(NULL,encoding,slen);
535 :
536 : /* When the insert position is not equal to the tail, we need to
537 : * make sure that the next entry can hold this entry's length in
538 : * its prevlen field. */
539 220350 : nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
540 :
541 : /* Store offset because a realloc may change the address of zl. */
542 192145 : offset = p-zl;
543 384290 : zl = ziplistResize(zl,curlen+reqlen+nextdiff);
544 192145 : p = zl+offset;
545 :
546 : /* Apply memory move when necessary and update tail offset. */
547 192145 : if (p[0] != ZIP_END) {
548 : /* Subtract one because of the ZIP_END bytes */
549 28205 : memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
550 :
551 : /* Encode this entry's raw length in the next entry. */
552 28205 : zipPrevEncodeLength(p+reqlen,reqlen);
553 :
554 : /* Update offset for tail */
555 56410 : ZIPLIST_TAIL_OFFSET(zl) =
556 28205 : intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
557 :
558 : /* When the tail contains more than one entry, we need to take
559 : * "nextdiff" in account as well. Otherwise, a change in the
560 : * size of prevlen doesn't have an effect on the *tail* offset. */
561 28205 : tail = zipEntry(p+reqlen);
562 28205 : if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
563 51212 : ZIPLIST_TAIL_OFFSET(zl) =
564 25606 : intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
565 : }
566 : } else {
567 : /* This element will be the new tail. */
568 163940 : ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
569 : }
570 :
571 : /* When nextdiff != 0, the raw length of the next entry has changed, so
572 : * we need to cascade the update throughout the ziplist */
573 192145 : if (nextdiff != 0) {
574 96 : offset = p-zl;
575 96 : zl = __ziplistCascadeUpdate(zl,p+reqlen);
576 96 : p = zl+offset;
577 : }
578 :
579 : /* Write the entry */
580 192145 : p += zipPrevEncodeLength(p,prevlen);
581 192145 : p += zipEncodeLength(p,encoding,slen);
582 192145 : if (ZIP_IS_STR(encoding)) {
583 66039 : memcpy(p,s,slen);
584 : } else {
585 126106 : zipSaveInteger(p,value,encoding);
586 : }
587 192145 : ZIPLIST_INCR_LENGTH(zl,1);
588 192145 : return zl;
589 : }
590 :
591 165984 : unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
592 : unsigned char *p;
593 165984 : p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
594 165984 : return __ziplistInsert(zl,p,s,slen);
595 : }
596 :
597 : /* Returns an offset to use for iterating with ziplistNext. When the given
598 : * index is negative, the list is traversed back to front. When the list
599 : * doesn't contain an element at the provided index, NULL is returned. */
600 262674 : unsigned char *ziplistIndex(unsigned char *zl, int index) {
601 : unsigned char *p;
602 : zlentry entry;
603 262674 : if (index < 0) {
604 5512 : index = (-index)-1;
605 5512 : p = ZIPLIST_ENTRY_TAIL(zl);
606 5512 : if (p[0] != ZIP_END) {
607 5512 : entry = zipEntry(p);
608 139726 : while (entry.prevrawlen > 0 && index--) {
609 128702 : p -= entry.prevrawlen;
610 128702 : entry = zipEntry(p);
611 : }
612 : }
613 : } else {
614 257162 : p = ZIPLIST_ENTRY_HEAD(zl);
615 2254920 : while (p[0] != ZIP_END && index--) {
616 1740596 : p += zipRawEntryLength(p);
617 : }
618 : }
619 262674 : return (p[0] == ZIP_END || index > 0) ? NULL : p;
620 : }
621 :
622 : /* Return pointer to next entry in ziplist.
623 : *
624 : * zl is the pointer to the ziplist
625 : * p is the pointer to the current element
626 : *
627 : * The element after 'p' is returned, otherwise NULL if we are at the end. */
628 4741884 : unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
629 : ((void) zl);
630 :
631 : /* "p" could be equal to ZIP_END, caused by ziplistDelete,
632 : * and we should return NULL. Otherwise, we should return NULL
633 : * when the *next* element is ZIP_END (there is no next entry). */
634 4741884 : if (p[0] == ZIP_END) {
635 2445 : return NULL;
636 : }
637 :
638 4739439 : p += zipRawEntryLength(p);
639 4739439 : if (p[0] == ZIP_END) {
640 78089 : return NULL;
641 : }
642 :
643 4661350 : return p;
644 : }
645 :
646 : /* Return pointer to previous entry in ziplist. */
647 660 : unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
648 : zlentry entry;
649 :
650 : /* Iterating backwards from ZIP_END should return the tail. When "p" is
651 : * equal to the first element of the list, we're already at the head,
652 : * and should return NULL. */
653 660 : if (p[0] == ZIP_END) {
654 2 : p = ZIPLIST_ENTRY_TAIL(zl);
655 2 : return (p[0] == ZIP_END) ? NULL : p;
656 658 : } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
657 9 : return NULL;
658 : } else {
659 649 : entry = zipEntry(p);
660 649 : assert(entry.prevrawlen > 0);
661 649 : return p-entry.prevrawlen;
662 : }
663 : }
664 :
665 : /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending
666 : * on the encoding of the entry. 'e' is always set to NULL to be able
667 : * to find out whether the string pointer or the integer value was set.
668 : * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */
669 545084 : unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
670 : zlentry entry;
671 545084 : if (p == NULL || p[0] == ZIP_END) return 0;
672 545084 : if (sstr) *sstr = NULL;
673 :
674 545084 : entry = zipEntry(p);
675 545084 : if (ZIP_IS_STR(entry.encoding)) {
676 346838 : if (sstr) {
677 346838 : *slen = entry.len;
678 346838 : *sstr = p+entry.headersize;
679 : }
680 : } else {
681 198246 : if (sval) {
682 198246 : *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
683 : }
684 : }
685 545084 : return 1;
686 : }
687 :
688 : /* Insert an entry at "p". */
689 26161 : unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
690 26161 : return __ziplistInsert(zl,p,s,slen);
691 : }
692 :
693 : /* Delete a single entry from the ziplist, pointed to by *p.
694 : * Also update *p in place, to be able to iterate over the
695 : * ziplist, while deleting entries. */
696 53329 : unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
697 53329 : size_t offset = *p-zl;
698 53329 : zl = __ziplistDelete(zl,*p,1);
699 :
700 : /* Store pointer to current element in p, because ziplistDelete will
701 : * do a realloc which might result in a different "zl"-pointer.
702 : * When the delete direction is back to front, we might delete the last
703 : * entry and end up with "p" pointing to ZIP_END, so check this. */
704 53329 : *p = zl+offset;
705 53329 : return zl;
706 : }
707 :
708 : /* Delete a range of entries from the ziplist. */
709 2032 : unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
710 2032 : unsigned char *p = ziplistIndex(zl,index);
711 2032 : return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
712 : }
713 :
714 : /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */
715 2032073 : unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
716 : zlentry entry;
717 : unsigned char sencoding;
718 : long long zval, sval;
719 2032073 : if (p[0] == ZIP_END) return 0;
720 :
721 2029634 : entry = zipEntry(p);
722 2029634 : if (ZIP_IS_STR(entry.encoding)) {
723 : /* Raw compare */
724 29444 : if (entry.len == slen) {
725 8678 : return memcmp(p+entry.headersize,sstr,slen) == 0;
726 : } else {
727 20766 : return 0;
728 : }
729 : } else {
730 : /* Try to compare encoded values */
731 2000190 : if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
732 1967189 : if (entry.encoding == sencoding) {
733 1955742 : zval = zipLoadInteger(p+entry.headersize,entry.encoding);
734 1955742 : return zval == sval;
735 : }
736 : }
737 : }
738 44448 : return 0;
739 : }
740 :
741 : /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
742 : * between every comparison. Returns NULL when the field could not be found. */
743 60659 : unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
744 60659 : int skipcnt = 0;
745 60659 : unsigned char vencoding = 0;
746 60659 : long long vll = 0;
747 :
748 146856 : while (p[0] != ZIP_END) {
749 : unsigned int prevlensize, encoding, lensize, len;
750 : unsigned char *q;
751 :
752 84552 : ZIP_DECODE_PREVLENSIZE(p, prevlensize);
753 84552 : ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
754 84552 : q = p + prevlensize + lensize;
755 :
756 84552 : if (skipcnt == 0) {
757 : /* Compare current entry with specified entry */
758 71783 : if (ZIP_IS_STR(encoding)) {
759 54785 : if (len == vlen && memcmp(q, vstr, vlen) == 0) {
760 47830 : return p;
761 : }
762 : } else {
763 : /* Find out if the specified entry can be encoded */
764 16998 : if (vencoding == 0) {
765 : /* UINT_MAX when the entry CANNOT be encoded */
766 12447 : if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
767 302 : vencoding = UCHAR_MAX;
768 : }
769 :
770 : /* Must be non-zero by now */
771 12447 : assert(vencoding);
772 : }
773 :
774 : /* Compare current entry with specified entry */
775 16998 : if (encoding == vencoding) {
776 13779 : long long ll = zipLoadInteger(q, encoding);
777 13779 : if (ll == vll) {
778 11184 : return p;
779 : }
780 : }
781 : }
782 :
783 : /* Reset skip count */
784 12769 : skipcnt = skip;
785 : } else {
786 : /* Skip entry */
787 12769 : skipcnt--;
788 : }
789 :
790 : /* Move to next entry */
791 25538 : p = q + len;
792 : }
793 :
794 1645 : return NULL;
795 : }
796 :
797 : /* Return length of ziplist. */
798 266050 : unsigned int ziplistLen(unsigned char *zl) {
799 266050 : unsigned int len = 0;
800 266050 : if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
801 266050 : len = intrev16ifbe(ZIPLIST_LENGTH(zl));
802 : } else {
803 0 : unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
804 0 : while (*p != ZIP_END) {
805 0 : p += zipRawEntryLength(p);
806 0 : len++;
807 : }
808 :
809 : /* Re-store length if small enough */
810 0 : if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
811 : }
812 266050 : return len;
813 : }
814 :
815 : /* Return ziplist blob size in bytes. */
816 23924 : size_t ziplistBlobLen(unsigned char *zl) {
817 23924 : return intrev32ifbe(ZIPLIST_BYTES(zl));
818 : }
819 :
820 0 : void ziplistRepr(unsigned char *zl) {
821 : unsigned char *p;
822 0 : int index = 0;
823 : zlentry entry;
824 :
825 0 : printf(
826 : "{total bytes %d} "
827 : "{length %u}\n"
828 : "{tail offset %u}\n",
829 0 : intrev32ifbe(ZIPLIST_BYTES(zl)),
830 0 : intrev16ifbe(ZIPLIST_LENGTH(zl)),
831 0 : intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)));
832 0 : p = ZIPLIST_ENTRY_HEAD(zl);
833 0 : while(*p != ZIP_END) {
834 0 : entry = zipEntry(p);
835 0 : printf(
836 : "{"
837 : "addr 0x%08lx, "
838 : "index %2d, "
839 : "offset %5ld, "
840 : "rl: %5u, "
841 : "hs %2u, "
842 : "pl: %5u, "
843 : "pls: %2u, "
844 : "payload %5u"
845 : "} ",
846 : (long unsigned)p,
847 : index,
848 0 : (unsigned long) (p-zl),
849 : entry.headersize+entry.len,
850 : entry.headersize,
851 : entry.prevrawlen,
852 : entry.prevrawlensize,
853 : entry.len);
854 0 : p += entry.headersize;
855 0 : if (ZIP_IS_STR(entry.encoding)) {
856 0 : if (entry.len > 40) {
857 0 : if (fwrite(p,40,1,stdout) == 0) perror("fwrite");
858 0 : printf("...");
859 : } else {
860 0 : if (entry.len &&
861 0 : fwrite(p,entry.len,1,stdout) == 0) perror("fwrite");
862 : }
863 : } else {
864 0 : printf("%lld", (long long) zipLoadInteger(p,entry.encoding));
865 : }
866 0 : printf("\n");
867 0 : p += entry.len;
868 0 : index++;
869 : }
870 0 : printf("{end}\n\n");
871 0 : }
872 :
873 : #ifdef ZIPLIST_TEST_MAIN
874 : #include <sys/time.h>
875 : #include "adlist.h"
876 : #include "sds.h"
877 :
878 : #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); }
879 :
880 : unsigned char *createList() {
881 : unsigned char *zl = ziplistNew();
882 : zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
883 : zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
884 : zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
885 : zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL);
886 : return zl;
887 : }
888 :
889 : unsigned char *createIntList() {
890 : unsigned char *zl = ziplistNew();
891 : char buf[32];
892 :
893 : sprintf(buf, "100");
894 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
895 : sprintf(buf, "128000");
896 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
897 : sprintf(buf, "-100");
898 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
899 : sprintf(buf, "4294967296");
900 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
901 : sprintf(buf, "non integer");
902 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
903 : sprintf(buf, "much much longer non integer");
904 : zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
905 : return zl;
906 : }
907 :
908 : long long usec(void) {
909 : struct timeval tv;
910 : gettimeofday(&tv,NULL);
911 : return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
912 : }
913 :
914 : void stress(int pos, int num, int maxsize, int dnum) {
915 : int i,j,k;
916 : unsigned char *zl;
917 : char posstr[2][5] = { "HEAD", "TAIL" };
918 : long long start;
919 : for (i = 0; i < maxsize; i+=dnum) {
920 : zl = ziplistNew();
921 : for (j = 0; j < i; j++) {
922 : zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL);
923 : }
924 :
925 : /* Do num times a push+pop from pos */
926 : start = usec();
927 : for (k = 0; k < num; k++) {
928 : zl = ziplistPush(zl,(unsigned char*)"quux",4,pos);
929 : zl = ziplistDeleteRange(zl,0,1);
930 : }
931 : printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n",
932 : i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start);
933 : zfree(zl);
934 : }
935 : }
936 :
937 : void pop(unsigned char *zl, int where) {
938 : unsigned char *p, *vstr;
939 : unsigned int vlen;
940 : long long vlong;
941 :
942 : p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1);
943 : if (ziplistGet(p,&vstr,&vlen,&vlong)) {
944 : if (where == ZIPLIST_HEAD)
945 : printf("Pop head: ");
946 : else
947 : printf("Pop tail: ");
948 :
949 : if (vstr)
950 : if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite");
951 : else
952 : printf("%lld", vlong);
953 :
954 : printf("\n");
955 : ziplistDeleteRange(zl,-1,1);
956 : } else {
957 : printf("ERROR: Could not pop\n");
958 : exit(1);
959 : }
960 : }
961 :
962 : int randstring(char *target, unsigned int min, unsigned int max) {
963 : int p, len = min+rand()%(max-min+1);
964 : int minval, maxval;
965 : switch(rand() % 3) {
966 : case 0:
967 : minval = 0;
968 : maxval = 255;
969 : break;
970 : case 1:
971 : minval = 48;
972 : maxval = 122;
973 : break;
974 : case 2:
975 : minval = 48;
976 : maxval = 52;
977 : break;
978 : default:
979 : assert(NULL);
980 : }
981 :
982 : while(p < len)
983 : target[p++] = minval+rand()%(maxval-minval+1);
984 : return len;
985 : }
986 :
987 : int main(int argc, char **argv) {
988 : unsigned char *zl, *p;
989 : unsigned char *entry;
990 : unsigned int elen;
991 : long long value;
992 :
993 : /* If an argument is given, use it as the random seed. */
994 : if (argc == 2)
995 : srand(atoi(argv[1]));
996 :
997 : zl = createIntList();
998 : ziplistRepr(zl);
999 :
1000 : zl = createList();
1001 : ziplistRepr(zl);
1002 :
1003 : pop(zl,ZIPLIST_TAIL);
1004 : ziplistRepr(zl);
1005 :
1006 : pop(zl,ZIPLIST_HEAD);
1007 : ziplistRepr(zl);
1008 :
1009 : pop(zl,ZIPLIST_TAIL);
1010 : ziplistRepr(zl);
1011 :
1012 : pop(zl,ZIPLIST_TAIL);
1013 : ziplistRepr(zl);
1014 :
1015 : printf("Get element at index 3:\n");
1016 : {
1017 : zl = createList();
1018 : p = ziplistIndex(zl, 3);
1019 : if (!ziplistGet(p, &entry, &elen, &value)) {
1020 : printf("ERROR: Could not access index 3\n");
1021 : return 1;
1022 : }
1023 : if (entry) {
1024 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1025 : printf("\n");
1026 : } else {
1027 : printf("%lld\n", value);
1028 : }
1029 : printf("\n");
1030 : }
1031 :
1032 : printf("Get element at index 4 (out of range):\n");
1033 : {
1034 : zl = createList();
1035 : p = ziplistIndex(zl, 4);
1036 : if (p == NULL) {
1037 : printf("No entry\n");
1038 : } else {
1039 : printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1040 : return 1;
1041 : }
1042 : printf("\n");
1043 : }
1044 :
1045 : printf("Get element at index -1 (last element):\n");
1046 : {
1047 : zl = createList();
1048 : p = ziplistIndex(zl, -1);
1049 : if (!ziplistGet(p, &entry, &elen, &value)) {
1050 : printf("ERROR: Could not access index -1\n");
1051 : return 1;
1052 : }
1053 : if (entry) {
1054 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1055 : printf("\n");
1056 : } else {
1057 : printf("%lld\n", value);
1058 : }
1059 : printf("\n");
1060 : }
1061 :
1062 : printf("Get element at index -4 (first element):\n");
1063 : {
1064 : zl = createList();
1065 : p = ziplistIndex(zl, -4);
1066 : if (!ziplistGet(p, &entry, &elen, &value)) {
1067 : printf("ERROR: Could not access index -4\n");
1068 : return 1;
1069 : }
1070 : if (entry) {
1071 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1072 : printf("\n");
1073 : } else {
1074 : printf("%lld\n", value);
1075 : }
1076 : printf("\n");
1077 : }
1078 :
1079 : printf("Get element at index -5 (reverse out of range):\n");
1080 : {
1081 : zl = createList();
1082 : p = ziplistIndex(zl, -5);
1083 : if (p == NULL) {
1084 : printf("No entry\n");
1085 : } else {
1086 : printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1087 : return 1;
1088 : }
1089 : printf("\n");
1090 : }
1091 :
1092 : printf("Iterate list from 0 to end:\n");
1093 : {
1094 : zl = createList();
1095 : p = ziplistIndex(zl, 0);
1096 : while (ziplistGet(p, &entry, &elen, &value)) {
1097 : printf("Entry: ");
1098 : if (entry) {
1099 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1100 : } else {
1101 : printf("%lld", value);
1102 : }
1103 : p = ziplistNext(zl,p);
1104 : printf("\n");
1105 : }
1106 : printf("\n");
1107 : }
1108 :
1109 : printf("Iterate list from 1 to end:\n");
1110 : {
1111 : zl = createList();
1112 : p = ziplistIndex(zl, 1);
1113 : while (ziplistGet(p, &entry, &elen, &value)) {
1114 : printf("Entry: ");
1115 : if (entry) {
1116 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1117 : } else {
1118 : printf("%lld", value);
1119 : }
1120 : p = ziplistNext(zl,p);
1121 : printf("\n");
1122 : }
1123 : printf("\n");
1124 : }
1125 :
1126 : printf("Iterate list from 2 to end:\n");
1127 : {
1128 : zl = createList();
1129 : p = ziplistIndex(zl, 2);
1130 : while (ziplistGet(p, &entry, &elen, &value)) {
1131 : printf("Entry: ");
1132 : if (entry) {
1133 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1134 : } else {
1135 : printf("%lld", value);
1136 : }
1137 : p = ziplistNext(zl,p);
1138 : printf("\n");
1139 : }
1140 : printf("\n");
1141 : }
1142 :
1143 : printf("Iterate starting out of range:\n");
1144 : {
1145 : zl = createList();
1146 : p = ziplistIndex(zl, 4);
1147 : if (!ziplistGet(p, &entry, &elen, &value)) {
1148 : printf("No entry\n");
1149 : } else {
1150 : printf("ERROR\n");
1151 : }
1152 : printf("\n");
1153 : }
1154 :
1155 : printf("Iterate from back to front:\n");
1156 : {
1157 : zl = createList();
1158 : p = ziplistIndex(zl, -1);
1159 : while (ziplistGet(p, &entry, &elen, &value)) {
1160 : printf("Entry: ");
1161 : if (entry) {
1162 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1163 : } else {
1164 : printf("%lld", value);
1165 : }
1166 : p = ziplistPrev(zl,p);
1167 : printf("\n");
1168 : }
1169 : printf("\n");
1170 : }
1171 :
1172 : printf("Iterate from back to front, deleting all items:\n");
1173 : {
1174 : zl = createList();
1175 : p = ziplistIndex(zl, -1);
1176 : while (ziplistGet(p, &entry, &elen, &value)) {
1177 : printf("Entry: ");
1178 : if (entry) {
1179 : if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1180 : } else {
1181 : printf("%lld", value);
1182 : }
1183 : zl = ziplistDelete(zl,&p);
1184 : p = ziplistPrev(zl,p);
1185 : printf("\n");
1186 : }
1187 : printf("\n");
1188 : }
1189 :
1190 : printf("Delete inclusive range 0,0:\n");
1191 : {
1192 : zl = createList();
1193 : zl = ziplistDeleteRange(zl, 0, 1);
1194 : ziplistRepr(zl);
1195 : }
1196 :
1197 : printf("Delete inclusive range 0,1:\n");
1198 : {
1199 : zl = createList();
1200 : zl = ziplistDeleteRange(zl, 0, 2);
1201 : ziplistRepr(zl);
1202 : }
1203 :
1204 : printf("Delete inclusive range 1,2:\n");
1205 : {
1206 : zl = createList();
1207 : zl = ziplistDeleteRange(zl, 1, 2);
1208 : ziplistRepr(zl);
1209 : }
1210 :
1211 : printf("Delete with start index out of range:\n");
1212 : {
1213 : zl = createList();
1214 : zl = ziplistDeleteRange(zl, 5, 1);
1215 : ziplistRepr(zl);
1216 : }
1217 :
1218 : printf("Delete with num overflow:\n");
1219 : {
1220 : zl = createList();
1221 : zl = ziplistDeleteRange(zl, 1, 5);
1222 : ziplistRepr(zl);
1223 : }
1224 :
1225 : printf("Delete foo while iterating:\n");
1226 : {
1227 : zl = createList();
1228 : p = ziplistIndex(zl,0);
1229 : while (ziplistGet(p,&entry,&elen,&value)) {
1230 : if (entry && strncmp("foo",(char*)entry,elen) == 0) {
1231 : printf("Delete foo\n");
1232 : zl = ziplistDelete(zl,&p);
1233 : } else {
1234 : printf("Entry: ");
1235 : if (entry) {
1236 : if (elen && fwrite(entry,elen,1,stdout) == 0)
1237 : perror("fwrite");
1238 : } else {
1239 : printf("%lld",value);
1240 : }
1241 : p = ziplistNext(zl,p);
1242 : printf("\n");
1243 : }
1244 : }
1245 : printf("\n");
1246 : ziplistRepr(zl);
1247 : }
1248 :
1249 : printf("Regression test for >255 byte strings:\n");
1250 : {
1251 : char v1[257],v2[257];
1252 : memset(v1,'x',256);
1253 : memset(v2,'y',256);
1254 : zl = ziplistNew();
1255 : zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL);
1256 : zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL);
1257 :
1258 : /* Pop values again and compare their value. */
1259 : p = ziplistIndex(zl,0);
1260 : assert(ziplistGet(p,&entry,&elen,&value));
1261 : assert(strncmp(v1,(char*)entry,elen) == 0);
1262 : p = ziplistIndex(zl,1);
1263 : assert(ziplistGet(p,&entry,&elen,&value));
1264 : assert(strncmp(v2,(char*)entry,elen) == 0);
1265 : printf("SUCCESS\n\n");
1266 : }
1267 :
1268 : printf("Create long list and check indices:\n");
1269 : {
1270 : zl = ziplistNew();
1271 : char buf[32];
1272 : int i,len;
1273 : for (i = 0; i < 1000; i++) {
1274 : len = sprintf(buf,"%d",i);
1275 : zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL);
1276 : }
1277 : for (i = 0; i < 1000; i++) {
1278 : p = ziplistIndex(zl,i);
1279 : assert(ziplistGet(p,NULL,NULL,&value));
1280 : assert(i == value);
1281 :
1282 : p = ziplistIndex(zl,-i-1);
1283 : assert(ziplistGet(p,NULL,NULL,&value));
1284 : assert(999-i == value);
1285 : }
1286 : printf("SUCCESS\n\n");
1287 : }
1288 :
1289 : printf("Compare strings with ziplist entries:\n");
1290 : {
1291 : zl = createList();
1292 : p = ziplistIndex(zl,0);
1293 : if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
1294 : printf("ERROR: not \"hello\"\n");
1295 : return 1;
1296 : }
1297 : if (ziplistCompare(p,(unsigned char*)"hella",5)) {
1298 : printf("ERROR: \"hella\"\n");
1299 : return 1;
1300 : }
1301 :
1302 : p = ziplistIndex(zl,3);
1303 : if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
1304 : printf("ERROR: not \"1024\"\n");
1305 : return 1;
1306 : }
1307 : if (ziplistCompare(p,(unsigned char*)"1025",4)) {
1308 : printf("ERROR: \"1025\"\n");
1309 : return 1;
1310 : }
1311 : printf("SUCCESS\n\n");
1312 : }
1313 :
1314 : printf("Stress with random payloads of different encoding:\n");
1315 : {
1316 : int i,j,len,where;
1317 : unsigned char *p;
1318 : char buf[1024];
1319 : int buflen;
1320 : list *ref;
1321 : listNode *refnode;
1322 :
1323 : /* Hold temp vars from ziplist */
1324 : unsigned char *sstr;
1325 : unsigned int slen;
1326 : long long sval;
1327 :
1328 : for (i = 0; i < 20000; i++) {
1329 : zl = ziplistNew();
1330 : ref = listCreate();
1331 : listSetFreeMethod(ref,sdsfree);
1332 : len = rand() % 256;
1333 :
1334 : /* Create lists */
1335 : for (j = 0; j < len; j++) {
1336 : where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
1337 : if (rand() % 2) {
1338 : buflen = randstring(buf,1,sizeof(buf)-1);
1339 : } else {
1340 : switch(rand() % 3) {
1341 : case 0:
1342 : buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20);
1343 : break;
1344 : case 1:
1345 : buflen = sprintf(buf,"%lld",(0LL + rand()));
1346 : break;
1347 : case 2:
1348 : buflen = sprintf(buf,"%lld",(0LL + rand()) << 20);
1349 : break;
1350 : default:
1351 : assert(NULL);
1352 : }
1353 : }
1354 :
1355 : /* Add to ziplist */
1356 : zl = ziplistPush(zl, (unsigned char*)buf, buflen, where);
1357 :
1358 : /* Add to reference list */
1359 : if (where == ZIPLIST_HEAD) {
1360 : listAddNodeHead(ref,sdsnewlen(buf, buflen));
1361 : } else if (where == ZIPLIST_TAIL) {
1362 : listAddNodeTail(ref,sdsnewlen(buf, buflen));
1363 : } else {
1364 : assert(NULL);
1365 : }
1366 : }
1367 :
1368 : assert(listLength(ref) == ziplistLen(zl));
1369 : for (j = 0; j < len; j++) {
1370 : /* Naive way to get elements, but similar to the stresser
1371 : * executed from the Tcl test suite. */
1372 : p = ziplistIndex(zl,j);
1373 : refnode = listIndex(ref,j);
1374 :
1375 : assert(ziplistGet(p,&sstr,&slen,&sval));
1376 : if (sstr == NULL) {
1377 : buflen = sprintf(buf,"%lld",sval);
1378 : } else {
1379 : buflen = slen;
1380 : memcpy(buf,sstr,buflen);
1381 : buf[buflen] = '\0';
1382 : }
1383 : assert(memcmp(buf,listNodeValue(refnode),buflen) == 0);
1384 : }
1385 : zfree(zl);
1386 : listRelease(ref);
1387 : }
1388 : printf("SUCCESS\n\n");
1389 : }
1390 :
1391 : printf("Stress with variable ziplist size:\n");
1392 : {
1393 : stress(ZIPLIST_HEAD,100000,16384,256);
1394 : stress(ZIPLIST_TAIL,100000,16384,256);
1395 : }
1396 :
1397 : return 0;
1398 : }
1399 :
1400 : #endif
|
