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