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