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