1 | /* |
2 | * Copyright (c) 2009-2012, Pieter Noordhuis <pcnoordhuis at gmail dot com> |
3 | * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com> |
4 | * All rights reserved. |
5 | * |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions are met: |
8 | * |
9 | * * Redistributions of source code must retain the above copyright notice, |
10 | * this list of conditions and the following disclaimer. |
11 | * * Redistributions in binary form must reproduce the above copyright |
12 | * notice, this list of conditions and the following disclaimer in the |
13 | * documentation and/or other materials provided with the distribution. |
14 | * * Neither the name of Redis nor the names of its contributors may be used |
15 | * to endorse or promote products derived from this software without |
16 | * specific prior written permission. |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
19 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
20 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
21 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
22 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
23 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
24 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
25 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
26 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
27 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
28 | * POSSIBILITY OF SUCH DAMAGE. |
29 | */ |
30 | |
31 | #include <stdio.h> |
32 | #include <stdlib.h> |
33 | #include <string.h> |
34 | #include "intset.h" |
35 | #include "zmalloc.h" |
36 | #include "endianconv.h" |
37 | #include "redisassert.h" |
38 | |
39 | /* Note that these encodings are ordered, so: |
40 | * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */ |
41 | #define INTSET_ENC_INT16 (sizeof(int16_t)) |
42 | #define INTSET_ENC_INT32 (sizeof(int32_t)) |
43 | #define INTSET_ENC_INT64 (sizeof(int64_t)) |
44 | |
45 | /* Return the required encoding for the provided value. */ |
46 | static uint8_t _intsetValueEncoding(int64_t v) { |
47 | if (v < INT32_MIN || v > INT32_MAX) |
48 | return INTSET_ENC_INT64; |
49 | else if (v < INT16_MIN || v > INT16_MAX) |
50 | return INTSET_ENC_INT32; |
51 | else |
52 | return INTSET_ENC_INT16; |
53 | } |
54 | |
55 | /* Return the value at pos, given an encoding. */ |
56 | static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) { |
57 | int64_t v64; |
58 | int32_t v32; |
59 | int16_t v16; |
60 | |
61 | if (enc == INTSET_ENC_INT64) { |
62 | memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64)); |
63 | memrev64ifbe(&v64); |
64 | return v64; |
65 | } else if (enc == INTSET_ENC_INT32) { |
66 | memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32)); |
67 | memrev32ifbe(&v32); |
68 | return v32; |
69 | } else { |
70 | memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16)); |
71 | memrev16ifbe(&v16); |
72 | return v16; |
73 | } |
74 | } |
75 | |
76 | /* Return the value at pos, using the configured encoding. */ |
77 | static int64_t _intsetGet(intset *is, int pos) { |
78 | return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding)); |
79 | } |
80 | |
81 | /* Set the value at pos, using the configured encoding. */ |
82 | static void _intsetSet(intset *is, int pos, int64_t value) { |
83 | uint32_t encoding = intrev32ifbe(is->encoding); |
84 | |
85 | if (encoding == INTSET_ENC_INT64) { |
86 | ((int64_t*)is->contents)[pos] = value; |
87 | memrev64ifbe(((int64_t*)is->contents)+pos); |
88 | } else if (encoding == INTSET_ENC_INT32) { |
89 | ((int32_t*)is->contents)[pos] = value; |
90 | memrev32ifbe(((int32_t*)is->contents)+pos); |
91 | } else { |
92 | ((int16_t*)is->contents)[pos] = value; |
93 | memrev16ifbe(((int16_t*)is->contents)+pos); |
94 | } |
95 | } |
96 | |
97 | /* Create an empty intset. */ |
98 | intset *intsetNew(void) { |
99 | intset *is = zmalloc(sizeof(intset)); |
100 | is->encoding = intrev32ifbe(INTSET_ENC_INT16); |
101 | is->length = 0; |
102 | return is; |
103 | } |
104 | |
105 | /* Resize the intset */ |
106 | static intset *intsetResize(intset *is, uint32_t len) { |
107 | uint64_t size = (uint64_t)len*intrev32ifbe(is->encoding); |
108 | assert(size <= SIZE_MAX - sizeof(intset)); |
109 | is = zrealloc(is,sizeof(intset)+size); |
110 | return is; |
111 | } |
112 | |
113 | /* Search for the position of "value". Return 1 when the value was found and |
114 | * sets "pos" to the position of the value within the intset. Return 0 when |
115 | * the value is not present in the intset and sets "pos" to the position |
116 | * where "value" can be inserted. */ |
117 | static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { |
118 | int min = 0, max = intrev32ifbe(is->length)-1, mid = -1; |
119 | int64_t cur = -1; |
120 | |
121 | /* The value can never be found when the set is empty */ |
122 | if (intrev32ifbe(is->length) == 0) { |
123 | if (pos) *pos = 0; |
124 | return 0; |
125 | } else { |
126 | /* Check for the case where we know we cannot find the value, |
127 | * but do know the insert position. */ |
128 | if (value > _intsetGet(is,max)) { |
129 | if (pos) *pos = intrev32ifbe(is->length); |
130 | return 0; |
131 | } else if (value < _intsetGet(is,0)) { |
132 | if (pos) *pos = 0; |
133 | return 0; |
134 | } |
135 | } |
136 | |
137 | while(max >= min) { |
138 | mid = ((unsigned int)min + (unsigned int)max) >> 1; |
139 | cur = _intsetGet(is,mid); |
140 | if (value > cur) { |
141 | min = mid+1; |
142 | } else if (value < cur) { |
143 | max = mid-1; |
144 | } else { |
145 | break; |
146 | } |
147 | } |
148 | |
149 | if (value == cur) { |
150 | if (pos) *pos = mid; |
151 | return 1; |
152 | } else { |
153 | if (pos) *pos = min; |
154 | return 0; |
155 | } |
156 | } |
157 | |
158 | /* Upgrades the intset to a larger encoding and inserts the given integer. */ |
159 | static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { |
160 | uint8_t curenc = intrev32ifbe(is->encoding); |
161 | uint8_t newenc = _intsetValueEncoding(value); |
162 | int length = intrev32ifbe(is->length); |
163 | int prepend = value < 0 ? 1 : 0; |
164 | |
165 | /* First set new encoding and resize */ |
166 | is->encoding = intrev32ifbe(newenc); |
167 | is = intsetResize(is,intrev32ifbe(is->length)+1); |
168 | |
169 | /* Upgrade back-to-front so we don't overwrite values. |
170 | * Note that the "prepend" variable is used to make sure we have an empty |
171 | * space at either the beginning or the end of the intset. */ |
172 | while(length--) |
173 | _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); |
174 | |
175 | /* Set the value at the beginning or the end. */ |
176 | if (prepend) |
177 | _intsetSet(is,0,value); |
178 | else |
179 | _intsetSet(is,intrev32ifbe(is->length),value); |
180 | is->length = intrev32ifbe(intrev32ifbe(is->length)+1); |
181 | return is; |
182 | } |
183 | |
184 | static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) { |
185 | void *src, *dst; |
186 | uint32_t bytes = intrev32ifbe(is->length)-from; |
187 | uint32_t encoding = intrev32ifbe(is->encoding); |
188 | |
189 | if (encoding == INTSET_ENC_INT64) { |
190 | src = (int64_t*)is->contents+from; |
191 | dst = (int64_t*)is->contents+to; |
192 | bytes *= sizeof(int64_t); |
193 | } else if (encoding == INTSET_ENC_INT32) { |
194 | src = (int32_t*)is->contents+from; |
195 | dst = (int32_t*)is->contents+to; |
196 | bytes *= sizeof(int32_t); |
197 | } else { |
198 | src = (int16_t*)is->contents+from; |
199 | dst = (int16_t*)is->contents+to; |
200 | bytes *= sizeof(int16_t); |
201 | } |
202 | memmove(dst,src,bytes); |
203 | } |
204 | |
205 | /* Insert an integer in the intset */ |
206 | intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { |
207 | uint8_t valenc = _intsetValueEncoding(value); |
208 | uint32_t pos; |
209 | if (success) *success = 1; |
210 | |
211 | /* Upgrade encoding if necessary. If we need to upgrade, we know that |
212 | * this value should be either appended (if > 0) or prepended (if < 0), |
213 | * because it lies outside the range of existing values. */ |
214 | if (valenc > intrev32ifbe(is->encoding)) { |
215 | /* This always succeeds, so we don't need to curry *success. */ |
216 | return intsetUpgradeAndAdd(is,value); |
217 | } else { |
218 | /* Abort if the value is already present in the set. |
219 | * This call will populate "pos" with the right position to insert |
220 | * the value when it cannot be found. */ |
221 | if (intsetSearch(is,value,&pos)) { |
222 | if (success) *success = 0; |
223 | return is; |
224 | } |
225 | |
226 | is = intsetResize(is,intrev32ifbe(is->length)+1); |
227 | if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1); |
228 | } |
229 | |
230 | _intsetSet(is,pos,value); |
231 | is->length = intrev32ifbe(intrev32ifbe(is->length)+1); |
232 | return is; |
233 | } |
234 | |
235 | /* Delete integer from intset */ |
236 | intset *intsetRemove(intset *is, int64_t value, int *success) { |
237 | uint8_t valenc = _intsetValueEncoding(value); |
238 | uint32_t pos; |
239 | if (success) *success = 0; |
240 | |
241 | if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) { |
242 | uint32_t len = intrev32ifbe(is->length); |
243 | |
244 | /* We know we can delete */ |
245 | if (success) *success = 1; |
246 | |
247 | /* Overwrite value with tail and update length */ |
248 | if (pos < (len-1)) intsetMoveTail(is,pos+1,pos); |
249 | is = intsetResize(is,len-1); |
250 | is->length = intrev32ifbe(len-1); |
251 | } |
252 | return is; |
253 | } |
254 | |
255 | /* Determine whether a value belongs to this set */ |
256 | uint8_t intsetFind(intset *is, int64_t value) { |
257 | uint8_t valenc = _intsetValueEncoding(value); |
258 | return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL); |
259 | } |
260 | |
261 | /* Return random member */ |
262 | int64_t intsetRandom(intset *is) { |
263 | uint32_t len = intrev32ifbe(is->length); |
264 | assert(len); /* avoid division by zero on corrupt intset payload. */ |
265 | return _intsetGet(is,rand()%len); |
266 | } |
267 | |
268 | /* Get the value at the given position. When this position is |
269 | * out of range the function returns 0, when in range it returns 1. */ |
270 | uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) { |
271 | if (pos < intrev32ifbe(is->length)) { |
272 | *value = _intsetGet(is,pos); |
273 | return 1; |
274 | } |
275 | return 0; |
276 | } |
277 | |
278 | /* Return intset length */ |
279 | uint32_t intsetLen(const intset *is) { |
280 | return intrev32ifbe(is->length); |
281 | } |
282 | |
283 | /* Return intset blob size in bytes. */ |
284 | size_t intsetBlobLen(intset *is) { |
285 | return sizeof(intset)+(size_t)intrev32ifbe(is->length)*intrev32ifbe(is->encoding); |
286 | } |
287 | |
288 | /* Validate the integrity of the data structure. |
289 | * when `deep` is 0, only the integrity of the header is validated. |
290 | * when `deep` is 1, we make sure there are no duplicate or out of order records. */ |
291 | int intsetValidateIntegrity(const unsigned char *p, size_t size, int deep) { |
292 | intset *is = (intset *)p; |
293 | /* check that we can actually read the header. */ |
294 | if (size < sizeof(*is)) |
295 | return 0; |
296 | |
297 | uint32_t encoding = intrev32ifbe(is->encoding); |
298 | |
299 | size_t record_size; |
300 | if (encoding == INTSET_ENC_INT64) { |
301 | record_size = INTSET_ENC_INT64; |
302 | } else if (encoding == INTSET_ENC_INT32) { |
303 | record_size = INTSET_ENC_INT32; |
304 | } else if (encoding == INTSET_ENC_INT16){ |
305 | record_size = INTSET_ENC_INT16; |
306 | } else { |
307 | return 0; |
308 | } |
309 | |
310 | /* check that the size matches (all records are inside the buffer). */ |
311 | uint32_t count = intrev32ifbe(is->length); |
312 | if (sizeof(*is) + count*record_size != size) |
313 | return 0; |
314 | |
315 | /* check that the set is not empty. */ |
316 | if (count==0) |
317 | return 0; |
318 | |
319 | if (!deep) |
320 | return 1; |
321 | |
322 | /* check that there are no dup or out of order records. */ |
323 | int64_t prev = _intsetGet(is,0); |
324 | for (uint32_t i=1; i<count; i++) { |
325 | int64_t cur = _intsetGet(is,i); |
326 | if (cur <= prev) |
327 | return 0; |
328 | prev = cur; |
329 | } |
330 | |
331 | return 1; |
332 | } |
333 | |
334 | #ifdef REDIS_TEST |
335 | #include <sys/time.h> |
336 | #include <time.h> |
337 | |
338 | #if 0 |
339 | static void intsetRepr(intset *is) { |
340 | for (uint32_t i = 0; i < intrev32ifbe(is->length); i++) { |
341 | printf("%lld\n" , (uint64_t)_intsetGet(is,i)); |
342 | } |
343 | printf("\n" ); |
344 | } |
345 | |
346 | static void error(char *err) { |
347 | printf("%s\n" , err); |
348 | exit(1); |
349 | } |
350 | #endif |
351 | |
352 | static void ok(void) { |
353 | printf("OK\n" ); |
354 | } |
355 | |
356 | static long long usec(void) { |
357 | struct timeval tv; |
358 | gettimeofday(&tv,NULL); |
359 | return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; |
360 | } |
361 | |
362 | static intset *createSet(int bits, int size) { |
363 | uint64_t mask = (1<<bits)-1; |
364 | uint64_t value; |
365 | intset *is = intsetNew(); |
366 | |
367 | for (int i = 0; i < size; i++) { |
368 | if (bits > 32) { |
369 | value = (rand()*rand()) & mask; |
370 | } else { |
371 | value = rand() & mask; |
372 | } |
373 | is = intsetAdd(is,value,NULL); |
374 | } |
375 | return is; |
376 | } |
377 | |
378 | static void checkConsistency(intset *is) { |
379 | for (uint32_t i = 0; i < (intrev32ifbe(is->length)-1); i++) { |
380 | uint32_t encoding = intrev32ifbe(is->encoding); |
381 | |
382 | if (encoding == INTSET_ENC_INT16) { |
383 | int16_t *i16 = (int16_t*)is->contents; |
384 | assert(i16[i] < i16[i+1]); |
385 | } else if (encoding == INTSET_ENC_INT32) { |
386 | int32_t *i32 = (int32_t*)is->contents; |
387 | assert(i32[i] < i32[i+1]); |
388 | } else { |
389 | int64_t *i64 = (int64_t*)is->contents; |
390 | assert(i64[i] < i64[i+1]); |
391 | } |
392 | } |
393 | } |
394 | |
395 | #define UNUSED(x) (void)(x) |
396 | int intsetTest(int argc, char **argv, int flags) { |
397 | uint8_t success; |
398 | int i; |
399 | intset *is; |
400 | srand(time(NULL)); |
401 | |
402 | UNUSED(argc); |
403 | UNUSED(argv); |
404 | UNUSED(flags); |
405 | |
406 | printf("Value encodings: " ); { |
407 | assert(_intsetValueEncoding(-32768) == INTSET_ENC_INT16); |
408 | assert(_intsetValueEncoding(+32767) == INTSET_ENC_INT16); |
409 | assert(_intsetValueEncoding(-32769) == INTSET_ENC_INT32); |
410 | assert(_intsetValueEncoding(+32768) == INTSET_ENC_INT32); |
411 | assert(_intsetValueEncoding(-2147483648) == INTSET_ENC_INT32); |
412 | assert(_intsetValueEncoding(+2147483647) == INTSET_ENC_INT32); |
413 | assert(_intsetValueEncoding(-2147483649) == INTSET_ENC_INT64); |
414 | assert(_intsetValueEncoding(+2147483648) == INTSET_ENC_INT64); |
415 | assert(_intsetValueEncoding(-9223372036854775808ull) == |
416 | INTSET_ENC_INT64); |
417 | assert(_intsetValueEncoding(+9223372036854775807ull) == |
418 | INTSET_ENC_INT64); |
419 | ok(); |
420 | } |
421 | |
422 | printf("Basic adding: " ); { |
423 | is = intsetNew(); |
424 | is = intsetAdd(is,5,&success); assert(success); |
425 | is = intsetAdd(is,6,&success); assert(success); |
426 | is = intsetAdd(is,4,&success); assert(success); |
427 | is = intsetAdd(is,4,&success); assert(!success); |
428 | ok(); |
429 | zfree(is); |
430 | } |
431 | |
432 | printf("Large number of random adds: " ); { |
433 | uint32_t inserts = 0; |
434 | is = intsetNew(); |
435 | for (i = 0; i < 1024; i++) { |
436 | is = intsetAdd(is,rand()%0x800,&success); |
437 | if (success) inserts++; |
438 | } |
439 | assert(intrev32ifbe(is->length) == inserts); |
440 | checkConsistency(is); |
441 | ok(); |
442 | zfree(is); |
443 | } |
444 | |
445 | printf("Upgrade from int16 to int32: " ); { |
446 | is = intsetNew(); |
447 | is = intsetAdd(is,32,NULL); |
448 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16); |
449 | is = intsetAdd(is,65535,NULL); |
450 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32); |
451 | assert(intsetFind(is,32)); |
452 | assert(intsetFind(is,65535)); |
453 | checkConsistency(is); |
454 | zfree(is); |
455 | |
456 | is = intsetNew(); |
457 | is = intsetAdd(is,32,NULL); |
458 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16); |
459 | is = intsetAdd(is,-65535,NULL); |
460 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32); |
461 | assert(intsetFind(is,32)); |
462 | assert(intsetFind(is,-65535)); |
463 | checkConsistency(is); |
464 | ok(); |
465 | zfree(is); |
466 | } |
467 | |
468 | printf("Upgrade from int16 to int64: " ); { |
469 | is = intsetNew(); |
470 | is = intsetAdd(is,32,NULL); |
471 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16); |
472 | is = intsetAdd(is,4294967295,NULL); |
473 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64); |
474 | assert(intsetFind(is,32)); |
475 | assert(intsetFind(is,4294967295)); |
476 | checkConsistency(is); |
477 | zfree(is); |
478 | |
479 | is = intsetNew(); |
480 | is = intsetAdd(is,32,NULL); |
481 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16); |
482 | is = intsetAdd(is,-4294967295,NULL); |
483 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64); |
484 | assert(intsetFind(is,32)); |
485 | assert(intsetFind(is,-4294967295)); |
486 | checkConsistency(is); |
487 | ok(); |
488 | zfree(is); |
489 | } |
490 | |
491 | printf("Upgrade from int32 to int64: " ); { |
492 | is = intsetNew(); |
493 | is = intsetAdd(is,65535,NULL); |
494 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32); |
495 | is = intsetAdd(is,4294967295,NULL); |
496 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64); |
497 | assert(intsetFind(is,65535)); |
498 | assert(intsetFind(is,4294967295)); |
499 | checkConsistency(is); |
500 | zfree(is); |
501 | |
502 | is = intsetNew(); |
503 | is = intsetAdd(is,65535,NULL); |
504 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32); |
505 | is = intsetAdd(is,-4294967295,NULL); |
506 | assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64); |
507 | assert(intsetFind(is,65535)); |
508 | assert(intsetFind(is,-4294967295)); |
509 | checkConsistency(is); |
510 | ok(); |
511 | zfree(is); |
512 | } |
513 | |
514 | printf("Stress lookups: " ); { |
515 | long num = 100000, size = 10000; |
516 | int i, bits = 20; |
517 | long long start; |
518 | is = createSet(bits,size); |
519 | checkConsistency(is); |
520 | |
521 | start = usec(); |
522 | for (i = 0; i < num; i++) intsetSearch(is,rand() % ((1<<bits)-1),NULL); |
523 | printf("%ld lookups, %ld element set, %lldusec\n" , |
524 | num,size,usec()-start); |
525 | zfree(is); |
526 | } |
527 | |
528 | printf("Stress add+delete: " ); { |
529 | int i, v1, v2; |
530 | is = intsetNew(); |
531 | for (i = 0; i < 0xffff; i++) { |
532 | v1 = rand() % 0xfff; |
533 | is = intsetAdd(is,v1,NULL); |
534 | assert(intsetFind(is,v1)); |
535 | |
536 | v2 = rand() % 0xfff; |
537 | is = intsetRemove(is,v2,NULL); |
538 | assert(!intsetFind(is,v2)); |
539 | } |
540 | checkConsistency(is); |
541 | ok(); |
542 | zfree(is); |
543 | } |
544 | |
545 | return 0; |
546 | } |
547 | #endif |
548 | |