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