1 /* $NetBSD: idl.c,v 1.3 2021/08/14 16:15:00 christos Exp $ */
2
3 /* idl.c - ldap id list handling routines */
4 /* $OpenLDAP$ */
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 2000-2021 The OpenLDAP Foundation.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted only as authorized by the OpenLDAP
12 * Public License.
13 *
14 * A copy of this license is available in the file LICENSE in the
15 * top-level directory of the distribution or, alternatively, at
16 * <http://www.OpenLDAP.org/license.html>.
17 */
18
19 #include <sys/cdefs.h>
20 __RCSID("$NetBSD: idl.c,v 1.3 2021/08/14 16:15:00 christos Exp $");
21
22 #include "portable.h"
23
24 #include <stdio.h>
25 #include <ac/string.h>
26
27 #include "back-mdb.h"
28 #include "idl.h"
29
30 unsigned int MDB_idl_logn = MDB_IDL_LOGN;
31 unsigned int MDB_idl_db_size = 1 << MDB_IDL_LOGN;
32 unsigned int MDB_idl_um_size = 1 << (MDB_IDL_LOGN+1);
33 unsigned int MDB_idl_db_max = (1 << MDB_IDL_LOGN) - 1;
34 unsigned int MDB_idl_um_max = (1 << (MDB_IDL_LOGN+1)) - 1;
35
36 #define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
37 #define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
38 #define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
39
40 #if IDL_DEBUG > 0
idl_check(ID * ids)41 static void idl_check( ID *ids )
42 {
43 if( MDB_IDL_IS_RANGE( ids ) ) {
44 assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
45 } else {
46 ID i;
47 for( i=1; i < ids[0]; i++ ) {
48 assert( ids[i+1] > ids[i] );
49 }
50 }
51 }
52
53 #if IDL_DEBUG > 1
idl_dump(ID * ids)54 static void idl_dump( ID *ids )
55 {
56 if( MDB_IDL_IS_RANGE( ids ) ) {
57 Debug( LDAP_DEBUG_ANY,
58 "IDL: range ( %ld - %ld )\n",
59 (long) MDB_IDL_RANGE_FIRST( ids ),
60 (long) MDB_IDL_RANGE_LAST( ids ) );
61
62 } else {
63 ID i;
64 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0] );
65
66 for( i=1; i<=ids[0]; i++ ) {
67 if( i % 16 == 1 ) {
68 Debug( LDAP_DEBUG_ANY, "\n" );
69 }
70 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i] );
71 }
72
73 Debug( LDAP_DEBUG_ANY, "\n" );
74 }
75
76 idl_check( ids );
77 }
78 #endif /* IDL_DEBUG > 1 */
79 #endif /* IDL_DEBUG > 0 */
80
mdb_idl_reset()81 void mdb_idl_reset()
82 {
83 if ( !MDB_idl_logn )
84 MDB_idl_logn = MDB_IDL_LOGN;
85
86 MDB_idl_db_size = 1 << MDB_idl_logn;
87 MDB_idl_um_size = 1 << (MDB_idl_logn+1);
88 MDB_idl_db_max = MDB_idl_db_size - 1;
89 MDB_idl_um_max = MDB_idl_um_size - 1;
90 }
91
mdb_idl_search(ID * ids,ID id)92 unsigned mdb_idl_search( ID *ids, ID id )
93 {
94 #define IDL_BINARY_SEARCH 1
95 #ifdef IDL_BINARY_SEARCH
96 /*
97 * binary search of id in ids
98 * if found, returns position of id
99 * if not found, returns first position greater than id
100 */
101 unsigned base = 0;
102 unsigned cursor = 1;
103 int val = 0;
104 unsigned n = ids[0];
105
106 #if IDL_DEBUG > 0
107 idl_check( ids );
108 #endif
109
110 while( 0 < n ) {
111 unsigned pivot = n >> 1;
112 cursor = base + pivot + 1;
113 val = IDL_CMP( id, ids[cursor] );
114
115 if( val < 0 ) {
116 n = pivot;
117
118 } else if ( val > 0 ) {
119 base = cursor;
120 n -= pivot + 1;
121
122 } else {
123 return cursor;
124 }
125 }
126
127 if( val > 0 ) {
128 ++cursor;
129 }
130 return cursor;
131
132 #else
133 /* (reverse) linear search */
134 int i;
135
136 #if IDL_DEBUG > 0
137 idl_check( ids );
138 #endif
139
140 for( i=ids[0]; i; i-- ) {
141 if( id > ids[i] ) {
142 break;
143 }
144 }
145
146 return i+1;
147 #endif
148 }
149
mdb_idl_insert(ID * ids,ID id)150 int mdb_idl_insert( ID *ids, ID id )
151 {
152 unsigned x;
153
154 #if IDL_DEBUG > 1
155 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x );
156 idl_dump( ids );
157 #elif IDL_DEBUG > 0
158 idl_check( ids );
159 #endif
160
161 if (MDB_IDL_IS_RANGE( ids )) {
162 /* if already in range, treat as a dup */
163 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
164 return -1;
165 if (id < MDB_IDL_RANGE_FIRST(ids))
166 ids[1] = id;
167 else if (id > MDB_IDL_RANGE_LAST(ids))
168 ids[2] = id;
169 return 0;
170 }
171
172 x = mdb_idl_search( ids, id );
173 assert( x > 0 );
174
175 if( x < 1 ) {
176 /* internal error */
177 return -2;
178 }
179
180 if ( x <= ids[0] && ids[x] == id ) {
181 /* duplicate */
182 return -1;
183 }
184
185 if ( ++ids[0] >= MDB_idl_db_max ) {
186 if( id < ids[1] ) {
187 ids[1] = id;
188 ids[2] = ids[ids[0]-1];
189 } else if ( ids[ids[0]-1] < id ) {
190 ids[2] = id;
191 } else {
192 ids[2] = ids[ids[0]-1];
193 }
194 ids[0] = NOID;
195
196 } else {
197 /* insert id */
198 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
199 ids[x] = id;
200 }
201
202 #if IDL_DEBUG > 1
203 idl_dump( ids );
204 #elif IDL_DEBUG > 0
205 idl_check( ids );
206 #endif
207
208 return 0;
209 }
210
mdb_idl_delete(ID * ids,ID id)211 static int mdb_idl_delete( ID *ids, ID id )
212 {
213 unsigned x;
214
215 #if IDL_DEBUG > 1
216 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x );
217 idl_dump( ids );
218 #elif IDL_DEBUG > 0
219 idl_check( ids );
220 #endif
221
222 if (MDB_IDL_IS_RANGE( ids )) {
223 /* If deleting a range boundary, adjust */
224 if ( ids[1] == id )
225 ids[1]++;
226 else if ( ids[2] == id )
227 ids[2]--;
228 /* deleting from inside a range is a no-op */
229
230 /* If the range has collapsed, re-adjust */
231 if ( ids[1] > ids[2] )
232 ids[0] = 0;
233 else if ( ids[1] == ids[2] )
234 ids[1] = 1;
235 return 0;
236 }
237
238 x = mdb_idl_search( ids, id );
239 assert( x > 0 );
240
241 if( x <= 0 ) {
242 /* internal error */
243 return -2;
244 }
245
246 if( x > ids[0] || ids[x] != id ) {
247 /* not found */
248 return -1;
249
250 } else if ( --ids[0] == 0 ) {
251 if( x != 1 ) {
252 return -3;
253 }
254
255 } else {
256 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
257 }
258
259 #if IDL_DEBUG > 1
260 idl_dump( ids );
261 #elif IDL_DEBUG > 0
262 idl_check( ids );
263 #endif
264
265 return 0;
266 }
267
268 static char *
mdb_show_key(char * buf,void * val,size_t len)269 mdb_show_key(
270 char *buf,
271 void *val,
272 size_t len )
273 {
274 if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
275 unsigned char *c = val;
276 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
277 return buf;
278 } else {
279 return val;
280 }
281 }
282
283 int
mdb_idl_fetch_key(BackendDB * be,MDB_txn * txn,MDB_dbi dbi,MDB_val * key,ID * ids,MDB_cursor ** saved_cursor,int get_flag)284 mdb_idl_fetch_key(
285 BackendDB *be,
286 MDB_txn *txn,
287 MDB_dbi dbi,
288 MDB_val *key,
289 ID *ids,
290 MDB_cursor **saved_cursor,
291 int get_flag )
292 {
293 MDB_val data, key2, *kptr;
294 MDB_cursor *cursor;
295 ID *i;
296 size_t len;
297 int rc;
298 MDB_cursor_op opflag;
299
300 char keybuf[16];
301
302 Debug( LDAP_DEBUG_ARGS,
303 "mdb_idl_fetch_key: %s\n",
304 mdb_show_key( keybuf, key->mv_data, key->mv_size ) );
305
306 assert( ids != NULL );
307
308 if ( saved_cursor && *saved_cursor ) {
309 opflag = MDB_NEXT;
310 } else if ( get_flag == LDAP_FILTER_GE ) {
311 opflag = MDB_SET_RANGE;
312 } else if ( get_flag == LDAP_FILTER_LE ) {
313 opflag = MDB_FIRST;
314 } else {
315 opflag = MDB_SET;
316 }
317
318 /* If we're not reusing an existing cursor, get a new one */
319 if( opflag != MDB_NEXT ) {
320 rc = mdb_cursor_open( txn, dbi, &cursor );
321 if( rc != 0 ) {
322 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
323 "cursor failed: %s (%d)\n", mdb_strerror(rc), rc );
324 return rc;
325 }
326 } else {
327 cursor = *saved_cursor;
328 }
329
330 /* If this is a LE lookup, save original key so we can determine
331 * when to stop. If this is a GE lookup, save the key since it
332 * will be overwritten.
333 */
334 if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
335 key2.mv_data = keybuf;
336 key2.mv_size = key->mv_size;
337 AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
338 kptr = &key2;
339 } else {
340 kptr = key;
341 }
342 len = key->mv_size;
343 rc = mdb_cursor_get( cursor, kptr, &data, opflag );
344
345 /* skip presence key on range inequality lookups */
346 while (rc == 0 && kptr->mv_size != len) {
347 rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
348 }
349 /* If we're doing a LE compare and the new key is greater than
350 * our search key, we're done
351 */
352 if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
353 key->mv_data, key->mv_size ) > 0 ) {
354 rc = MDB_NOTFOUND;
355 }
356 if (rc == 0) {
357 i = ids+1;
358 rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
359 while (rc == 0) {
360 memcpy( i, data.mv_data, data.mv_size );
361 i += data.mv_size / sizeof(ID);
362 rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
363 }
364 if ( rc == MDB_NOTFOUND ) rc = 0;
365 ids[0] = i - &ids[1];
366 /* On disk, a range is denoted by 0 in the first element */
367 if (ids[1] == 0) {
368 if (ids[0] != MDB_IDL_RANGE_SIZE) {
369 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
370 "range size mismatch: expected %d, got %ld\n",
371 MDB_IDL_RANGE_SIZE, ids[0] );
372 mdb_cursor_close( cursor );
373 return -1;
374 }
375 MDB_IDL_RANGE( ids, ids[2], ids[3] );
376 }
377 data.mv_size = MDB_IDL_SIZEOF(ids);
378 }
379
380 if ( saved_cursor && rc == 0 ) {
381 if ( !*saved_cursor )
382 *saved_cursor = cursor;
383 }
384 else
385 mdb_cursor_close( cursor );
386
387 if( rc == MDB_NOTFOUND ) {
388 return rc;
389
390 } else if( rc != 0 ) {
391 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
392 "get failed: %s (%d)\n",
393 mdb_strerror(rc), rc );
394 return rc;
395
396 } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
397 /* size not multiple of ID size */
398 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
399 "odd size: expected %ld multiple, got %ld\n",
400 (long) sizeof( ID ), (long) data.mv_size );
401 return -1;
402
403 } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
404 /* size mismatch */
405 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
406 "get size mismatch: expected %ld, got %ld\n",
407 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size );
408 return -1;
409 }
410
411 return rc;
412 }
413
414 int
mdb_idl_insert_keys(BackendDB * be,MDB_cursor * cursor,struct berval * keys,ID id)415 mdb_idl_insert_keys(
416 BackendDB *be,
417 MDB_cursor *cursor,
418 struct berval *keys,
419 ID id )
420 {
421 struct mdb_info *mdb = be->be_private;
422 MDB_val key, data;
423 ID lo, hi, *i;
424 char *err;
425 int rc = 0, k;
426 unsigned int flag = MDB_NODUPDATA;
427 #ifndef MISALIGNED_OK
428 int kbuf[2];
429 #endif
430
431 {
432 char buf[16];
433 Debug( LDAP_DEBUG_ARGS,
434 "mdb_idl_insert_keys: %lx %s\n",
435 (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ) );
436 }
437
438 assert( id != NOID );
439
440 #ifndef MISALIGNED_OK
441 if (keys[0].bv_len & ALIGNER)
442 kbuf[1] = 0;
443 #endif
444 for ( k=0; keys[k].bv_val; k++ ) {
445 /* Fetch the first data item for this key, to see if it
446 * exists and if it's a range.
447 */
448 #ifndef MISALIGNED_OK
449 if (keys[k].bv_len & ALIGNER) {
450 key.mv_size = sizeof(kbuf);
451 key.mv_data = kbuf;
452 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
453 } else
454 #endif
455 {
456 key.mv_size = keys[k].bv_len;
457 key.mv_data = keys[k].bv_val;
458 }
459 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
460 err = "c_get";
461 if ( rc == 0 ) {
462 i = data.mv_data;
463 memcpy(&lo, data.mv_data, sizeof(ID));
464 if ( lo != 0 ) {
465 /* not a range, count the number of items */
466 size_t count;
467 rc = mdb_cursor_count( cursor, &count );
468 if ( rc != 0 ) {
469 err = "c_count";
470 goto fail;
471 }
472 if ( count >= MDB_idl_db_max ) {
473 /* No room, convert to a range */
474 lo = *i;
475 rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
476 if ( rc != 0 && rc != MDB_NOTFOUND ) {
477 err = "c_get last_dup";
478 goto fail;
479 }
480 i = data.mv_data;
481 hi = *i;
482 /* Update hi/lo if needed */
483 if ( id < lo ) {
484 lo = id;
485 } else if ( id > hi ) {
486 hi = id;
487 }
488 /* delete the old key */
489 rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
490 if ( rc != 0 ) {
491 err = "c_del dups";
492 goto fail;
493 }
494 /* Store the range */
495 data.mv_size = sizeof(ID);
496 data.mv_data = &id;
497 id = 0;
498 rc = mdb_cursor_put( cursor, &key, &data, 0 );
499 if ( rc != 0 ) {
500 err = "c_put range";
501 goto fail;
502 }
503 id = lo;
504 rc = mdb_cursor_put( cursor, &key, &data, 0 );
505 if ( rc != 0 ) {
506 err = "c_put lo";
507 goto fail;
508 }
509 id = hi;
510 rc = mdb_cursor_put( cursor, &key, &data, 0 );
511 if ( rc != 0 ) {
512 err = "c_put hi";
513 goto fail;
514 }
515 } else {
516 /* There's room, just store it */
517 if (id == mdb->mi_nextid)
518 flag |= MDB_APPENDDUP;
519 goto put1;
520 }
521 } else {
522 /* It's a range, see if we need to rewrite
523 * the boundaries
524 */
525 lo = i[1];
526 hi = i[2];
527 if ( id < lo || id > hi ) {
528 /* position on lo */
529 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
530 if ( rc != 0 ) {
531 err = "c_get lo";
532 goto fail;
533 }
534 if ( id > hi ) {
535 /* position on hi */
536 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
537 if ( rc != 0 ) {
538 err = "c_get hi";
539 goto fail;
540 }
541 }
542 data.mv_size = sizeof(ID);
543 data.mv_data = &id;
544 /* Replace the current lo/hi */
545 rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
546 if ( rc != 0 ) {
547 err = "c_put lo/hi";
548 goto fail;
549 }
550 }
551 }
552 } else if ( rc == MDB_NOTFOUND ) {
553 flag &= ~MDB_APPENDDUP;
554 put1: data.mv_data = &id;
555 data.mv_size = sizeof(ID);
556 rc = mdb_cursor_put( cursor, &key, &data, flag );
557 /* Don't worry if it's already there */
558 if ( rc == MDB_KEYEXIST )
559 rc = 0;
560 if ( rc ) {
561 err = "c_put id";
562 goto fail;
563 }
564 } else {
565 /* initial c_get failed, nothing was done */
566 fail:
567 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
568 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
569 break;
570 }
571 }
572 return rc;
573 }
574
575 int
mdb_idl_delete_keys(BackendDB * be,MDB_cursor * cursor,struct berval * keys,ID id)576 mdb_idl_delete_keys(
577 BackendDB *be,
578 MDB_cursor *cursor,
579 struct berval *keys,
580 ID id )
581 {
582 int rc = 0, k;
583 MDB_val key, data;
584 ID lo, hi, tmp, *i;
585 char *err;
586 #ifndef MISALIGNED_OK
587 int kbuf[2];
588 #endif
589
590 {
591 char buf[16];
592 Debug( LDAP_DEBUG_ARGS,
593 "mdb_idl_delete_keys: %lx %s\n",
594 (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ) );
595 }
596 assert( id != NOID );
597
598 #ifndef MISALIGNED_OK
599 if (keys[0].bv_len & ALIGNER)
600 kbuf[1] = 0;
601 #endif
602 for ( k=0; keys[k].bv_val; k++) {
603 /* Fetch the first data item for this key, to see if it
604 * exists and if it's a range.
605 */
606 #ifndef MISALIGNED_OK
607 if (keys[k].bv_len & ALIGNER) {
608 key.mv_size = sizeof(kbuf);
609 key.mv_data = kbuf;
610 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
611 } else
612 #endif
613 {
614 key.mv_size = keys[k].bv_len;
615 key.mv_data = keys[k].bv_val;
616 }
617 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
618 err = "c_get";
619 if ( rc == 0 ) {
620 memcpy( &tmp, data.mv_data, sizeof(ID) );
621 i = data.mv_data;
622 if ( tmp != 0 ) {
623 /* Not a range, just delete it */
624 data.mv_data = &id;
625 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
626 if ( rc != 0 ) {
627 err = "c_get id";
628 goto fail;
629 }
630 rc = mdb_cursor_del( cursor, 0 );
631 if ( rc != 0 ) {
632 err = "c_del id";
633 goto fail;
634 }
635 } else {
636 /* It's a range, see if we need to rewrite
637 * the boundaries
638 */
639 lo = i[1];
640 hi = i[2];
641 if ( id == lo || id == hi ) {
642 ID lo2 = lo, hi2 = hi;
643 if ( id == lo ) {
644 lo2++;
645 } else if ( id == hi ) {
646 hi2--;
647 }
648 if ( lo2 >= hi2 ) {
649 /* The range has collapsed... */
650 /* delete the range marker */
651 rc = mdb_cursor_del( cursor, 0 );
652 if ( rc != 0 ) {
653 err = "c_del dup1";
654 goto fail;
655 }
656 /* skip past deleted marker */
657 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
658 if ( rc != 0 ) {
659 err = "c_get dup1";
660 goto fail;
661 }
662 /* delete the requested id */
663 if ( id == hi ) {
664 /* skip lo */
665 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
666 if ( rc != 0 ) {
667 err = "c_get dup2";
668 goto fail;
669 }
670 }
671 rc = mdb_cursor_del( cursor, 0 );
672 if ( rc != 0 ) {
673 err = "c_del dup2";
674 goto fail;
675 }
676 } else {
677 /* position on lo */
678 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
679 if ( id == lo )
680 data.mv_data = &lo2;
681 else {
682 /* position on hi */
683 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
684 data.mv_data = &hi2;
685 }
686 /* Replace the current lo/hi */
687 data.mv_size = sizeof(ID);
688 rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
689 if ( rc != 0 ) {
690 err = "c_put lo/hi";
691 goto fail;
692 }
693 }
694 }
695 }
696 } else {
697 /* initial c_get failed, nothing was done */
698 fail:
699 if ( rc == MDB_NOTFOUND )
700 rc = 0;
701 if ( rc ) {
702 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
703 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
704 break;
705 }
706 }
707 }
708 return rc;
709 }
710
711
712 /*
713 * idl_intersection - return a = a intersection b
714 */
715 int
mdb_idl_intersection(ID * a,ID * b)716 mdb_idl_intersection(
717 ID *a,
718 ID *b )
719 {
720 ID ida, idb;
721 ID idmax, idmin;
722 ID cursora = 0, cursorb = 0, cursorc;
723 int swap = 0;
724
725 if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
726 a[0] = 0;
727 return 0;
728 }
729
730 idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
731 idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
732 if ( idmin > idmax ) {
733 a[0] = 0;
734 return 0;
735 } else if ( idmin == idmax ) {
736 a[0] = 1;
737 a[1] = idmin;
738 return 0;
739 }
740
741 if ( MDB_IDL_IS_RANGE( a ) ) {
742 if ( MDB_IDL_IS_RANGE(b) ) {
743 /* If both are ranges, just shrink the boundaries */
744 a[1] = idmin;
745 a[2] = idmax;
746 return 0;
747 } else {
748 /* Else swap so that b is the range, a is a list */
749 ID *tmp = a;
750 a = b;
751 b = tmp;
752 swap = 1;
753 }
754 }
755
756 /* If a range completely covers the list, the result is
757 * just the list.
758 */
759 if ( MDB_IDL_IS_RANGE( b )
760 && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a )
761 && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) {
762 goto done;
763 }
764
765 /* Fine, do the intersection one element at a time.
766 * First advance to idmin in both IDLs.
767 */
768 cursora = cursorb = idmin;
769 ida = mdb_idl_first( a, &cursora );
770 idb = mdb_idl_first( b, &cursorb );
771 cursorc = 0;
772
773 while( ida <= idmax || idb <= idmax ) {
774 if( ida == idb ) {
775 a[++cursorc] = ida;
776 ida = mdb_idl_next( a, &cursora );
777 idb = mdb_idl_next( b, &cursorb );
778 } else if ( ida < idb ) {
779 ida = mdb_idl_next( a, &cursora );
780 } else {
781 idb = mdb_idl_next( b, &cursorb );
782 }
783 }
784 a[0] = cursorc;
785 done:
786 if (swap)
787 MDB_IDL_CPY( b, a );
788
789 return 0;
790 }
791
792
793 /*
794 * idl_union - return a = a union b
795 */
796 int
mdb_idl_union(ID * a,ID * b)797 mdb_idl_union(
798 ID *a,
799 ID *b )
800 {
801 ID ida, idb;
802 ID cursora = 0, cursorb = 0, cursorc;
803
804 if ( MDB_IDL_IS_ZERO( b ) ) {
805 return 0;
806 }
807
808 if ( MDB_IDL_IS_ZERO( a ) ) {
809 MDB_IDL_CPY( a, b );
810 return 0;
811 }
812
813 if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
814 over: ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
815 idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
816 a[0] = NOID;
817 a[1] = ida;
818 a[2] = idb;
819 return 0;
820 }
821
822 ida = mdb_idl_first( a, &cursora );
823 idb = mdb_idl_first( b, &cursorb );
824
825 cursorc = b[0];
826
827 /* The distinct elements of a are cat'd to b */
828 while( ida != NOID || idb != NOID ) {
829 if ( ida < idb ) {
830 if( ++cursorc > MDB_idl_um_max ) {
831 goto over;
832 }
833 b[cursorc] = ida;
834 ida = mdb_idl_next( a, &cursora );
835
836 } else {
837 if ( ida == idb )
838 ida = mdb_idl_next( a, &cursora );
839 idb = mdb_idl_next( b, &cursorb );
840 }
841 }
842
843 /* b is copied back to a in sorted order */
844 a[0] = cursorc;
845 cursora = 1;
846 cursorb = 1;
847 cursorc = b[0]+1;
848 while (cursorb <= b[0] || cursorc <= a[0]) {
849 if (cursorc > a[0])
850 idb = NOID;
851 else
852 idb = b[cursorc];
853 if (cursorb <= b[0] && b[cursorb] < idb)
854 a[cursora++] = b[cursorb++];
855 else {
856 a[cursora++] = idb;
857 cursorc++;
858 }
859 }
860
861 return 0;
862 }
863
864
865 #if 0
866 /*
867 * mdb_idl_notin - return a intersection ~b (or a minus b)
868 */
869 int
870 mdb_idl_notin(
871 ID *a,
872 ID *b,
873 ID *ids )
874 {
875 ID ida, idb;
876 ID cursora = 0, cursorb = 0;
877
878 if( MDB_IDL_IS_ZERO( a ) ||
879 MDB_IDL_IS_ZERO( b ) ||
880 MDB_IDL_IS_RANGE( b ) )
881 {
882 MDB_IDL_CPY( ids, a );
883 return 0;
884 }
885
886 if( MDB_IDL_IS_RANGE( a ) ) {
887 MDB_IDL_CPY( ids, a );
888 return 0;
889 }
890
891 ida = mdb_idl_first( a, &cursora ),
892 idb = mdb_idl_first( b, &cursorb );
893
894 ids[0] = 0;
895
896 while( ida != NOID ) {
897 if ( idb == NOID ) {
898 /* we could shortcut this */
899 ids[++ids[0]] = ida;
900 ida = mdb_idl_next( a, &cursora );
901
902 } else if ( ida < idb ) {
903 ids[++ids[0]] = ida;
904 ida = mdb_idl_next( a, &cursora );
905
906 } else if ( ida > idb ) {
907 idb = mdb_idl_next( b, &cursorb );
908
909 } else {
910 ida = mdb_idl_next( a, &cursora );
911 idb = mdb_idl_next( b, &cursorb );
912 }
913 }
914
915 return 0;
916 }
917 #endif
918
mdb_idl_first(ID * ids,ID * cursor)919 ID mdb_idl_first( ID *ids, ID *cursor )
920 {
921 ID pos;
922
923 if ( ids[0] == 0 ) {
924 *cursor = NOID;
925 return NOID;
926 }
927
928 if ( MDB_IDL_IS_RANGE( ids ) ) {
929 if( *cursor < ids[1] ) {
930 *cursor = ids[1];
931 }
932 return *cursor;
933 }
934
935 if ( *cursor == 0 )
936 pos = 1;
937 else
938 pos = mdb_idl_search( ids, *cursor );
939
940 if( pos > ids[0] ) {
941 return NOID;
942 }
943
944 *cursor = pos;
945 return ids[pos];
946 }
947
mdb_idl_next(ID * ids,ID * cursor)948 ID mdb_idl_next( ID *ids, ID *cursor )
949 {
950 if ( MDB_IDL_IS_RANGE( ids ) ) {
951 if( ids[2] < ++(*cursor) ) {
952 return NOID;
953 }
954 return *cursor;
955 }
956
957 if ( ++(*cursor) <= ids[0] ) {
958 return ids[*cursor];
959 }
960
961 return NOID;
962 }
963
964 /* Add one ID to an unsorted list. We ensure that the first element is the
965 * minimum and the last element is the maximum, for fast range compaction.
966 * this means IDLs up to length 3 are always sorted...
967 */
mdb_idl_append_one(ID * ids,ID id)968 int mdb_idl_append_one( ID *ids, ID id )
969 {
970 if (MDB_IDL_IS_RANGE( ids )) {
971 /* if already in range, treat as a dup */
972 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
973 return -1;
974 if (id < MDB_IDL_RANGE_FIRST(ids))
975 ids[1] = id;
976 else if (id > MDB_IDL_RANGE_LAST(ids))
977 ids[2] = id;
978 return 0;
979 }
980 if ( ids[0] ) {
981 ID tmp;
982
983 if (id < ids[1]) {
984 tmp = ids[1];
985 ids[1] = id;
986 id = tmp;
987 }
988 if ( ids[0] > 1 && id < ids[ids[0]] ) {
989 tmp = ids[ids[0]];
990 ids[ids[0]] = id;
991 id = tmp;
992 }
993 }
994 ids[0]++;
995 if ( ids[0] >= MDB_idl_um_max ) {
996 ids[0] = NOID;
997 ids[2] = id;
998 } else {
999 ids[ids[0]] = id;
1000 }
1001 return 0;
1002 }
1003
1004 /* Append sorted list b to sorted list a. The result is unsorted but
1005 * a[1] is the min of the result and a[a[0]] is the max.
1006 */
mdb_idl_append(ID * a,ID * b)1007 int mdb_idl_append( ID *a, ID *b )
1008 {
1009 ID ida, idb, tmp, swap = 0;
1010
1011 if ( MDB_IDL_IS_ZERO( b ) ) {
1012 return 0;
1013 }
1014
1015 if ( MDB_IDL_IS_ZERO( a ) ) {
1016 MDB_IDL_CPY( a, b );
1017 return 0;
1018 }
1019
1020 ida = MDB_IDL_LAST( a );
1021 idb = MDB_IDL_LAST( b );
1022 if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
1023 a[0] + b[0] >= MDB_idl_um_max ) {
1024 a[2] = IDL_MAX( ida, idb );
1025 a[1] = IDL_MIN( a[1], b[1] );
1026 a[0] = NOID;
1027 return 0;
1028 }
1029
1030 if ( b[0] > 1 && ida > idb ) {
1031 swap = idb;
1032 a[a[0]] = idb;
1033 b[b[0]] = ida;
1034 }
1035
1036 if ( b[1] < a[1] ) {
1037 tmp = a[1];
1038 a[1] = b[1];
1039 } else {
1040 tmp = b[1];
1041 }
1042 a[0]++;
1043 a[a[0]] = tmp;
1044
1045 if ( b[0] > 1 ) {
1046 int i = b[0] - 1;
1047 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
1048 a[0] += i;
1049 }
1050 if ( swap ) {
1051 b[b[0]] = swap;
1052 }
1053 return 0;
1054 }
1055
1056 #if 1
1057
1058 /* Quicksort + Insertion sort for small arrays */
1059
1060 #define SMALL 8
1061 #define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp
1062
1063 void
mdb_idl_sort(ID * ids,ID * tmp)1064 mdb_idl_sort( ID *ids, ID *tmp )
1065 {
1066 int *istack = (int *)tmp; /* Private stack, not used by caller */
1067 int i,j,k,l,ir,jstack;
1068 ID a, itmp;
1069
1070 if ( MDB_IDL_IS_RANGE( ids ))
1071 return;
1072
1073 ir = ids[0];
1074 l = 1;
1075 jstack = 0;
1076 for(;;) {
1077 if (ir - l < SMALL) { /* Insertion sort */
1078 for (j=l+1;j<=ir;j++) {
1079 a = ids[j];
1080 for (i=j-1;i>=1;i--) {
1081 if (ids[i] <= a) break;
1082 ids[i+1] = ids[i];
1083 }
1084 ids[i+1] = a;
1085 }
1086 if (jstack == 0) break;
1087 ir = istack[jstack--];
1088 l = istack[jstack--];
1089 } else {
1090 k = (l + ir) >> 1; /* Choose median of left, center, right */
1091 SWAP(ids[k], ids[l+1]);
1092 if (ids[l] > ids[ir]) {
1093 SWAP(ids[l], ids[ir]);
1094 }
1095 if (ids[l+1] > ids[ir]) {
1096 SWAP(ids[l+1], ids[ir]);
1097 }
1098 if (ids[l] > ids[l+1]) {
1099 SWAP(ids[l], ids[l+1]);
1100 }
1101 i = l+1;
1102 j = ir;
1103 a = ids[l+1];
1104 for(;;) {
1105 do i++; while(ids[i] < a);
1106 do j--; while(ids[j] > a);
1107 if (j < i) break;
1108 SWAP(ids[i],ids[j]);
1109 }
1110 ids[l+1] = ids[j];
1111 ids[j] = a;
1112 jstack += 2;
1113 if (ir-i+1 >= j-l) {
1114 istack[jstack] = ir;
1115 istack[jstack-1] = i;
1116 ir = j-1;
1117 } else {
1118 istack[jstack] = j-1;
1119 istack[jstack-1] = l;
1120 l = i;
1121 }
1122 }
1123 }
1124 }
1125
1126 #else
1127
1128 /* 8 bit Radix sort + insertion sort
1129 *
1130 * based on code from http://www.cubic.org/docs/radix.htm
1131 * with improvements by ebackes@symas.com and hyc@symas.com
1132 *
1133 * This code is O(n) but has a relatively high constant factor. For lists
1134 * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1135 * Much faster than quicksort for lists longer than ~100. Insertion
1136 * sort is actually superior for lists <50.
1137 */
1138
1139 #define BUCKETS (1<<8)
1140 #define SMALL 50
1141
1142 void
mdb_idl_sort(ID * ids,ID * tmp)1143 mdb_idl_sort( ID *ids, ID *tmp )
1144 {
1145 int count, soft_limit, phase = 0, size = ids[0];
1146 ID *idls[2];
1147 unsigned char *maxv = (unsigned char *)&ids[size];
1148
1149 if ( MDB_IDL_IS_RANGE( ids ))
1150 return;
1151
1152 /* Use insertion sort for small lists */
1153 if ( size <= SMALL ) {
1154 int i,j;
1155 ID a;
1156
1157 for (j=1;j<=size;j++) {
1158 a = ids[j];
1159 for (i=j-1;i>=1;i--) {
1160 if (ids[i] <= a) break;
1161 ids[i+1] = ids[i];
1162 }
1163 ids[i+1] = a;
1164 }
1165 return;
1166 }
1167
1168 tmp[0] = size;
1169 idls[0] = ids;
1170 idls[1] = tmp;
1171
1172 #if BYTE_ORDER == BIG_ENDIAN
1173 for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1174 #else
1175 for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1176 #endif
1177
1178 for (
1179 #if BYTE_ORDER == BIG_ENDIAN
1180 count = sizeof(ID)-1; count >= soft_limit; --count
1181 #else
1182 count = 0; count <= soft_limit; ++count
1183 #endif
1184 ) {
1185 unsigned int num[BUCKETS], * np, n, sum;
1186 int i;
1187 ID *sp, *source, *dest;
1188 unsigned char *bp, *source_start;
1189
1190 source = idls[phase]+1;
1191 dest = idls[phase^1]+1;
1192 source_start = ((unsigned char *) source) + count;
1193
1194 np = num;
1195 for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1196
1197 /* count occurrences of every byte value */
1198 bp = source_start;
1199 for ( i = size; i > 0; --i, bp += sizeof(ID) )
1200 num[*bp]++;
1201
1202 /* transform count into index by summing elements and storing
1203 * into same array
1204 */
1205 sum = 0;
1206 np = num;
1207 for ( i = BUCKETS; i > 0; --i ) {
1208 n = *np;
1209 *np++ = sum;
1210 sum += n;
1211 }
1212
1213 /* fill dest with the right values in the right place */
1214 bp = source_start;
1215 sp = source;
1216 for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1217 np = num + *bp;
1218 dest[*np] = *sp++;
1219 ++(*np);
1220 }
1221 phase ^= 1;
1222 }
1223
1224 /* copy back from temp if needed */
1225 if ( phase ) {
1226 ids++; tmp++;
1227 for ( count = 0; count < size; ++count )
1228 *ids++ = *tmp++;
1229 }
1230 }
1231 #endif /* Quick vs Radix */
1232
mdb_id2l_search(ID2L ids,ID id)1233 unsigned mdb_id2l_search( ID2L ids, ID id )
1234 {
1235 /*
1236 * binary search of id in ids
1237 * if found, returns position of id
1238 * if not found, returns first position greater than id
1239 */
1240 unsigned base = 0;
1241 unsigned cursor = 1;
1242 int val = 0;
1243 unsigned n = ids[0].mid;
1244
1245 while( 0 < n ) {
1246 unsigned pivot = n >> 1;
1247 cursor = base + pivot + 1;
1248 val = IDL_CMP( id, ids[cursor].mid );
1249
1250 if( val < 0 ) {
1251 n = pivot;
1252
1253 } else if ( val > 0 ) {
1254 base = cursor;
1255 n -= pivot + 1;
1256
1257 } else {
1258 return cursor;
1259 }
1260 }
1261
1262 if( val > 0 ) {
1263 ++cursor;
1264 }
1265 return cursor;
1266 }
1267
mdb_id2l_insert(ID2L ids,ID2 * id)1268 int mdb_id2l_insert( ID2L ids, ID2 *id )
1269 {
1270 unsigned x, i;
1271
1272 x = mdb_id2l_search( ids, id->mid );
1273 assert( x > 0 );
1274
1275 if( x < 1 ) {
1276 /* internal error */
1277 return -2;
1278 }
1279
1280 if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
1281 /* duplicate */
1282 return -1;
1283 }
1284
1285 if ( ids[0].mid >= MDB_idl_um_max ) {
1286 /* too big */
1287 return -2;
1288
1289 } else {
1290 /* insert id */
1291 ids[0].mid++;
1292 for (i=ids[0].mid; i>x; i--)
1293 ids[i] = ids[i-1];
1294 ids[x] = *id;
1295 }
1296
1297 return 0;
1298 }
1299