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

   1 /* idl.c - ldap id list handling routines */
   2
   3 #include <stdio.h>
   4 #include <sys/types.h>
   5 #include <sys/socket.h>
   6 #include "slap.h"
   7 #include "ldapconfig.h"
   8 #include "back-ldbm.h"
   9
  10 extern Datum    ldbm_cache_fetch();
  11
  12 IDList *
  13 idl_alloc( int nids )
  14 {
  15         IDList  *new;
  16
  17         /* nmax + nids + space for the ids */
  18         new = (IDList *) ch_calloc( (2 + nids), sizeof(ID) );
  19         new->b_nmax = nids;
  20         new->b_nids = 0;
  21
  22         return( new );
  23 }
  24
  25 IDList  *
  26 idl_allids( Backend *be )
  27 {
  28         IDList  *idl;
  29
  30         idl = idl_alloc( 0 );
  31         idl->b_nmax = ALLIDSBLOCK;
  32         idl->b_nids = next_id_get( be );
  33
  34         return( idl );
  35 }
  36
  37 void
  38 idl_free( IDList *idl )
  39 {
  40         if ( idl == NULL ) {
  41                 return;
  42         }
  43
  44         free( (char *) idl );
  45 }
  46
  47 static IDList *
  48 idl_fetch_one(
  49     Backend             *be,
  50     struct dbcache      *db,
  51     Datum               key
  52 )
  53 {
  54         Datum   data, k2;
  55         IDList  *idl;
  56         IDList  **tmp;
  57         char    *kstr;
  58         int     i, nids;
  59
  60         /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch_one\n", 0, 0, 0 ); */
  61
  62         data = ldbm_cache_fetch( db, key );
  63
  64         idl = (IDList *) data.dptr;
  65
  66         return( idl );
  67 }
  68
  69 IDList *
  70 idl_fetch(
  71     Backend             *be,
  72     struct dbcache      *db,
  73     Datum               key
  74 )
  75 {
  76         Datum   data, k2;
  77         IDList  *idl;
  78         IDList  **tmp;
  79         char    *kstr;
  80         int     i, nids;
  81
  82         /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch\n", 0, 0, 0 ); */
  83
  84         data = ldbm_cache_fetch( db, key );
  85
  86         if ( (idl = (IDList *) data.dptr) == NULL ) {
  87                 return( NULL );
  88         }
  89
  90         /* regular block */
  91         if ( ! INDIRECT_BLOCK( idl ) ) {
  92                 /*
  93                 Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %d ids (%d max)\n",
  94                     idl->b_nids, idl->b_nmax, 0 );
  95                 */
  96
  97                 /* make sure we have the current value of highest id */
  98                 if ( idl->b_nmax == ALLIDSBLOCK ) {
  99                         idl_free( idl );
 100                         idl = idl_allids( be );
 101                 }
 102                 return( idl );
 103         }
 104
 105         /*
 106          * this is an indirect block which points to other blocks.
 107          * we need to read in all the blocks it points to and construct
 108          * a big id list containing all the ids, which we will return.
 109          */
 110
 111         /* count the number of blocks & allocate space for pointers to them */
 112         for ( i = 0; idl->b_ids[i] != NOID; i++ )
 113                 ;       /* NULL */
 114         tmp = (IDList **) ch_malloc( (i + 1) * sizeof(IDList *) );
 115
 116         /* read in all the blocks */
 117         kstr = (char *) ch_malloc( key.dsize + 20 );
 118         nids = 0;
 119         for ( i = 0; idl->b_ids[i] != NOID; i++ ) {
 120                 sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr, idl->b_ids[i] );
 121                 k2.dptr = kstr;
 122                 k2.dsize = strlen( kstr ) + 1;
 123
 124                 if ( (tmp[i] = idl_fetch_one( be, db, k2 )) == NULL ) {
 125                         Debug( LDAP_DEBUG_ANY,
 126                             "idl_fetch of (%s) returns NULL\n", k2.dptr, 0, 0 );
 127                         continue;
 128                 }
 129
 130                 nids += tmp[i]->b_nids;
 131         }
 132         tmp[i] = NULL;
 133         idl_free( idl );
 134
 135         /* allocate space for the big block */
 136         idl = idl_alloc( nids );
 137         idl->b_nids = nids;
 138         nids = 0;
 139
 140         /* copy in all the ids from the component blocks */
 141         for ( i = 0; tmp[i] != NULL; i++ ) {
 142                 if ( tmp[i] == NULL ) {
 143                         continue;
 144                 }
 145
 146                 SAFEMEMCPY( (char *) &idl->b_ids[nids], (char *) tmp[i]->b_ids,
 147                     tmp[i]->b_nids * sizeof(ID) );
 148                 nids += tmp[i]->b_nids;
 149
 150                 idl_free( tmp[i] );
 151         }
 152         free( (char *) tmp );
 153
 154         Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %d ids (%d max)\n", idl->b_nids,
 155             idl->b_nmax, 0 );
 156         return( idl );
 157 }
 158
 159 static int
 160 idl_store(
 161     Backend             *be,
 162     struct dbcache      *db,
 163     Datum               key,
 164     IDList              *idl
 165 )
 166 {
 167         int     rc, flags;
 168         Datum   data;
 169         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 170
 171         /* Debug( LDAP_DEBUG_TRACE, "=> idl_store\n", 0, 0, 0 ); */
 172
 173         data.dptr = (char *) idl;
 174         data.dsize = (2 + idl->b_nmax) * sizeof(ID);
 175
 176         flags = LDBM_REPLACE;
 177         if( li->li_flush_wrt ) flags |= LDBM_SYNC;
 178
 179         rc = ldbm_cache_store( db, key, data, flags );
 180
 181         /* Debug( LDAP_DEBUG_TRACE, "<= idl_store %d\n", rc, 0, 0 ); */
 182         return( rc );
 183 }
 184
 185 static void
 186 idl_split_block(
 187     IDList      *b,
 188     ID          id,
 189     IDList      **n1,
 190     IDList      **n2
 191 )
 192 {
 193         int     i;
 194
 195         /* find where to split the block */
 196         for ( i = 0; i < b->b_nids && id > b->b_ids[i]; i++ )
 197                 ;       /* NULL */
 198
 199         *n1 = idl_alloc( i == 0 ? 1 : i );
 200         *n2 = idl_alloc( b->b_nids - i + (i == 0 ? 0 : 1));
 201
 202         /*
 203          * everything before the id being inserted in the first block
 204          * unless there is nothing, in which case the id being inserted
 205          * goes there.
 206          */
 207         SAFEMEMCPY( (char *) &(*n1)->b_ids[0], (char *) &b->b_ids[0],
 208             i * sizeof(ID) );
 209         (*n1)->b_nids = (i == 0 ? 1 : i);
 210
 211         if ( i == 0 ) {
 212                 (*n1)->b_ids[0] = id;
 213         } else {
 214                 (*n2)->b_ids[0] = id;
 215         }
 216
 217         /* the id being inserted & everything after in the second block */
 218         SAFEMEMCPY( (char *) &(*n2)->b_ids[i == 0 ? 0 : 1],
 219             (char *) &b->b_ids[i], (b->b_nids - i) * sizeof(ID) );
 220         (*n2)->b_nids = b->b_nids - i + (i == 0 ? 0 : 1);
 221 }
 222
 223 /*
 224  * idl_change_first - called when an indirect block's first key has
 225  * changed, meaning it needs to be stored under a new key, and the
 226  * header block pointing to it needs updating.
 227  */
 228
 229 static int
 230 idl_change_first(
 231     Backend             *be,
 232     struct dbcache      *db,
 233     Datum               hkey,           /* header block key     */
 234     IDList              *h,             /* header block         */
 235     int                 pos,            /* pos in h to update   */
 236     Datum               bkey,           /* data block key       */
 237     IDList              *b              /* data block           */
 238 )
 239 {
 240         int     rc;
 241
 242         /* Debug( LDAP_DEBUG_TRACE, "=> idl_change_first\n", 0, 0, 0 ); */
 243
 244         /* delete old key block */
 245         if ( (rc = ldbm_cache_delete( db, bkey )) != 0 ) {
 246                 Debug( LDAP_DEBUG_ANY,
 247                     "ldbm_delete of (%s) returns %d\n", bkey.dptr, rc,
 248                     0 );
 249                 return( rc );
 250         }
 251
 252         /* write block with new key */
 253         sprintf( bkey.dptr, "%c%s%d", CONT_PREFIX, hkey.dptr, b->b_ids[0] );
 254         bkey.dsize = strlen( bkey.dptr ) + 1;
 255         if ( (rc = idl_store( be, db, bkey, b )) != 0 ) {
 256                 Debug( LDAP_DEBUG_ANY,
 257                     "idl_store of (%s) returns %d\n", bkey.dptr, rc, 0 );
 258                 return( rc );
 259         }
 260
 261         /* update + write indirect header block */
 262         h->b_ids[pos] = b->b_ids[0];
 263         if ( (rc = idl_store( be, db, hkey, h )) != 0 ) {
 264                 Debug( LDAP_DEBUG_ANY,
 265                     "idl_store of (%s) returns %d\n", hkey.dptr, rc, 0 );
 266                 return( rc );
 267         }
 268
 269         return( 0 );
 270 }
 271
 272 int
 273 idl_insert_key(
 274     Backend             *be,
 275     struct dbcache      *db,
 276     Datum               key,
 277     ID                  id
 278 )
 279 {
 280         int     i, j, first, rc;
 281         IDList  *idl, *tmp, *tmp2, *tmp3;
 282         char    *kstr;
 283         Datum   k2;
 284
 285         if ( (idl = idl_fetch_one( be, db, key )) == NULL ) {
 286                 idl = idl_alloc( 1 );
 287                 idl->b_ids[idl->b_nids++] = id;
 288                 rc = idl_store( be, db, key, idl );
 289
 290                 idl_free( idl );
 291                 return( rc );
 292         }
 293
 294         /* regular block */
 295         if ( ! INDIRECT_BLOCK( idl ) ) {
 296                 switch ( idl_insert( &idl, id, db->dbc_maxids ) ) {
 297                 case 0:         /* id inserted - store the updated block */
 298                 case 1:
 299                         rc = idl_store( be, db, key, idl );
 300                         break;
 301
 302                 case 2:         /* id already there - nothing to do */
 303                         rc = 0;
 304                         break;
 305
 306                 case 3:         /* id not inserted - block must be split */
 307                         /* check threshold for marking this an all-id block */
 308                         if ( db->dbc_maxindirect < 2 ) {
 309                                 idl_free( idl );
 310                                 idl = idl_allids( be );
 311                                 rc = idl_store( be, db, key, idl );
 312                                 idl_free( idl );
 313
 314                                 return( rc );
 315                         }
 316
 317                         idl_split_block( idl, id, &tmp, &tmp2 );
 318                         idl_free( idl );
 319
 320                         /* create the header indirect block */
 321                         idl = idl_alloc( 3 );
 322                         idl->b_nmax = 3;
 323                         idl->b_nids = INDBLOCK;
 324                         idl->b_ids[0] = tmp->b_ids[0];
 325                         idl->b_ids[1] = tmp2->b_ids[0];
 326                         idl->b_ids[2] = NOID;
 327
 328                         /* store it */
 329                         rc = idl_store( be, db, key, idl );
 330
 331                         /* store the first id block */
 332                         kstr = (char *) ch_malloc( key.dsize + 20 );
 333                         sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 334                             tmp->b_ids[0] );
 335                         k2.dptr = kstr;
 336                         k2.dsize = strlen( kstr ) + 1;
 337                         rc = idl_store( be, db, k2, tmp );
 338
 339                         /* store the second id block */
 340                         sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 341                             tmp2->b_ids[0] );
 342                         k2.dptr = kstr;
 343                         k2.dsize = strlen( kstr ) + 1;
 344                         rc = idl_store( be, db, k2, tmp2 );
 345
 346                         free( kstr );
 347                         idl_free( tmp );
 348                         idl_free( tmp2 );
 349                         break;
 350                 }
 351
 352                 idl_free( idl );
 353                 return( rc );
 354         }
 355
 356         /*
 357          * this is an indirect block which points to other blocks.
 358          * we need to read in the block into which the id should be
 359          * inserted, then insert the id and store the block.  we might
 360          * have to split the block if it is full, which means we also
 361          * need to write a new "header" block.
 362          */
 363
 364         /* select the block to try inserting into */
 365         for ( i = 0; idl->b_ids[i] != NOID && id > idl->b_ids[i]; i++ )
 366                 ;       /* NULL */
 367         if ( i != 0 ) {
 368                 i--;
 369                 first = 0;
 370         } else {
 371                 first = 1;
 372         }
 373
 374         /* get the block */
 375         kstr = (char *) ch_malloc( key.dsize + 20 );
 376         sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr, idl->b_ids[i] );
 377         k2.dptr = kstr;
 378         k2.dsize = strlen( kstr ) + 1;
 379         if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) {
 380                 Debug( LDAP_DEBUG_ANY, "nonexistent continuation block (%s)\n",
 381                     k2.dptr, 0, 0 );
 382                 return( -1 );
 383         }
 384
 385         /* insert the id */
 386         switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) {
 387         case 0:         /* id inserted ok */
 388                 if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
 389                         Debug( LDAP_DEBUG_ANY,
 390                             "idl_store of (%s) returns %d\n", k2.dptr, rc, 0 );
 391                 }
 392                 break;
 393
 394         case 1:         /* id inserted - first id in block has changed */
 395                 /*
 396                  * key for this block has changed, so we have to
 397                  * write the block under the new key, delete the
 398                  * old key block + update and write the indirect
 399                  * header block.
 400                  */
 401
 402                 rc = idl_change_first( be, db, key, idl, i, k2, tmp );
 403                 break;
 404
 405         case 2:         /* id not inserted - already there */
 406                 break;
 407
 408         case 3:         /* id not inserted - block is full */
 409                 /*
 410                  * first, see if it will fit in the next block,
 411                  * without splitting, unless we're trying to insert
 412                  * into the beginning of the first block.
 413                  */
 414
 415                 /* is there a next block? */
 416                 if ( !first && idl->b_ids[i + 1] != NOID ) {
 417                         /* read it in */
 418                         sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 419                             idl->b_ids[i + 1] );
 420                         k2.dptr = kstr;
 421                         k2.dsize = strlen( kstr ) + 1;
 422                         if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) {
 423                                 Debug( LDAP_DEBUG_ANY,
 424                                     "idl_fetch_one (%s) returns NULL\n",
 425                                     k2.dptr, 0, 0 );
 426                                 break;
 427                         }
 428
 429                         switch ( (rc = idl_insert( &tmp2, id,
 430                             db->dbc_maxids )) ) {
 431                         case 1:         /* id inserted first in block */
 432                                 rc = idl_change_first( be, db, key, idl,
 433                                     i + 1, k2, tmp2 );
 434                                 /* FALL */
 435
 436                         case 2:         /* id already there - how? */
 437                         case 0:         /* id inserted */
 438                                 if ( rc == 2 ) {
 439                                         Debug( LDAP_DEBUG_ANY,
 440                                             "id %d already in next block\n",
 441                                             id, 0, 0 );
 442                                 }
 443                                 free( kstr );
 444                                 idl_free( tmp );
 445                                 idl_free( tmp2 );
 446                                 idl_free( idl );
 447                                 return( 0 );
 448
 449                         case 3:         /* split the original block */
 450                                 idl_free( tmp2 );
 451                                 break;
 452                         }
 453
 454                 }
 455
 456                 /*
 457                  * must split the block, write both new blocks + update
 458                  * and write the indirect header block.
 459                  */
 460
 461                 /* count how many indirect blocks */
 462                 for ( j = 0; idl->b_ids[j] != NOID; j++ )
 463                         ;       /* NULL */
 464
 465                 /* check it against all-id thresholed */
 466                 if ( j + 1 > db->dbc_maxindirect ) {
 467                         /*
 468                          * we've passed the all-id threshold, meaning
 469                          * that this set of blocks should be replaced
 470                          * by a single "all-id" block.  our job: delete
 471                          * all the indirect blocks, and replace the header
 472                          * block by an all-id block.
 473                          */
 474
 475                         /* delete all indirect blocks */
 476                         for ( j = 0; idl->b_ids[j] != NOID; j++ ) {
 477                                 sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 478                                     idl->b_ids[j] );
 479                                 k2.dptr = kstr;
 480                                 k2.dsize = strlen( kstr ) + 1;
 481
 482                                 rc = ldbm_cache_delete( db, k2 );
 483                         }
 484
 485                         /* store allid block in place of header block */
 486                         idl_free( idl );
 487                         idl = idl_allids( be );
 488                         rc = idl_store( be, db, key, idl );
 489
 490                         free( kstr );
 491                         idl_free( idl );
 492                         idl_free( tmp );
 493                         return( rc );
 494                 }
 495
 496                 idl_split_block( tmp, id, &tmp2, &tmp3 );
 497                 idl_free( tmp );
 498
 499                 /* create a new updated indirect header block */
 500                 tmp = idl_alloc( idl->b_nmax + 1 );
 501                 tmp->b_nids = INDBLOCK;
 502                 /* everything up to the split block */
 503                 SAFEMEMCPY( (char *) tmp->b_ids, (char *) idl->b_ids,
 504                     i * sizeof(ID) );
 505                 /* the two new blocks */
 506                 tmp->b_ids[i] = tmp2->b_ids[0];
 507                 tmp->b_ids[i + 1] = tmp3->b_ids[0];
 508                 /* everything after the split block */
 509                 SAFEMEMCPY( (char *) &tmp->b_ids[i + 2], (char *)
 510                     &idl->b_ids[i + 1], (idl->b_nmax - i - 1) * sizeof(ID) );
 511
 512                 /* store the header block */
 513                 rc = idl_store( be, db, key, tmp );
 514
 515                 /* store the first id block */
 516                 sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 517                     tmp2->b_ids[0] );
 518                 k2.dptr = kstr;
 519                 k2.dsize = strlen( kstr ) + 1;
 520                 rc = idl_store( be, db, k2, tmp2 );
 521
 522                 /* store the second id block */
 523                 sprintf( kstr, "%c%s%d", CONT_PREFIX, key.dptr,
 524                     tmp3->b_ids[0] );
 525                 k2.dptr = kstr;
 526                 k2.dsize = strlen( kstr ) + 1;
 527                 rc = idl_store( be, db, k2, tmp3 );
 528
 529                 idl_free( tmp2 );
 530                 idl_free( tmp3 );
 531                 break;
 532         }
 533
 534         free( kstr );
 535         idl_free( tmp );
 536         idl_free( idl );
 537         return( rc );
 538 }
 539
 540 /*
 541  * idl_insert - insert an id into an id list.
 542  * returns      0       id inserted
 543  *              1       id inserted, first id in block has changed
 544  *              2       id not inserted, already there
 545  *              3       id not inserted, block must be split
 546  */
 547
 548 int
 549 idl_insert( IDList **idl, ID id, int maxids )
 550 {
 551         int     i, j;
 552
 553         if ( ALLIDS( *idl ) ) {
 554                 return( 2 );    /* already there */
 555         }
 556
 557         /* is it already there? XXX bin search XXX */
 558         for ( i = 0; i < (*idl)->b_nids && id > (*idl)->b_ids[i]; i++ ) {
 559                 ;       /* NULL */
 560         }
 561         if ( i < (*idl)->b_nids && (*idl)->b_ids[i] == id ) {
 562                 return( 2 );    /* already there */
 563         }
 564
 565         /* do we need to make room for it? */
 566         if ( (*idl)->b_nids == (*idl)->b_nmax ) {
 567                 /* make room or indicate block needs splitting */
 568                 if ( (*idl)->b_nmax == maxids ) {
 569                         return( 3 );    /* block needs splitting */
 570                 }
 571
 572                 (*idl)->b_nmax *= 2;
 573                 if ( (*idl)->b_nmax > maxids ) {
 574                         (*idl)->b_nmax = maxids;
 575                 }
 576                 *idl = (IDList *) ch_realloc( (char *) *idl,
 577                     ((*idl)->b_nmax + 2) * sizeof(ID) );
 578         }
 579
 580         /* make a slot for the new id */
 581         for ( j = (*idl)->b_nids; j != i; j-- ) {
 582                 (*idl)->b_ids[j] = (*idl)->b_ids[j-1];
 583         }
 584         (*idl)->b_ids[i] = id;
 585         (*idl)->b_nids++;
 586         (void) memset( (char *) &(*idl)->b_ids[(*idl)->b_nids], '\0',
 587             ((*idl)->b_nmax - (*idl)->b_nids) * sizeof(ID) );
 588
 589         return( i == 0 ? 1 : 0 );       /* inserted - first id changed or not */
 590 }
 591
 592 static IDList *
 593 idl_dup( IDList *idl )
 594 {
 595         IDList  *new;
 596
 597         if ( idl == NULL ) {
 598                 return( NULL );
 599         }
 600
 601         new = idl_alloc( idl->b_nmax );
 602         SAFEMEMCPY( (char *) new, (char *) idl, (idl->b_nmax + 2)
 603             * sizeof(ID) );
 604
 605         return( new );
 606 }
 607
 608 static IDList *
 609 idl_min( IDList *a, IDList *b )
 610 {
 611         return( a->b_nids > b->b_nids ? b : a );
 612 }
 613
 614 /*
 615  * idl_intersection - return a intersection b
 616  */
 617
 618 IDList *
 619 idl_intersection(
 620     Backend     *be,
 621     IDList      *a,
 622     IDList      *b
 623 )
 624 {
 625         int     ai, bi, ni;
 626         IDList  *n;
 627
 628         if ( a == NULL || b == NULL ) {
 629                 return( NULL );
 630         }
 631         if ( ALLIDS( a ) ) {
 632                 return( idl_dup( b ) );
 633         }
 634         if ( ALLIDS( b ) ) {
 635                 return( idl_dup( a ) );
 636         }
 637
 638         n = idl_dup( idl_min( a, b ) );
 639
 640         for ( ni = 0, ai = 0, bi = 0; ai < a->b_nids; ai++ ) {
 641                 for ( ; bi < b->b_nids && b->b_ids[bi] < a->b_ids[ai]; bi++ )
 642                         ;       /* NULL */
 643
 644                 if ( bi == b->b_nids ) {
 645                         break;
 646                 }
 647
 648                 if ( b->b_ids[bi] == a->b_ids[ai] ) {
 649                         n->b_ids[ni++] = a->b_ids[ai];
 650                 }
 651         }
 652
 653         if ( ni == 0 ) {
 654                 idl_free( n );
 655                 return( NULL );
 656         }
 657         n->b_nids = ni;
 658
 659         return( n );
 660 }
 661
 662 /*
 663  * idl_union - return a union b
 664  */
 665
 666 IDList *
 667 idl_union(
 668     Backend     *be,
 669     IDList      *a,
 670     IDList      *b
 671 )
 672 {
 673         int     ai, bi, ni;
 674         IDList  *n;
 675
 676         if ( a == NULL ) {
 677                 return( idl_dup( b ) );
 678         }
 679         if ( b == NULL ) {
 680                 return( idl_dup( a ) );
 681         }
 682         if ( ALLIDS( a ) || ALLIDS( b ) ) {
 683                 return( idl_allids( be ) );
 684         }
 685
 686         if ( b->b_nids < a->b_nids ) {
 687                 n = a;
 688                 a = b;
 689                 b = n;
 690         }
 691
 692         n = idl_alloc( a->b_nids + b->b_nids );
 693
 694         for ( ni = 0, ai = 0, bi = 0; ai < a->b_nids && bi < b->b_nids; ) {
 695                 if ( a->b_ids[ai] < b->b_ids[bi] ) {
 696                         n->b_ids[ni++] = a->b_ids[ai++];
 697                 } else if ( b->b_ids[bi] < a->b_ids[ai] ) {
 698                         n->b_ids[ni++] = b->b_ids[bi++];
 699                 } else {
 700                         n->b_ids[ni++] = a->b_ids[ai];
 701                         ai++, bi++;
 702                 }
 703         }
 704
 705         for ( ; ai < a->b_nids; ai++ ) {
 706                 n->b_ids[ni++] = a->b_ids[ai];
 707         }
 708         for ( ; bi < b->b_nids; bi++ ) {
 709                 n->b_ids[ni++] = b->b_ids[bi];
 710         }
 711         n->b_nids = ni;
 712
 713         return( n );
 714 }
 715
 716 /*
 717  * idl_notin - return a intersection ~b (or a minus b)
 718  */
 719
 720 IDList *
 721 idl_notin(
 722     Backend     *be,
 723     IDList      *a,
 724     IDList      *b
 725 )
 726 {
 727         int     ni, ai, bi;
 728         IDList  *n;
 729
 730         if ( a == NULL ) {
 731                 return( NULL );
 732         }
 733         if ( b == NULL || ALLIDS( b )) {
 734                 return( idl_dup( a ) );
 735         }
 736
 737         if ( ALLIDS( a ) ) {
 738                 n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
 739                 ni = 0;
 740
 741                 for ( ai = 1, bi = 0; ai < a->b_nids && ni < n->b_nmax &&
 742                     bi < b->b_nmax; ai++ ) {
 743                         if ( b->b_ids[bi] == ai ) {
 744                                 bi++;
 745                         } else {
 746                                 n->b_ids[ni++] = ai;
 747                         }
 748                 }
 749
 750                 for ( ; ai < a->b_nids && ni < n->b_nmax; ai++ ) {
 751                         n->b_ids[ni++] = ai;
 752                 }
 753
 754                 if ( ni == n->b_nmax ) {
 755                         idl_free( n );
 756                         return( idl_allids( be ) );
 757                 } else {
 758                         n->b_nids = ni;
 759                         return( n );
 760                 }
 761         }
 762
 763         n = idl_dup( a );
 764
 765         ni = 0;
 766         for ( ai = 0, bi = 0; ai < a->b_nids; ai++ ) {
 767                 for ( ; bi < b->b_nids && b->b_ids[bi] < a->b_ids[ai];
 768                     bi++ ) {
 769                         ;       /* NULL */
 770                 }
 771
 772                 if ( bi == b->b_nids ) {
 773                         break;
 774                 }
 775
 776                 if ( b->b_ids[bi] != a->b_ids[ai] ) {
 777                         n->b_ids[ni++] = a->b_ids[ai];
 778                 }
 779         }
 780
 781         for ( ; ai < a->b_nids; ai++ ) {
 782                 n->b_ids[ni++] = a->b_ids[ai];
 783         }
 784         n->b_nids = ni;
 785
 786         return( n );
 787 }
 788
 789 ID
 790 idl_firstid( IDList *idl )
 791 {
 792         if ( idl == NULL || idl->b_nids == 0 ) {
 793                 return( NOID );
 794         }
 795
 796         if ( ALLIDS( idl ) ) {
 797                 return( idl->b_nids == 1 ? NOID : 1 );
 798         }
 799
 800         return( idl->b_ids[0] );
 801 }
 802
 803 ID
 804 idl_nextid( IDList *idl, ID id )
 805 {
 806         int     i;
 807
 808         if ( ALLIDS( idl ) ) {
 809                 return( ++id < idl->b_nids ? id : NOID );
 810         }
 811
 812         for ( i = 0; i < idl->b_nids && idl->b_ids[i] < id; i++ ) {
 813                 ;       /* NULL */
 814         }
 815         i++;
 816
 817         if ( i >= idl->b_nids ) {
 818                 return( NOID );
 819         } else {
 820                 return( idl->b_ids[i] );
 821         }
 822 }