git.sur5r.net Git - openldap/blob - servers/slapd/back-mdb/idl.c

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