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