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 30unsigned int MDB_idl_logn = MDB_IDL_LOGN; 31unsigned int MDB_idl_db_size = 1 << MDB_IDL_LOGN; 32unsigned int MDB_idl_um_size = 1 << (MDB_IDL_LOGN+1); 33unsigned int MDB_idl_db_max = (1 << MDB_IDL_LOGN) - 1; 34unsigned 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 41static 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 54static 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 81void 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 92unsigned 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 150int 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 211static 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 268static char * 269mdb_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 283int 284mdb_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 414int 415mdb_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; 554put1: 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 */ 566fail: 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 575int 576mdb_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 */ 698fail: 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 */ 715int 716mdb_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; 785done: 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 */ 796int 797mdb_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) ) { 814over: 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 */ 869int 870mdb_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 919ID 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 948ID 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 */ 968int 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 */ 1007int 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 1063void 1064mdb_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 1142void 1143mdb_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 1233unsigned 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 1268int 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