Redis源码笔记五: intset

xiu12

1 /*
2  * Copyright (c) 2009-2012, Pieter Noordhuis
3  * Copyright (c) 2009-2012, Salvatore Sanfilippo
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 #ifndef __INTSET_H
32 #define __INTSET_H
33 #include
34
35 typedef struct intset {
36
37     /*  保存元素使用的类型的长度 */
38     uint32_t encoding;
39
40     /* 元素个数 */
41     uint32_t length;
42
43     /* 保存元素的数组 */
44     int8_t contents[];
45 } intset; /* 整数集 */
46
47 /* 创建intset */
48 intset *intsetNew(void);
49
50 /* 添加新元素(不升级) */
51 intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
52
53 /* 删除元素 */
54 intset *intsetRemove(intset *is, int64_t value, int *success);
55
56 uint8_t intsetFind(intset *is, int64_t value);
57
58 int64_t intsetRandom(intset *is);
59
60 /* 按索引获取元素 */
61 uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
62
63 uint32_t intsetLen(intset *is);
64
65 size_t intsetBlobLen(intset *is);
66
67 #endif // __INTSET_H
intset.h




  1 /*
  2  * Copyright (c) 2009-2012, Pieter Noordhuis
  3  * Copyright (c) 2009-2012, Salvatore Sanfilippo
  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
32 #include
33 #include
34 #include "intset.h"
35 #include "zmalloc.h"
36 #include "endianconv.h"
37
38 /* Note that these encodings are ordered, so:
39  * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
40 #define INTSET_ENC_INT16 (sizeof(int16_t))
41 #define INTSET_ENC_INT32 (sizeof(int32_t))
42 #define INTSET_ENC_INT64 (sizeof(int64_t))
43
44 /* Return the required encoding for the provided value. */
45 /* 返回编码v所需的长度 */
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 /* 根据给定编码方式,返回给定位置上的值 */
57 static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
58     int64_t v64;
59     int32_t v32;
60     int16_t v16;
61
62     if (enc == INTSET_ENC_INT64) {
63         memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
64         memrev64ifbe(&v64);
65         return v64;
66     } else if (enc == INTSET_ENC_INT32) {
67         memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
68         memrev32ifbe(&v32);
69         return v32;
70     } else {
71         memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
72         memrev16ifbe(&v16);
73         return v16;
74     }
75 }
76
77 /* Return the value at pos, using the configured encoding. */
78 /* 返回intset上给定pos的值 */
79 static int64_t _intsetGet(intset *is, int pos) {
80     return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
81 }
82
83 /* Set the value at pos, using the configured encoding. */
84 /* 将intset上给定pos的值设置为value */
85 static void _intsetSet(intset *is, int pos, int64_t value) {
86     uint32_t encoding = intrev32ifbe(is->encoding);
87
88     if (encoding == INTSET_ENC_INT64) {
89         ((int64_t*)is->contents)[pos] = value;
90         memrev64ifbe(((int64_t*)is->contents)+pos);
91     } else if (encoding == INTSET_ENC_INT32) {
92         ((int32_t*)is->contents)[pos] = value;
93         memrev32ifbe(((int32_t*)is->contents)+pos);
94     } else {
95         ((int16_t*)is->contents)[pos] = value;
96         memrev16ifbe(((int16_t*)is->contents)+pos);
97     }
98 }
99
100 /* Create an empty intset. */
101 /* 创建一个空的intset */
102 intset *intsetNew(void) {
103     /* 分配内存空间 */
104     intset *is = zmalloc(sizeof(intset));
105
106     /* 更新属性 */
107     is->encoding = intrev32ifbe(INTSET_ENC_INT16);
108     is->length = 0;
109
110     return is;
111 }
112
113 /* Resize the intset */
114 /* 调整intset的大小 */
115 static intset *intsetResize(intset *is, uint32_t len) {
116     uint32_t size = len*intrev32ifbe(is->encoding);
117
118     /* 重新分配空间 */
119     is = zrealloc(is,sizeof(intset)+size);
120
121     return is;
122 }
123
124 /* Search for the position of "value". Return 1 when the value was found and
125  * sets "pos" to the position of the value within the intset. Return 0 when
126  * the value is not present in the intset and sets "pos" to the position
127  * where "value" can be inserted. */
128  /* 查找value在is中的索引
129   *
130   * 查找成功时,将索引保存到pos,并返回1;
131   * 查找失败时,返回0,并将value可以插入的索引保存到pos;
132  */
133 static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
134     int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
135     int64_t cur = -1;
136
137     /* The value can never be found when the set is empty */
138     if (intrev32ifbe(is->length) == 0) {
139         /* 当is为空时,总是查找失败 */
140         if (pos) *pos = 0;
141         return 0;
142     } else {
143         /* Check for the case where we know we cannot find the value,
144          * but do know the insert position. */
145         if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
146             /* 值比is中的最后一个值(所有元素中的最大值)要大,那么这个值应该插入到is最后 */
147             if (pos) *pos = intrev32ifbe(is->length);
148             return 0;
149         } else if (value < _intsetGet(is,0)) {
150             /* value最为新的最小值,插入到is最前 */
151             if (pos) *pos = 0;
152             return 0;
153         }
154     }
155     
156     /* 在is元素数组中进行二分查找 */
157     while(max >= min) {
158         mid = (min+max)/2;
159         cur = _intsetGet(is,mid);
160         if (value > cur) {
161             min = mid+1;
162         } else if (value < cur) {
163             max = mid-1;
164         } else {
165             break;
166         }
167     }
168
169     if (value == cur) {
170         if (pos) *pos = mid;
171         return 1;
172     } else {
173         if (pos) *pos = min;
174         return 0;
175     }
176 }
177
178 /* Upgrades the intset to a larger encoding and inserts the given integer. */
179 /* 根据value,对intset所使用的编码方式进行升级,并扩容intset,最后将value插入到新intset中 */
180 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
181     /* 当前值的编码类型 */
182     uint8_t curenc = intrev32ifbe(is->encoding);
183     /* 新值的编码类型 */
184     uint8_t newenc = _intsetValueEncoding(value);
185
186     /* 元素数量 */
187     int length = intrev32ifbe(is->length);
188
189     /* 决定新值插入的位置(0为头,1为尾) */
190     int prepend = value < 0 ? 1 : 0;
191
192     /* First set new encoding and resize */
193     /* 设置新编码.并根据新编码进行扩容 */
194     is->encoding = intrev32ifbe(newenc);
195     is = intsetResize(is,intrev32ifbe(is->length)+1);
196
197     /* Upgrade back-to-front so we don't overwrite values.
198      * Note that the "prepend" variable is used to make sure we have an empty
199      * space at either the beginning or the end of the intset. */
200     /* 从最后的元素开始进行重新插入
201      * 以新元素插入到最开始为例子,之前:
202      * | 1 | 2 | 3 |
203      * 之后:
204      * | 1 | 2 |                       |   3   |  重插入3
205      * | 1 |                   |   2   |   3   |  重插入2
206      * |               |   1   |   2   |   3   |  重插入1
207      * |     ????      |   1   |   2   |   3   |  ???预留给新元素的空位
208      *
209      * 注: "prepend"是为插入新值而设置的索引偏移量;
210     */
211     while(length--)
212         _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
213
214     /* Set the value at the beginning or the end. */
215     if (prepend)
216         _intsetSet(is,0,value);
217     else
218         _intsetSet(is,intrev32ifbe(is->length),value);
219
220     /* 更新is元素数量 */
221     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
222
223     return is;
224 }
225
226 /*
227  * 对从from开始,到is末尾的所有数据进行移动,以to为起点
228  *
229  * 假设索引2 为from, 索引1 为to:
230  * 之前:
231  * 索引 | 0 | 1 | 2 | 3 |
232  * 值   | a | b | c | d |
233  * 之后：
234  * 索引 | 0 | 1 | 2 | 3 |
235  * 值   | a | c | d | d |
236
237 */
238 static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
239     void *src, *dst;
240
241     /* 需要移动的元素个数 */
242     uint32_t bytes = intrev32ifbe(is->length)-from;
243
244     /* 数组内元素的编码方式 */
245     uint32_t encoding = intrev32ifbe(is->encoding);
246
247     if (encoding == INTSET_ENC_INT64) {
248         /* 计算地址 */
249         src = (int64_t*)is->contents+from;
250         dst = (int64_t*)is->contents+to;
251
252         /* 需要移动的字节数 */
253         bytes *= sizeof(int64_t);
254     } else if (encoding == INTSET_ENC_INT32) {
255         src = (int32_t*)is->contents+from;
256         dst = (int32_t*)is->contents+to;
257         bytes *= sizeof(int32_t);
258     } else {
259         src = (int16_t*)is->contents+from;
260         dst = (int16_t*)is->contents+to;
261         bytes *= sizeof(int16_t);
262     }
263     memmove(dst,src,bytes);
264 }
265
266 /* Insert an integer in the intset */
267 /* 将value添加到集合中
268  * 如果元素已经存在, *success被设置为0;
269  * 如果元素添加成功m *success被设置为1;
270 */
271 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
272     uint8_t valenc = _intsetValueEncoding(value);
273     uint32_t pos;
274     if (success) *success = 1;
275
276     /* Upgrade encoding if necessary. If we need to upgrade, we know that
277      * this value should be either appended (if > 0) or prepended (if < 0),
278      * because it lies outside the range of existing values. */
279     /* 如果有需要,进行升级并插入新值 */
280     if (valenc > intrev32ifbe(is->encoding)) {
281         /* This always succeeds, so we don't need to curry *success. */
282         return intsetUpgradeAndAdd(is,value);
283     } else {
284         /* Abort if the value is already present in the set.
285          * This call will populate "pos" with the right position to insert
286          * the value when it cannot be found. */
287         /* 如果值已经存在,那么直接返回 */
288         /* 如果不存在,那么设置*pos设置为新元素添加的位置 */
289         if (intsetSearch(is,value,&pos)) {
290             if (success) *success = 0;
291             return is;
292         }
293     
294         /* 扩张is,准备添加新元素 */
295         is = intsetResize(is,intrev32ifbe(is->length)+1);
296
297         /* 如果pos不是数组中最后一个元素, 那么对数组中的原有元素进行移动 */
298         if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
299     }
300     
301     /* 添加新元素 */
302     _intsetSet(is,pos,value);
303
304     /* 更新元素数量 */
305     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
306
307     return is;
308 }
309
310 /* Delete integer from intset */
311 /* 把value从inset中移除
312  *
313  * 移除成功将*success设置为1,失败则设置为0;
314 */
315 intset *intsetRemove(intset *is, int64_t value, int *success) {
316     uint8_t valenc = _intsetValueEncoding(value);
317     uint32_t pos;
318     if (success) *success = 0;
319
320     if (valenc encoding) && /* 编码方式匹配 */
321         intsetSearch(is,value,&pos))            /* 将位置保存到pos */
322     {
323         uint32_t len = intrev32ifbe(is->length);
324
325         /* We know we can delete */
326         if (success) *success = 1;
327
328         /* Overwrite value with tail and update length */
329         /* 如果pos不是is的最末尾,那么显示的删除它 */
330         /* 如果pos = (len - 1), 那么紧缩空间时值就会被自动抹除掉 */
331         if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
332
333         /* 紧缩空间, 并更新数量计数器 */
334         is = intsetResize(is,len-1);
335         is->length = intrev32ifbe(len-1);
336     }
337     return is;
338 }
339
340 /* Determine whether a value belongs to this set */
341 /* 查看value是否存在于is */
342 uint8_t intsetFind(intset *is, int64_t value) {
343     uint8_t valenc = _intsetValueEncoding(value);
344     return valenc encoding) && /* 编码方式匹配 */
345             intsetSearch(is,value,NULL); /* 查找value */
346 }
347
348 /* Return random member */
349 /* 随机返回一个intset里的元素 */
350 int64_t intsetRandom(intset *is) {
351     return _intsetGet(is,rand()%intrev32ifbe(is->length));
352 }
353
354 /* Sets the value to the value at the given position. When this position is
355  * out of range the function returns 0, when in range it returns 1. */
356 /* 将is中位置pos的值保存到*value当中,并返回1 */
357 /* 如果pos超过is的元素数量(out of range),则返回0 */
358 uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) {
359     if (pos < intrev32ifbe(is->length)) {
360         *value = _intsetGet(is,pos);
361         return 1;
362     }
363     return 0;
364 }
365
366 /* 返回intset的元素数量 */
367 /* Return intset length */
368 uint32_t intsetLen(intset *is) {
369     return intrev32ifbe(is->length);
370 }
371
372 /* Return intset blob size in bytes. */
373 /* 以字节形式返回intset占用的空间大小 */
374 size_t intsetBlobLen(intset *is) {
375     return sizeof(intset)+intrev32ifbe(is->length)*intrev32ifbe(is->encoding);
376 }
377
378 #ifdef INTSET_TEST_MAIN
379 #include
380
381 void intsetRepr(intset *is) {
382     int i;
383     for (i = 0; i < intrev32ifbe(is->length); i++) {
384         printf("%lld\n", (uint64_t)_intsetGet(is,i));
385     }
386     printf("\n");
387 }
388
389 void error(char *err) {
390     printf("%s\n", err);
391     exit(1);
392 }
393
394 void ok(void) {
395     printf("OK\n");
396 }
397
398 long long usec(void) {
399     struct timeval tv;
400     gettimeofday(&tv,NULL);
401     return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
402 }
403
404 #define assert(_e) ((_e)?(void)0:(_assert(#_e,__FILE__,__LINE__),exit(1)))
405 void _assert(char *estr, char *file, int line) {
406     printf("\n\n=== ASSERTION FAILED ===\n");
407     printf("==> %s:%d '%s' is not true\n",file,line,estr);
408 }
409
410 intset *createSet(int bits, int size) {
411     uint64_t mask = (1length)-1); i++) {
430         uint32_t encoding = intrev32ifbe(is->encoding);
431
432         if (encoding == INTSET_ENC_INT16) {
433             int16_t *i16 = (int16_t*)is->contents;
434             assert(i16 < i16[i+1]);
435         } else if (encoding == INTSET_ENC_INT32) {
436             int32_t *i32 = (int32_t*)is->contents;
437             assert(i32 < i32[i+1]);
438         } else {
439             int64_t *i64 = (int64_t*)is->contents;
440             assert(i64 < i64[i+1]);
441         }
442     }
443 }
444
445 int main(int argc, char **argv) {
446     uint8_t success;
447     int i;
448     intset *is;
449     sranddev();
450
451     printf("Value encodings: "); {
452         assert(_intsetValueEncoding(-32768) == INTSET_ENC_INT16);
453         assert(_intsetValueEncoding(+32767) == INTSET_ENC_INT16);
454         assert(_intsetValueEncoding(-32769) == INTSET_ENC_INT32);
455         assert(_intsetValueEncoding(+32768) == INTSET_ENC_INT32);
456         assert(_intsetValueEncoding(-2147483648) == INTSET_ENC_INT32);
457         assert(_intsetValueEncoding(+2147483647) == INTSET_ENC_INT32);
458         assert(_intsetValueEncoding(-2147483649) == INTSET_ENC_INT64);
459         assert(_intsetValueEncoding(+2147483648) == INTSET_ENC_INT64);
460         assert(_intsetValueEncoding(-9223372036854775808ull) == INTSET_ENC_INT64);
461         assert(_intsetValueEncoding(+9223372036854775807ull) == INTSET_ENC_INT64);
462         ok();
463     }
464
465     printf("Basic adding: "); {
466         is = intsetNew();
467         is = intsetAdd(is,5,&success); assert(success);
468         is = intsetAdd(is,6,&success); assert(success);
469         is = intsetAdd(is,4,&success); assert(success);
470         is = intsetAdd(is,4,&success); assert(!success);
471         ok();
472     }
473
474     printf("Large number of random adds: "); {
475         int inserts = 0;
476         is = intsetNew();
477         for (i = 0; i < 1024; i++) {
478             is = intsetAdd(is,rand()%0x800,&success);
479             if (success) inserts++;
480         }
481         assert(intrev32ifbe(is->length) == inserts);
482         checkConsistency(is);
483         ok();
484     }
485
486     printf("Upgrade from int16 to int32: "); {
487         is = intsetNew();
488         is = intsetAdd(is,32,NULL);
489         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16);
490         is = intsetAdd(is,65535,NULL);
491         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32);
492         assert(intsetFind(is,32));
493         assert(intsetFind(is,65535));
494         checkConsistency(is);
495
496         is = intsetNew();
497         is = intsetAdd(is,32,NULL);
498         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16);
499         is = intsetAdd(is,-65535,NULL);
500         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32);
501         assert(intsetFind(is,32));
502         assert(intsetFind(is,-65535));
503         checkConsistency(is);
504         ok();
505     }
506
507     printf("Upgrade from int16 to int64: "); {
508         is = intsetNew();
509         is = intsetAdd(is,32,NULL);
510         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16);
511         is = intsetAdd(is,4294967295,NULL);
512         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64);
513         assert(intsetFind(is,32));
514         assert(intsetFind(is,4294967295));
515         checkConsistency(is);
516
517         is = intsetNew();
518         is = intsetAdd(is,32,NULL);
519         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT16);
520         is = intsetAdd(is,-4294967295,NULL);
521         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64);
522         assert(intsetFind(is,32));
523         assert(intsetFind(is,-4294967295));
524         checkConsistency(is);
525         ok();
526     }
527
528     printf("Upgrade from int32 to int64: "); {
529         is = intsetNew();
530         is = intsetAdd(is,65535,NULL);
531         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32);
532         is = intsetAdd(is,4294967295,NULL);
533         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64);
534         assert(intsetFind(is,65535));
535         assert(intsetFind(is,4294967295));
536         checkConsistency(is);
537
538         is = intsetNew();
539         is = intsetAdd(is,65535,NULL);
540         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT32);
541         is = intsetAdd(is,-4294967295,NULL);
542         assert(intrev32ifbe(is->encoding) == INTSET_ENC_INT64);
543         assert(intsetFind(is,65535));
544         assert(intsetFind(is,-4294967295));
545         checkConsistency(is);
546         ok();
547     }
548
549     printf("Stress lookups: "); {
550         long num = 100000, size = 10000;
551         int i, bits = 20;
552         long long start;
553         is = createSet(bits,size);
554         checkConsistency(is);
555
556         start = usec();
557         for (i = 0; i < num; i++) intsetSearch(is,rand() % ((1