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