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