1 /* OpenLDAP WiredTiger backend */
2 /* $OpenLDAP$ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2002-2021 The OpenLDAP Foundation.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
10 * Public License.
11 *
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
15 */
16 /* ACKNOWLEDGEMENTS:
17 * This work was developed by HAMANO Tsukasa <hamano@osstech.co.jp>
18 * based on back-bdb for inclusion in OpenLDAP Software.
19 * WiredTiger is a product of MongoDB Inc.
20 */
21
22 #include "portable.h"
23
24 #include <stdio.h>
25 #include <ac/string.h>
26
27 #include "back-wt.h"
28 #include "idl.h"
29
30 #define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
31 #define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
32 #define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
33
wt_idl_check(ID * ids)34 void wt_idl_check( ID *ids )
35 {
36 if( WT_IDL_IS_RANGE( ids ) ) {
37 assert( WT_IDL_RANGE_FIRST(ids) <= WT_IDL_RANGE_LAST(ids) );
38 } else {
39 ID i;
40 for( i=1; i < ids[0]; i++ ) {
41 assert( ids[i+1] > ids[i] );
42 }
43 }
44 }
45
wt_idl_dump(ID * ids)46 void wt_idl_dump( ID *ids )
47 {
48 if( WT_IDL_IS_RANGE( ids ) ) {
49 Debug( LDAP_DEBUG_ANY,
50 "IDL: range ( %ld - %ld )\n",
51 (long) WT_IDL_RANGE_FIRST( ids ),
52 (long) WT_IDL_RANGE_LAST( ids ) );
53
54 } else {
55 ID i;
56 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0] );
57
58 for( i=1; i<=ids[0]; i++ ) {
59 if( i % 16 == 1 ) {
60 Debug( LDAP_DEBUG_ANY, "\n" );
61 }
62 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i] );
63 }
64
65 Debug( LDAP_DEBUG_ANY, "\n" );
66 }
67
68 wt_idl_check( ids );
69 }
70
wt_idl_search(ID * ids,ID id)71 unsigned wt_idl_search( ID *ids, ID id )
72 {
73 #define IDL_BINARY_SEARCH 1
74 #ifdef IDL_BINARY_SEARCH
75 /*
76 * binary search of id in ids
77 * if found, returns position of id
78 * if not found, returns first position greater than id
79 */
80 unsigned base = 0;
81 unsigned cursor = 1;
82 int val = 0;
83 unsigned n = ids[0];
84
85 #if IDL_DEBUG > 0
86 idl_check( ids );
87 #endif
88
89 while( 0 < n ) {
90 unsigned pivot = n >> 1;
91 cursor = base + pivot + 1;
92 val = IDL_CMP( id, ids[cursor] );
93
94 if( val < 0 ) {
95 n = pivot;
96
97 } else if ( val > 0 ) {
98 base = cursor;
99 n -= pivot + 1;
100
101 } else {
102 return cursor;
103 }
104 }
105
106 if( val > 0 ) {
107 ++cursor;
108 }
109 return cursor;
110
111 #else
112 /* (reverse) linear search */
113 int i;
114
115 #if IDL_DEBUG > 0
116 idl_check( ids );
117 #endif
118
119 for( i=ids[0]; i; i-- ) {
120 if( id > ids[i] ) {
121 break;
122 }
123 }
124
125 return i+1;
126 #endif
127 }
128
wt_idl_insert(ID * ids,ID id)129 int wt_idl_insert( ID *ids, ID id )
130 {
131 unsigned x;
132
133 #if IDL_DEBUG > 1
134 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x );
135 idl_dump( ids );
136 #elif IDL_DEBUG > 0
137 wt_idl_check( ids );
138 #endif
139
140 if (WT_IDL_IS_RANGE( ids )) {
141 /* if already in range, treat as a dup */
142 if (id >= WT_IDL_RANGE_FIRST(ids) && id <= WT_IDL_RANGE_LAST(ids))
143 return -1;
144 if (id < WT_IDL_RANGE_FIRST(ids))
145 ids[1] = id;
146 else if (id > WT_IDL_RANGE_LAST(ids))
147 ids[2] = id;
148 return 0;
149 }
150
151 x = wt_idl_search( ids, id );
152 assert( x > 0 );
153
154 if( x < 1 ) {
155 /* internal error */
156 return -2;
157 }
158
159 if ( x <= ids[0] && ids[x] == id ) {
160 /* duplicate */
161 return -1;
162 }
163
164 if ( ++ids[0] >= WT_IDL_DB_MAX ) {
165 if( id < ids[1] ) {
166 ids[1] = id;
167 ids[2] = ids[ids[0]-1];
168 } else if ( ids[ids[0]-1] < id ) {
169 ids[2] = id;
170 } else {
171 ids[2] = ids[ids[0]-1];
172 }
173 ids[0] = NOID;
174
175 } else {
176 /* insert id */
177 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
178 ids[x] = id;
179 }
180
181 #if IDL_DEBUG > 1
182 wt_idl_dump( ids );
183 #elif IDL_DEBUG > 0
184 wt_idl_check( ids );
185 #endif
186
187 return 0;
188 }
189
wt_idl_delete(ID * ids,ID id)190 static int wt_idl_delete( ID *ids, ID id )
191 {
192 unsigned x;
193
194 #if IDL_DEBUG > 1
195 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x );
196 idl_dump( ids );
197 #elif IDL_DEBUG > 0
198 wt_idl_check( ids );
199 #endif
200
201 if (WT_IDL_IS_RANGE( ids )) {
202 /* If deleting a range boundary, adjust */
203 if ( ids[1] == id )
204 ids[1]++;
205 else if ( ids[2] == id )
206 ids[2]--;
207 /* deleting from inside a range is a no-op */
208
209 /* If the range has collapsed, re-adjust */
210 if ( ids[1] > ids[2] )
211 ids[0] = 0;
212 else if ( ids[1] == ids[2] )
213 ids[1] = 1;
214 return 0;
215 }
216
217 x = wt_idl_search( ids, id );
218 assert( x > 0 );
219
220 if( x <= 0 ) {
221 /* internal error */
222 return -2;
223 }
224
225 if( x > ids[0] || ids[x] != id ) {
226 /* not found */
227 return -1;
228
229 } else if ( --ids[0] == 0 ) {
230 if( x != 1 ) {
231 return -3;
232 }
233
234 } else {
235 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
236 }
237
238 #if IDL_DEBUG > 1
239 wt_idl_dump( ids );
240 #elif IDL_DEBUG > 0
241 wt_idl_check( ids );
242 #endif
243
244 return 0;
245 }
246
247 static char *
wt_show_key(char * buf,void * val,size_t len)248 wt_show_key(
249 char *buf,
250 void *val,
251 size_t len )
252 {
253 if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
254 unsigned char *c = val;
255 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
256 return buf;
257 } else {
258 return val;
259 }
260 }
261
262 /*
263 * idl_intersection - return a = a intersection b
264 */
265 int
wt_idl_intersection(ID * a,ID * b)266 wt_idl_intersection(
267 ID *a,
268 ID *b )
269 {
270 ID ida, idb;
271 ID idmax, idmin;
272 ID cursora = 0, cursorb = 0, cursorc;
273 int swap = 0;
274
275 if ( WT_IDL_IS_ZERO( a ) || WT_IDL_IS_ZERO( b ) ) {
276 a[0] = 0;
277 return 0;
278 }
279
280 idmin = IDL_MAX( WT_IDL_FIRST(a), WT_IDL_FIRST(b) );
281 idmax = IDL_MIN( WT_IDL_LAST(a), WT_IDL_LAST(b) );
282 if ( idmin > idmax ) {
283 a[0] = 0;
284 return 0;
285 } else if ( idmin == idmax ) {
286 a[0] = 1;
287 a[1] = idmin;
288 return 0;
289 }
290
291 if ( WT_IDL_IS_RANGE( a ) ) {
292 if ( WT_IDL_IS_RANGE(b) ) {
293 /* If both are ranges, just shrink the boundaries */
294 a[1] = idmin;
295 a[2] = idmax;
296 return 0;
297 } else {
298 /* Else swap so that b is the range, a is a list */
299 ID *tmp = a;
300 a = b;
301 b = tmp;
302 swap = 1;
303 }
304 }
305
306 /* If a range completely covers the list, the result is
307 * just the list. If idmin to idmax is contiguous, just
308 * turn it into a range.
309 */
310 if ( WT_IDL_IS_RANGE( b )
311 && WT_IDL_RANGE_FIRST( b ) <= WT_IDL_FIRST( a )
312 && WT_IDL_RANGE_LAST( b ) >= WT_IDL_LLAST( a ) ) {
313 if (idmax - idmin + 1 == a[0])
314 {
315 a[0] = NOID;
316 a[1] = idmin;
317 a[2] = idmax;
318 }
319 goto done;
320 }
321
322 /* Fine, do the intersection one element at a time.
323 * First advance to idmin in both IDLs.
324 */
325 cursora = cursorb = idmin;
326 ida = wt_idl_first( a, &cursora );
327 idb = wt_idl_first( b, &cursorb );
328 cursorc = 0;
329
330 while( ida <= idmax || idb <= idmax ) {
331 if( ida == idb ) {
332 a[++cursorc] = ida;
333 ida = wt_idl_next( a, &cursora );
334 idb = wt_idl_next( b, &cursorb );
335 } else if ( ida < idb ) {
336 ida = wt_idl_next( a, &cursora );
337 } else {
338 idb = wt_idl_next( b, &cursorb );
339 }
340 }
341 a[0] = cursorc;
342 done:
343 if (swap)
344 WT_IDL_CPY( b, a );
345
346 return 0;
347 }
348
349
350 /*
351 * idl_union - return a = a union b
352 */
353 int
wt_idl_union(ID * a,ID * b)354 wt_idl_union(
355 ID *a,
356 ID *b )
357 {
358 ID ida, idb;
359 ID cursora = 0, cursorb = 0, cursorc;
360
361 if ( WT_IDL_IS_ZERO( b ) ) {
362 return 0;
363 }
364
365 if ( WT_IDL_IS_ZERO( a ) ) {
366 WT_IDL_CPY( a, b );
367 return 0;
368 }
369
370 if ( WT_IDL_IS_RANGE( a ) || WT_IDL_IS_RANGE(b) ) {
371 over: ida = IDL_MIN( WT_IDL_FIRST(a), WT_IDL_FIRST(b) );
372 idb = IDL_MAX( WT_IDL_LAST(a), WT_IDL_LAST(b) );
373 a[0] = NOID;
374 a[1] = ida;
375 a[2] = idb;
376 return 0;
377 }
378
379 ida = wt_idl_first( a, &cursora );
380 idb = wt_idl_first( b, &cursorb );
381
382 cursorc = b[0];
383
384 /* The distinct elements of a are cat'd to b */
385 while( ida != NOID || idb != NOID ) {
386 if ( ida < idb ) {
387 if( ++cursorc > WT_IDL_UM_MAX ) {
388 goto over;
389 }
390 b[cursorc] = ida;
391 ida = wt_idl_next( a, &cursora );
392
393 } else {
394 if ( ida == idb )
395 ida = wt_idl_next( a, &cursora );
396 idb = wt_idl_next( b, &cursorb );
397 }
398 }
399
400 /* b is copied back to a in sorted order */
401 a[0] = cursorc;
402 cursora = 1;
403 cursorb = 1;
404 cursorc = b[0]+1;
405 while (cursorb <= b[0] || cursorc <= a[0]) {
406 if (cursorc > a[0])
407 idb = NOID;
408 else
409 idb = b[cursorc];
410 if (cursorb <= b[0] && b[cursorb] < idb)
411 a[cursora++] = b[cursorb++];
412 else {
413 a[cursora++] = idb;
414 cursorc++;
415 }
416 }
417
418 return 0;
419 }
420
421
422 #if 0
423 /*
424 * wt_idl_notin - return a intersection ~b (or a minus b)
425 */
426 int
427 wt_idl_notin(
428 ID *a,
429 ID *b,
430 ID *ids )
431 {
432 ID ida, idb;
433 ID cursora = 0, cursorb = 0;
434
435 if( WT_IDL_IS_ZERO( a ) ||
436 WT_IDL_IS_ZERO( b ) ||
437 WT_IDL_IS_RANGE( b ) )
438 {
439 WT_IDL_CPY( ids, a );
440 return 0;
441 }
442
443 if( WT_IDL_IS_RANGE( a ) ) {
444 WT_IDL_CPY( ids, a );
445 return 0;
446 }
447
448 ida = wt_idl_first( a, &cursora ),
449 idb = wt_idl_first( b, &cursorb );
450
451 ids[0] = 0;
452
453 while( ida != NOID ) {
454 if ( idb == NOID ) {
455 /* we could shortcut this */
456 ids[++ids[0]] = ida;
457 ida = wt_idl_next( a, &cursora );
458
459 } else if ( ida < idb ) {
460 ids[++ids[0]] = ida;
461 ida = wt_idl_next( a, &cursora );
462
463 } else if ( ida > idb ) {
464 idb = wt_idl_next( b, &cursorb );
465
466 } else {
467 ida = wt_idl_next( a, &cursora );
468 idb = wt_idl_next( b, &cursorb );
469 }
470 }
471
472 return 0;
473 }
474 #endif
475
wt_idl_first(ID * ids,ID * cursor)476 ID wt_idl_first( ID *ids, ID *cursor )
477 {
478 ID pos;
479
480 if ( ids[0] == 0 ) {
481 *cursor = NOID;
482 return NOID;
483 }
484
485 if ( WT_IDL_IS_RANGE( ids ) ) {
486 if( *cursor < ids[1] ) {
487 *cursor = ids[1];
488 }
489 return *cursor;
490 }
491
492 if ( *cursor == 0 )
493 pos = 1;
494 else
495 pos = wt_idl_search( ids, *cursor );
496
497 if( pos > ids[0] ) {
498 return NOID;
499 }
500
501 *cursor = pos;
502 return ids[pos];
503 }
504
wt_idl_next(ID * ids,ID * cursor)505 ID wt_idl_next( ID *ids, ID *cursor )
506 {
507 if ( WT_IDL_IS_RANGE( ids ) ) {
508 if( ids[2] < ++(*cursor) ) {
509 return NOID;
510 }
511 return *cursor;
512 }
513
514 if ( ++(*cursor) <= ids[0] ) {
515 return ids[*cursor];
516 }
517
518 return NOID;
519 }
520
521 /* Add one ID to an unsorted list. We ensure that the first element is the
522 * minimum and the last element is the maximum, for fast range compaction.
523 * this means IDLs up to length 3 are always sorted...
524 */
wt_idl_append_one(ID * ids,ID id)525 int wt_idl_append_one( ID *ids, ID id )
526 {
527 if (WT_IDL_IS_RANGE( ids )) {
528 /* if already in range, treat as a dup */
529 if (id >= WT_IDL_RANGE_FIRST(ids) && id <= WT_IDL_RANGE_LAST(ids))
530 return -1;
531 if (id < WT_IDL_RANGE_FIRST(ids))
532 ids[1] = id;
533 else if (id > WT_IDL_RANGE_LAST(ids))
534 ids[2] = id;
535 return 0;
536 }
537 if ( ids[0] ) {
538 ID tmp;
539
540 if (id < ids[1]) {
541 tmp = ids[1];
542 ids[1] = id;
543 id = tmp;
544 }
545 if ( ids[0] > 1 && id < ids[ids[0]] ) {
546 tmp = ids[ids[0]];
547 ids[ids[0]] = id;
548 id = tmp;
549 }
550 }
551 ids[0]++;
552 if ( ids[0] >= WT_IDL_UM_MAX ) {
553 ids[0] = NOID;
554 ids[2] = id;
555 } else {
556 ids[ids[0]] = id;
557 }
558 return 0;
559 }
560
561 /* Append sorted list b to sorted list a. The result is unsorted but
562 * a[1] is the min of the result and a[a[0]] is the max.
563 */
wt_idl_append(ID * a,ID * b)564 int wt_idl_append( ID *a, ID *b )
565 {
566 ID ida, idb, tmp, swap = 0;
567
568 if ( WT_IDL_IS_ZERO( b ) ) {
569 return 0;
570 }
571
572 if ( WT_IDL_IS_ZERO( a ) ) {
573 WT_IDL_CPY( a, b );
574 return 0;
575 }
576
577 ida = WT_IDL_LAST( a );
578 idb = WT_IDL_LAST( b );
579 if ( WT_IDL_IS_RANGE( a ) || WT_IDL_IS_RANGE(b) ||
580 a[0] + b[0] >= WT_IDL_UM_MAX ) {
581 a[2] = IDL_MAX( ida, idb );
582 a[1] = IDL_MIN( a[1], b[1] );
583 a[0] = NOID;
584 return 0;
585 }
586
587 if ( b[0] > 1 && ida > idb ) {
588 swap = idb;
589 a[a[0]] = idb;
590 b[b[0]] = ida;
591 }
592
593 if ( b[1] < a[1] ) {
594 tmp = a[1];
595 a[1] = b[1];
596 } else {
597 tmp = b[1];
598 }
599 a[0]++;
600 a[a[0]] = tmp;
601
602 if ( b[0] > 1 ) {
603 int i = b[0] - 1;
604 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
605 a[0] += i;
606 }
607 if ( swap ) {
608 b[b[0]] = swap;
609 }
610 return 0;
611 }
612
613 #if 1
614
615 /* Quicksort + Insertion sort for small arrays */
616
617 #define SMALL 8
618 #define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp
619
620 void
wt_idl_sort(ID * ids,ID * tmp)621 wt_idl_sort( ID *ids, ID *tmp )
622 {
623 int *istack = (int *)tmp; /* Private stack, not used by caller */
624 int i,j,k,l,ir,jstack;
625 ID a, itmp;
626
627 if ( WT_IDL_IS_RANGE( ids ))
628 return;
629
630 ir = ids[0];
631 l = 1;
632 jstack = 0;
633 for(;;) {
634 if (ir - l < SMALL) { /* Insertion sort */
635 for (j=l+1;j<=ir;j++) {
636 a = ids[j];
637 for (i=j-1;i>=1;i--) {
638 if (ids[i] <= a) break;
639 ids[i+1] = ids[i];
640 }
641 ids[i+1] = a;
642 }
643 if (jstack == 0) break;
644 ir = istack[jstack--];
645 l = istack[jstack--];
646 } else {
647 k = (l + ir) >> 1; /* Choose median of left, center, right */
648 SWAP(ids[k], ids[l+1]);
649 if (ids[l] > ids[ir]) {
650 SWAP(ids[l], ids[ir]);
651 }
652 if (ids[l+1] > ids[ir]) {
653 SWAP(ids[l+1], ids[ir]);
654 }
655 if (ids[l] > ids[l+1]) {
656 SWAP(ids[l], ids[l+1]);
657 }
658 i = l+1;
659 j = ir;
660 a = ids[l+1];
661 for(;;) {
662 do i++; while(ids[i] < a);
663 do j--; while(ids[j] > a);
664 if (j < i) break;
665 SWAP(ids[i],ids[j]);
666 }
667 ids[l+1] = ids[j];
668 ids[j] = a;
669 jstack += 2;
670 if (ir-i+1 >= j-l) {
671 istack[jstack] = ir;
672 istack[jstack-1] = i;
673 ir = j-1;
674 } else {
675 istack[jstack] = j-1;
676 istack[jstack-1] = l;
677 l = i;
678 }
679 }
680 }
681 }
682
683 #else
684
685 /* 8 bit Radix sort + insertion sort
686 *
687 * based on code from http://www.cubic.org/docs/radix.htm
688 * with improvements by ebackes@symas.com and hyc@symas.com
689 *
690 * This code is O(n) but has a relatively high constant factor. For lists
691 * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
692 * Much faster than quicksort for lists longer than ~100. Insertion
693 * sort is actually superior for lists <50.
694 */
695
696 #define BUCKETS (1<<8)
697 #define SMALL 50
698
699 void
wt_idl_sort(ID * ids,ID * tmp)700 wt_idl_sort( ID *ids, ID *tmp )
701 {
702 int count, soft_limit, phase = 0, size = ids[0];
703 ID *idls[2];
704 unsigned char *maxv = (unsigned char *)&ids[size];
705
706 if ( WT_IDL_IS_RANGE( ids ))
707 return;
708
709 /* Use insertion sort for small lists */
710 if ( size <= SMALL ) {
711 int i,j;
712 ID a;
713
714 for (j=1;j<=size;j++) {
715 a = ids[j];
716 for (i=j-1;i>=1;i--) {
717 if (ids[i] <= a) break;
718 ids[i+1] = ids[i];
719 }
720 ids[i+1] = a;
721 }
722 return;
723 }
724
725 tmp[0] = size;
726 idls[0] = ids;
727 idls[1] = tmp;
728
729 #if BYTE_ORDER == BIG_ENDIAN
730 for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
731 #else
732 for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
733 #endif
734
735 for (
736 #if BYTE_ORDER == BIG_ENDIAN
737 count = sizeof(ID)-1; count >= soft_limit; --count
738 #else
739 count = 0; count <= soft_limit; ++count
740 #endif
741 ) {
742 unsigned int num[BUCKETS], * np, n, sum;
743 int i;
744 ID *sp, *source, *dest;
745 unsigned char *bp, *source_start;
746
747 source = idls[phase]+1;
748 dest = idls[phase^1]+1;
749 source_start = ((unsigned char *) source) + count;
750
751 np = num;
752 for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
753
754 /* count occurrences of every byte value */
755 bp = source_start;
756 for ( i = size; i > 0; --i, bp += sizeof(ID) )
757 num[*bp]++;
758
759 /* transform count into index by summing elements and storing
760 * into same array
761 */
762 sum = 0;
763 np = num;
764 for ( i = BUCKETS; i > 0; --i ) {
765 n = *np;
766 *np++ = sum;
767 sum += n;
768 }
769
770 /* fill dest with the right values in the right place */
771 bp = source_start;
772 sp = source;
773 for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
774 np = num + *bp;
775 dest[*np] = *sp++;
776 ++(*np);
777 }
778 phase ^= 1;
779 }
780
781 /* copy back from temp if needed */
782 if ( phase ) {
783 ids++; tmp++;
784 for ( count = 0; count < size; ++count )
785 *ids++ = *tmp++;
786 }
787 }
788 #endif /* Quick vs Radix */
789
790