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_key(
 395         BackendDB       *be,
 396         MDB_txn         *txn,
 397         MDB_dbi         dbi,
 398         MDB_val         *key,
 399         ID                      id )
 400 {
 401         MDB_cursor *cursor;
 402         MDB_val data;
 403         ID lo, hi, *i;
 404         char *err;
 405         int     rc;
 406
 407         {
 408                 char buf[16];
 409                 Debug( LDAP_DEBUG_ARGS,
 410                         "mdb_idl_insert_key: %lx %s\n",
 411                         (long) id, mdb_show_key( key, buf ), 0 );
 412         }
 413
 414         assert( id != NOID );
 415
 416         rc = mdb_cursor_open( txn, dbi, &cursor );
 417         if ( rc != 0 ) {
 418                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_key: "
 419                         "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
 420                 return rc;
 421         }
 422         /* Fetch the first data item for this key, to see if it
 423          * exists and if it's a range.
 424          */
 425         rc = mdb_cursor_get( cursor, key, &data, MDB_SET );
 426         err = "c_get";
 427         if ( rc == 0 ) {
 428                 i = data.mv_data;
 429                 memcpy(&lo, data.mv_data, sizeof(ID));
 430                 if ( lo != 0 ) {
 431                         /* not a range, count the number of items */
 432                         unsigned long count;
 433                         rc = mdb_cursor_count( cursor, &count );
 434                         if ( rc != 0 ) {
 435                                 err = "c_count";
 436                                 goto fail;
 437                         }
 438                         if ( count >= MDB_IDL_DB_MAX ) {
 439                         /* No room, convert to a range */
 440                                 MDB_val key2;
 441
 442                                 lo = *i;
 443                                 rc = mdb_cursor_get( cursor, &key2, &data, MDB_NEXT_NODUP );
 444                                 if ( rc != 0 && rc != MDB_NOTFOUND ) {
 445                                         err = "c_get next_nodup";
 446                                         goto fail;
 447                                 }
 448                                 key2 = *key;
 449                                 if ( rc == MDB_NOTFOUND ) {
 450                                         rc = mdb_cursor_get( cursor, &key2, &data, MDB_LAST );
 451                                         if ( rc != 0 ) {
 452                                                 err = "c_get last";
 453                                                 goto fail;
 454                                         }
 455                                 } else {
 456                                         rc = mdb_cursor_get( cursor, &key2, &data, MDB_PREV );
 457                                         if ( rc != 0 ) {
 458                                                 err = "c_get prev";
 459                                                 goto fail;
 460                                         }
 461                                 }
 462                                 i = data.mv_data;
 463                                 hi = *i;
 464                                 /* Update hi/lo if needed */
 465                                 if ( id < lo ) {
 466                                         lo = id;
 467                                 } else if ( id > hi ) {
 468                                         hi = id;
 469                                 }
 470                                 /* delete the old key */
 471                                 rc = mdb_del( txn, dbi, &key2, NULL );
 472                                 if ( rc != 0 ) {
 473                                         err = "mdb_del";
 474                                         goto fail;
 475                                 }
 476                                 /* Store the range */
 477                                 data.mv_size = sizeof(ID);
 478                                 data.mv_data = &id;
 479                                 id = 0;
 480                                 rc = mdb_put( txn, dbi, key, &data, 0 );
 481                                 if ( rc != 0 ) {
 482                                         err = "mdb_put range";
 483                                         goto fail;
 484                                 }
 485                                 id = lo;
 486                                 rc = mdb_put( txn, dbi, key, &data, 0 );
 487                                 if ( rc != 0 ) {
 488                                         err = "mdb_put lo";
 489                                         goto fail;
 490                                 }
 491                                 id = hi;
 492                                 rc = mdb_put( txn, dbi, key, &data, 0 );
 493                                 if ( rc != 0 ) {
 494                                         err = "mdb_put hi";
 495                                         goto fail;
 496                                 }
 497                         } else {
 498                         /* There's room, just store it */
 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                                 if ( id < lo )
 509                                         data.mv_data = &lo;
 510                                 else
 511                                         data.mv_data = &hi;
 512                                 data.mv_size = sizeof(ID);
 513                                 /* Delete the current lo/hi */
 514                                 rc = mdb_del( txn, dbi, key, &data );
 515                                 if ( rc != 0 ) {
 516                                         err = "mdb_del lo/hi";
 517                                         goto fail;
 518                                 }
 519                                 goto put1;
 520                         }
 521                 }
 522         } else if ( rc == MDB_NOTFOUND ) {
 523 put1:   data.mv_data = &id;
 524                 data.mv_size = sizeof(ID);
 525                 rc = mdb_put( txn, dbi, key, &data, MDB_NODUPDATA );
 526                 /* Don't worry if it's already there */
 527                 if ( rc != 0 && rc != MDB_KEYEXIST ) {
 528                         err = "mdb_put id";
 529                         goto fail;
 530                 }
 531         } else {
 532                 /* initial c_get failed, nothing was done */
 533 fail:
 534                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_key: "
 535                         "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
 536         }
 537         mdb_cursor_close( cursor );
 538         return rc;
 539 }
 540
 541 int
 542 mdb_idl_delete_key(
 543         BackendDB       *be,
 544         MDB_txn         *txn,
 545         MDB_dbi         dbi,
 546         MDB_val         *key,
 547         ID                      id )
 548 {
 549         int     rc;
 550         MDB_val data;
 551         MDB_cursor *cursor;
 552         ID lo, hi, tmp, *i;
 553         char *err;
 554
 555         {
 556                 char buf[16];
 557                 Debug( LDAP_DEBUG_ARGS,
 558                         "mdb_idl_delete_key: %lx %s\n",
 559                         (long) id, mdb_show_key( key, buf ), 0 );
 560         }
 561         assert( id != NOID );
 562
 563         rc = mdb_cursor_open( txn, dbi, &cursor );
 564         if ( rc != 0 ) {
 565                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
 566                         "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
 567                 return rc;
 568         }
 569         /* Fetch the first data item for this key, to see if it
 570          * exists and if it's a range.
 571          */
 572         rc = mdb_cursor_get( cursor, key, &data, MDB_SET );
 573         err = "c_get";
 574         if ( rc == 0 ) {
 575                 memcpy( &tmp, data.mv_data, sizeof(ID) );
 576                 i = data.mv_data;
 577                 if ( tmp != 0 ) {
 578                         /* Not a range, just delete it */
 579                         data.mv_data = &id;
 580                         rc = mdb_del( txn, dbi, key, &data );
 581                         if ( rc != 0 ) {
 582                                 err = "mdb_del id";
 583                                 goto fail;
 584                         }
 585                 } else {
 586                         /* It's a range, see if we need to rewrite
 587                          * the boundaries
 588                          */
 589                         lo = i[1];
 590                         hi = i[2];
 591                         if ( id == lo || id == hi ) {
 592                                 ID lo2 = lo, hi2 = hi;
 593                                 if ( id == lo ) {
 594                                         lo2++;
 595                                 } else if ( id == hi ) {
 596                                         hi2--;
 597                                 }
 598                                 if ( lo2 >= hi2 ) {
 599                                 /* The range has collapsed... */
 600                                         rc = mdb_del( txn, dbi, key, NULL );
 601                                         if ( rc != 0 ) {
 602                                                 err = "mdb_del";
 603                                                 goto fail;
 604                                         }
 605                                 } else {
 606                                         data.mv_size = sizeof(ID);
 607                                         if ( id == lo )
 608                                                 data.mv_data = &lo;
 609                                         else
 610                                                 data.mv_data = &hi;
 611                                         rc = mdb_del( txn, dbi, key, &data );
 612                                         if ( rc != 0 ) {
 613                                                 err = "c_del";
 614                                                 goto fail;
 615                                         }
 616                                         if ( id == lo )
 617                                                 data.mv_data = &lo2;
 618                                         else
 619                                                 data.mv_data = &hi2;
 620                                         rc = mdb_put( txn, dbi, key, &data, 0 );
 621                                         if ( rc != 0 ) {
 622                                                 err = "mdb_put lo/hi";
 623                                                 goto fail;
 624                                         }
 625                                 }
 626                         }
 627                 }
 628         } else {
 629                 /* initial c_get failed, nothing was done */
 630 fail:
 631                 if ( rc != MDB_NOTFOUND ) {
 632                         Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
 633                                 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
 634                 }
 635         }
 636         mdb_cursor_close( cursor );
 637         return rc;
 638 }
 639
 640
 641 /*
 642  * idl_intersection - return a = a intersection b
 643  */
 644 int
 645 mdb_idl_intersection(
 646         ID *a,
 647         ID *b )
 648 {
 649         ID ida, idb;
 650         ID idmax, idmin;
 651         ID cursora = 0, cursorb = 0, cursorc;
 652         int swap = 0;
 653
 654         if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
 655                 a[0] = 0;
 656                 return 0;
 657         }
 658
 659         idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
 660         idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
 661         if ( idmin > idmax ) {
 662                 a[0] = 0;
 663                 return 0;
 664         } else if ( idmin == idmax ) {
 665                 a[0] = 1;
 666                 a[1] = idmin;
 667                 return 0;
 668         }
 669
 670         if ( MDB_IDL_IS_RANGE( a ) ) {
 671                 if ( MDB_IDL_IS_RANGE(b) ) {
 672                 /* If both are ranges, just shrink the boundaries */
 673                         a[1] = idmin;
 674                         a[2] = idmax;
 675                         return 0;
 676                 } else {
 677                 /* Else swap so that b is the range, a is a list */
 678                         ID *tmp = a;
 679                         a = b;
 680                         b = tmp;
 681                         swap = 1;
 682                 }
 683         }
 684
 685         /* If a range completely covers the list, the result is
 686          * just the list. If idmin to idmax is contiguous, just
 687          * turn it into a range.
 688          */
 689         if ( MDB_IDL_IS_RANGE( b )
 690                 && MDB_IDL_FIRST( b ) <= MDB_IDL_FIRST( a )
 691                 && MDB_IDL_LAST( b ) >= MDB_IDL_LAST( a ) ) {
 692                 if (idmax - idmin + 1 == a[0])
 693                 {
 694                         a[0] = NOID;
 695                         a[1] = idmin;
 696                         a[2] = idmax;
 697                 }
 698                 goto done;
 699         }
 700
 701         /* Fine, do the intersection one element at a time.
 702          * First advance to idmin in both IDLs.
 703          */
 704         cursora = cursorb = idmin;
 705         ida = mdb_idl_first( a, &cursora );
 706         idb = mdb_idl_first( b, &cursorb );
 707         cursorc = 0;
 708
 709         while( ida <= idmax || idb <= idmax ) {
 710                 if( ida == idb ) {
 711                         a[++cursorc] = ida;
 712                         ida = mdb_idl_next( a, &cursora );
 713                         idb = mdb_idl_next( b, &cursorb );
 714                 } else if ( ida < idb ) {
 715                         ida = mdb_idl_next( a, &cursora );
 716                 } else {
 717                         idb = mdb_idl_next( b, &cursorb );
 718                 }
 719         }
 720         a[0] = cursorc;
 721 done:
 722         if (swap)
 723                 MDB_IDL_CPY( b, a );
 724
 725         return 0;
 726 }
 727
 728
 729 /*
 730  * idl_union - return a = a union b
 731  */
 732 int
 733 mdb_idl_union(
 734         ID      *a,
 735         ID      *b )
 736 {
 737         ID ida, idb;
 738         ID cursora = 0, cursorb = 0, cursorc;
 739
 740         if ( MDB_IDL_IS_ZERO( b ) ) {
 741                 return 0;
 742         }
 743
 744         if ( MDB_IDL_IS_ZERO( a ) ) {
 745                 MDB_IDL_CPY( a, b );
 746                 return 0;
 747         }
 748
 749         if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
 750 over:           ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
 751                 idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
 752                 a[0] = NOID;
 753                 a[1] = ida;
 754                 a[2] = idb;
 755                 return 0;
 756         }
 757
 758         ida = mdb_idl_first( a, &cursora );
 759         idb = mdb_idl_first( b, &cursorb );
 760
 761         cursorc = b[0];
 762
 763         /* The distinct elements of a are cat'd to b */
 764         while( ida != NOID || idb != NOID ) {
 765                 if ( ida < idb ) {
 766                         if( ++cursorc > MDB_IDL_UM_MAX ) {
 767                                 goto over;
 768                         }
 769                         b[cursorc] = ida;
 770                         ida = mdb_idl_next( a, &cursora );
 771
 772                 } else {
 773                         if ( ida == idb )
 774                                 ida = mdb_idl_next( a, &cursora );
 775                         idb = mdb_idl_next( b, &cursorb );
 776                 }
 777         }
 778
 779         /* b is copied back to a in sorted order */
 780         a[0] = cursorc;
 781         cursora = 1;
 782         cursorb = 1;
 783         cursorc = b[0]+1;
 784         while (cursorb <= b[0] || cursorc <= a[0]) {
 785                 if (cursorc > a[0])
 786                         idb = NOID;
 787                 else
 788                         idb = b[cursorc];
 789                 if (cursorb <= b[0] && b[cursorb] < idb)
 790                         a[cursora++] = b[cursorb++];
 791                 else {
 792                         a[cursora++] = idb;
 793                         cursorc++;
 794                 }
 795         }
 796
 797         return 0;
 798 }
 799
 800
 801 #if 0
 802 /*
 803  * mdb_idl_notin - return a intersection ~b (or a minus b)
 804  */
 805 int
 806 mdb_idl_notin(
 807         ID      *a,
 808         ID      *b,
 809         ID *ids )
 810 {
 811         ID ida, idb;
 812         ID cursora = 0, cursorb = 0;
 813
 814         if( MDB_IDL_IS_ZERO( a ) ||
 815                 MDB_IDL_IS_ZERO( b ) ||
 816                 MDB_IDL_IS_RANGE( b ) )
 817         {
 818                 MDB_IDL_CPY( ids, a );
 819                 return 0;
 820         }
 821
 822         if( MDB_IDL_IS_RANGE( a ) ) {
 823                 MDB_IDL_CPY( ids, a );
 824                 return 0;
 825         }
 826
 827         ida = mdb_idl_first( a, &cursora ),
 828         idb = mdb_idl_first( b, &cursorb );
 829
 830         ids[0] = 0;
 831
 832         while( ida != NOID ) {
 833                 if ( idb == NOID ) {
 834                         /* we could shortcut this */
 835                         ids[++ids[0]] = ida;
 836                         ida = mdb_idl_next( a, &cursora );
 837
 838                 } else if ( ida < idb ) {
 839                         ids[++ids[0]] = ida;
 840                         ida = mdb_idl_next( a, &cursora );
 841
 842                 } else if ( ida > idb ) {
 843                         idb = mdb_idl_next( b, &cursorb );
 844
 845                 } else {
 846                         ida = mdb_idl_next( a, &cursora );
 847                         idb = mdb_idl_next( b, &cursorb );
 848                 }
 849         }
 850
 851         return 0;
 852 }
 853 #endif
 854
 855 ID mdb_idl_first( ID *ids, ID *cursor )
 856 {
 857         ID pos;
 858
 859         if ( ids[0] == 0 ) {
 860                 *cursor = NOID;
 861                 return NOID;
 862         }
 863
 864         if ( MDB_IDL_IS_RANGE( ids ) ) {
 865                 if( *cursor < ids[1] ) {
 866                         *cursor = ids[1];
 867                 }
 868                 return *cursor;
 869         }
 870
 871         if ( *cursor == 0 )
 872                 pos = 1;
 873         else
 874                 pos = mdb_idl_search( ids, *cursor );
 875
 876         if( pos > ids[0] ) {
 877                 return NOID;
 878         }
 879
 880         *cursor = pos;
 881         return ids[pos];
 882 }
 883
 884 ID mdb_idl_next( ID *ids, ID *cursor )
 885 {
 886         if ( MDB_IDL_IS_RANGE( ids ) ) {
 887                 if( ids[2] < ++(*cursor) ) {
 888                         return NOID;
 889                 }
 890                 return *cursor;
 891         }
 892
 893         if ( ++(*cursor) <= ids[0] ) {
 894                 return ids[*cursor];
 895         }
 896
 897         return NOID;
 898 }
 899
 900 /* Add one ID to an unsorted list. We ensure that the first element is the
 901  * minimum and the last element is the maximum, for fast range compaction.
 902  *   this means IDLs up to length 3 are always sorted...
 903  */
 904 int mdb_idl_append_one( ID *ids, ID id )
 905 {
 906         if (MDB_IDL_IS_RANGE( ids )) {
 907                 /* if already in range, treat as a dup */
 908                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
 909                         return -1;
 910                 if (id < MDB_IDL_FIRST(ids))
 911                         ids[1] = id;
 912                 else if (id > MDB_IDL_LAST(ids))
 913                         ids[2] = id;
 914                 return 0;
 915         }
 916         if ( ids[0] ) {
 917                 ID tmp;
 918
 919                 if (id < ids[1]) {
 920                         tmp = ids[1];
 921                         ids[1] = id;
 922                         id = tmp;
 923                 }
 924                 if ( ids[0] > 1 && id < ids[ids[0]] ) {
 925                         tmp = ids[ids[0]];
 926                         ids[ids[0]] = id;
 927                         id = tmp;
 928                 }
 929         }
 930         ids[0]++;
 931         if ( ids[0] >= MDB_IDL_UM_MAX ) {
 932                 ids[0] = NOID;
 933                 ids[2] = id;
 934         } else {
 935                 ids[ids[0]] = id;
 936         }
 937         return 0;
 938 }
 939
 940 /* Append sorted list b to sorted list a. The result is unsorted but
 941  * a[1] is the min of the result and a[a[0]] is the max.
 942  */
 943 int mdb_idl_append( ID *a, ID *b )
 944 {
 945         ID ida, idb, tmp, swap = 0;
 946
 947         if ( MDB_IDL_IS_ZERO( b ) ) {
 948                 return 0;
 949         }
 950
 951         if ( MDB_IDL_IS_ZERO( a ) ) {
 952                 MDB_IDL_CPY( a, b );
 953                 return 0;
 954         }
 955
 956         ida = MDB_IDL_LAST( a );
 957         idb = MDB_IDL_LAST( b );
 958         if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
 959                 a[0] + b[0] >= MDB_IDL_UM_MAX ) {
 960                 a[2] = IDL_MAX( ida, idb );
 961                 a[1] = IDL_MIN( a[1], b[1] );
 962                 a[0] = NOID;
 963                 return 0;
 964         }
 965
 966         if ( b[0] > 1 && ida > idb ) {
 967                 swap = idb;
 968                 a[a[0]] = idb;
 969                 b[b[0]] = ida;
 970         }
 971
 972         if ( b[1] < a[1] ) {
 973                 tmp = a[1];
 974                 a[1] = b[1];
 975         } else {
 976                 tmp = b[1];
 977         }
 978         a[0]++;
 979         a[a[0]] = tmp;
 980
 981         if ( b[0] > 1 ) {
 982                 int i = b[0] - 1;
 983                 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
 984                 a[0] += i;
 985         }
 986         if ( swap ) {
 987                 b[b[0]] = swap;
 988         }
 989         return 0;
 990 }
 991
 992 #if 1
 993
 994 /* Quicksort + Insertion sort for small arrays */
 995
 996 #define SMALL   8
 997 #define SWAP(a,b)       itmp=(a);(a)=(b);(b)=itmp
 998
 999 void
1000 mdb_idl_sort( ID *ids, ID *tmp )
1001 {
1002         int *istack = (int *)tmp;
1003         int i,j,k,l,ir,jstack;
1004         ID a, itmp;
1005
1006         if ( MDB_IDL_IS_RANGE( ids ))
1007                 return;
1008
1009         ir = ids[0];
1010         l = 1;
1011         jstack = 0;
1012         for(;;) {
1013                 if (ir - l < SMALL) {   /* Insertion sort */
1014                         for (j=l+1;j<=ir;j++) {
1015                                 a = ids[j];
1016                                 for (i=j-1;i>=1;i--) {
1017                                         if (ids[i] <= a) break;
1018                                         ids[i+1] = ids[i];
1019                                 }
1020                                 ids[i+1] = a;
1021                         }
1022                         if (jstack == 0) break;
1023                         ir = istack[jstack--];
1024                         l = istack[jstack--];
1025                 } else {
1026                         k = (l + ir) >> 1;      /* Choose median of left, center, right */
1027                         SWAP(ids[k], ids[l+1]);
1028                         if (ids[l] > ids[ir]) {
1029                                 SWAP(ids[l], ids[ir]);
1030                         }
1031                         if (ids[l+1] > ids[ir]) {
1032                                 SWAP(ids[l+1], ids[ir]);
1033                         }
1034                         if (ids[l] > ids[l+1]) {
1035                                 SWAP(ids[l], ids[l+1]);
1036                         }
1037                         i = l+1;
1038                         j = ir;
1039                         a = ids[l+1];
1040                         for(;;) {
1041                                 do i++; while(ids[i] < a);
1042                                 do j--; while(ids[j] > a);
1043                                 if (j < i) break;
1044                                 SWAP(ids[i],ids[j]);
1045                         }
1046                         ids[l+1] = ids[j];
1047                         ids[j] = a;
1048                         jstack += 2;
1049                         if (ir-i+1 >= j-1) {
1050                                 istack[jstack] = ir;
1051                                 istack[jstack-1] = i;
1052                                 ir = j-1;
1053                         } else {
1054                                 istack[jstack] = j-1;
1055                                 istack[jstack-1] = l;
1056                                 l = i;
1057                         }
1058                 }
1059         }
1060 }
1061
1062 #else
1063
1064 /* 8 bit Radix sort + insertion sort
1065  *
1066  * based on code from http://www.cubic.org/docs/radix.htm
1067  * with improvements by mbackes@symas.com and hyc@symas.com
1068  *
1069  * This code is O(n) but has a relatively high constant factor. For lists
1070  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1071  * Much faster than quicksort for lists longer than ~100. Insertion
1072  * sort is actually superior for lists <50.
1073  */
1074
1075 #define BUCKETS (1<<8)
1076 #define SMALL   50
1077
1078 void
1079 mdb_idl_sort( ID *ids, ID *tmp )
1080 {
1081         int count, soft_limit, phase = 0, size = ids[0];
1082         ID *idls[2];
1083         unsigned char *maxv = (unsigned char *)&ids[size];
1084
1085         if ( MDB_IDL_IS_RANGE( ids ))
1086                 return;
1087
1088         /* Use insertion sort for small lists */
1089         if ( size <= SMALL ) {
1090                 int i,j;
1091                 ID a;
1092
1093                 for (j=1;j<=size;j++) {
1094                         a = ids[j];
1095                         for (i=j-1;i>=1;i--) {
1096                                 if (ids[i] <= a) break;
1097                                 ids[i+1] = ids[i];
1098                         }
1099                         ids[i+1] = a;
1100                 }
1101                 return;
1102         }
1103
1104         tmp[0] = size;
1105         idls[0] = ids;
1106         idls[1] = tmp;
1107
1108 #if BYTE_ORDER == BIG_ENDIAN
1109     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1110 #else
1111     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1112 #endif
1113
1114         for (
1115 #if BYTE_ORDER == BIG_ENDIAN
1116         count = sizeof(ID)-1; count >= soft_limit; --count
1117 #else
1118         count = 0; count <= soft_limit; ++count
1119 #endif
1120         ) {
1121                 unsigned int num[BUCKETS], * np, n, sum;
1122                 int i;
1123         ID *sp, *source, *dest;
1124         unsigned char *bp, *source_start;
1125
1126                 source = idls[phase]+1;
1127                 dest = idls[phase^1]+1;
1128                 source_start =  ((unsigned char *) source) + count;
1129
1130         np = num;
1131         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1132
1133                 /* count occurences of every byte value */
1134                 bp = source_start;
1135         for ( i = size; i > 0; --i, bp += sizeof(ID) )
1136                                 num[*bp]++;
1137
1138                 /* transform count into index by summing elements and storing
1139                  * into same array
1140                  */
1141         sum = 0;
1142         np = num;
1143         for ( i = BUCKETS; i > 0; --i ) {
1144                 n = *np;
1145                 *np++ = sum;
1146                 sum += n;
1147         }
1148
1149                 /* fill dest with the right values in the right place */
1150                 bp = source_start;
1151         sp = source;
1152         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1153                 np = num + *bp;
1154                 dest[*np] = *sp++;
1155                 ++(*np);
1156         }
1157                 phase ^= 1;
1158         }
1159
1160         /* copy back from temp if needed */
1161         if ( phase ) {
1162                 ids++; tmp++;
1163                 for ( count = 0; count < size; ++count )
1164                         *ids++ = *tmp++;
1165         }
1166 }
1167 #endif  /* Quick vs Radix */